Dynamic programming (value - policy iteration): Exercises

This page is a self-test ladder for Dynamic Programming. Every problem states its difficulty level (L1 Recognition → L5 Mastery). Try each one before opening its Solution callout. Every symbol you need is recalled inline right here, so you can work the whole page without leaving it; the Bellman-equations and Contraction-mapping-theorem pages carry the fuller proofs.

Definition The symbols this page uses (built once, used everywhere)

$π$ — a policy: a rule that, in each state $s$ , tells you which action to take (possibly randomly). $π (a ∣ s)$ is the probability it picks action $a$ in state $s$ .
$p (s^{'} ∣ s, a)$ — the transition model: the probability that taking action $a$ in state $s$ lands you in next state $s^{'}$ . "Deterministic" means one $s^{'}$ gets probability $1$ ; "stochastic" means the probability is split over several $s^{'}$ . $r (s, a)$ (or just $r$ ) is the immediate reward for that step.
$V^{π} (s)$ — state value under $π$ : expected total discounted reward if you start in $s$ and follow $π$ forever.
$Q^{π} (s, a)$ — action value under $π$ : expected total discounted reward if you start in $s$ , take action $a$ once, then follow $π$ . So $Q$ splits value by the first move; $V$ is the $π$ -weighted average of $Q$ over first moves.
$V^{*} (s) = max_{π} V^{π} (s)$ — optimal state value: the best any policy can achieve from $s$ . The star $*$ always means "under the best possible behaviour."
$Q^{*} (s, a) =$ reward for taking $a$ now $+ γ$ times $V^{*}$ of where you land — optimal action value. Optimality ties them: $V^{*} (s) = max_{a} Q^{*} (s, a)$ and the optimal policy picks $ar g max_{a} Q^{*} (s, a)$ .

Notation convention for this page: we always write the superscript. $V^{π}$ / $Q^{π}$ = "under this particular policy"; $V^{*}$ / $Q^{*}$ = "under the optimal policy." A bare $V (s)$ appears only as a running estimate mid-algorithm (a number in an array we keep updating that has not yet earned a $π$ or $*$ ). Whenever you see $max$ or $*$ , think "the agent is choosing, not averaging."

Before we start, one tiny toy world we reuse. It is the smallest MDP that still shows everything.

Figure — Dynamic programming (value - policy iteration)

Figure s01 — the 3-state chain. Three circles left to right: A (magenta, "start") → B (violet) → G (orange, "terminal", labelled V=0). Two navy arrows, each labelled r = −1, point A→B and B→G. It is a deterministic MDP with one forced action per non-terminal state and a per-step cost of 1.

Definition The "3-state chain" we use in several problems (read figure s01 above)

The figure shows three circles in a row — $A$ (magenta, "start"), $B$ (violet), $G$ (orange, "terminal") — joined by two navy arrows each labelled $r = - 1$ . That picture is the MDP:

$G$ is terminal (the goal): once there, the episode ends and its value is fixed at $V (G) = 0$ (shown under the orange circle). Since only one policy exists here, $V (G) = V^{π} (G) = V^{*} (G) = 0$ .
From $A$ the only action moves you to $B$ ; from $B$ the only action moves you to $G$ — exactly the two arrows drawn.
Every transition gives reward $r = - 1$ (a "cost of one step"), so the agent wants to reach $G$ fast.
Transitions are deterministic: $p (s^{'} ∣ s, a) = 1$ for the single next state. "Deterministic" = no dice; the action always does exactly what it says.

Because there is only one action per state, the policy is forced — so on this chain $V^{π}$ and $V^{*}$ coincide, and we may write $V$ for the running estimate. This lets us focus on the values first, then add choices later.

Level 1 — Recognition

Exercise 1.1 (L1)

State in words what $V^{π} (s)$ means, and what the discount factor $γ$ does. No formulas.

Recall Solution 1.1

$V^{π} (s)$ is the expected total future reward you will collect if you start in state $s$ and act forever according to policy $π$ . "Expected" = the average over all the random things that could happen.

$γ$ (gamma), a number with $0 \leq γ < 1$ , shrinks rewards that arrive later. A reward $r$ that is $k$ steps away counts as only $γ^{k} r$ . Picture each future step's reward passing through a "dimmer switch" that multiplies it by $γ$ once per step. This keeps the infinite sum finite and expresses "sooner is better."

Exercise 1.2 (L1)

Match each name to its one-line role: (a) policy evaluation, (b) policy improvement, (c) Bellman backup.

Recall Solution 1.2

(a) Policy evaluation — given a fixed policy $π$ , compute $V^{π}$ (how good is this behaviour?) by repeating the expectation backup $T^{π}$ .
(b) Policy improvement — given values $V$ , pick the greedy action in each state to build a better policy.
(c) Bellman backup — one update step ( $T^{π}$ or $T$ ) that replaces a state's value estimate with "immediate reward + discounted value of where you land."

Exercise 1.3 (L1)

In the Bellman optimality equation, which symbol turns "average over what the policy does" into "pick the best action"?

Recall Solution 1.3

The $max_{a}$ operator. The expectation backup $T^{π}$ weights actions by $π (a ∣ s)$ (an average); the optimality backup $T$ replaces that whole weighted sum by $max_{a}$ (choose the single best). That swap is the entire difference between "evaluate a policy" and "find the optimal one."

Level 2 — Application

Exercise 2.1 (L2)

On the 3-state chain with $r = - 1$ per step and $γ = 0.9$ , compute $V^{*} (G)$ , $V^{*} (B)$ , $V^{*} (A)$ by backward substitution. (On this forced-policy chain $V^{*} = V^{π}$ .)

Recall Solution 2.1

Terminal first: $V^{*} (G) = 0$ .

One step from goal — apply the (deterministic) backup $T [V] (s) = r + γ V (s^{'})$ : $V^{*} (B) = - 1 + 0.9 \cdot V^{*} (G) = - 1 + 0.9 (0) = - 1.$ Two steps from goal: $V^{*} (A) = - 1 + 0.9 \cdot V^{*} (B) = - 1 + 0.9 (- 1) = - 1.9.$ What it looks like — read figure s02 below. The two curved coloured arrows show value flowing backward from $G$ : the orange arrow carries $- 1 + 0.9 (0)$ into $B$ , then the violet arrow carries $- 1 + 0.9 (- 1)$ into $A$ . Each circle is labelled with its final value, and you can see value gets more negative the farther you sit from $G$ — the cost of the remaining steps, discounted.

Figure s02 — backward value propagation on the chain (γ = 0.9). The same three circles A, B, G now carry their converged values V = −1.9, V = −1, V = 0. Curved arrows point from G back to B (labelled −1+0.9(0)) and from B back to A (labelled −1+0.9(−1)), visualising how each backup pushes value one hop backward, discounted by γ.

Exercise 2.2 (L2)

Redo Exercise 2.1 with $γ = 0.5$ . Which state's value changes more, $A$ or $B$ ? Why?

Recall Solution 2.2

$V^{*} (B) = - 1 + 0.5 (0) = - 1, V^{*} (A) = - 1 + 0.5 (- 1) = - 1.5.$ $B$ is unchanged ( $- 1$ ) because it is one step from the terminal, so $γ$ only multiplies $V^{*} (G) = 0$ . $A$ changes from $- 1.9$ to $- 1.5$ : a smaller $γ$ discounts $B$ 's future cost more heavily, so far-away costs matter less. Rule of thumb: smaller $γ$ ⇒ values of distant states get pulled toward the immediate reward.

Exercise 2.3 (L2)

A single synchronous value-iteration sweep starts from the running estimate $V (s) = 0$ everywhere on the chain. Compute $V (A), V (B)$ after one sweep ( $γ = 0.9$ ). Have they converged? (Recall: a sweep applies the optimality backup $T$ to every state; synchronous means every backup reads the previous array of zeros.)

Recall Solution 2.3

With all values $0$ before the sweep, each backup uses the old zeros: $V (B) \leftarrow - 1 + 0.9 (0) = - 1, V (A) \leftarrow - 1 + 0.9 (0) = - 1.$ Both become $- 1$ . Not converged: the true $V^{*} (A) = - 1.9$ . One sweep only lets value travel one hop back from where it was known. It takes another sweep for $A$ to "hear about" $B$ 's updated $- 1$ .

Level 3 — Analysis

Exercise 3.1 (L3)

Now give state $A$ two actions: go (deterministic to $B$ , $r = - 1$ ) and stay (deterministic self-loop to $A$ , $r = - 1$ ). With $γ = 0.9$ and the correct values $V^{*} (B) = - 1$ , $V^{*} (G) = 0$ , is stay ever optimal? Compute $Q^{*} (A, go)$ and set up the equation for $Q^{*} (A, stay)$ .

Recall Solution 3.1

Recall from the symbol box that $Q^{*} (s, a)$ = "reward for $a$ now $+ γ V^{*}$ of where you land." For go you land on $B$ whose value is known: $Q^{*} (A, go) = - 1 + 0.9 \cdot V^{*} (B) = - 1 + 0.9 (- 1) = - 1.9.$ For stay, you land back on $A$ , so $Q^{*} (A, stay) = - 1 + 0.9 V^{*} (A)$ — and since $V^{*} (A) = max_{a} Q^{*} (A, a)$ , the unknown $V^{*} (A)$ appears on both sides: $V^{*} (A) = max {- 1.9, - 1 + 0.9 V^{*} (A)} .$ Suppose stay were optimal: then $V^{*} (A) = - 1 + 0.9 V^{*} (A) \Rightarrow 0.1 V^{*} (A) = - 1 \Rightarrow V^{*} (A) = - 10.$ Since $- 10 < - 1.9$ , stay gives a worse value than go. So $V^{*} (A) = - 1.9$ and stay is never optimal — looping just piles up $- 1$ costs forever.

Exercise 3.2 (L3)

The Policy Improvement Theorem says the greedy policy $π^{'}$ satisfies $V^{π^{'}} (s) \geq V^{π} (s)$ for all $s$ . Explain, using the chain, why greedy w.r.t. $V^{π}$ can only help, never hurt.

Recall Solution 3.2

Greedy picks, in each state, the action with the largest $Q^{π} (s, a)$ . By construction: $Q^{π} (s, π^{'} (s)) = max_{a} Q^{π} (s, a) \geq Q^{π} (s, π (s)) = V^{π} (s) .$ That inequality says: "acting greedily for one step, then reverting to $π$ , is at least as good as $π$ ." Chaining this across every state (each step you swap in the greedy choice and never lose value) gives $V^{π^{'}} \geq V^{π}$ everywhere. On the chain: if the random policy sometimes chose stay, greedy always chooses go, strictly raising $A$ 's value from a mixture toward $- 1.9$ . You cannot do worse than the max, and the max is what greedy takes.

Exercise 3.3 (L3)

Why does value iteration converge to a unique $V^{*}$ regardless of the initial $V$ ? Name the property and the role of $γ$ , and explain each step of the argument in words.

Recall Solution 3.3

The Bellman optimality operator $T$ (one full sweep of "reward + discounted best next value" over all states) is a $γ$ -contraction in max-norm (see Contraction-mapping-theorem): for any two value arrays $U, W$ , $∥ T [U] - T [W] ∥_{\infty} \leq γ ∥ U - W ∥_{\infty} .$ Reading each piece in plain words:

What $∥ U - W ∥_{\infty}$ is — the biggest disagreement between two value guesses across all states (the worst state). We track the worst case because if the worst shrinks, everything shrinks.
Why the update shrinks it — a backup replaces each value by $r + γ (next value)$ . The $r$ is identical for both guesses (same model), so it cancels; only the $γ \times (next value)$ part differs, and it carries a factor $γ < 1$ out front. So any gap the input had comes out multiplied by at most $γ$ . That single $γ$ is doing all the work.
Why uniqueness and convergence follow — start from any guess; each sweep multiplies the worst-case error by $\leq γ$ , so after $n$ sweeps the error is $\leq γ^{n} \times (start error)$ , which $\to 0$ because $γ < 1$ . Two different fixed points would have to sit zero distance apart (a contraction can't hold them apart), so there is exactly one $V^{*}$ (Banach fixed-point theorem).

What it looks like: no matter where you start, all initial guesses funnel to the same value, and the funnelling is geometrically fast (error killed by $γ$ each step). This is exactly why $γ < 1$ is not optional — it is the spring that pulls every guess to $V^{*}$ .

Level 4 — Synthesis

Exercise 4.1 (L4)

Run one full iteration of policy iteration on a 2-state MDP. States ${s_{0}, s_{1}}$ , $s_{1}$ terminal ( $V (s_{1}) = 0$ ). From $s_{0}$ : action L → $s_{0}$ (self-loop, $r = - 2$ ); action R → $s_{1}$ ( $r = - 3$ ). Start with policy $π (s_{0}) = L$ . Use $γ = 0.9$ . (a) Evaluate $V^{π}$ . (b) Improve. (c) Did the policy change?

Recall Solution 4.1

(a) Policy evaluation of $π = L$ (run $T^{π}$ to its fixed point). L self-loops, so $V^{π} (s_{0}) = - 2 + 0.9 V^{π} (s_{0}) \Rightarrow 0.1 V^{π} (s_{0}) = - 2 \Rightarrow V^{π} (s_{0}) = - 20.$ (b) Policy improvement. Compute both $Q^{π}$ values using $V^{π} (s_{0}) = - 20$ , $V (s_{1}) = 0$ : $Q^{π} (s_{0}, L) = - 2 + 0.9 (- 20) = - 20, Q^{π} (s_{0}, R) = - 3 + 0.9 (0) = - 3.$ Greedy picks the larger: $- 3 > - 20$ , so $π^{'} (s_{0}) = R$ . (c) Yes, the policy changed from L to R. Re-evaluating $π^{'} = R$ gives $V^{π^{'}} (s_{0}) = - 3$ — a huge jump up from $- 20$ . This is the policy-improvement theorem in action: escaping the costly loop.

Exercise 4.2 (L4)

For the same MDP, run synchronous value iteration from the running estimate $V (s_{0}) = 0$ . Show sweeps 1, 2 and 3, and give the converged $V^{*} (s_{0})$ . ( $V (s_{1}) = 0$ always, since $s_{1}$ is terminal.)

Recall Solution 4.2

Each sweep applies the optimality backup $T [V] (s_{0}) = max {- 2 + 0.9 V (s_{0}), - 3 + 0.9 V (s_{1})}$ reading the previous array. Sweep 1 (old $V (s_{0}) = 0$ ): $V (s_{0}) \leftarrow max {- 2 + 0.9 (0), - 3 + 0.9 (0)} = max {- 2, - 3} = - 2.$ Sweep 2 (old $V (s_{0}) = - 2$ ): $V (s_{0}) \leftarrow max {- 2 + 0.9 (- 2), - 3 + 0.9 (0)} = max {- 3.8, - 3} = - 3.$ Sweep 3 (old $V (s_{0}) = - 3$ ): $V (s_{0}) \leftarrow max {- 2 + 0.9 (- 3), - 3 + 0.9 (0)} = max {- 4.7, - 3} = - 3.$ The value is stable at $- 3$ (sweep 3 reproduces sweep 2's output), so we stop. Converged $V^{*} (s_{0}) = - 3$ , matching policy iteration's answer in 4.1 — as it must, since both solve the same Bellman optimality equation. The greedy action extracted from this $V^{*}$ is R.

Level 5 — Mastery

Exercise 5.1 (L5)

Stochastic action. State $s_{0}$ has one action try that with probability $0.8$ reaches terminal $s_{1}$ ( $r = + 10$ ) and with probability $0.2$ stays at $s_{0}$ ( $r = - 1$ ). $γ = 0.9$ , $V (s_{1}) = 0$ . Find $V^{π} (s_{0})$ by solving the fixed-point equation. (Here the $\sum_{s^{'}} p (s^{'} ∣ s, a) [\dots]$ from the backup has two terms.)

Recall Solution 5.1

The expectation backup with a stochastic outcome averages over both branches (the $\sum_{s^{'}} p (s^{'} ∣ s_{0}, try)$ ): $V^{π} (s_{0}) = 0.8 [10 + 0.9 \cdot 0] + 0.2 [- 1 + 0.9 V^{π} (s_{0})] .$ Expand: $V^{π} (s_{0}) = 8 + 0.2 (- 1) + 0.2 (0.9) V^{π} (s_{0}) = 7.8 + 0.18 V^{π} (s_{0}) .$ Solve: $V^{π} (s_{0}) - 0.18 V^{π} (s_{0}) = 7.8 \Rightarrow 0.82 V^{π} (s_{0}) = 7.8 \Rightarrow V^{π} (s_{0}) = \frac{7.8}{0.82} \approx 9.5122.$ What it looks like: the value sits just below the "lucky" branch's $+ 10$ , dragged down by the $20%$ chance of a $- 1$ stall that also delays the payoff.

Exercise 5.2 (L5)

Truncated evaluation trade-off. Explain precisely why value iteration equals policy iteration with policy-evaluation truncated to a single sweep, giving the intuitive "why" behind the fused-update identity. Then give one situation where full evaluation (policy iteration) wins and one where truncation (value iteration) wins.

Recall Solution 5.2

Why identical structure (step by step). Policy iteration alternates two phases: (i) many evaluation sweeps of the expectation backup $T^{π} [V] (s) = \sum_{a} π (a ∣ s) \sum_{s^{'}} p (s^{'} ∣ s, a) [r + γ V (s^{'})]$ until $V^{π}$ settles, then (ii) a greedy improvement $π (s) \leftarrow ar g max_{a} Q (s, a)$ .

Step 1 — truncate evaluation to one sweep. Instead of running phase (i) to convergence, do a single backup and move on. The values are now only roughly right, but they are directional — good enough to pick a better action.
Step 2 — see that "one greedy sweep of evaluation" already contains the improvement. If, in that single sweep, you evaluate under the greedy policy, then choosing $π (s) = ar g max_{a} Q (s, a)$ and immediately plugging it in makes the sweep read $V (s) \leftarrow max_{a} [r + γ \sum_{s^{'}} p (s^{'} ∣ s, a) V (s^{'})]$ . The $ar g max$ (improvement) and the $\sum$ (evaluation) have fused into a single $max$ — that fused line is the optimality backup $T$ , i.e. the value-iteration update.
Why this is legal: picking the greedy action and then evaluating that one action is the same arithmetic as taking the $max$ directly, because "evaluate the best action" and "take the maximum action value" are literally the same number. So value iteration = policy iteration whose evaluation phase is cut to a single greedy sweep. Nothing is lost in correctness (both converge to the same $V^{*}$ ); only the bookkeeping of an explicit policy is dropped.

Full evaluation wins when the environment has long chains where value must propagate far and the same policy stays greedy across many states (e.g. our long corridor): converging $V^{π}$ fully means each improvement is a big, well-informed jump, so total outer iterations are few.

Truncation wins when the greedy policy changes frequently as values shift: spending many sweeps to perfectly evaluate a policy you are about to discard is wasted work. Value iteration improves the policy implicitly every sweep, avoiding that waste. This same "don't fully evaluate before improving" idea seeds TD learning, 5.1.11-Q-learning, and 5.1.12-SARSA.

Exercise 5.3 (L5)

Edge cases in $γ$ . Discuss what happens to the DP methods as (a) $γ \to 0$ and (b) $γ \to 1$ , and (c) whether $γ = 1$ is ever allowed in the infinite-horizon setting.

Recall Solution 5.3

(a) $γ \to 0$ (myopic agent). The backup collapses to $V (s) \leftarrow max_{a} r (s, a)$ — only the immediate reward survives, all future terms are multiplied by (nearly) zero. The agent becomes greedy-for-now, blind to consequences. Convergence is instant (the contraction factor is $\approx 0$ , so one sweep essentially finishes), but the resulting policy can be terrible on tasks needing foresight. On our chain, $γ = 0$ makes every non-terminal value exactly $- 1$ ; the agent cannot "see" the goal beyond one step.

(b) $γ \to 1$ (far-sighted agent). The future is barely discounted, so distant rewards matter almost as much as near ones — good for long-horizon planning. But the contraction factor $γ$ approaches $1$ , so each sweep shrinks the error only slightly ( $γ^{n} \to 0$ very slowly). Practically: convergence gets dramatically slower as $γ \to 1$ , and value magnitudes blow up (on the chain, $V^{*} (A) = - 1 - γ \to - 2$ ; on a long corridor of length $L$ , values scale like $- \frac{1 - γ ^{L}}{1 - γ}$ , which grows without bound as $γ \to 1$ ).

(c) Is $γ = 1$ allowed? In the infinite-horizon setting, $γ = 1$ is generally not allowed unless the problem is guaranteed to terminate. Reason: with $γ = 1$ the return $R_{t + 1} + R_{t + 2} + \dots$ can be an infinite sum that does not settle to a finite number (e.g. a self-loop with $r = - 1$ gives $- 1 - 1 - 1 - \dots = - \infty$ ), and the operator is no longer a contraction ( $γ = 1$ removes the shrinking factor), so the fixed-point/uniqueness guarantee of Contraction-mapping-theorem fails. $γ = 1$ is safe for episodic tasks with a reachable terminal state (a "proper" policy), where every trajectory ends and the sum is finite — that is the undiscounted episodic case, common in shortest-path grid worlds.

Recall Quick self-check ledger (answers)

$V^{*} (A)$ chain, $γ = 0.9$ ::: $- 1.9$ $V^{*} (A)$ chain, $γ = 0.5$ ::: $- 1.5$ $V (A)$ after one synchronous VI sweep ::: $- 1$ $V^{*} (s_{0})$ in the loop-vs-exit MDP ::: $- 3$ Loop-forever value $V = - 1 + 0.9 V$ ::: $- 10$ Stochastic $V^{π} (s_{0})$ in 5.1 ::: $\approx 9.5122$

Exercises — Dynamic programming (value - policy iteration)