M4-T4 — Dynamic Programming and Value Iteration

Learning objectives

After this lesson, you should be able to:

• Run policy evaluation, policy iteration and value iteration by hand on a small chain and read the sweeps.
• State why the Bellman optimality backup is a gamma-contraction in the max norm and use it to bound the error after k sweeps and at a stopping test.
• Compare synchronous and in-place sweeps and say what changes (the number of sweeps, not the answer).
• Count the cost of a sweep as states times actions times successors and explain why dynamic programming needs a model and does not scale.

The intuition

Picture the nurse-station corridor with the pharmacy at one end. Before any sweep, Scout knows nothing: every value is zero. The pharmacy is the only place where something real happens, because entering it pays a reward. After the first sweep the cell next to the pharmacy knows it is worth something. After the second, the cell next to that one knows, and so on. Information flows backwards from the goal, one step per sweep, like water filling a channel.

That picture also says when you can stop. Once the information has reached the farthest state, further sweeps change nothing. In a deterministic corridor that happens after about as many sweeps as the longest route. With slippery floors the information keeps arriving in ever smaller amounts, so you stop when a sweep changes no value by more than a tolerance. The figure shows the first three sweeps on a four-state chain; the worked example below computes every number.

The mathematics

Setting: a known MDP

Dynamic programming (DP) assumes the full model from lesson M4-T1: the transition probabilities p(s′ | s, a) and the rewards. Write q(s, a) for the expected one-step return computed with the current value table V. Terminal states keep V = 0.

V

a table with one number per state; the current estimate of the value.

done

1 when the move ends the episode (goal or terminal stairwell), else 0. No bootstrapping through a terminal state.

sweep

one pass that updates every non-terminal state once.

T

the Bellman optimality operator: (T V)(s) = max over a of q(s, a).

The three algorithms

Policy iteration alternates two steps: evaluation (run the expectation backup to convergence) and improvement (act greedily). Each improvement can only help, and a finite MDP has finitely many deterministic policies, so it stops. Value iteration is the extreme in which evaluation is cut to a single sweep and merged with the improvement step. The family in between, with a few evaluation sweeps per round, is called modified policy iteration. The idea goes back to Bellman (1957) and Howard (1960).

Why value iteration converges: the contraction

Measure the distance between two value tables by the largest difference over states, the max norm.

For any two tables V and W and any state s, the key inequality is that a max cannot move by more than the largest change inside it: |max_a x_a − max_a y_a| ≤ max_a |x_a − y_a|. Applied to q(s, a) computed from V and from W, the rewards cancel and the probabilities sum to at most 1, so each action's value moves by at most gamma · ||V − W||. Hence:

T is a gamma-contraction. Two consequences follow from the Banach fixed-point theorem, which says a contraction on a complete space has exactly one fixed point and iterating it converges to that point from any start. The fixed point of T is V*, so V* is unique and value iteration finds it from any initial table. Writing V_k for the table after k synchronous sweeps:

The second bound is what a stopping rule can use, because it needs only quantities you have in hand. Stopping when the largest change in a sweep is below tol therefore guarantees an error below gamma · tol / (1 − gamma). At gamma = 0.99 that is 99 times tol, so choose tol accordingly. The first bound gives the worst-case number of sweeps, k ≥ ln(tol / ||V₀ − V*||) / ln(gamma). Both bounds are worst case: the true error is often far smaller, and the example below shows by how much.

Synchronous and in-place sweeps

A synchronous sweep reads every right-hand side from the old table and writes a new one; the contraction argument applies to it directly. An in-place sweep overwrites V(s) immediately, so later states in the same sweep already see the new values. It also converges to V* (Sutton and Barto, 2018, section 4.1), uses one table, and usually needs fewer sweeps. The state order now matters: sweeping from the goal outward spreads real information faster than sweeping the other way. The proof above is for the synchronous form only; I rely on the cited book for the in-place claim.

Cost

K is the number of different next states per (s, a). It is 1 for a deterministic world and 3 for the ward's slip model. The whole method also needs the model p and r, as a table or as a function you can call for every successor. A robot rarely has that, which is why lessons M4-T5 and M4-T6 learn from sampled experience instead.

A worked example

