Dynamic programming (value - policy iteration): Visual walkthrough

This page builds the central engine of dynamic programming — the value iteration update — one picture at a time. We start with nothing but a grid, a walking agent, and the idea of "how good is it to stand here?" By the end you will have watched a number we will call $V (s)$ grow, step by step, from a blank board into the true "distance-to-goal" map. That settled map has a name we will earn in Step 3 — the optimal value $V^{*}$ — but for now, think of it simply as the number written on each square.

Prerequisites we lean on (and re-explain visually): Bellman-equations, Markov Decision Processes, and the Contraction-mapping-theorem. The parent is Dynamic Programming (Value/Policy Iteration).

Step 1 — What does a "value" even mean? Draw the walker

WHAT. Picture a $4 \times 4$ board. A tiny walker stands on a square. We label squares by (column, row) starting from the top-left: column runs $0, 1, 2, 3$ left-to-right, row runs $0, 1, 2, 3$ top-to-bottom. So the walker's home top-left corner is $(0, 0)$ and the goal bottom-right is $(3, 3)$ . Every square holds a single number I will call $V (s)$ — read it as "if I start here and play well forever, how much total reward do I collect?" The letter $s$ just means "which square" (the state).

WHY. Before any formula, we need one honest question: how good is it to be standing here? Everything else is machinery for filling in that number correctly. In our grid the only reward is $- 1$ for every step you take, and stepping onto the goal ends the game. So "good" means "close to the goal" — few steps left — and $V$ will end up being (roughly) minus the number of steps to the exit.

Edge case — walking into a wall. What if the walker tries to move off the board (e.g. "left" from column $0$ )? We use the standard rule: the move is blocked, the walker stays on the same square, and it still pays the $- 1$ step cost. So a wall-bump keeps you put but costs you — never a free move.

PICTURE. The board below with coordinates. The goal square $(3, 3)$ is special: standing on it, the game is already over, so its value is pinned at $0$ forever. Every other square starts life as a blank $0$ too — we simply don't know better yet.

Figure — Dynamic programming (value - policy iteration)

Step 2 — One move, taken apart: reward now + value of where you land

WHAT. Focus on a single square $s$ and a single action $a$ (say "move right"). Taking that action does exactly two things: it hands you an immediate reward $r$ , and it drops you on a new square $s^{'}$ whose value is $V (s^{'})$ . The worth of that one action is:

$paid right now r + patience dial γ value of where I land V (s^{'})$

WHY. This is the whole trick of dynamic programming: a long journey's value = this one step + the value of everything after this one step. We never sum an infinite future by hand; we borrow it from $V (s^{'})$ , which already stores it. This "borrow the rest from the neighbour" idea is the Bellman backbone.

WHY the $γ$ (and why not just add?). $γ$ (gamma) is the discount factor, a number with $0 \leq γ < 1$ ; here $γ = 0.9$ . It shrinks future rewards a little each step. We need it for two reasons: (1) rewards far away should matter slightly less, and (2) — the deep one — multiplying by a number smaller than $1$ is exactly what makes the whole update a contraction, guaranteeing it settles to one answer. Without $γ < 1$ the numbers could spiral forever.

PICTURE. One square, one arrow to its neighbour, the two pieces $r$ and $γ V (s^{'})$ labelled on the arrow.

Step 3 — Four actions, one winner: the $max$

WHAT. From square $s$ you don't have just one action — you have up, down, left, right. Each gives its own "reward now + discounted next value". We compute all four and keep the best one. Write the updated guess as $V_{new} (s)$ — the fresh number we are about to write into square $s$ , computed from the old numbers $V (s^{'})$ still on the board:

