Worked examples — Dynamic programming (value - policy iteration)

You have seen the machinery of MDPs, the Bellman equations, and the two big algorithms (value iteration and policy iteration) in the parent note Dynamic Programming. This page does one thing: it runs the numbers, by hand, for every kind of situation the topic can throw at you.

We will not assume you remember any formula. Each example re-states the one line of maths it needs, in words, before touching a number.

---

The one equation everything uses

Before the matrix, let us pin the single computation that every example below performs. It is the Bellman backup — one update of a state's value. But first we must earn one symbol.

Two backups differ only in the last step:

Here ${\sum }_a$ ("sum over actions") means add up over every action, ${\sum }_{s^{\prime }}$ ("sum over next states") means add up over every possible landing spot weighted by its probability, ${\max }_a$ means take the largest over actions, and $\arg {\max }_a$ means return which action gave that largest value.

---

The scenario matrix

Every DP exercise is one of these cells. The examples that follow are labelled with the cell they cover, and together they hit all of them.

#	Case class	What makes it tricky	Example
A	Single deterministic backup	just plug in $r+\gamma V(s^{\prime })$	Ex 1
B	Terminal / degenerate state	$V=0$, backup must not loop	Ex 1, Ex 4
C	Stochastic transition	must average over $s^{\prime }$ with probabilities	Ex 2
D	Full policy evaluation to convergence	fixed point of a linear system	Ex 3
E	Value iteration, several sweeps	values propagate outward from goal	Ex 4
F	Policy improvement flips an action	greedy $\arg \max$ changes $\pi$	Ex 5
G	Limiting case $\gamma \to 0$ and $\gamma \to 1$	myopic vs. far-sighted	Ex 6
H	Real-world word problem	translate story → MDP → numbers	Ex 7
I	Exam twist: value iteration = policy iteration with 1 sweep	conceptual + numeric	Ex 8

The picture below makes Case C (the stochastic backup) concrete before any numbers appear: from state $s$ a single action can land you in two different next states, so the backup must average over them (the two cyan arrows, weighted by probability) before adding the discounted future. It is exactly the geometry Example 2 will compute. Look at the two cyan arrows leaving $s$ — those are the two random landing spots; the amber circles are the destinations you average over.

---

Example 1 — Cells A, B: one deterministic backup next to the goal

Steps.

1. Write the backup for this single action: $q(s,\text{right})=r+\gamma V(g)$. Why this step? This is the definition of the value of an action; since the move is deterministic the ${\sum }_{s^{\prime }}P(\cdot )$ collapses to one term, so nothing else applies when there is exactly one action and one destination.
2. Substitute the terminal value $V(g)=0$. Why this step? A terminal state ends the episode — there is no future reward to collect, so its value is exactly $0$. If we forgot this, the backup would try to look "past" the goal and loop forever (cell B trap).
3. Compute: $q=-1+0.9\times 0=-1$. Why this step? We simply substitute the numbers into the backup from step 1; the $\gamma V(g)$ term is $0.9\times 0=0$, so only the immediate reward survives.

Verify: Landing on the goal in one $-1$ step should cost exactly one step's reward — and $-1$ is exactly that. Units: reward, consistent. Since the future term vanished, $\gamma$ had no effect here, which is correct (the future is worth nothing when you stop).

---

Example 2 — Cell C: a stochastic move (average over next states)

Steps.

1. Because the outcome is random, we cannot use a single $s^{\prime }$. We must average the destination value weighted by its probability $P(s^{\prime }\mid s,\text{jump})$: $V_{\text{next}}=0.8\times 10+0.2\times (-5).$ Why this step? $P(s^{\prime }\mid s,a)$ is the environment's dice roll; the expected value of a random destination is the probability-weighted sum. This is the ${\sum }_{s^{\prime }}P(\cdot )$ in the Bellman equation made concrete.
2. Compute the average: $0.8\times 10=8$, $0.2\times (-5)=-1$, so $V_{\text{next}}=7$. Why this step? We evaluate each product and add them; this collapses the random destination into a single expected value we can feed to the backup.
3. Apply the backup: $q(s,\text{jump})=r+\gamma V_{\text{next}}=2+0.9\times 7=8.3$. Why this step? Same $r+\gamma V$ rule — the only change was building the expected next value first.

Verify: The answer $8.3$ sits above the reward-only-plus-worst-case floor ($2+0.9\times (-5)=-2.5$) and below the all-good-case ceiling ($2+0.9\times 10=11$), and leans toward $10$ because $0.8$ of the mass points there. Sanity check holds.

---

Example 3 — Cell D: full policy evaluation as a tiny linear system

Steps.

