Dynamic Programming in Control
Dynamic programming solves sequential decision problems by working backward from the goal, building optimal policies from optimal subproblems.
Optimality from Subproblems
Dynamic programming, formulated by Richard Bellman, solves multistage decision problems by exploiting the principle of optimality: an optimal policy has the property that whatever the current state, the remaining decisions must form an optimal policy for the subproblem that starts there. This lets a large problem be built up from smaller optimal pieces.
Working backward
The method typically proceeds backward in time. Starting from the final stage, where the optimal cost is known, it computes the optimal decision and cost at each earlier stage assuming all later stages are already solved optimally. By the time it reaches the initial state, it has an optimal decision for every possible state at every stage: a complete feedback policy.
Discrete and continuous forms
- In discrete time and discrete state, dynamic programming fills a table of optimal values by recursion, the basis of many algorithms.
- In continuous time it becomes the Hamilton-Jacobi-Bellman partial differential equation.
- In stochastic settings it uses expected costs, giving the Bellman equation at the heart of Markov decision processes and reinforcement learning.
The curse of dimensionality
Bellman himself named the central obstacle: the number of states to evaluate grows exponentially with the number of state variables. A modest continuous problem discretized into a grid quickly becomes computationally impossible. This curse limits exact dynamic programming to low-dimensional or specially structured problems.
Approximate and learning-based methods
Modern practice sidesteps the curse with approximation. Approximate dynamic programming and reinforcement learning estimate the value function with function approximators rather than exhaustive tables, learning good policies for high-dimensional problems from simulation or data. Model-predictive control can be seen as solving a truncated dynamic program online at each step.
Dynamic programming's lasting contribution is conceptual as much as computational: the value function and the Bellman recursion give a unified language for optimal sequential decision making that connects classical optimal control to modern reinforcement learning.