Abstract Dynamic Programming

Front Matter......Page 1
About the Author......Page 3
Contents......Page 5
Preface of the First Edition......Page 9
Preface to the Second Edition......Page 13
1.1 Structure of Dynamic Programming Problems......Page 15
1.2 Abstract Dynamic Programming Models......Page 19
1.2.1 Problem Formulation......Page 18
1.2.2 Monotonicity and Contraction Properties......Page 21
1.2.3 Some Examples......Page 23
1.2.4 Approximation Models - Projected and Aggregation Bellman Equations......Page 37
1.2.5 Multistep Models - Temporal Difference and Proximal Algorithms......Page 39
1.3 Organization of the Book......Page 42
1.4 Notes, Sources and Exercises......Page 45
Exercises......Page 46
2. Contractive Models......Page 52
2.1 Bellman's Equation and Optimality Conditions......Page 54
2.2 Limited Lookahead Policies......Page 61
2.3 Value Iteration......Page 65
2.3.1 Approximate Value Iteration......Page 67
2.4 Policy Iteration......Page 70
2.4.1 Approximate Policy Iteration......Page 72
2.4.2 Approximate Policy Iteration Where Policies Converge......Page 75
2.5 Optimistic Policy Iteration and λ-Policy Iteration......Page 76
2.5.1 Convergence of Optimistic Policy Iteration......Page 78
2.5.2 Approximate Optimistic Policy Iteration......Page 83
2.5.3 Randomized Optimistic Policy Iteration......Page 87
2.6.1 Asynchronous Value Iteration......Page 91
2.6.2 Asynchronous Policy Iteration......Page 97
2.6.3 Optimistic Asynchronous Policy Iteration with a Uniform Fixed Point......Page 102
2.7 Notes, Sources and Exercises......Page 110
Exercises......Page 113
3. Semicontractive Models......Page 119
3.1 Pathologies of Noncontractive DP Models......Page 121
3.1.1 Deterministic Shortest Path Problems......Page 124
3.1.2 Stochastic Shortest Path Problems......Page 127
3.1.3 The Blackmailer's Dilemma......Page 129
3.1.4 Linear-Quadratic Problems......Page 131
3.1.5 An Intuitive View of Semicontractive Analysis......Page 136
3.2 Semicontractive Models and Regular Policies......Page 139
3.2.1 S-Regular Policies......Page 142
3.2.2 Restricted Optimization over S-Regular Policies......Page 144
3.2.3 Policy Iteration Analysis of Bellman's Equation......Page 150
3.2.4 Optimistic Policy Iteration and λ-Policy Iteration......Page 157
3.2.5 A Mathematical Programming Approach......Page 161
3.3 Irregular Policies/Infinite Cost Case......Page 163
3.4 Irregular Policies/Finite Cost Case - A Perturbation Approach......Page 169
3.5 Applications in Shortest Path and Other Contexts......Page 175
3.5.1 Stochastic Shortest Path Problems......Page 176
3.5.2 Affine Monotonic Problems......Page 184
3.5.3 Robust Shortest Path Planning......Page 193
3.5.4 Linear-Quadratic Optimal Control......Page 202
3.5.5 Continuous-State Deterministic Optimal Control......Page 204
3.6.1 Asynchronous Value Iteration......Page 209
3.6.2 Asynchronous Policy Iteration......Page 210
3.7 Notes, Sources and Exercises......Page 217
Exercises......Page 219
4. Noncontractive Models......Page 229
4.1 Noncontractive Models - Problem Formulation......Page 231
4.2 Finite Horizon Problems......Page 232
4.3 Infinite Horizon Problems......Page 238
4.3.1 Fixed Point Properties and Optimality Conditions......Page 242
4.3.2 Value Iteration......Page 253
4.3.3 Exact and Optimistic Policy Iteration - λ-Policy Iteration......Page 257
4.4 Regularity and Nonstationary Policies......Page 262
4.4.1 Regularity and Monotone Increasing Models......Page 269
4.4.2 Nonnegative Cost Stochastic Optimal Control......Page 270
4.4.3 Discounted Stochastic Optimal Control......Page 274
4.4.4 Convergent Models......Page 276
4.5 Stable Policies and Deterministic Optimal Control......Page 280
4.5.1 Forcing Functions and p-Stable Policies......Page 283
4.5.2 Restricted Optimization over Stable Policies......Page 286
4.5.3 Policy Iteration Methods......Page 299
4.6 Infinite-Spaces Stochastic Shortest Path Problems......Page 305
4.6.1 The Multiplicity of Solutions of Bellman's Equation......Page 313
4.6.2 The Case of Bounded Cost per Stage......Page 314
4.7 Notes, Sources and Exercises......Page 317
Exercises......Page 322
Appendix A: Notation and Mathematical Conventions......Page 334
A.1 Set Notation and Conventions......Page 335
A.2 Functions......Page 337
B.1 Contraction Mapping Fixed Point Theorems......Page 339
B.2 Weighted sup-norm Contractions......Page 343
References......Page 349
Index......Page 356