1. Write the Bellman expectation equation for each state. With a deterministic policy the ${\sum }_a\pi$ and the ${\sum }_{s^{\prime }}P(\cdot )$ each collapse to a single term: $V(A)=-1+0.9V(B),V(B)=-1+0.9V(A).$ Why this step? Policy evaluation is nothing but "each state's value equals its own backup." With two states you get two simultaneous equations.
2. By symmetry set $V(A)=V(B)=v$. Then $v=-1+0.9v$. Why this step? The setup is symmetric ($A$ and $B$ play identical roles), so their values must be equal — this shortcuts two equations into one.
3. Solve: $v-0.9v=-1\Rightarrow 0.1v=-1\Rightarrow v=-10$. Why this step? We collect the $v$ terms on one side and divide, the standard way to isolate the unknown in a linear equation.

Verify: Plug back: $-1+0.9\times (-10)=-1-9=-10$. ✓ It is the fixed point. The value is finite ($-10$) despite the infinite loop precisely because $\gamma =0.9<1$ makes the geometric series $-1(1+0.9+0.9^2+\cdots )=-1/(1-0.9)=-10$ converge. This is the contraction-mapping guarantee in action.

---

Example 4 — Cells B, E: value iteration, watch values propagate

Steps.

1. Initialise everything to $0$: $V(s_0)=V(s_1)=V(s_2)=0$, $V(G)=0$ fixed. Why this step? Value iteration starts from any guess; zeros are simplest, and $V(G)$ never changes because $G$ has no actions to back up through.
2. Sweep 1, using $V(s)\leftarrow {\max }_a[r+\gamma V(s^{\prime })]$ with $\gamma =1$ (every move is deterministic, so no ${\sum }_{s^{\prime }}$ needed):
   • $V(s_2)=\max \{\text{right}:-1+V(G)=-1,\text{left}:-1+V(s_1)=-1\}=-1$.
   • $V(s_1)=\max \{-1+V(s_2)=-1,-1+V(s_0)=-1\}=-1$.
   • $V(s_0)=\max \{\text{right}:-1+V(s_1)=-1,\text{left(bump)}:-1+V(s_0)=-1\}=-1$. Why this step? Each square keeps its best neighbour value. After one sweep only $s_2$ has real goal information; the others are still guessing $-1$.
3. Sweep 2 (now $V(s_2)=-1,V(s_1)=-1$ from sweep 1):
   • $V(s_2)=\max \{-1+0,-1+(-1)\}=-1$ (stable).
   • $V(s_1)=\max \{\text{right}:-1+(-1),\text{left}:-1+(-1)\}=-2$.
   • $V(s_0)=\max \{-1+V(s_1)=-1+(-1)=-2,-1+V(s_0)=-1+(-1)=-2\}=-2$. Why this step? The corrected value at $s_2$ from sweep 1 now flows one square left into $s_1$ and $s_0$.
4. Sweep 3 — re-back-up all three squares (we never skip states; a state is only "done" when its backup returns the same number):
   • $V(s_2)=\max \{\text{right}:-1+V(G)=-1,\text{left}:-1+V(s_1)=-1+(-2)=-3\}=-1$ (unchanged — already at its true value, so it stays put).
   • $V(s_1)=\max \{\text{right}:-1+V(s_2)=-1+(-1)=-2,\text{left}:-1+V(s_0)=-1+(-2)=-3\}=-2$ (unchanged — also settled).
   • $V(s_0)=\max \{\text{right}:-1+V(s_1)=-1+(-2)=-3,\text{left(bump)}:-1+V(s_0)=-1+(-2)=-3\}=-3$. Why this step? We do not update only $s_0$ by hand-waving; we re-run the backup for every state and observe that $s_1,s_2$ return the same values they already had (they have converged), while $s_0$ is the only one whose value still improves. Correct information marches one square left per sweep — so the farthest square $s_0$ is the last to settle.

Verify: The true cost from $s_0$ is 3 right-steps to $G$: $-1-1-1=-3$. Value iteration reached $V(s_0)=-3$. ✓ And notice it took 3 sweeps for the far square to learn — one per step of distance (cell E behaviour confirmed).

---

Example 5 — Cell F: policy improvement flips an action

Steps.

1. Policy improvement makes the policy greedy: ${\pi }^{\prime }(s)=\arg {\max }_{a}q(s,a)$. Why this step? The policy improvement theorem says switching to the best-looking action can only help (or leave you equal), never hurt.
2. Compare the two numbers: $-2.8$ (right) vs. $-8.2$ (up). The larger (closer to zero) is $-2.8$. Why this step? "Best" means highest value; among negative numbers the one nearest zero is the largest, so this comparison decides the $\arg \max$.
3. So ${\pi }^{\prime }(s)=\text{right}$ — the policy flips from "up" to "right". Why this step? The greedy rule returns whichever action won step 2, and here that action ("right") differs from the old choice ("up"), so the policy genuinely changes.

Verify: New value under the flip is at least the old: $V^{{\pi }^{\prime }}(s)\ge q(s,\text{right})=-2.8>-8.2=V^{\pi }(s)$. The value strictly increased, so this was a genuine improvement — exactly what the theorem promises. If instead both actions had tied, the policy would be left unchanged and we'd have hit optimality.

---

