Dynamic Programming for MDPs
When the environment model is known, dynamic programming solves an MDP exactly by iterating the Bellman equations over all states.
Solving a known MDP
Dynamic programming (DP) refers to a family of methods that compute optimal policies for a Markov decision process when the transition and reward model is fully known. DP is the theoretical backbone from which sample-based reinforcement learning methods are derived as model-free approximations.
Two core operations
- Policy evaluation: given a policy, compute its value function by iterating the Bellman expectation equation until it converges.
- Policy improvement: given a value function, produce a better policy by acting greedily with respect to it.
Alternating these two operations is policy iteration. Collapsing them into a single per-state max is value iteration.
Why it works
Both operations rest on the Bellman equation being a contraction mapping: repeated application converges geometrically to a unique fixed point. The policy improvement theorem guarantees that acting greedily with respect to a policy's value function yields a policy at least as good, so iteration monotonically improves until it reaches the optimum.
The cost
DP requires a full model and sweeps over the entire state space each iteration, so its cost grows with the number of states and actions. This is the curse of dimensionality: enumerating states is infeasible for high-dimensional or continuous problems. Real control tasks, such as a simulated plasma with many continuous variables, need function approximation instead of exact tables.
The bridge to RL
Model-free RL keeps the DP logic but replaces the known model with sampled experience. Monte Carlo methods estimate values from complete returns; temporal-difference methods bootstrap from current estimates, echoing DP's use of the Bellman recursion without needing the model.