Stochastic Learning and Optimization (eBook)

Preface 6
Introduction 19
An Overview of Learning and Optimization 19
Problem Description 19
Optimal Policies 23
Fundamental Limitations of Learning and Optimization 30
A Sensitivity-Based View of Learning and Optimization 35
Problem Formulations in Different Disciplines 37
Perturbation Analysis (PA) 39
Markov Decision Processes (MDPs) 44
Reinforcement Learning (RL) 49
Identification and Adaptive Control (I& AC)
Event-Based Optimization and Potential Aggregation 55
A Map of the Learning and Optimization World 59
Terminology and Notation 60
Problems 60
Part I Four Disciplines in Learning and Optimization 67
Perturbation Analysis 68
Perturbation Analysis of Markov Chains 69
Constructing a Perturbed Sample Path 70
Perturbation Realization Factors and Performance Potentials 74
Performance Derivative Formulas 81
Gradients with Discounted Reward Criteria 85
Higher-Order Derivatives and the MacLaurin Series 91
Performance Sensitivities of Markov Processes 100
Performance Sensitivities of Semi-Markov Processes* 107
Fundamentals for Semi-Markov Processes* 107
Performance Sensitivity Formulas* 112
Perturbation Analysis of Queueing Systems 119
Constructing a Perturbed Sample Path 122
Perturbation Realization 132
Performance Derivatives 138
Remarks on Theoretical Issues* 142
Other Methods* 149
Problems 154
Learning and Optimization with Perturbation Analysis 164
The Potentials 165
Numerical Methods 165
Learning Potentials from Sample Paths 168
Coupling* 173
Performance Derivatives 178
Estimating through Potentials 178
Learning Directly 179
Optimization with PA 189
Gradient Methods and Stochastic Approximation 189
Optimization with Long Sample Paths 191
Applications 194
Problems 194
Markov Decision Processes 200
Ergodic Chains 202
Policy Iteration 203
Bias Optimality 209
MDPs with Discounted Rewards 218
Multi-Chains 220
Policy Iteration 222
Bias Optimality 233
MDPs with Discounted Rewards 243
The nth-Bias Optimization* 245
nth-Bias Difference Formulas* 246
Optimality Equations* 249
Policy Iteration* 257
nth-Bias Optimal Policy Spaces* 261
Problems 261
Sample-Path-Based Policy Iteration 270
Motivation 271
Convergence Properties 275
Convergence of Potential Estimates 276
Sample Paths with a Fixed Number of Regenerative Periods 277
Sample Paths with Increasing Lengths 284
``Fast" Algorithms* 294
The Algorithm That Stops in a Finite Number of Periods* 295
With Stochastic Approximation* 299
Problems 300
Reinforcement Learning 305
Stochastic Approximation 306
Finding the Zeros of a Function Recursively 307
Estimating Mean Values 313
Temporal Difference Methods 314
TD Methods for Potentials 314
Q-Factors and Other Extensions 324
TD Methods for Performance Derivatives 329
TD Methods and Performance Optimization 334
PA-Based Optimization 334
Q-Learning 337
Optimistic On-Line Policy Iteration 341
Value Iteration 343
Summary of the Learning and Optimization Methods 346
Problems 350
Adaptive Control Problems as MDPs 357
Control Problems and MDPs 358
Control Systems Modelled as MDPs 358
A Comparison of the Two Approaches 361
MDPs with Continuous State Spaces 369
Operators on Continuous Spaces 370
Potentials and Policy Iteration 375
Linear Control Systems and the Riccati Equation 379
The LQ Problem 379
The JLQ Problem* 384
On-Line Optimization and Adaptive Control 389
Discretization and Estimation 390
Discussion 395
Problems 396
Part II The Event-Based Optimization - A New Approach 400
Event-Based Optimization of Markov Systems 401
An Overview 402
Summary of Previous Chapters 402
An Overview of the Event-Based Approach 404
Events Associated with Markov Chains 412
The Event and Event Space 414
The Probabilities of Events 417
The Basic Ideas Illustrated by Examples 421
Classification of Three Types of Events 424
Event-Based Optimization 428
The Problem Formulation 428
Performance Difference Formulas 431
Performance Derivative Formulas 434
Optimization 439
Learning: Estimating Aggregated Potentials 443
Aggregated Potentials 443
Aggregated Potentials in the Event-Based Optimization 446
Applications and Examples 448
Manufacturing 448
Service Rate Control 452
General Applications 458
Problems 459
Constructing Sensitivity Formulas 469
Motivation 469
Markov Chains on the Same State Space 470
Event-Based Systems 478
Sample-Path Construction* 478
Parameterized Systems: An Example 481
Markov Chains with Different State Spaces* 484
One Is a Subspace of the Other* 484
A More General Case 492
Summary 496
Problems 496
Part III Appendices: Mathematical Background 501
Probability and Markov Processes 503
Probability 503
Markov Processes 510
Problems 515
Stochastic Matrices 519
Canonical Form 519
Eigenvalues 520
The Limiting Matrix 523
Problems 528
Queueing Theory 530
Single-Server Queues 530
Queueing Networks 535
Some Useful Techniques 547
Problems 549
Notation and Abbreviations 64
References 557
Index 572