Example 6 — Cell G: the two limits of $\gamma$

Steps.

1. Case $\gamma =0$ (totally myopic): $q(\text{greedy})=5+0\times 0=5$; $q(\text{patient})=0+0\times 100=0$. Greedy wins. Why this step? $\gamma =0$ zeroes out all future terms, so the agent only sees the immediate reward. The future worth $100$ is invisible.
2. Case $\gamma =0.99$ (far-sighted): $q(\text{greedy})=5$; $q(\text{patient})=0+0.99\times 100=99$. Patient wins. Why this step? A near-$1$ discount barely shrinks the future, so the $100$ payoff dominates the small $+5$.
3. Find the tipping point. Set the two action-values equal and solve for $\gamma$: $5=\gamma \times 100\Rightarrow \gamma =0.05$. Why this step? The winner flips exactly where the two $q$-values cross; solving $q(\text{greedy})=q(\text{patient})$ locates that boundary so we know which $\gamma$ chooses which action, not just the two endpoints.

Verify: Below the tipping point patience is not yet worth it, above it patience wins. Check the endpoints against $\gamma =0.05$: at $\gamma =0$ ($<0.05$) the answer was greedy ✓; at $\gamma =0.99$ ($>0.05$) the answer was patient ✓. Both limits sit on the correct side of the boundary, so the tipping-point calculation is consistent. Intuition holds: $\gamma \to 0$ is "live for today", $\gamma \to 1$ is "plan for the long run". This same discount idea reappears in TD learning and Q-learning.

---

Example 7 — Cell H: a word problem (inventory)

Steps.

1. Translate the story into $r$ and $V(s^{\prime })$:
   • restock: $r=-3$, next-day value $V=+10$;
   • skip: $r=0$, next-day value $V=+1$. Why this step? Every word problem must first become numbers for the $r+\gamma V(s^{\prime })$ machine — "cost" is a negative reward, "goodwill/earnings" is the destination value.
2. Backup each: $q(\text{restock})=-3+0.8\times 10=5$; $q(\text{skip})=0+0.8\times 1=0.8$. Why this step? Standard optimality backup on the two actions.
3. Take the max: $5>0.8$, so restock. Why this step? Value iteration keeps the largest action-value, and $5$ beats $0.8$.

Verify: Restock nets $+5$ vs. skip's $+0.8$. The up-front $-3$ is more than repaid by the discounted future $0.8\times 10=8$: net $8-3=5$, which equals $q(\text{restock})$ ✓. Sensible: the discount didn't kill the future enough to make skipping worthwhile.

---

Example 8 — Cell I: value iteration = policy iteration with one evaluation sweep

Steps.

1. One value-iteration sweep (each state keeps its best action — here only one action exists per state): $V(A)\leftarrow -1+0.9\times 0=-1,V(B)\leftarrow -1+0.9\times 0=-1.$ Why this step? Value iteration does a single $\max$-backup per state per sweep — it does not wait for full convergence.
2. Now do the policy-iteration equivalent. Policy improvement: for each state the greedy $\arg \max$ has only one candidate action, so the policy stays "$A\to B$, $B\to A$" — unchanged. Why this step? With one action per state there is nothing to switch to; improvement is a no-op here, which isolates the evaluation part for comparison.
3. One-sweep policy evaluation of that policy, starting from $V=0$: $V(A)\leftarrow -1+0.9\times 0=-1,V(B)\leftarrow -1+0.9\times 0=-1.$ Why this step? A single evaluation sweep applies the same $r+\gamma V(s^{\prime })$ backup — and produces the identical numbers as step 1.
4. Conclusion: the two procedures gave the same $V=-1$ after one sweep. Value iteration is policy iteration whose evaluation is truncated to a single sweep. Keep iterating either one and you re-derive the fixed point $V=-10$ from Example 3. Why this step? Matching the numbers line-for-line is the whole point of the exam twist: the algorithms coincide when policy evaluation is cut to one step.

Verify: After 1 sweep both give $-1$ ✓ (not yet the fixed point $-10$, so it only approaches — forecast confirmed). Running value iteration to convergence returns $-10$, checked in Example 3. This truncation idea is what makes model-free methods like SARSA and policy gradients practical.

---

Recall Quick self-test

One deterministic step to a terminal goal, $r=-1$, $\gamma =0.9$: what is $q$? ::: $-1$ (future term vanishes since $V(\text{terminal})=0$). Ping-pong loop with $r=-1$ each step, $\gamma =0.9$: value of each state? ::: $-10$, from $v=-1+0.9v$. Slippery jump $0.8\to V=10$, $0.2\to V=-5$, $r=2$, $\gamma =0.9$: $q$? ::: $8.3$. How is value iteration related to policy iteration? ::: Policy iteration with policy evaluation truncated to one sweep. $\gamma \to 0$ makes the agent behave how? ::: Myopic — only immediate reward matters. When is $\gamma =1$ safe? ::: Only with an absorbing terminal state, so every path ends and totals stay finite.