DCT Lexicon · Governing Dynamics
Bellman Recursion
Bellman's principle says an optimal plan stays optimal from every state it reaches. It turns a decision over a whole horizon into a recursion over one step.
DCT Governing Dynamics
In depth
Formal statement
For a discounted problem with reward , kernel and discount , the value function is the unique fixed point of the Bellman operator.
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
Contraction and verification
is a -contraction on bounded functions, so value iteration converges geometrically, and a greedy policy for is optimal. The Bellman residual of any approximation bounds its distance to the true value.
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
In DCT
Schedules of automation rounds, hiring rules and the timing of a sale are dynamic programs. The Bellman residual is the dynamic certificate: it states how far from optimal a computed policy can be, in money.
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
Limits
The curse of dimensionality: grids grow exponentially with the state. Approximate dynamic programming trades exactness for scale, and its certificates weaken to bounds.
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
Go next
- HJB Equations and Viscosity Solutions: In continuous time the recursion becomes the HJB equation (Pathway 3).
- Robust Viability: Robust viability is a dynamic program with an adversary (Pathway 5).
- Occupation Measures: The dual of the Bellman LP is a program over occupation measures.
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
References
- Bellman (1957), Dynamic Programming
- Puterman (1994), Markov Decision Processes
- Bertsekas (2012), Dynamic Programming and Optimal Control
DCT Governing Dynamics: the element's drawer (/governing-dynamics)
In the book: Vol. II, Ch. 5: Dynamic Enterprise Optimization · Vol. II, Ch. 7: Dynamic Programming for Enterprise Systems
Related: HJB Equations and Viscosity Solutions · Robust Viability · Occupation Measures
GD.11


