Solving MDPs · Machine Learning

01 · Motivation

Why does this matter?

Chapter 8 introduced the language of Markov decision processes: states, actions, transitions, rewards, the Bellman equations that relate the value of a state to the values of its successors. We have the definition of what an optimal policy is. We do not yet have a way to actually find one. That is the missing piece, and it is what this chapter fills in.

Before we build any algorithm, let’s pin down what “solving an MDP” actually means. It is the conjunction of two outputs:

Optimal value function $V^*$: a vector in $\mathbb{R}^{|S|}$ telling us, for each state, the best possible expected discounted return achievable from that state.
Optimal policy $\pi^*$: a rule $\pi^* : S \to A$ that achieves $V^*$ — that is, $V^{\pi^*}(s) = V^*(s)$ for every $s$ .

These two outputs are tightly coupled: once you have $V^*$ , the optimal policy is just “act greedily with respect to $V^*$ ”; once you have $\pi^*$ , the optimal value function is just “evaluate $\pi^*$ ”. The three algorithms in this chapter differ only in which of these two objects they compute first.

The naive approach is straightforward and catastrophic. Enumerate every deterministic Markov policy $\pi : S \to A$ , evaluate each one, keep the best. The number of such policies is $|A|^{|S|}$ : with just 20 states and 4 actions, that’s $4^{20} \approx 10^{12}$ policies. With 100 states the universe ends before we finish counting. We need a fundamentally smarter method.

Plans share structure

