// the one-minute version
Dynamic programming (DP) assumes a finite MDP and complete dynamics p(s′,r|s,a). Policy evaluation repeatedly applies the Bellman expectation backup until V approximates vπ. Policy improvement makes the policy greedy with respect to one-step action values, guaranteed not to worsen it. Policy iteration alternates these operations; value iteration uses the Bellman optimality backup, effectively doing one evaluation sweep before improving. Asynchronous DP updates states in flexible orders. Generalized policy iteration (GPI) is the deeper pattern: value estimates move toward a policy while the policy moves toward greediness. Most later control algorithms are sampled or approximate forms of this interaction.
Asha's simulator is finally calibrated. Given any warehouse state and action, it returns every possible next state, reward, and probability. She celebrates—then realizes a model is only a book of consequences. It does not tell the robot what to do. Enumerating every possible route tree is exponential. She needs a way to reuse solutions to smaller future problems instead of solving every trajectory from scratch. Dynamic programming turns Bellman's recursive equations into that procedure.
01 Why a complete model changes the problem
Chapter 3 gave Bellman equations as consistency conditions. With p known, their expectations can be computed rather than sampled. DP refers to algorithms that use these full expectations and decompose a sequential problem into overlapping subproblems.
For each state, a backup replaces or moves its estimate toward immediate reward plus successor values. Because many trajectories share successors, storing one value per state avoids recomputing entire futures. The cost is sweeping through states and actions, not enumerating trajectories.
02 Iterative policy evaluation
Fix policy π. Its value function is the unique solution of the Bellman expectation equations for γ<1 or proper episodic settings. Directly solving the linear system is possible but expensive and structurally unnecessary. Iterative evaluation starts from arbitrary V and sweeps:
Each sweep uses old successor estimates to construct new estimates. Reward information propagates backward: states one step from a terminal improve first, then their predecessors. Under standard conditions Vk converges to vπ.
In-place updates overwrite V(s) immediately and later states in the same sweep can use fresh values. This changes intermediate numbers and often accelerates convergence, while still converging. Stop when the largest change Δ across a sweep is below tolerance θ; smaller θ gives a more accurate evaluation at greater cost.
03 Policy improvement and its theorem
After evaluating π, ask whether another action at state s has higher one-step value:
If qπ(s,a)≥vπ(s), choosing a in s and following π afterward is no worse than following π immediately. Applying this choice at every state yields a greedy policy π′. The policy-improvement theorem guarantees vπ′(s)≥vπ(s) for all states.
If the greedy policy equals the old policy, Bellman optimality holds and both are optimal. Otherwise at least one state improves. Ties matter: careless tie changes can make a stable optimal policy appear to oscillate. Treat the policy as stable when its old action remains among the maximizers.
04 Policy iteration
Policy iteration alternates two phases:
Because a finite MDP has finitely many deterministic policies and each genuine change improves value, the sequence reaches an optimal policy in finitely many improvement steps. Exact evaluation, however, may take many sweeps, and most precision is discarded as soon as the policy changes.
Modified policy iteration stops evaluation early—perhaps after a few sweeps—then improves anyway. The surprising lesson is that evaluation need not be complete for useful policy progress. That insight leads directly to GPI.
Fig 1 — Evaluation and improvement need not finish in lockstep. Their interaction is the recurring architecture of control.
05 Value iteration
Value iteration truncates policy evaluation after one sweep and immediately applies maximization:
This is the Bellman optimality operator. Repeated application converges to v* in the discounted finite setting. Once values stabilize sufficiently, extract a greedy policy using one-step lookahead.
Do not confuse “one sweep” with “one update.” One sweep still visits every state. Value iteration saves full policy-evaluation convergence, but it still assumes the model and exhaustive state access.
For Asha's grid, value iteration makes every cell point toward the neighbor with the best current estimate while values propagate from delivery states. Policy iteration holds a policy fixed for multiple sweeps; value iteration changes the implied policy continuously.
06 Asynchronous dynamic programming
Synchronous algorithms sweep all states in a fixed order. Asynchronous DP updates states individually in any order, using whatever values are currently available. Convergence still holds if every relevant state continues to be updated under suitable conditions.
This flexibility matters because not all states deserve equal compute. Asha can update states near active routes more often, process states whose successors changed, or perform real-time updates while the robot waits. In-place Gauss–Seidel-style ordering can propagate information faster than rigid full copies.
But prioritization changes speed, not the fixed point. Starving states indefinitely can leave their values wrong and later corrupt decisions when the robot finally visits them.
07 Generalized policy iteration—the chapter's deepest idea
GPI describes any process in which evaluation pushes values toward the current policy while improvement pushes the policy toward greediness with respect to current values. The two targets move because each process changes the other's objective.
This looks unstable, yet they converge together. If evaluation catches up, improvement changes the policy. If improvement becomes greedy, evaluation changes values and exposes new improvements. The only shared fixed point is an optimal value function with a policy greedy relative to it.
Policy iteration, value iteration, actor–critic, Sarsa, Q-learning, and many planning methods differ in how much evaluation and improvement they perform, what data they use, and whether expectations are sampled. Seeing GPI prevents the book from becoming an acronym list.
08 Efficiency, assumptions, and limits
DP is polynomial in the number of states and actions, far better than enumerating policies, but it suffers the curse of dimensionality. Ten binary features already create 210 states; a realistic robot's continuous state is effectively uncountable.
DP also requires p(s′,r|s,a). Real models may be unknown, costly, or biased. Later chapters replace expected backups with sampled experience. The backup target remains recognizable; only the source of the expectation changes.
Convergence tolerance affects policy quality. A small value error can change a greedy action when alternatives are close. Conversely, exact values are unnecessary when action gaps are large. Practical stopping criteria should consider both residual size and policy stability.
common catches & gotchas
- Calling one backup “dynamic programming” — DP is the iterative organization of model-based expected backups across subproblems.
- Mixing old and new arrays accidentally — Synchronous and in-place updates both work, but produce different intermediate results; document which is implemented.
- Breaking ties as policy changes — A policy can appear unstable while switching among equally good actions. Preserve an old maximizing action.
- Extracting a policy too early — Values may have small residual error but wrong action ordering where action gaps are tiny.
- Ignoring unreachable states — Full sweeps waste work, yet never updating a state can become dangerous after the start distribution or dynamics change.
- Treating the simulator as truth — DP optimizes the supplied model perfectly; model bias can make the real policy systematically wrong.
09 Questions master's students should answer
Why does iterative policy evaluation converge?
For discounted finite MDPs, the Bellman expectation operator is a γ-contraction in max norm: applying it shrinks the distance between value functions by at most γ, so repeated applications reach its unique fixed point.
Why can a greedy policy not be worse?
Each greedy action has one-step value at least as high as the policy-weighted action value under vπ. Repeated substitution shows its return is at least vπ in every state.
Policy iteration or value iteration?
Policy iteration performs more evaluation per improvement and often needs few policy changes. Value iteration performs cheaper intertwined updates. Relative speed depends on model structure, solver, and desired accuracy.
Does update order matter?
It changes convergence speed and intermediate values, not the limiting solution when all states are updated adequately. Prioritizing high-residual or reachable states can be much faster.
Where does sampling enter later?
Monte Carlo and TD methods replace sums over model outcomes with sampled returns or transitions. They preserve the evaluation/improvement logic while removing the complete-model requirement.
10 Key takeaways
- DP converts Bellman consistency equations into repeated model-based expected backups.
- Iterative policy evaluation converges toward vπ; in-place updates can accelerate propagation.
- Greedy improvement is guaranteed not to worsen a fully evaluated policy.
- Policy iteration alternates evaluation and improvement; modified variants evaluate only approximately.
- Value iteration repeatedly applies the Bellman optimality operator and extracts a greedy policy afterward.
- Asynchronous DP permits flexible ordering as long as important states continue receiving updates.
- GPI—evaluation interacting with improvement—is the conceptual template for most control algorithms ahead.
evaluation
control
implementation
11 Wrapping up and source trail
Asha's model now produces a policy, not just predictions. But the simulator is expensive and never perfectly matches the warehouse. Chapter 5, Monte Carlo methods, removes the transition model and asks how complete episodes themselves can evaluate and improve behavior. The GPI structure survives; only the source of the backup target changes.
These are independent companion notes written in original language. Primary references: the authors' book page, the author-hosted open-access draft, the MIT Press edition page, and the official contents.