Every number here was computed by running the reference code in rl-core.js (the gridworld, valueIteration and evaluatePolicyDP functions) or a short script on the same environments. The sweep counts below use a tolerance of 1e-9 on the largest change in one sweep, and the count includes the last sweep that changed nothing.

1. Two sweeps by hand. A one-row ward: states A, B, C, then the terminal pharmacy. Action right moves one cell; left moves one cell, and bumping the wall at A leaves Scout in place. Every step costs 1, entering the pharmacy pays +10 (so the move into it returns 9 in total), gamma is 0.9, and the model is deterministic. Start with V₀ = 0 everywhere and sweep synchronously.

• Sweep 1. C: right gives −1 + 10 = 9, left gives −1 + 0.9 · 0 = −1, so V(C) = 9. B: both moves give −1 + 0.9 · 0 = −1, so V(B) = −1. A: both give −1, so V(A) = −1. Result (−1, −1, 9).
• Sweep 2. C stays 9. B: right gives −1 + 0.9 · V₁(C) = −1 + 8.1 = 7.1. A: right gives −1 + 0.9 · V₁(B) = −1.9, and left (a bump) gives −1 + 0.9 · V₁(A) = −1.9. Result (−1.9, 7.1, 9).
• Sweep 3. A: right gives −1 + 0.9 · 7.1 = 5.39. Result (5.39, 7.1, 9), which is V*. Sweep 4 changes nothing, so the stopping test fires there: 4 sweeps in total, the reference code reports 4 for this chain.

The greedy policy is right in every state. The max-norm error against V* is 9, 8.1, 7.29 and then 0 after sweeps 0, 1, 2 and 3: the first two steps shrink by exactly the factor gamma = 0.9, the bound holding with equality, and the last step shrinks to zero because the chain is only three states long.

2. In-place order. Update the same chain in place in the order C, B, A. In one sweep C becomes 9, then B sees it (7.1), then A sees that (5.39): V* after one sweep, and the second sweep confirms it, so 2 sweeps in total. In the order A, B, C the in-place sweep behaves like the synchronous one and needs 4. Same fixed point, different path.

3. Sweeps to convergence on the two worlds. The cliff is deterministic (31 non-terminal states; 124 successor terms per sweep). The ward has slip 0.2, step reward −0.1, goal +10 and a terminal stairwell edge of −10 (23 non-terminal states, 234 successor terms per sweep). The in-place forward order is row by row from the top-left, which is what RLCore.valueIteration uses; the reverse order starts at the bottom right, near the goal.

The cliff needs 11 sweeps at every gamma I tried (0.5, 0.8, 0.9, 0.95 and 0.99): it is deterministic, so values are exact once the information has crossed the longest route, 10 steps from the top-left corner to the goal, and the eleventh sweep detects it. On the ward each state keeps receiving a little information from slips, so the count grows with gamma, and at gamma = 0.99 it is 172 to 192. The forward in-place order saves about 25% of the sweeps at gamma = 0.95 (35 against 46); the goal-first order saves a further 6.

4. The contraction on the ward (gamma = 0.95, synchronous). ||V₀ − V*|| = 9.7531. The error after k sweeps is 9.05, 8.47, 6.13 (k = 1, 2, 3) and 1.25, 0.0657, 2.6e-3, 7.9e-5 at k = 15, 20, 25, 30, reaching 8.8e-10 at k = 45. The error ratio from one sweep to the next never exceeded 0.9358, below gamma = 0.95, and settles near 0.455 once the slow part of the error has gone. The a priori bound gamma^k · 9.7531 predicts 449 sweeps for 1e-9, against the 46 observed: the bound is valid but about ten times too pessimistic. On the cliff at gamma = 0.99 it predicts 2,281 sweeps against 11. The stopping bound also holds: at sweep 20 the largest change is 0.0598, so the error is at most 0.95 / 0.05 · 0.0598 = 1.13, and the true error is 0.0657.