The value of being in state $s$ is determined by the values of the states you reach in one step. If we already know $V(s')$ for every successor $s'$ , computing $V(s)$ takes one Bellman backup. Subproblems overlap massively.

The Bellman equations are recursive

Recursion + caching = dynamic programming. The Bellman expectation and optimality equations are textbook examples of “the principle of optimality applies.”

A model unlocks planning

When $P$ and $R$ are known, we don’t need experience — we can plan. The agent computes the optimal policy offline, then executes it. This is the foundation that model-free RL (Ch. 10) tries to imitate without a model.

why

The conceptual shift

Chapter 8 was a language: how to write down a sequential decision problem. Chapter 9 is a workshop: three different machines that take that description and return an optimal policy. All three are mathematically equivalent — they compute the same fixed point — but each exposes a different facet of the structure, and each pays a different computational price.

recall

Quick recap from Chapter 8 — V and Q

The state-value $V^\pi(s)$ is the expected discounted return starting from $s$ and following $\pi$ thereafter. The action-value $Q^\pi(s, a)$ starts from $s$ , takes action $a$ right now, and follows $\pi$ only from the next step. They are linked by

Q^\pi(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s'), \qquad V^\pi(s) = \sum_a \pi(a \mid s)\, Q^\pi(s, a).

Their starred versions $V^*$ and $Q^*$ replace the policy-weighted sum with a maximum. The Q-form is the natural object for comparing actions — we reach for it whenever we improve a policy.

This chapter assumes full knowledge of the MDP — every $P(s' \mid s, a)$ and every $R(s, a)$ is given. That assumption is what distinguishes planning (this chapter) from reinforcement learning (next chapter). When the model is unknown, we’ll estimate values from sampled experience — but the algorithms there are direct relatives of the ones we build here.

02 · Intuition

The idea in plain language

Forget the algebra for a moment. Imagine you stand at the entrance of a maze with a one-step lookahead. You want to know “how good is each cell” — if I follow the best plan from here, how much reward will I collect? The trick that makes the whole chapter tick: the value of a cell is the immediate reward for moving, plus a discounted copy of the value of wherever you land. The far future is already baked into the values of your neighbours. If you knew your neighbours’ values, computing your own is one arithmetic operation. We never enumerate plans.

Reward information flowing backward through states

Imagine the rewards as drops of dye placed at certain transitions. A Bellman backup at state $s$ inspects the dye at the immediately reachable transitions and stains $s$ a little. After two backups, dye from two steps away has reached $s$ ; after $k$ backups, dye from $k$ steps away has soaked in. In the limit, every state knows about every reachable reward — discounted by distance. Both value iteration and the inner loop of policy iteration are doing exactly this: pumping reward information backward through the transition graph, one hop per sweep. With $\gamma < 1$ , far-away rewards fade as they propagate, so finitely many sweeps suffice to any chosen accuracy.

Two nested loops, two ways to break the recursion

The Bellman equations talk about a value function that satisfies itself. There are two ways to handle the circular reference, and they give us the two main algorithms.

Policy iteration

Lock the policy. Solve the (now-linear) Bellman equations exactly for it — policy evaluation. Then update the policy by acting greedily with respect to those values — policy improvement. Repeat until the policy stops changing. Few iterations, each one a linear solve.

Value iteration

Don’t bother with explicit policies. Treat the Bellman optimality equation as an update rule: plug any current estimate into the right-hand side, get a better one, repeat. The values converge to $V^*$ ; read off the greedy policy at the end. Many iterations, each one cheap.

And as a third voice, linear programming. The Bellman optimality equation with its $\max$ can be linearised by replacing the $\max$ with one inequality per action. The result is a textbook LP — solve once, get $V^*$ directly. Different machinery, same answer.

Why greedy improvement cannot hurt

Here is the load-bearing intuition for policy iteration. Suppose you’ve evaluated $\pi$ and know $V^\pi$ and $Q^\pi$ . In some state $s$ there is an action $a' \neq \pi(s)$ with $Q^\pi(s, a') > V^\pi(s)$ . Modify $\pi$ to take $a'$ at $s$ but keep it identical everywhere else. Two things happen: at $s$ you now collect strictly more expected return (by definition of $Q^\pi$ ); and after that single deviation you revert to $\pi$ , so the tail of the trajectory is unchanged in distribution. The new policy is at least as good at $s$ and identical elsewhere — so it is globally at least as good. One greedy step is never a step backwards.

key

The chapter in one sentence

Plug the Bellman equations into themselves until they stop changing. Policy iteration alternates “solve the linear Bellman expectation for a fixed policy” and “be greedy.” Value iteration iterates the non-linear Bellman optimality directly. LP solves the optimality equation as a set of inequalities. All three machines drive the same fixed point, $V^*$ , into existence.

A value function silently contains a policy

Once you have any value function $V$ — optimal or not — there is automatically a corresponding greedy policy: the one that, at each state, picks the action with the highest one-step lookahead value,

\pi_V(s) = \arg\max_a \Bigl[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V(s') \Bigr].

This is why value iteration doesn’t track policies during the loop. Every $V_k$ silently induces $\pi_{V_k}$ ; at convergence $\pi_{V^*} = \pi^*$ . Policy iteration just makes this greedy extraction explicit at every step, which lets it terminate exactly rather than asymptotically. Two sides of one coin.

Why iterating converges at all

Why doesn’t the loop oscillate forever or diverge? Because the Bellman optimality operator is a contraction: applying it to two different value estimates always brings them closer together by a factor of at least $\gamma < 1$ . Any two starting points converge to the same fixed point, geometrically fast. The reason is the discount factor — it scales down all disagreements between iterations. Discounting is what makes infinite-horizon dynamic programming possible at all; without it, the future could swamp the present and iterates would never settle.

03 · Formalism

Definitions and equations

We assume the setting of Chapter 8: a discounted infinite-horizon MDP $\langle S, A, P, R, \gamma, \mu \rangle$ with finite $S$ and $A$ , $\gamma \in [0, 1)$ .

The Bellman operators (recap from Ch. 8)

For a fixed policy $\pi$ , the Bellman expectation operator $T^\pi$ acts on a value function $V : S \to \mathbb{R}$ by

Bellman expectation

(T^\pi V)(s) = \sum_{a} \pi(a \mid s) \Bigl[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V(s') \Bigr].

In matrix form, with $P^\pi \in \mathbb{R}^{|S| \times |S|}$ and $R^\pi \in \mathbb{R}^{|S|}$ , this is simply $T^\pi V = R^\pi + \gamma P^\pi V$ . Linear in $V$ .

The Bellman optimality operator $T^*$ replaces the policy-weighted sum with a maximum:

Bellman optimality

(T^* V)(s) = \max_{a \in A} \Bigl[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V(s') \Bigr].

Non-linear in $V$ because of the $\max$ . Still a contraction in $\|\cdot\|_\infty$ .

Fixed points: $V^\pi$ is the unique fixed point of $T^\pi$ ; $V^*$ is the unique fixed point of $T^*$ .
Contraction: for any $V, U$ : $\|T^\pi V - T^\pi U\|_\infty \le \gamma\, \|V - U\|_\infty$ , and the same for $T^*$ .
Monotonicity: if $V \le U$ componentwise, then $T^* V \le T^* U$ .

Deep dive

Before the infinite-horizon machinery, the cleanest possible DP. If the agent acts for exactly $N$ steps, the optimal value is computed by backward recursion:

V^*_k(s) = \max_{a \in A_k} \Bigl[ R_k(s, a) + \sum_{s'} P_k(s' \mid s, a)\, V^*_{k+1}(s') \Bigr], \quad k = N-1, \ldots, 0,

with terminal condition $V^*_N(s) = 0$ . The optimal action at stage $k$ is the argmax of the same bracket. Total cost $O(N |S|^2 |A|)$ — versus $|A|^{N|S|}$ for brute force. The infinite-horizon discounted case is the limit $N \to \infty$ : the recursion no longer terminates, so we replace “step backward from the horizon” with “iterate the Bellman operator to its fixed point.”

Iterative policy evaluation

For a fixed policy $\pi$ , $V^\pi$ satisfies the linear system $V^\pi = R^\pi + \gamma P^\pi V^\pi$ . Two ways to compute it:

Direct solve

V^\pi = (I - \gamma P^\pi)^{-1}\, R^\pi.

Cost $O(|S|^3)$ . Always invertible because $\gamma < 1$ makes $I - \gamma P^\pi$ strictly diagonally dominant.

Iterative evaluation

V_{k+1}(s) \leftarrow \sum_a \pi(a \mid s) \Bigl[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V_k(s') \Bigr].

Policy improvement

Given any value function $V$ , the greedy policy with respect to $V$ is

Greedy policy

\pi'(s) \in \arg\max_{a \in A} \Bigl[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V(s') \Bigr].

Ties broken arbitrarily. If $V = V^\pi$ , this is the action that maximises $Q^\pi(s, a)$ .

thm

Policy improvement theorem

Let $\pi, \pi'$ be deterministic policies. If $Q^\pi(s, \pi'(s)) \ge V^\pi(s)$ for every $s \in S$ , then $V^{\pi'}(s) \ge V^\pi(s)$ for every $s \in S$ .

In particular, the greedy policy with respect to $V^\pi$ is at least as good as $\pi$ . If equality holds everywhere, $\pi$ is already optimal. (Proof in the exam-intel section — the unrolling argument is short and worth memorising.)

Policy iteration

Putting the pieces together:

Policy iteration

\pi_0 \xrightarrow{\text{eval}} V^{\pi_0} \xrightarrow{\text{greedy}} \pi_1 \xrightarrow{\text{eval}} V^{\pi_1} \xrightarrow{\text{greedy}} \pi_2 \to \cdots \to \pi^* \to V^*.

Two phases per iteration: policy evaluation (solve the linear system) and policy improvement (act greedily). Terminates exactly when the policy stops changing.

Because there are only finitely many deterministic policies and each iteration strictly improves the policy (or terminates), PI converges in a finite number of steps.

Value iteration

Iterate the Bellman optimality operator directly:

Value iteration

V_{k+1}(s) \leftarrow \max_{a \in A} \Bigl[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V_k(s') \Bigr].

No explicit policy. After convergence, extract $\pi^*$ as the greedy policy of $V^*$ .

An equivalent formulation works directly with Q-values:

Q-value iteration

Q_{k+1}(s, a) \leftarrow R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, \max_{a'} Q_k(s', a').

Reads off the optimal policy with no separate greedy step: $\pi^*(s) = \arg\max_a Q^*(s, a)$ . Memory is $|S|\cdot|A|$ instead of $|S|$ , but no model query at extraction time — exactly why model-free RL (Ch. 10) prefers Q-values.

thm

Value iteration converges

For any initial $V_0$ , the sequence $V_k = T^* V_{k-1}$ converges to $V^*$ in $\|\cdot\|_\infty$ , with $\|V_k - V^*\|_\infty \le \gamma^k \|V_0 - V^*\|_\infty$ .

stop

A practical stopping rule

If $\|V_{k+1} - V_k\|_\infty < \varepsilon$ , then

\|V_{k+1} - V^*\|_\infty \le \frac{\gamma\,\varepsilon}{1 - \gamma}.

A looser but commonly cited form replaces $\gamma$ with $2\gamma$ in the numerator. We can only measure successive-iterate differences, never the gap to $V^*$ directly — this inequality converts the measurable signal into a certificate.

Linear programming — primal

The fixed-point condition $V \ge T^* V$ (componentwise) characterises supersolutions of the Bellman equation. $V^*$ is the smallest supersolution — which is exactly an LP:

Primal LP

\begin{aligned} \min_{V \in \mathbb{R}^{|S|}} \quad & \sum_{s} \mu(s)\, V(s) \\ \text{s.t.} \quad & V(s) \ge R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V(s'),\quad \forall s,\;\forall a. \end{aligned}

$|S|$ variables, $|S|\cdot|A|$ constraints. The weights $\mu(s) > 0$ (often the initial-state distribution) make the objective strictly proper without changing the optimum.

The constraints encode ” $V$ lies above the Bellman backup.” Among all such $V$ , the LP picks the one with smallest weighted sum — and that point is exactly $V^*$ .

Linear programming — dual

The dual introduces variables $\lambda(s, a) \ge 0$ , one per state-action pair:

Dual LP

\begin{aligned} \max_{\lambda \ge 0} \quad & \sum_{s, a} \lambda(s, a)\, R(s, a) \\ \text{s.t.} \quad & \sum_{a'} \lambda(s', a') = \mu(s') + \gamma \sum_{s, a} \lambda(s, a)\, P(s' \mid s, a),\quad \forall s'. \end{aligned}

$|S|\cdot|A|$ variables, $|S|$ equality constraints. The dual variables admit a beautiful interpretation.

The dual variables $\lambda(s, a)$ are the discounted state-action occupancy measures under a policy $\pi$ : how often, in present value, the agent visits $(s, a)$ when starting from $\mu$ and following $\pi$ ,

\lambda(s, a) = \sum_{t = 0}^{\infty} \gamma^t \, \Pr(s_t = s, a_t = a \mid s_0 \sim \mu, \pi).

The equality constraints are the discounted Chapman–Kolmogorov flow equations: occupancy in $s'$ comes from initial probability $\mu(s')$ plus discounted transitions into $s'$ . Maximising $\sum \lambda R$ over flows gives the best long-run reward, and the optimal policy is read off as $\pi^*(s) = \arg\max_{a} \lambda^*(s, a)$ .

Three machines, one fixed point

Policy Iteration

Alternate exact evaluation and greedy improvement. Few iterations, each expensive (a linear system). Terminates exactly in finitely many steps. Cost: eval $O(|S|^3)$ + improve $O(|S|^2|A|)$ .

Value Iteration

Iterate Bellman optimality. Many iterations, each cheap. Geometric convergence at rate $\gamma$ . Stop when iterates differ by less than $\varepsilon(1-\gamma)/(2\gamma)$ . Cost: $O(|S|^2|A|)$ per sweep.

Linear Programming

One LP, polynomial-time solver. Strong worst-case bounds; impractical at large state-action counts due to constraint blow-up. The dual exposes occupancy measures. Cost: $\mathrm{poly}(|S|, |A|)$ .

04 · Worked example

Three states, two actions, by hand

We solve a tiny MDP three different ways — policy iteration, value iteration, and the LP — and watch the same answer drop out.

setup

Why this example is instructive

Three things to watch. One: the “obvious greedy” plan (grab the $+10$ from $s_2$ immediately) turns out suboptimal — the discounted infinite loop beats it. That kind of finding requires a solver. Two: the three algorithms reach the same answer through visibly different paths. Three: the LP’s constraints “select” the optimal action at each state by going tight.

Worked example Solving the 3-state MDP three ways

1 · The MDP

Three states $S = \{s_1, s_2, s_3\}$ , where $s_3$ is an absorbing terminal with zero reward. Two actions $A = \{a, b\}$ in $s_1$ and $s_2$ . Discount $\gamma = 0.9$ . Transitions deterministic; rewards on transition.

State	Action	Next state	Reward
$s_1$	$a$	$s_2$	$+5$
$s_1$	$b$	$s_3$	$+1$
$s_2$	$a$	$s_1$	$0$
$s_2$	$b$	$s_3$	$+10$
$s_3$	·	$s_3$	$0$

Intuition first: the big prize is the $+10$ at $s_2 \to s_3$ . We should reach $s_2$ from $s_1$ (action $a$ , reward 5), then cash out (action $b$ , reward 10). Let’s confirm by algorithm.

2 · Policy iteration — from a bad guess

Start with $\pi_0$ that always picks $b$ : $\pi_0(s_1) = b$ , $\pi_0(s_2) = b$ . Evaluate: both states go straight to $s_3$ , so $V^{\pi_0}(s_1) = 1$ , $V^{\pi_0}(s_2) = 10$ . Improve greedily:

Q(s_1, a) = 5 + 0.9 \cdot 10 = 14 > Q(s_1, b) = 1, \qquad Q(s_2, a) = 0.9 \cdot 1 = 0.9 < Q(s_2, b) = 10.

So $\pi_1(s_1) = a$ , $\pi_1(s_2) = b$ — the policy changed at $s_1$ . Continue.

3 · Policy iteration — the surprise, then convergence

Evaluate $\pi_1$ : $V^{\pi_1}(s_2) = 10$ , $V^{\pi_1}(s_1) = 5 + 0.9 \cdot 10 = 14$ . Improve:

Q^{\pi_1}(s_2, a) = 0.9 \cdot 14 = 12.6 > Q^{\pi_1}(s_2, b) = 10.

At $s_2$ , action $a$ now beats $b$ ! Update to $\pi_2(s_1) = a$ , $\pi_2(s_2) = a$ . Evaluate $\pi_2$ : now both states cycle, $s_1 \xrightarrow{a,+5} s_2 \xrightarrow{a,0} s_1$ :

V(s_1) = 5 + 0.9\, V(s_2), \quad V(s_2) = 0.9\, V(s_1) \;\Rightarrow\; V(s_1) = \tfrac{5}{1 - 0.81} \approx 26.32,\; V(s_2) \approx 23.68.

Improve once more: $Q(s_1, a) \approx 26.32 > 1$ and $Q(s_2, a) \approx 23.68 > 10$ . Policy unchanged. Stop. $\pi^* = (a, a)$ , $V^* \approx (26.32,\, 23.68,\, 0)$ .

The optimal policy says: stay in the loop forever, collecting $+5$ every two steps. Our naive intuition was wrong — discounting doesn’t kill the loop because $5/(1 - 0.81) \approx 26 > 10$ .

4 · Value iteration

Initialise $V_0 = 0$ and sweep the optimality operator. At $k = 1$ , $V_1(s_1) = \max(5 + 0,\, 1 + 0) = 5$ and $V_1(s_2) = \max(0,\, 10) = 10$ . The values march toward $V^*$ at rate $\gamma = 0.9$ :

$k$	$V(s_1)$	$V(s_2)$	$\lVert V_k - V_{k-1}\rVert_\infty$
0	0.00	0.00	—
1	5.00	10.00	10.00
2	14.00	10.00	9.00
3	14.00	12.60	2.60
5	16.34	14.71	2.11
10	22.08	19.87	—
50	26.31	23.68	—
$\infty$	26.32	23.68	—

Once stable, the greedy policy is $\pi^*(s_1) = a$ (since $5 + 0.9 \cdot 23.68 > 1$ ) and $\pi^*(s_2) = a$ (since $0.9 \cdot 26.32 > 10$ ). Same answer as PI.

5 · The LP view

Set $\mu = (1/3, 1/3, 1/3)$ . The primal LP is

\min_{V_1, V_2, V_3}\; \tfrac{1}{3}(V_1 + V_2 + V_3) \quad \text{s.t.}\quad \begin{cases} V_1 \ge 5 + 0.9\, V_2, \\ V_1 \ge 1 + 0.9\, V_3, \\ V_2 \ge 0 + 0.9\, V_1, \\ V_2 \ge 10 + 0.9\, V_3, \\ V_3 \ge 0. \end{cases}

At the optimum, exactly one constraint per state is tight — the optimal action. The tight set $V_1 = 5 + 0.9 V_2$ , $V_2 = 0.9 V_1$ , $V_3 = 0$ is the same linear system we solved in step 3: $V^* = (26.32,\, 23.68,\, 0)$ . The slack on the two non-tight constraints (action $b$ at $s_1$ and $s_2$ ) certifies those actions are suboptimal.

map

Three lenses, one fixed point

PI: 3 iterations until the policy stops changing; each solved a 2×2 linear system exactly.
VI: dozens of one-step max-backups; geometrically convergent.
LP: a single 3-variable, 5-constraint program, solved by simplex in a constant number of pivots.

All three return $V^*(s_1) \approx 26.32$ , $V^*(s_2) \approx 23.68$ , $V^*(s_3) = 0$ , with optimal action $a$ at both non-terminal states.

05 · Visual explanation

The geometry of dynamic programming

The Bellman backup as a tree

Every Bellman update is a one-step game tree: from a state, branch on actions; from each action, branch on possible next states (weighted by $P$ ); collect reward; bring back the discounted value of the leaf. $T^\pi$ averages over actions using $\pi$ ; $T^*$ takes the max.

The shape is identical. The only difference is the action node: expectation averages with $\pi(a \mid s)$ ; optimality takes a $\max$ . That one symbol — sum vs max — is the entire algorithmic gap between evaluating a policy and finding the best one.

Why the iteration converges

Picture the space of value functions as $\mathbb{R}^{|S|}$ . The operator $T^*$ maps this space to itself, and applying it to any two value functions brings them at least a factor $\gamma$ closer in max-norm. After $k$ sweeps the disagreement with $V^*$ has radius $\gamma^k \|V_0 - V^*\|_\infty$ . For $\gamma = 0.9$ the error halves every $\approx 7$ sweeps; for $\gamma = 0.99$ , every $\approx 69$ . Convergence is geometric but slows as $\gamma \to 1$ — you can watch this directly in the contraction widget below.

Generalized Policy Iteration — the unifying picture

Every algorithm in this chapter is an instance of one master pattern. Two arrows are in tension: one pulls $V$ toward $V^\pi$ (evaluation makes the value consistent with the policy); the other pulls $\pi$ toward $\text{greedy}(V)$ (improvement makes the policy consistent with the value). Both arrows are zero at exactly one point: $(V^*, \pi^*)$ .

Policy iteration takes the evaluation arrow all the way (exact $V^\pi$ ) before improving. Value iteration applies one tiny piece of evaluation before each improvement — and because the greedy step is implicit in the $\max$ of $T^*$ , the two arrows fuse into a single update. Modified policy iteration sits between: run the inner evaluation loop for $k$ sweeps instead of to convergence, then improve. $k = 1$ recovers value iteration; $k = \infty$ recovers exact policy iteration; intermediate $k$ is often fastest in practice.

The LP polytope

In the primal LP, each constraint $V(s) \ge R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s')$ is a half-space in $\mathbb{R}^{|S|}$ . The feasible set — the intersection of these half-spaces — contains all overestimates of $V^*$ , anything satisfying $V \ge T^* V$ . The objective $\sum_s \mu(s) V(s)$ with positive $\mu$ picks the smallest such overestimate, which is $V^*$ itself, sitting at a vertex where exactly one constraint per state is tight — and the tight constraint names the optimal action there.

06 · Hands-on

Try it yourself

Three widgets, each illustrating one core idea. Drag, click, watch the numbers update.

First, step value or policy iteration on a 4×4 gridworld (constant $-1$ reward, two terminal corners). Press Step to apply one Bellman optimality backup (VI) or one full evaluation + greedy improvement (PI), and watch $V$ converge and the greedy arrows settle.

Hands-on 1

Step value & policy iteration on a 4×4 gridworld

A 4×4 grid; the top-left and bottom-right squares are terminal (shaded). Every move costs −1 until termination. Pick a discount γ, choose VI or PI, and press Step to apply one Bellman optimality sweep (VI) or one full evaluation + greedy improvement (PI). Numbers are Vₖ; arrows show the greedy policy.

γ0.90

iter 0

VI · iteration 0

‖Vₖ − Vₖ₋₁‖∞

—

‖Vₖ − V*‖∞ bound

—

policy changes

—

‖Vₖ − V*‖∞ true

—

init

Try thisRun VI step by step at γ = 0.9: after step 1 every non-terminal cell holds −1 (one move from termination if it could teleport); deeper cells fill in over the next sweeps and the values keep creeping for a while. Now switch to PI and reset — it reaches the same optimal arrows in just 2–3 iterations, but each PI iteration solves a 14×14 linear system internally.

TakeawayVI does many cheap iterations; PI does a few expensive ones. Crucially, the greedy policy(the arrows) usually freezes well before the values stop moving — once the arrows settle you already have π*, even while the numbers keep inching toward V*. That is why VI's stopping rule certifies the gap with the 2γε/(1−γ) bound rather than waiting for exact equality.

Next, walk policy iteration through the exact 3-state worked example, alternating evaluation and greedy improvement with the full $Q$ -table exposed — watch the argmax flip and the policy converge to $(a, a)$ .

Hands-on 2

Policy iteration, evaluation ↔ improvement

The 3-state worked-example MDP. Pick a starting policy and a discount, then step the algorithm: each iteration evaluates the current policy exactly (a 2×2 linear system) and improves it greedily from the full Q-table. PI stops the moment the greedy action equals the current action in every state.

γ0.90

π₀(s₁)

π₀(s₂)

Iteration 1 · evaluate π = (s₁→b, s₂→b)

Vπ(s₁)

1.00

Vπ(s₂)

10.00

Vπ(s₃)

0.00

Q(s₁, a)

14.00

Q(s₁, b)

1.00

Q(s₂, a)

0.90

Q(s₂, b)

10.00

greedy → (s₁→a, s₂→b)policy changed

iterating…

Try thisStart from π₀ = (b, b) at γ = 0.9 — the deliberately bad "grab the +10 now" guess. Watch the Q-table flip: iteration 1 fixes s₁ to a, iteration 2 discovers that even at s₂ the loop (action a) beats cashing out, and iteration 3 confirms nothing changes. Now drop γ below ~0.82: the discount no longer rewards looping, so PI keeps s₂→b.

TakeawayEach green cell is the action the greedy step "selects"; improvement simply reads the argmax of the Q-row. By the policy-improvement theorem each iteration is monotone — the values never go down — and because there are only finitely many deterministic policies, PI terminates exactly when the greedy policy matches the one it just evaluated.

Finally, feel the contraction: run value iteration on the same 3-state MDP and plot $\|V_k - V^*\|_\infty$ on a log scale against $k$ . Slide $\gamma$ and watch the slope — it is exactly $\log\gamma$ , the geometric rate the contraction guarantees.

Hands-on 3

Feel the contraction — how fast does VI converge?

Value iteration on the 3-state MDP of §04. The plot shows ‖Vₖ − V*‖∞ on a log scale against the sweep count k. The dashed amber line is the contraction guarantee γᵏ·‖V₀ − V*‖∞ — slide γ and watch the actual error hug a straight line of slope log γ.

γ0.90

iterations60

geometric rate

0.90

half-life (sweeps)

6.6

iters for ε = 10⁻³

97

final ‖Vₖ − V*‖∞

3.04e-2

V* ≈ (s₁: 26.32, s₂: 23.68, s₃: 0.00)

Try thisAt γ = 0.5 VI hits 10⁻³ error in about 10 sweeps; at γ = 0.9 it needs roughly 65; at γ = 0.99 around 700. The dependence is log ε / log γ — as γ → 1 the line flattens and convergence slows dramatically. Watch the actual error sit right on the dashed bound.

TakeawayDiscounting is not just modelling taste — it is the engine of convergence. The closer γ is to 1, the longer the effective planning horizon, the smaller each shrinkage step, and the more sweeps you need. The contraction factor γ is literally the slope of this log-error line.

07 · Exam intel

What the exam actually tests

This chapter loads several short proofs and at least one numerical walk-through. Seven patterns cover essentially every question.

Q1

Prove the policy improvement theorem

Hypothesis: $Q^\pi(s, \pi'(s)) \ge V^\pi(s)$ for all $s$ . Goal: $V^{\pi'}(s) \ge V^\pi(s)$ for all $s$ . One chain of inequalities, applying the hypothesis once per unrolling step:

\begin{aligned} V^\pi(s) &\le Q^\pi(s, \pi'(s)) = \mathbb{E}_{\pi'}\bigl[ r_{t+1} + \gamma V^\pi(s_{t+1}) \mid s_t = s \bigr] \\ &\le \mathbb{E}_{\pi'}\bigl[ r_{t+1} + \gamma\, Q^\pi(s_{t+1}, \pi'(s_{t+1})) \mid s_t = s \bigr] \\ &\le \cdots \le \mathbb{E}_{\pi'}\bigl[ r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots \mid s_t = s \bigr] = V^{\pi'}(s). \end{aligned}

The infinite sum converges because $\gamma < 1$ and rewards are bounded. Corollary: greedy improvement either strictly improves the policy or leaves it unchanged — in which case Bellman optimality holds and $\pi = \pi^*$ .

Q2

Show that T-star is a γ-contraction in max-norm

Fix a state $s$ and let $a^*$ maximise the backup for $V$ , so $(T^* V)(s) = R(s, a^*) + \gamma \sum_{s'} P(s' \mid s, a^*) V(s')$ . Then

(T^* V)(s) - (T^* U)(s) \le \gamma \sum_{s'} P(s' \mid s, a^*) \bigl[ V(s') - U(s') \bigr] \le \gamma \|V - U\|_\infty.

A symmetric argument (swap $V$ and $U$ ) gives the lower bound, so $\|T^* V - T^* U\|_\infty \le \gamma \|V - U\|_\infty$ . Banach’s fixed-point theorem then gives existence, uniqueness, and the geometric rate $\gamma^k$ .

Q3

Derive the practical stopping rule

Suppose $\|V_{k+1} - V_k\|_\infty < \varepsilon$ . By the contraction, $\|V_{k+m} - V_{k+m-1}\|_\infty \le \gamma^{m-1}\varepsilon$ . Telescoping and the triangle inequality give, for $M \to \infty$ (so $V_M \to V^*$ ),

\|V^* - V_{k+1}\|_\infty \le \sum_{m=2}^{\infty} \gamma^{m-1}\varepsilon = \frac{\gamma}{1-\gamma}\,\varepsilon.

The §3 version with a factor of 2 also accounts for the gap at iterate $k$ itself, giving $\frac{2\gamma\varepsilon}{1-\gamma}$ . Either form works; the tighter one is preferable when available.

Q4

Run policy iteration on a small MDP

Typical setup: 2–3 states, 2 actions, $\gamma \approx 0.9$ . Start from a given policy, evaluate exactly (solve a 2×2 or 3×3 system), greedily improve, repeat — expect 2–3 iterations. Three things to nail: (i) write the Bellman equations in matrix form and solve; (ii) compute the full Q-table at each improvement, not just one action; (iii) stop only when every state’s greedy action matches the current policy.

Q5

State and interpret the dual LP

Write down both primal and dual. The dual variables $\lambda(s, a)$ are discounted occupancy measures, $\lambda(s, a) = \sum_{t} \gamma^t \Pr(s_t = s, a_t = a \mid \mu, \pi)$ . The flow constraint $\sum_a \lambda(s', a) = \mu(s') + \gamma \sum_{s,a} \lambda(s,a) P(s' \mid s, a)$ says occupancy at $s'$ = initial probability + discounted inflow. Maximising $\sum \lambda R$ finds the occupancy pattern collecting the most discounted reward; read off $\pi^*(s) = \arg\max_a \lambda^*(s, a)$ .

Q6

Expectation vs optimality — which goes where?

A reliable trap. The Bellman expectation $T^\pi$ (sum over actions weighted by $\pi$ ) appears in iterative policy evaluation and the inner loop of policy iteration. The Bellman optimality $T^*$ (max over actions) appears in the value-iteration backup, the primal LP constraints, and policy improvement (one-step lookahead). The mnemonic: expectation evaluates, optimality optimises.

Q7

Compare the costs of DP methods

Method	Per iteration	Iterations
Iterative policy eval	$O(\lvert S\rvert^2 \lvert A\rvert)$	$O(\log(1/\varepsilon)/\log(1/\gamma))$
Direct policy eval	$O(\lvert S\rvert^3)$ once	1
Value iteration	$O(\lvert S\rvert^2 \lvert A\rvert)$	$O(\log(1/\varepsilon)/\log(1/\gamma))$
Policy iteration	cubic eval + $O(\lvert S\rvert^2\lvert A\rvert)$ improve	few (strongly polynomial)
Linear programming	$\mathrm{poly}(\lvert S\rvert, \lvert A\rvert)$ end-to-end	—

08 · Common mistakes

Where students get this wrong

×

Value iteration produces a policy at every step

Intermediate iterates $V_k$ need not correspond to any achievable policy — they are abstract fixed-point iterates. Only after convergence do we extract a policy by being greedy w.r.t. $V^*$ . The greedy policy $\text{greedy}(V_k)$ can even be a non-monotone function of $k$ ; what is monotone is the contraction toward $V^*$ .

×

PI converges in fewer iterations, therefore PI is faster

Fewer iterations, yes — but each PI iteration solves a full linear system (or runs many evaluation sweeps). VI iterations are individually much cheaper. Which wins depends on $\gamma$ , $|S|$ , $|A|$ , structure, and implementation. Modified PI (truncated evaluation) is often best in practice.

×

The iterate difference tells me the gap to V-star

Almost. The exact relation is $\|V_{k+1} - V^*\|_\infty \le \frac{2\gamma\varepsilon}{1-\gamma}$ when $\|V_{k+1} - V_k\|_\infty < \varepsilon$ — a multiplicative blow-up by $\frac{2\gamma}{1-\gamma}$ . With $\gamma = 0.99$ that factor is $\approx 198$ : an iterate change of $10^{-3}$ only guarantees a gap of $\approx 0.2$ , not $10^{-3}$ .

×

Confusing T-pi and T-star

$T^\pi$ is linear in $V$ — just $R^\pi + \gamma P^\pi V$ . $T^*$ is non-linear because of the $\max$ . Iterative policy evaluation uses $T^\pi$ (no policy update); value iteration uses $T^*$ (the greedy policy is updated implicitly every step). Mixing them up is the single most common slip on “which algorithm does what” questions.

×

DP is polynomial, so MDPs are easy

Polynomial in the number of states — and the number of states is typically exponential in the number of state variables (the curse of dimensionality). A 10×10 screen with 256 colours already has $256^{100}$ states, far beyond any DP method. That is exactly the motivation for function approximation and deep RL.

×

Classical PI evaluates the policy approximately

Classical PI evaluates exactly. The variant that evaluates approximately (run $k$ sweeps of iterative evaluation, then improve) is modified policy iteration. $k = 1$ is value iteration; $k = \infty$ is exact PI. Related, but not the same algorithm.

09 · Self-check

Can you answer these?

Which statement about value iteration is true?

Policy iteration in a fully observable MDP with |S| states and |A| actions:

In the LP formulation of an MDP, what does the dual variable λ(s, a) mean?

You run value iteration with γ = 0.95 and observe ‖V_{k+1} − V_k‖∞ < 10⁻³. What can you conclude?

10 · Recap

One-screen summary

Chapter 09 — load-bearing ideas

Brute-force is impossible. $|A|^{|S|}$ deterministic policies. Dynamic programming exploits the Bellman recursion to cache and reuse subproblem solutions.
Two operators run the show. The Bellman expectation $T^\pi$ is linear in $V$ ; the optimality $T^*$ is non-linear (the max). Both are γ-contractions in $\|\cdot\|_\infty$ .
Policy evaluation. Solve $V^\pi = R^\pi + \gamma P^\pi V^\pi$ either directly in $O(|S|^3)$ or iteratively as $V_{k+1} = T^\pi V_k$ at $O(|S|^2|A|)$ per sweep with rate $\gamma$ .
Policy improvement theorem. If $Q^\pi(s, \pi'(s)) \ge V^\pi(s)$ everywhere, then $V^{\pi'} \ge V^\pi$ everywhere. Greedy improvement is always safe.
Policy iteration. Alternate exact evaluation and greedy improvement. Terminates exactly in finitely many iterations — few iterations, each expensive.
Value iteration. Iterate $V_{k+1} = T^* V_k$ to $V^*$ with $\|V_k - V^*\|_\infty \le \gamma^k \|V_0 - V^*\|_\infty$ . Stop when $\|V_{k+1} - V_k\|_\infty < \varepsilon$ and certify $\|V_{k+1} - V^*\|_\infty < \frac{2\gamma\varepsilon}{1-\gamma}$ .
Linear programming. Primal: $\min \mu^\top V$ s.t. $V \ge T^* V$ . Dual: optimise reward-weighted occupancy $\lambda(s, a) = \sum_t \gamma^t \Pr(s_t = s, a_t = a)$ . Optimal policy $\pi^*(s) = \arg\max_a \lambda^*(s, a)$ .
Curse of dimensionality. DP is polynomial in $|S|$ , but $|S|$ is typically exponential in the problem variables — the motivation for the approximate, sample-based methods of Chapter 10.

✓

Could you teach this back?

Without looking back, can you: state what “solving an MDP” means in terms of $V^*$ and $\pi^*$ ; write the Bellman expectation and optimality equations and say which appears in which algorithm; explain in plain English why one greedy improvement step cannot make a policy worse; explain why value iteration converges (contraction) and at what rate ( $\gamma$ ); sketch one iteration of policy iteration on a 2-state MDP; and write the primal LP and state what its dual variables mean physically? If any of those stick, revisit the matching section. If all six flow, you’re ready for Chapter 10 — where the model goes away and we learn these same values from samples.