Dynamic Programming and Optimal Control

Table of Contents:

Volume 1

1. The Dynamic Programming Algorithm

   1. Introduction
   2. The Basic Problem
   3. The Dynamic Programming Algorithm
   4. State Augmentation and Other Reformulations
   5. Some Mathematical Issues
   6. Dynamic Programming and Minimax Control
   7. Notes, Sources, and Exercises
   
   

2. Deterministic Systems and the Shortest Path Problem

   1. Finite-State Systems and Shortest Paths
   2. Some Shortest Path Applications
      1. Critical Path Analysis
      2. Hidden Markov Models and the Viterbi Algorithm
   3. Shortest Path Algorithms
      1. Label Correcting Methods - A* Algorithm
      2. Branch-and-Bound
      3. Constrained and Multiobjective Problems
   4. Notes, Sources, and Exercises
   
   

3. Deterministic Continuous-Time Optimal Control

   1. Continuous-Time Optimal Control
   2. The Hamilton-Jacobi-Bellman Equation
   3. The Pontryagin Minimum Principle
      1. An Informal Derivation Using the HJB Equation
      2. A Derivation Based on Variational Ideas
      3. The Minimum Principle for Discrete-Time Problems
   4. Extensions of the Minimum Principle
      1. Fixed Terminal State
      2. Free Initial State
      3. Free Terminal Time
      4. Time-Varying System and Cost
      5. Singular Problems
   5. Notes, Sources, and Exercises
   
   

4. Problems with Perfect State Information

   1. Linear Systems and Quadratic Cost
   2. Inventory Control
   3. Dynamic Portfolio Analysis
   4. Optimal Stopping Problems
   5. Scheduling and the Interchange Argument
   6. Set-Membership Description of Uncertainty
      1. Set-Membership Estimation
      2. Control with Unknown-but-Bounded Disturbances
   7. Notes, Sources, and Exercises
   
   

5. Problems with Imperfect State Information

   1. Reductions to the Perfect Information Case
   2. Linear Systems and Quadratic Cost
   3. Minimum Variance Control of Linear Systems
   4. Sufficient Statistics and Finite-State Markov Chains
   5. Sequential Hypothesis Testing
   6. Notes, Sources, and Exercises
   
   

6. Suboptimal and Adaptive Control

   1. Certainty Equivalent and Adaptive Control
      1. Caution, Probing, and Dual Control
      2. Two-Phase Control and Identifiability
      3. Certainty Equivalent Control and Identifiability
      4. Self-Tuning Regulators
   2. Open-Loop Feedback Control
   3. Limited Lookahead Policies and Applications
      1. Performance Bounds of Limited Lookahead Policies
      2. Computational Issues in Limited Lookahead
      3. Problem Approximation -- Enforced Decomposition
      4. Aggregation
      5. Parametric Cost-to-Go Approximation
   4. Rollout Algorithms
      1. Discrete Deterministic Problems
      2. Q-Factors Evaluated by Simulation
      3. Q-Factor Approximation
   5. Model Predictive Control and Related Methods
      1. Rolling Horizon Approximations
      2. Stability Issues in Model Predictive Control
      3. Restricted Structure Policies
   6. Additional Topics in Approximate DP
      1. Discretization
      2. Other Approximation Approaches
   7. Notes, Sources, and Exercises
   
   

7. Introduction to Infinite Horizon Problems

   1. An Overview
   2. Stochastic Shortest Path Problems
   3. Discounted Problems
   4. Average Cost Problems
   5. Semi-Markov Problems
   6. Notes, Sources, and Exercises
   
   

8. Appendix A: Mathematical Review

9. Appendix B: On Optimization Theory

10. Appendix C: On Probability Theory

11. Appendix D: On Finite-State Markov Chains

12. Appendix E: Kalman Filtering

13. Appendix F: Modeling of Stochastic Linear Systems

14. Appendix G: Formulating Problems of Decision Under Uncertainty

Volume 2

1. Infinite Horizon - Discounted Problems

   1. Minimization of Total Cost - Introduction
      1. The Finite-Horizon DP Algorithm
      2. Shorthand Notation and Monotonicity
      3. A Preview of Infinite Horizon Results
      4. The Finite-Horizon DP Algorithm
      5. Randomized and History-Dependent Policies
   2. Discounted Problems with Bounded Cost per Stage
   3. Finite-State Systems - Computational Methods
      1. Value Iteration and Error Bounds
      2. Variants of Value Iteration
      3. Policy Iteration
      4. Linear Programming
      5. Limited Lookahead and Rollout Policies
   4. The Role of Contraction Mappings
      1. Sup-Norm Contractions
      2. m-Stage Sup-Norm Contractions
      3. Discounted Problems - Unbounded Cost per Stage
   5. Scheduling and Multiarmed Bandit Problems
   6. Notes, Sources, and Exercises
   
   

2. Stochastic Shortest Path Problems

   1. Problem Formulation
   2. Bellman's Equation
   3. Value Iteration
   4. Policy Iteration
   5. Countable State Spaces
   6. Notes, Sources, and Exercises
   
   

3. Undiscounted Problems

   1. Unbounded Costs per Stage
   2. Linear Systems and Quadratic Cost
   3. Inventory Control
   4. Optimal Stopping
   5. Optimal Gambling Strategies
   6. Nonstationary and Periodic Problems
   7. Notes, Sources, and Exercises
   
   

4. Average Cost per Stage Problems

   1. Finite-Spaces Average Cost Models
      1. Relation with the Discounted Cost Problem
      2. Blackwell Optimal Policies
      3. Optimality Equations
   2. Conditions for Equal Average Cost for all Initial States
   3. Value Iteration
      1. Single-Chain Value Iteration
      2. Multi-Chain Value Iteration
   4. Policy Iteration
      1. Single-Chain Policy Iteration
      2. Multi-Chain Policy Iteration
   5. Linear Programming
   6. Infinite-Spaces Problems
      1. A Sufficient Condition for Optimality
      2. Finite State Space and Infinite Control Space
      3. Countable States -- Vanishing Discount Approach
      4. Countable States -- Contraction Approach
      5. Linear Systems with Quadratic Cost
   7. Notes, Sources, and Exercises
   
   

5. Continuous-Time Problems

   1. Uniformization
   2. Queueing Applications
   3. Semi-Markov Problems
   4. Notes, Sources, and Exercises