5. Policy iteration. Start from the policy that always chooses up, evaluate it to a tolerance of 1e-10 and improve greedily, switching an action only if it is better by more than 1e-9. The ward converges in 9 rounds (12, 4, 2, 8, 1, 1, 1, 1 and 0 actions changed per round) using 1,650 evaluation sweeps in total, to the same V* as value iteration within 4.4e-11. The cliff at gamma = 0.99 takes 11 rounds and 22,941 evaluation sweeps. Few rounds, many sweeps: the always-up policy bumps the top wall forever for −1 per step, a value of −1 / (1 − 0.99) = −100, and evaluating such a policy converges only as 0.99^k. Solving the linear system for V^π directly would avoid this; my counts are for the sweeping version.

6. Cost, and why it does not scale. One ward sweep is 234 multiply-adds, trivial. Now discretise Module 1's 10 m by 6 m hall into 10 cm cells: 100 x 60 = 6,000 states, 4 actions and 3 successors give 72,000 terms per sweep, still fine. But Scout's observation in Module 1 has four numbers [dx, dy, px, py]. A grid of 50 values per number has 50⁴ = 6,250,000 states; with 9 actions and 4 successors each, that is 225 million terms per sweep, and about a hundred sweeps is more than 2 x 10¹⁰ operations, plus 50 MB just for the table. Every extra state variable multiplies the table by its grid size. This is the curse of dimensionality, and it is why DP is a tool for small, known problems and for understanding, not for continuous robots.

What the simulation simplifies. The ward and cliff are tiny tabular worlds with an exactly known model. On a robot the model is estimated, the state is continuous, and the transition probabilities are themselves uncertain, so DP's answer is only as good as the model it is given.

Engineering implications and limitations

Use DP as the ground truth for small cases

When you build a learning agent for a small environment, compute V* and the optimal policy with value iteration first. Every learner in lessons M4-T5 and M4-T6 can then be scored against the exact answer, which is what lab M4-L2 (implement Q-learning) does when it grades a learned policy against the optimum.

Check the terminal handling

The commonest bug in a hand-written backup is bootstrapping from a terminal state: the target uses gamma · V(s′) for the goal cell and the goal's value drifts away from 0, or the goal leaks reward forever. Always multiply by (1 − done). Lab M4-L1 (solve an MDP by value iteration) starts from exactly this bug.

Choose the tolerance with the bound in mind

The stopping test gives error at most gamma / (1 − gamma) times tol. For gamma close to 1 that is a large factor, so tighten tol or compare greedy policies instead of values. Also cap the number of sweeps, so a modelling mistake cannot hang a planner.

Order the sweep

If you must sweep in place, order the states so that successors are updated before predecessors (goal outward). A priority queue that updates the states with the largest recent change first is a common refinement; I describe the idea only, without having measured it here.

Remember where the model comes from

If p and r are estimated from data, errors in them are amplified by the planner: a spurious shortcut in the model becomes the optimal route. Test the planned policy in the real or simulated system before trusting it.

Common misconceptions

Engineering takeaways

1. Policy evaluation, policy iteration and value iteration all sweep the Bellman equations over a known model; value iteration merges evaluation and improvement into one max.
2. The optimality backup is a gamma-contraction in the max norm, so value iteration converges to the unique V* from any start, with error at most gamma^k times the initial error.
3. The stopping test is a bound, gamma / (1 − gamma) times the last change; both bounds are worst case and the real count was 35 to 46 sweeps on the ward and 11 on the cliff.
4. In-place sweeps use fewer sweeps than synchronous ones (35 against 46 on the ward at gamma 0.95) and reach the same answer, and the state order matters.
5. A sweep costs states x actions x successors and needs the model, so DP does not scale to continuous robots; the next lessons learn from experience instead.

References and further reading

Primary sources on dynamic programming for Markov decision processes and the standard textbook treatment.

• R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd edition, MIT Press, 2018 (chapter 4, Dynamic Programming).
• R. Bellman, Dynamic Programming, Princeton University Press, 1957.
• R. A. Howard, Dynamic Programming and Markov Processes, MIT Press, 1960.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: when the model is not available, estimate values from sampled episodes with Monte Carlo and temporal-difference learning, and see what each method pays in bias and variance.

Related content

Nothing below is required to finish this lesson.

• Before
  M4-T3: Value Functions and the Bellman Equations

  Write the Bellman expectation and optimality equations and use them to evaluate and improve a policy.

• Lab
  M4-L1: Solve an MDP by Value Iteration

  Plan Scout's route through a hospital grid with slippery floors by computing optimal values and the greedy policy.