Abstract dynamic programming

Front Matter......Page 1About the Author......Page 3Contents......Page 5Preface of the First Edition......Page 9Preface to the Second Edition......Page 131.1 Structure of Dynamic Programming Problems......Page 151.2 Abstract Dynamic Programming Models......Page 191.2.1 Problem Formulation......Page 181.2.2 Monotonicity and Contraction Properties......Page 211.2.3 Some Examples......Page 231.2.4 Approximation Models - Projected and Aggregation Bellman Equations......Page 371.2.5 Multistep Models - Temporal Difference and Proximal Algorithms......Page 391.3 Organization of the Book......Page 421.4 Notes, Sources and Exercises......Page 45Exercises......Page 462. Contractive Models......Page 522.1 Bellman's Equation and Optimality Conditions......Page 542.2 Limited Lookahead Policies......Page 612.3 Value Iteration......Page 652.3.1 Approximate Value Iteration......Page 672.4 Policy Iteration......Page 702.4.1 Approximate Policy Iteration......Page 722.4.2 Approximate Policy Iteration Where Policies Converge......Page 752.5 Optimistic Policy Iteration and λ-Policy Iteration......Page 762.5.1 Convergence of Optimistic Policy Iteration......Page 782.5.2 Approximate Optimistic Policy Iteration......Page 832.5.3 Randomized Optimistic Policy Iteration......Page 872.6.1 Asynchronous Value Iteration......Page 912.6.2 Asynchronous Policy Iteration......Page 972.6.3 Optimistic Asynchronous Policy Iteration with a Uniform Fixed Point......Page 1022.7 Notes, Sources and Exercises......Page 110Exercises......Page 1133. Semicontractive Models......Page 1193.1 Pathologies of Noncontractive DP Models......Page 1213.1.1 Deterministic Shortest Path Problems......Page 1243.1.2 Stochastic Shortest Path Problems......Page 1273.1.3 The Blackmailer's Dilemma......Page 1293.1.4 Linear-Quadratic Problems......Page 1313.1.5 An Intuitive View of Semicontractive Analysis......Page 1363.2 Semicontractive Models and Regular Policies......Page 1393.2.1 S-Regular Policies......Page 1423.2.2 Restricted Optimization over S-Regular Policies......Page 1443.2.3 Policy Iteration Analysis of Bellman's Equation......Page 1503.2.4 Optimistic Policy Iteration and λ-Policy Iteration......Page 1573.2.5 A Mathematical Programming Approach......Page 1613.3 Irregular Policies/Infinite Cost Case......Page 1633.4 Irregular Policies/Finite Cost Case - A Perturbation Approach......Page 1693.5 Applications in Shortest Path and Other Contexts......Page 1753.5.1 Stochastic Shortest Path Problems......Page 1763.5.2 Affine Monotonic Problems......Page 1843.5.3 Robust Shortest Path Planning......Page 1933.5.4 Linear-Quadratic Optimal Control......Page 2023.5.5 Continuous-State Deterministic Optimal Control......Page 2043.6.1 Asynchronous Value Iteration......Page 2093.6.2 Asynchronous Policy Iteration......Page 2103.7 Notes, Sources and Exercises......Page 217Exercises......Page 2194. Noncontractive Models......Page 2294.1 Noncontractive Models - Problem Formulation......Page 2314.2 Finite Horizon Problems......Page 2324.3 Infinite Horizon Problems......Page 2384.3.1 Fixed Point Properties and Optimality Conditions......Page 2424.3.2 Value Iteration......Page 2534.3.3 Exact and Optimistic Policy Iteration - λ-Policy Iteration......Page 2574.4 Regularity and Nonstationary Policies......Page 2624.4.1 Regularity and Monotone Increasing Models......Page 2694.4.2 Nonnegative Cost Stochastic Optimal Control......Page 2704.4.3 Discounted Stochastic Optimal Control......Page 2744.4.4 Convergent Models......Page 2764.5 Stable Policies and Deterministic Optimal Control......Page 2804.5.1 Forcing Functions and p-Stable Policies......Page 2834.5.2 Restricted Optimization over Stable Policies......Page 2864.5.3 Policy Iteration Methods......Page 2994.6 Infinite-Spaces Stochastic Shortest Path Problems......Page 3054.6.1 The Multiplicity of Solutions of Bellman's Equation......Page 3134.6.2 The Case of Bounded Cost per Stage......Page 3144.7 Notes, Sources and Exercises......Page 317Exercises......Page 322Appendix A: Notation and Mathematical Conventions......Page 334A.1 Set Notation and Conventions......Page 335A.2 Functions......Page 337B.1 Contraction Mapping Fixed Point Theorems......Page 339B.2 Weighted sup-norm Contractions......Page 343References......Page 349Index......Page 356