$V_{new} (s) \leftarrow max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V (s^{'})]$

Reading it left to right:

$V_{new} (s)$ ::: the brand-new value we compute for square $s$ this sweep; $V (s^{'})$ on the right is still the old value from the previous sweep.
$max_{a}$ ::: try every action $a$ , keep the largest result — "pick my best move."
$\sum_{s^{'}, r} p (s^{'}, r ∣ s, a)$ ::: average over where action $a$ might land me. $p (s^{'}, r ∣ s, a)$ is the MDP dynamics: the chance that action $a$ from $s$ gives reward $r$ and lands me on $s^{'}$ . In our deterministic grid this probability is just $1$ for the one square you actually move to (or the same square, if you bump a wall), $0$ elsewhere — so the sum collapses to a single term.
$[r + γ V (s^{'})]$ ::: the value of that landing, from Step 2.
$\leftarrow$ ::: overwrite the old guess with this fresh, better number.

WHY the $max$ and not an average? We are hunting for the optimal value $V^{*}$ — now we can define it: $V^{*} (s)$ is how good square $s$ is if you always play perfectly from here on. A perfect player never dilutes their best move with worse ones, so we take the maximum, not the policy-weighted average. (Averaging over a fixed policy would instead give $V^{π}$ , the value of that policy — that's policy evaluation, a different goal.) Repeating this $max$ -update is what drives $V$ toward $V^{*}$ .

PICTURE. The four candidate values fanning out from one square; the winning arrow glows, the losers fade.

Step 4 — Sweep 1: information leaks out of the goal

WHAT. Now apply the Step 3 rule to every square, once. This is one sweep. Start from the blank board where every $V = 0$ .

On sweep 1, only the squares touching the goal learn anything real. From the square just left of the goal, the "move right" action gives $r = - 1$ and lands on the goal whose value is $0$ : $V_{new} (next to goal) = max {\dots} = - 1 + 0.9 \cdot 0 = - 1.$ Every other square also updates to $- 1$ (each action costs $- 1$ , all neighbours still read $0$ ), so after sweep 1 the whole board is $- 1$ except the goal at $0$ .

WHY. Value has to propagate. On the first pass, no square except the goal's neighbours has any way to "see" that the goal exists — everyone's neighbours are still zeros. So the useful signal lives only one ring out from the goal. This is the maze-solved-backwards intuition made literal.

PICTURE. The board after sweep 1: a rim of $- 1$ around a $0$ goal.

Step 5 — Sweep 2 and beyond: the wave spreads

WHAT. Run the same rule again. Now a square two steps from the goal has a neighbour worth $- 1$ , so its best move gives $- 1 + 0.9 \cdot (- 1) = - 1.9.$ The information ripples one ring further outward each sweep. The far corner $(0, 0)$ is six steps from the goal, so its optimal value settles at roughly $- 4.7$ (the discounted cost of the six-step best path, $- 1 - 0.9 - 0. 9^{2} - \dots - 0. 9^{5} \approx - 4.69$ ), while any given sweep keeps nudging it toward that limit.

WHY. Each sweep lets value cross exactly one more square, like a wave. Because $γ = 0.9 < 1$ , each ring's number is a shrunken copy of the ring before it — the numbers stay finite and the whole map converges.

PICTURE. Three boards side by side: sweep 1, sweep 2, sweep 3 — watch the dark "far" values crawl inward.

Step 6 — Why it always stops: the contraction squeeze

WHAT. Define the error as the single biggest gap between our current guess $V$ and the true answer $V^{*}$ over all squares. This "worst gap over all states" is the sup-norm (also called the max-norm or infinity-norm), written $∥ V - V^{*} ∥_{\infty} = max_{s} ∣ V (s) - V^{*} (s) ∣$ . One sweep guarantees: $∥ V_{new} - V^{*} ∥_{\infty} \leq γ ∥ V - V^{*} ∥_{\infty} .$ Every sweep multiplies the worst gap by $γ = 0.9$ . Ten sweeps shrink it by $0. 9^{10} \approx 0.35$ ; a hundred sweeps by $0. 9^{100} \approx 2.66 \times 1 0^{- 5}$ .

WHY this exact bound? The $max$ and the sum can each only shrink or preserve differences, and then $γ$ multiplies everything by less than one. That is the definition of a contraction mapping, and such maps have exactly one fixed point — the true $V^{*}$ — that they always march toward. So value iteration cannot get stuck, oscillate, or find a wrong answer.

PICTURE. Error-versus-sweep: a curve diving toward zero, each step a factor $γ$ shorter than the last.

Step 7 — Reading the policy off the finished map

WHAT. Once $V$ stops changing, we have $V^{*}$ . To act optimally you never need to plan ahead again — at each square just step toward the highest-valued neighbour: $π^{*} (s) = ar g max_{a} \sum_{s^{'}, r} p (s^{'}, r ∣ s, a) [r + γ V^{*} (s^{'})] .$ Here $ar g max_{a}$ means "the action that achieves the max" — not the value itself, but which move won.

WHY. The value map is a hill sloping up toward the goal. The optimal policy is simply "always walk uphill." This is the free lunch of value iteration: solve for the numbers once, and the arrows fall out for every square at once. The same greedy read-off feeds model-free cousins like Q-learning and SARSA, and contrasts with policy-gradient methods which skip the value map entirely.

PICTURE. The converged value board with a red arrow on every square pointing to its best neighbour — a clean flow to the goal.

The one-picture summary

The whole story in one frame: blank board → the " $r + γ V (s^{'})$ " one-step rule → pick the best action with $max$ → sweep after sweep the value wave fills the board → error shrinks by $γ$ each time → read off the arrows.

Recall Feynman retelling — say it like a story

Imagine a flooded room where the water is the "goodness" spilling out from the exit. At first the whole floor is dry (all zeros) except the exit. Each tick of the clock, goodness seeps one tile further from the exit, but a little weaker each time it moves (that's the $\times 0.9$ ). Every tile keeps asking its neighbours, "which of you is the best to walk toward, counting the one step it costs me?" and copies that best neighbour's soaked-in value minus the step cost. Even bumping a wall costs a step and lands you back where you were, so wandering never pays. Because each hop weakens the number by a fixed fraction, the seeping settles into a stable map — a hill whose peak is the exit. To escape from anywhere, you don't think: you just walk uphill. That walk-uphill rule is the optimal policy, and the settled hill is $V^{*}$ .

Recall

What does the $max_{a}$ in value iteration accomplish? ::: It picks the best action at every square, which silently improves the policy on each sweep so we converge straight to the optimal value $V^{*}$ (not a fixed policy's $V^{π}$ ). Why does value iteration always converge? ::: Because the update is a contraction in the sup-norm with factor $γ < 1$ : each sweep multiplies the worst error by $γ$ , and a contraction has exactly one fixed point, $V^{*}$ . After convergence, how do you act? ::: Greedily — at each state take the action pointing to the highest-valued neighbour, $π^{*} (s) = ar g max_{a} \sum p [r + γ V^{*} (s^{'})]$ .