The one assumption that changes everything
Dynamic programming (DP) is what you do when you have a perfect model of the environment — you know every transition probability and every reward in the Markov decision process (MDP). With that knowledge, you never have to act to learn; you can sit down with the equations and compute the value of any policy and the best policy outright.
Nodes representing states connected by arrows labeled with transition probabilities.
That sounds like cheating, and in a sense it is — most real problems never hand you the model. But DP matters anyway, because it is the ideal that every practical method approximates. Understand DP and you understand the skeleton inside temporal-difference learning, Monte Carlo methods, and even deep Q-networks.
The big idea: bootstrapping
DP rests on one trick: bootstrapping — estimating the value of a state from the estimated values of the states it leads to. You don't wait for an episode to finish; you update your guess about here using your guess about next. The Bellman expectation equation makes this precise: the value of a state equals the immediate reward plus the discounted value of wherever you land next.
Turning that equation into a repeated update gives us the Bellman backup: sweep over every state, replace its old value with the right-hand side of the Bellman equation, repeat. Each sweep pushes the estimates a little closer to the truth. The word backup is literal — value information flows backward from successor states to the state you are updating.
The Bellman backup: each sweep replaces a state's value with the expected reward plus the discounted value of where it leads — bootstrapping in one line.
Two jobs DP does
Everything in this track is built from two tasks. Prediction asks: given a fixed policy, how good is it? That is policy evaluation. Control asks: what is the best policy? DP solves control by alternating evaluation with improvement, which we build up over the next guides.
- Prediction — fix a policy, compute its value function (policy evaluation).
- Improvement — make the policy greedy with respect to those values.
- Control — repeat prediction + improvement until the policy stops changing.
Full backups, not samples
Because DP owns the model, it can do a full backup: when it updates a state, it considers every possible next state, weighted by its true probability. Sample-based methods like TD and Monte Carlo can only afford a sample backup — they follow one randomly sampled transition at a time. Full backups are exact but expensive; sample backups are cheap but noisy. This trade-off is the dividing line between planning and learning.
Where this track goes
Next we make policy evaluation concrete — an actual sweeping algorithm you could code in an afternoon. Then we add policy improvement to climb toward the optimal policy, collapse the whole loop into value iteration, study why it provably converges, and finally face the practical wall — the curse of dimensionality — that pushes us toward sampled RL.