Dynamic Programming

DYNAMIC
PROGRAMMING
RICHARD BELLMAN
Preface
Contents
A Multi-Stage Allocation Process
§ 1. Introduction
§ 2. A multi-stage allocation process
§ 3. Discussion
§ 4. Functional equation approach
§ 5. Discussion
§ 6. A multi-dimensional maximization problem
§ 7. A “smoothing” problem
§ 8. Infinite stage approximation
§ 9. Existence and uniqueness theorems
§ 10. Successive approximations
§ 11. Approximation in policy space
§ 12. Properties of the solution—I: Convexity
§ 13. Properties of the solution—II: Concavity
§ 14. Properties of the solution—III: Concavity
§ 15. An “ornery” example
§ 16. A particular example—I
§ 18. Approximation and stability
§ 19. Time-dependent processes
§ 20. Multi-activity processes
KJ
§ 21. Multi-dimensional structure theorems
§ 22. Locating the unique maximum of a concave function
§ 23. Continuity and memory
§ 24. Stochastic allocation processes
§ 25. Functional equations
§ 26. Stieltjes integrals
Exercises and Research Problems for Chapter I
A Stochastic Multi-Stage Decision Process
§ 1. Introduction
§ 2. Stochastic gold-mining
§ 5. Infinite stage approximation
§ 6. Existence and uniqueness
§ 7. Approximation in policy space and monotone convergence
§ 8. The solution
§ 9. Discussion
§ 10. Some generalizations
§11. The form of f (x, y)
§ 12. The problem for a finite number of stages
§ 13. A three-choice problem
§ 14. A stability theorem
Exercises and Research Problems for Chapter II
The Structure of Dynamic Programming Processes
§ 1. Introduction
§ 4. Mathematical formulation—I. A discrete deterministic process
§ 7. Continuous stochastic processes
§ 8. Generalizations
§ 9. Causality and optimality
§ 10. Approximation in policy space
Exercises and Research Problems for Chapter III
Existence and Uniqueness Theorems
§ 1. Introduction
§ 2. A Fundamental inequality
§ 3. Equations of Type One
§ 4. Equations of Type Two
§ 5. Monotone convergence
§ 6. Stability theorems
§ 7. Some directions of generalization
§ 8. An equation of the third type
§ 9. An “optimal inventory” equation
Exercises and Research Problems for Chapter IV
The Optimal Inventory Equation
§ 1. Introduction
§ 2. Formulation of the general problem
A. Finite total time period
E. Unbounded time period—two period lag
§ 3. A simple observation
§ 4. Constant stock level—preliminary discussion
§ 5. Proportional cost—one-dimensional case
§ 6. Proportional cost—multi-dimensional case
§ 8. Finite time—multi-dimensional case
§ 9. Non-proportional penalty cost—red tape
§ 10. Particular cases
§ 11. The form of the general solution
§ 12. Fixed costs
§ 13. Preliminaries to a discussion of more complicated policies
§ 14. Unbounded process—one period time lag
Appendix Chapter V—The Renewal Equation
Exercises and research problems
Bottleneck Problems in Multi-Stage Production Processes
§ 1. Introduction
§ 2. A General class of multi-stage production problems
§ 3. Discussion of the preceding model
§ 4. Functional equations
§ 5. A Continuous version 5
§ 6. Notation
§ 7. Dynamic programming formulation
§ 9. The resultant nonlinear partial differential equation
§ 10. Application of the partial differential equation
§ 11. A Particular example
§ 12. A Dual problem
§ 13. Verification of the solution given in § 11
§ 14. Computational solution
§ 15. Nonlinear problems
Exercises and Research Problems for Chapter VI
Bottleneck Problems: Examples
§ 1. Introduction
§ 2. Preliminaries
§ 3. Delta-functions
§ 6. The equilibrium solution
§ 8. Description of solution and proof
Summary Initial Adjustments
A Continuous Stochastic Decision Process
§ 1. Introduction
§ 2. Continuous versions—I: A differential approach
§ 3. Continuous versions—II: An integral approach
§ 4. Preliminary discussion
§ 5. Mixing at a point
§ 6. Reformulation of the gold-mining process
§ 7. Derivation of the differential equations
§ 8. The variational procedure
§ 9. The behavior of Ki.
§ 10. The solution for T = oo
§ 11. Solution for finite total time
§ 12. The three-choice problem
§ 13. Some lemmas and preliminary results
§ 14. Mixed policies
§ 15. The solution for infinite time, D > 0
§ 16. D < 0
§ 17. The case r3 = r4
§ 18. Nonlinear utility—two-choice problem
A New Formalism in the Calculus of Variations
§ 1. Introduction
§ 2. A new approach
§ 4. Discussion
§ 5. The two dimensional case
§ 7. Max F(x,y) dt under the Constraint 0 < y < x y Jo
§ 8. Computational solution
§ 9. Discussion
§ 10. An example
§ 11. A discrete version
§ 12. A convergence proof
§ 14. Generalization and discussion
§ 15. Integral constraints
§ 16. Further remarks concerning numerical solution
§ 17. Eigenvalue problem
§ 18. The first formulation
§ 19. An approximate solution
§ 20. Second formulation
§ 21. Discrete approximations
§ 22. Successive approximation
§ 23. Monotone approximation
§ 24. Uniqueness of solution
§ 25. Minimum maximum deviation
Exercises and Research Problems for Chapter IX
Multi-Stage Games
§ 1. Introduction
§ 2. A Single-stage discrete game
§ 3. The min-max theorem
§ 4. Continuous games
§ 5. Finite resources
§ 6. Games of survival
§ 7. Pursuit games
§ 8. General formulation
§ 9. The principle of optimality and functional equations
§ 10. More general process
§ 11. A basic lemma
§ 12. Existence and uniqueness
§ 13. Proof of results
§ 14. Alternate proof of existence
§ 15. Successive approximations in general
§ 16. Effectiveness of solution
§ 17. Further results
§ 18. One-sided min-max
§ 19. Existence and uniqueness for games of survival
§ 20. An approximation
§ 21. Non-zero-sum games—games of survival
§ 22. An approximate solution
§ 23. Proof of the extended min-max theorem
§ 24. A rationale for non-zero sum games
Exercises and research problems for Chapter X
Markovian Decision Processes
§ 1. Introduction
§ 2. Markovian decision processes
§ 3. Notation
§ 4. A lemma
§ 5. Existence and uniqueness—I
§ 6. Existence and uniqueness—II
§ 7. Existence and uniqueness—III
§ 8. The Riccati equation
§ 9. Approximation in policy space
§ 10. Discrete versions
§ 11. The recurrence relation
§ 12. Min-max
§ 13. Generalization of a von Neumann result
Exercises and Research Problems for Chapter XI