Dynamic programming: policy evaluation, policy iteration and value iteration

Before this lesson: lesson 01 (MDPs, $V^\pi$, $Q^\pi$, the Bellman equations); the $\infty$-norm (linear algebra 11); reading a proof by steps (foundations 09). Time: about 70 minutes, plus the notebook.

---

Why this matters #

DP is the exact version of reinforcement learning. Later lessons replace its parts with samples and neural networks: TD learning is sampled policy evaluation (lesson 04), Q-learning is sampled value iteration (lesson 05), actor-critic methods alternate approximate evaluation and improvement (lesson 08), and AlphaZero uses tree search as a policy improvement step and a network as the evaluation (lesson 10). The contraction argument of this lesson explains why these methods converge, and its failure explains why some of them diverge with function approximation (lesson 06).

1. Predict first #

2. The picture #

Evaluation: apply the Bellman equation again and again #

Lesson 01 solved $V^\pi = r_\pi + \gamma P_\pi V^\pi$ with one linear solve. There is a second way. Start from any guess, for example $V_0 = 0$, and use the right side as an update:

Each sweep updates every state from the values of the previous sweep. On the 4×4 gridworld (random policy, reward $-1$ per step, $\gamma = 1$), the first row of $V_k$ is:

sweep $k$	first row of $V_k$
0	$0,\ 0,\ 0,\ 0$
1	$0,\ -1,\ -1,\ -1$
2	$0,\ -1.75,\ -2,\ -2$
3	$0,\ -2.44,\ -2.94,\ -3$
10	$0,\ -6.14,\ -8.35,\ -8.97$
$\infty$	$0,\ -14,\ -20,\ -22$

After $k$ sweeps, $V_k(s)$ is the expected reward of the first $k$ steps. The values creep towards $V^\pi$. But look at the greedy policy with respect to $V_k$: from $k = 3$ on, it is already the optimal policy (move straight to the nearest corner). Policies settle long before values do.

Improvement: act greedily with respect to the values #

Given values $V$, the greedy policy picks in each state an action with the largest one-step lookahead $Q(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s')$. Evaluate and improve in turn, and you get policy iteration. Do one sweep, then improve, and you get value iteration.

Interactive figure: loading…

Generalized policy iteration #

Both methods are instances of one pattern. Evaluation pushes $V$ towards $V^\pi$ of the current policy. Improvement pushes $\pi$ towards the greedy policy of the current $V$. Each move spoils the other a little: after improvement, $V$ is no longer the value of the new policy; after evaluation, the policy is no longer greedy. But the two together move to the only point where both are satisfied: the optimal value $V^*$ and an optimal policy $\pi^*$. Sutton and Barto call this pattern generalized policy iteration (GPI).

3. Definitions and main results #

Iterative policy evaluation #

Algorithm (iterative policy evaluation).

1. Start with $V_0$, for example $V_0 = 0$.
2. Synchronous sweep: compute every state from the old vector, $V_{k+1}(s) = \sum_a \pi(a \mid s)\big[R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V_k(s')\big]$.
3. Stop when $\|V_{k+1} - V_k\|_\infty$ is small (the stopping rule below says how small).

In place. Keep one array and overwrite $V(s)$ as soon as it is computed, so later states in the same sweep already use the new values. This uses half the memory and usually converges faster. On the 4×4 gridworld with tolerance $10^{-10}$, synchronous sweeps need 426 sweeps; in-place sweeps in row order need 272.

Each sweep costs $O(|\mathcal S|^2 |\mathcal A|)$ for a dense model, and much less when each state has only a few successors. Why does it converge? The next section answers this for $\gamma < 1$. For $\gamma = 1$ (the 4×4 gridworld), it converges when the policy ends every episode with probability 1: then $P_\pi$ restricted to the non-terminal states has spectral radius below 1.

The Bellman operators #

Treat a value function as a vector $V \in \mathbb R^{\mathcal S}$. Two maps from vectors to vectors:

$T^\pi$ is the Bellman expectation operator, $T^\pi V = r_\pi + \gamma P_\pi V$. $T$ is the Bellman optimality operator. In this language, the Bellman equations of lesson 01 say that $V^\pi$ is a fixed point of $T^\pi$ ($T^\pi V^\pi = V^\pi$) and $V^*$ is a fixed point of $T$. Iterative policy evaluation is $V_{k+1} = T^\pi V_k$; value iteration will be $V_{k+1} = T V_k$.

Monotonicity. If $V \le U$ in every state, then $T^\pi V \le T^\pi U$ and $TV \le TU$. Reason: $P \ge 0$, so a larger $V$ gives a larger average, and the max of larger numbers is larger. We use this twice below.

The max lemma #

Lemma (max lemma). For two functions $f, g$ on a finite set, $\big|\max_a f(a) - \max_a g(a)\big| \le \max_a |f(a) - g(a)|$.

Proof. Suppose $\max f \ge \max g$ (the other case is the same with $f$ and $g$ swapped). Let $a^*$ be a maximiser of $f$. Then $\max g \ge g(a^*)$, so

In words: if no action changes its value by more than $c$, the best value cannot change by more than $c$ either. The best action may change, but the best value moves at most as much as the values themselves.

The contraction theorem #

Interactive figure: loading…

Theorem (contraction). For $0 \le \gamma < 1$ and all $V, U \in \mathbb R^{\mathcal S}$,

Hence $T$ has exactly one fixed point $V^*$, and value iteration $V_{k+1} = TV_k$ satisfies, from any start $V_0$,

Proof.

1. Fix a state $s$. Apply the max lemma with $f(a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s')$ and $g(a)$ the same expression with $U$. The rewards cancel in $f - g$: $|(TV)(s) - (TU)(s)| \le \gamma \max_a \big|\sum_{s'} P(s' \mid s, a)\,(V(s') - U(s'))\big|$.
2. The weights $P(s' \mid s, a)$ are $\ge 0$ and sum to at most 1, so a weighted sum of numbers of size at most $\|V - U\|_\infty$ has size at most $\|V - U\|_\infty$. So $|(TV)(s) - (TU)(s)| \le \gamma \|V - U\|_\infty$.
3. This holds for every $s$; take the max over $s$. This is the contraction.
4. At most one fixed point. If $V = TV$ and $U = TU$, then $\|V - U\|_\infty = \|TV - TU\|_\infty \le \gamma \|V - U\|_\infty$. With $\gamma < 1$ this forces $\|V - U\|_\infty = 0$.
5. A fixed point exists. By step 3, $\|V_{k+1} - V_k\|_\infty \le \gamma^k \|V_1 - V_0\|_\infty$, so $(V_k)$ is a Cauchy sequence and has a limit $V^*$ ($\mathbb R^{\mathcal S}$ is complete). $T$ is continuous, so $TV^* = \lim TV_k = \lim V_{k+1} = V^*$. (This is Banach's fixed-point theorem.)
6. Rate. $\|V_k - V^*\| = \|TV_{k-1} - TV^*\| \le \gamma \|V_{k-1} - V^*\| \le \dots \le \gamma^k \|V_0 - V^*\|$.
7. Stopping rule. By step 6 and the triangle inequality, $\|V_{k+1} - V^*\| \le \gamma \|V_k - V^*\| \le \gamma\big(\|V_k - V_{k+1}\| + \|V_{k+1} - V^*\|\big)$. Move the last term to the left: $(1 - \gamma)\|V_{k+1} - V^*\| \le \gamma \|V_{k+1} - V_k\|$. $\blacksquare$

The same proof without the max (step 1 without the lemma) shows that $T^\pi$ is a $\gamma$-contraction too. So iterative policy evaluation converges to $V^\pi$ from any start, with the same rate and stopping rule.

How many iterations? To shrink the error by a factor $\varepsilon$ you need $\gamma^k \le \varepsilon$, that is

The number of iterations grows like the effective horizon $1/(1-\gamma)$.

Interactive figure: loading…

$V^*$ is the fixed point of $T$ #

Lesson 01 used this fact. Here is the proof.

Theorem. Let $\gamma < 1$, let $\bar V$ be the fixed point of $T$, and let $\bar\pi$ be greedy with respect to $\bar V$. Then $V^{\bar\pi} = \bar V$, and $V^\pi \le \bar V$ for every policy $\pi$. So $\bar V = V^*$, and $\bar\pi$ is optimal.

Proof

1. Greedy means $T^{\bar\pi} \bar V = T \bar V$. With $T\bar V = \bar V$, this gives $T^{\bar\pi}\bar V = \bar V$. $V^{\bar\pi}$ is the only fixed point of $T^{\bar\pi}$, so $V^{\bar\pi} = \bar V$.
2. For any policy $\pi$ and any $V$, an average over actions is at most the max: $T^\pi V \le TV$. So $T^\pi \bar V \le T\bar V = \bar V$.
3. Apply $T^\pi$ again and use monotonicity: $(T^\pi)^2 \bar V \le T^\pi \bar V \le \bar V$. By induction, $(T^\pi)^k \bar V \le \bar V$ for all $k$.
4. Let $k \to \infty$: $(T^\pi)^k \bar V \to V^\pi$ (contraction). So $V^\pi \le \bar V$. With step 1, $\bar V = \max_\pi V^\pi = V^*$. $\blacksquare$

This proof compares stationary policies. A classical result (Puterman 1994, ch. 6) shows that policies that use the whole history or the time cannot do better in a finite discounted MDP, so nothing is lost.

The policy improvement theorem #

Theorem (policy improvement). Let $\pi$ and $\pi'$ be two policies with

Then $V^{\pi'}(s) \ge V^\pi(s)$ for every state $s$. If the first inequality is strict in some state, the second is strict there too.

For a deterministic $\pi'$ the condition reads $Q^\pi(s, \pi'(s)) \ge V^\pi(s)$: "take $\pi'$'s action now, then follow $\pi$" is at least as good as following $\pi$. The theorem says: then following $\pi'$ forever is also at least as good.

Proof.

1. The left side of the condition is $(T^{\pi'} V^\pi)(s)$. So the condition says $T^{\pi'} V^\pi \ge V^\pi$.
2. Apply $T^{\pi'}$ and use monotonicity: $(T^{\pi'})^2 V^\pi \ge T^{\pi'} V^\pi \ge V^\pi$. By induction the sequence $(T^{\pi'})^k V^\pi$ increases with $k$.
3. It converges to the fixed point of $T^{\pi'}$, which is $V^{\pi'}$. An increasing sequence stays above its first terms, so $V^{\pi'} \ge T^{\pi'} V^\pi \ge V^\pi$.
4. If $(T^{\pi'} V^\pi)(s) > V^\pi(s)$ in some state $s$, step 3 gives $V^{\pi'}(s) > V^\pi(s)$. $\blacksquare$

The same idea, unrolled in time: $V^\pi(s) \le \mathbb E[r_t + \gamma V^\pi(s_{t+1})]$ with the first action from $\pi'$; apply the condition again at $s_{t+1}$, then at $s_{t+2}$, and so on. Every rewritten step follows $\pi'$, and the leftover term $\gamma^k V^\pi(s_{t+k})$ goes to 0.

The greedy policy $\pi'(s) \in \arg\max_a Q^\pi(s, a)$ satisfies the condition, because the max is at least the $\pi$-average: $\max_a Q^\pi(s, a) \ge \sum_a \pi(a \mid s) Q^\pi(s, a) = V^\pi(s)$.

Policy iteration #

Algorithm (policy iteration). Start from any policy $\pi_0$. For $i = 0, 1, 2, \dots$:

1. Evaluate: compute $V^{\pi_i}$ exactly (one linear solve, lesson 01).
2. Improve: $\pi_{i+1}(s) \in \arg\max_a Q^{\pi_i}(s, a)$, where $Q^{\pi_i} = R + \gamma P V^{\pi_i}$. If the current action is already among the best, keep it.
3. If $\pi_{i+1} = \pi_i$, stop.

Why it stops at an optimal policy.

• Each step is at least as good: $V^{\pi_{i+1}} \ge V^{\pi_i}$ (policy improvement theorem).
• If the policy changes, some state gets a strictly better action, so the value strictly increases there. Then no policy can appear twice.
• There are at most $|\mathcal A|^{|\mathcal S|}$ deterministic policies, so the loop stops after finitely many steps.
• When it stops, $\pi_i$ is greedy with respect to its own values: $T V^{\pi_i} = T^{\pi_i} V^{\pi_i} = V^{\pi_i}$. So $V^{\pi_i}$ is the fixed point of $T$, which is $V^*$.

The rule "keep the current action when it is among the best" matters. Without it, two tied actions can make the policy switch back and forth forever (with floating-point numbers, use a small tolerance such as $10^{-10}$).

Value iteration and its relatives #

Algorithm (value iteration). Start from any $V_0$ (often 0). Repeat $V_{k+1} = TV_k$ until $\frac{\gamma}{1-\gamma}\|V_{k+1} - V_k\|_\infty$ is below your tolerance. Return the greedy policy with respect to the final $V$.

Value iteration is policy iteration with one sweep. Let $\pi_{k+1}$ be greedy with respect to $V_k$. Then $TV_k = T^{\pi_{k+1}} V_k$: one improvement, then one sweep of evaluation of the new policy, instead of a full solve.

What is $V_k$? $V_k = T^k 0$ is the best expected discounted reward over the first $k$ steps only. It is not the value of any stationary policy in general. For example, $V_1 = (2, 1)$ on the robot vacuum is just "the best reward now". Only the limit $V^*$ is a policy's value.

Modified policy iteration. Do $m$ sweeps of evaluation after each improvement, $V \leftarrow (T^{\pi})^m V$. With $m = 1$ this is value iteration; with $m \to \infty$ it is policy iteration. Values in between often work best in practice.

Generalized policy iteration is any scheme that interleaves some evaluation with some improvement, in any order and in any amount, state by state if you like. If both continue, the process converges to $V^*$ and $\pi^*$ (the GPI figure in section 2). Almost every RL algorithm has this form.

The cost of the two methods #

	one iteration costs (dense model)	number of iterations
policy iteration	$O(S^3 + S^2 A)$: a linear solve, then the improvement	few in practice (at most $A^S$)
value iteration	$O(S^2 A)$: one max backup of every state	about $\log(1/\varepsilon) / \log(1/\gamma)$; many when $\gamma \to 1$

Here $S = |\mathcal S|$ and $A = |\mathcal A|$. Policy iteration wins when $\gamma$ is close to 1 and the state space is small enough for a linear solve. Value iteration wins when $S$ is large and $\gamma$ is moderate, or when only a good policy (not exact values) is needed.

Interactive figure: loading…

Answers to section 1. (1) About 5: on the 5×5 grid, policy iteration needs 5 evaluations when tied actions share the probability (the widget above), and 3 when ties go to the lowest action index. (2) Before: the greedy policy is optimal from iteration 29, while the value error is still about 1.15. (3) About 10 times more, because the number of iterations grows like $1/(1-\gamma)$: on the 5×5 grid, 162 iterations for $\gamma = 0.9$ and 1904 for $\gamma = 0.99$ (error below $10^{-6}$).

Linear programming, asynchronous DP, and the curse of dimensionality

A linear program. $V^*$ is also the solution of

$$\min_V \sum_s V(s) \quad\text{subject to}\quad V(s) \ge R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s') \text{ for all } (s, a).$$

Why: the constraints say $V \ge TV$. By monotonicity, $V \ge TV \ge T^2 V \ge \dots \to V^*$, so every feasible $V$ is $\ge V^*$ in every state. And $V^*$ itself is feasible. So $V^*$ is the smallest feasible point, and it minimises any sum with positive weights. This gives a third exact method, and LP duality leads to the "occupancy measure" view used in offline RL and imitation learning.

Asynchronous DP. You do not have to sweep all states in order. Update any state at any time, using the latest values of the others. As long as every state is updated infinitely often, the values still converge to $V^\pi$ or $V^*$ (Bertsekas and Tsitsiklis). In-place sweeps are one example. Real-time DP updates only the states that an agent visits, which focuses the work on relevant states.

The curse of dimensionality. DP needs the model and touches every state in every sweep. A state made of $d$ variables with 10 values each has $10^d$ states. Backgammon has about $10^{20}$ positions and Go about $10^{170}$. So we need two more ideas: learning from samples instead of the model (lessons 03–05) and function approximation instead of a table (lesson 06).

4. Worked example #

(a) Policy iteration on the robot vacuum ($\gamma = 0.9$, states H, L), starting from "always clean".

Evaluation 1. From lesson 01: $V^{\pi_0} = (130/11,\ 10) \approx (11.82,\ 10)$.

Improvement 1. Compute $Q^{\pi_0} = R + \gamma P V^{\pi_0}$:

• H: clean $= 2 + 0.9\,(0.5 \cdot 11.82 + 0.5 \cdot 10) = 11.82$; charge $= 0 + 0.9 \cdot 11.82 = 10.64$. Keep clean.
• L: clean $= 1 + 0.9 \cdot 10 = 10$; charge $= 0.9 \cdot 11.82 = 10.64$. Switch to charge.

Evaluation 2. For "clean in H, charge in L": $V^{\pi_1} = (400/29,\ 360/29) \approx (13.79,\ 12.41)$ (lesson 01). Both states improved, as the theorem promises.

Improvement 2.

• H: clean $= 2 + 0.9\,(0.5 \cdot 13.79 + 0.5 \cdot 12.41) = 13.79$; charge $= 0.9 \cdot 13.79 = 12.41$. Keep clean.
• L: clean $= 1 + 0.9 \cdot 12.41 = 12.17$; charge $= 0.9 \cdot 13.79 = 12.41$. Keep charge.

Nothing changes, so the policy is optimal and $V^* = (400/29,\ 360/29)$. Policy iteration needed two evaluations.

(b) Value iteration on the robot vacuum, from $V_0 = (0, 0)$. Each step takes, in each state, the max of "clean" and "charge".

• $k = 1$: H: $\max(2 + 0.9 \cdot 0,\ 0.9 \cdot 0) = 2$. L: $\max(1 + 0,\ 0) = 1$. So $V_1 = (2, 1)$.
• $k = 2$: H: $\max\big(2 + 0.9\,(0.5 \cdot 2 + 0.5 \cdot 1),\ 0.9 \cdot 2\big)$ $= \max(3.35,\ 1.8) = 3.35$. L: $\max(1 + 0.9 \cdot 1,\ 0.9 \cdot 2)$ $= \max(1.9,\ 1.8) = 1.9$. So $V_2 = (3.35, 1.9)$.
• $k = 3$: H: $\max\big(2 + 0.9\,(0.5 \cdot 3.35 + 0.5 \cdot 1.9),\ 0.9 \cdot 3.35\big)$ $= \max(4.3625,\ 3.015) = 4.3625$. L: $\max(1 + 0.9 \cdot 1.9,\ 0.9 \cdot 3.35)$ $= \max(2.71,\ 3.015) = 3.015$. So $V_3 = (4.3625, 3.015)$.

At $k = 3$, the max in L is "charge" for the first time: the greedy policy with respect to $V_2$ is already optimal. But the values are still far from $V^*$:

• true error: $\|V_3 - V^*\|_\infty = 13.79 - 4.36 = 9.43$;
• theorem: $\gamma^3 \|V_0 - V^*\|_\infty = 0.729 \cdot 13.79 = 10.06 \ge 9.43$ ✓;
• stopping rule: $\frac{0.9}{0.1}\|V_3 - V_2\|_\infty = 9 \cdot \max(1.0125,\ 1.115) = 10.04 \ge 9.43$ ✓.

(c) The 5×5 gridworld (Sutton and Barto, Example 3.5, $\gamma = 0.9$). From cell A every action earns $+10$ and jumps to A′ in the bottom row. With $V^*(A') = 16.02$ (from value iteration):

The cell left of A has no reward of its own, and its best move is into A: $V^*(0, 0) = 0 + 0.9 \cdot 24.42 = 21.98$. Every optimal value is the best, over the four actions, of "reward now plus $0.9$ times the value of the next cell": exactly the optimality equation.

5. In code #

NumPy and SciPy check the worked example: policy iteration, value iteration with the stopping rule, and the linear program of the deeper box as a third route to $V^*$.

import numpy as np
from scipy.optimize import linprog

gamma = 0.9
P = np.zeros((2, 2, 2))                      # robot vacuum: P[s, a, s'], states (H, L)
P[0, 0] = [0.5, 0.5]; P[0, 1] = [1, 0]       # actions (clean, charge)
P[1, 0] = [0, 1];     P[1, 1] = [1, 0]
R = np.array([[2.0, 0.0], [1.0, 0.0]])

def evaluate(pi):                            # deterministic pi: one action per state
    P_pi, r_pi = P[[0, 1], pi], R[[0, 1], pi]
    return np.linalg.solve(np.eye(2) - gamma * P_pi, r_pi)

# policy iteration from "always clean"
pi = np.array([0, 0])
while True:
    V = evaluate(pi)
    print(pi, V.round(3))                    # [0 0] [11.818 10.   ]  then  [0 1] [13.793 12.414]
    new = (R + gamma * P @ V).argmax(axis=1) # greedy (no ties here)
    if np.array_equal(new, pi):
        break
    pi = new

# value iteration with the stopping rule
V, k = np.zeros(2), 0
while True:
    V_new = (R + gamma * P @ V).max(axis=1)
    k += 1
    done = gamma / (1 - gamma) * np.abs(V_new - V).max() < 1e-6
    V = V_new
    if done:
        break
print(k, V.round(4))                         # 156 [13.7931 12.4138]

# linear program: minimise sum V(s) subject to V(s) >= R(s,a) + gamma * sum_s' P V
A_ub = gamma * P.reshape(4, 2) - np.repeat(np.eye(2), 2, axis=0)   # rows (s, a)
res = linprog(c=np.ones(2), A_ub=A_ub, b_ub=-R.reshape(4), bounds=[(None, None)] * 2)
print(res.x.round(3), 400 / 29, 360 / 29)    # [13.793 12.414] 13.793... 12.413...

P[[0, 1], pi] picks the row P[s, pi[s]] for each state, which is $P_\pi$ for a deterministic policy.

6. Where it shows up #

• Planning with a known model. Inventory control, queueing and maintenance problems in operations research, and small control problems in engineering, are solved exactly with value or policy iteration, or with the LP.
• Q-learning and DQN are sampled value iteration on $Q$; their targets $r + \gamma \max_{a'} Q(s', a')$ are one application of $T$ (lessons 05 and 06).
• Actor-critic and PPO follow GPI: a critic does approximate evaluation, the policy update does a soft improvement (lessons 08 and 09).
• AlphaZero and expert iteration use tree search as the improvement step and a value network as the evaluation (lesson 10).
• Model-based RL learns $P$ and $R$ from data and then plans with DP-like updates (Dyna, lesson 10).
• ML for science. Planning on a learned emulator, for example the control of a physical process with a fitted model, is DP on an approximate MDP. The contraction bound tells you how errors in the model or in the values propagate: an error $\epsilon$ in each backup gives at most $\epsilon/(1-\gamma)$ in the final values.

7. Common mistakes #

• Expecting values and policies to converge together. The greedy policy is often optimal long before the values are accurate. Stop by the policy when you only need the policy.
• Mixing synchronous and in-place updates by accident. V = r_pi + gamma * P_pi @ V is synchronous; a loop that writes V[s] and reads V in the same sweep is in place. Both converge, but the iteration counts differ.
• Policy iteration that never stops. With ties and floating-point noise, the argmax can switch between equal actions forever. Keep the current action if it is within a small tolerance of the best.
• Using the stopping rule with $\gamma = 1$. The factor $\gamma/(1-\gamma)$ is infinite; the contraction proof does not apply. Episodic problems with $\gamma = 1$ converge only for policies that end every episode.
• Taking $V_k$ as a policy's value. Value iteration's $V_k$ is a $k$-step value, not $V^\pi$ of any policy. Evaluate the greedy policy if you need its true value.
• Forgetting the model. Every method here needs $P$ and $R$. Without them, use the sample-based methods of lessons 03–05.

8. Check yourself #

1. Show that $T$ is monotone: $V \le U$ implies $TV \le TU$.
   Answer

   For each $(s, a)$, $\sum_{s'} P(s' \mid s, a) V(s') \le \sum_{s'} P(s' \mid s, a) U(s')$ because $P \ge 0$. So every term inside the max is at most the matching term for $U$, and the max of smaller numbers is at most the max of larger numbers.
2. Value iteration with $\gamma = 0.95$ gives $\|V_{k+1} - V_k\|_\infty = 0.01$. What is the guaranteed bound on $\|V_{k+1} - V^*\|_\infty$?
   Answer

   $\frac{0.95}{0.05} \cdot 0.01 = 0.19$.
3. Why does policy iteration stop after finitely many iterations?
   Answer

   Each change gives a strictly better value in some state and no worse value anywhere, so no policy can repeat. There are at most $|\mathcal A|^{|\mathcal S|}$ deterministic policies. (This needs the rule that ties keep the current action.)
4. Write one value-iteration step as "improvement plus evaluation".
   Answer

   Let $\pi_{k+1}$ be greedy with respect to $V_k$. Then $V_{k+1} = TV_k = T^{\pi_{k+1}} V_k$: one sweep of evaluation of the new greedy policy, starting from $V_k$.
5. In the 5×5 gridworld, why is $V^*(0, 0) = 0.9\, V^*(A)$?
   Answer

   From the corner $(0, 0)$, the best action moves right into A with reward 0. The optimality equation gives $V^*(0,0) = 0 + 0.9 \cdot V^*(A) = 0.9 \cdot 24.42 = 21.98$.
6. You have 10 000 states, 4 actions and $\gamma = 0.999$. Would you start with policy iteration or value iteration? Why?
   Answer

   Policy iteration (or modified policy iteration). Value iteration needs about $\log(1/\varepsilon)/(1-\gamma) \approx 1000 \cdot \log(1/\varepsilon)$ sweeps. Policy iteration needs a few linear solves; with sparse transitions an iterative solver handles $10^4$ states easily.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Define the Bellman optimality operator $T$.

   Show answer

2. State the contraction property of $T$.

   Show answer

3. State the max lemma.

   Show answer

4. Give the stopping rule of value iteration.

   Show answer

5. About how many value-iteration steps shrink the error by a factor $\varepsilon$?

   Show answer

6. State the policy improvement theorem.

   Show answer

7. What does one iteration of policy iteration cost, and of value iteration?

   Show answer

8. Why is value iteration "policy iteration with one sweep"?

   Show answer

9. What is generalized policy iteration, in one sentence?

   Show answer

10. Compute the stopping-rule bound for $\gamma = 0.9$ and $\|V_{k+1} - V_k\|_\infty = 2$.

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Policy iteration or value iteration?" PI: few, expensive iterations (a linear solve each); good when $\gamma$ is close to 1 and $S$ is moderate. VI: cheap iterations, about $\log(1/\varepsilon)/(1-\gamma)$ of them. Modified PI sits in between.
• "Why does value iteration converge?" $T$ is a $\gamma$-contraction in the $\infty$-norm (max lemma plus $P \ge 0$, rows sum to at most 1), so Banach's theorem gives a unique fixed point and a geometric rate $\gamma^k$.
• "Prove the policy improvement theorem." The condition is $T^{\pi'} V^\pi \ge V^\pi$; monotonicity gives $(T^{\pi'})^k V^\pi \ge V^\pi$, and the limit is $V^{\pi'}$.
• "Why do we need anything beyond DP?" DP needs the model and a table over all states. Real problems have unknown dynamics and huge state spaces, so we sample (TD, Q-learning) and approximate (neural networks).

10. Practice #

The notebook for this lesson runs in Colab. It has five exercises, each with a check cell and a folded solution:

1. policy_evaluation_iterative: synchronous sweeps; count them on the 4×4 gridworld and compare with the linear solve.
2. bellman_optimality_operator, and a numerical check of the contraction on 200 random pairs $V, U$.
3. value_iteration with the stopping rule; reproduce $V^*$ of the 5×5 gridworld ($24.42$ at A).
4. policy_iteration with stable tie-breaking; check that it agrees with value iteration and that values never decrease.
5. The linear program with scipy.optimize.linprog: its solution equals $V^*$.

11. Watch and read #

RL Course by David Silver - Lecture 3: Planning by Dynamic ProgrammingGoogle DeepMind · David Silver, UCL RL course · 99 min

Policy evaluation, policy iteration, value iteration and the contraction argument, with the small gridworld of this lesson.

Bellman Equations, Dynamic Programming, Generalized Policy Iteration | Reinforcement Learning Part 2Mutual Information · 22 min

A visual summary of the Bellman equations, policy and value iteration, and the GPI picture.

L1 MDPs, Exact Solution Methods, Max-ent RL (Foundations of Deep RL Series)Pieter Abbeel · 76 min

Value iteration and policy iteration from the deep-RL point of view; the last part previews entropy-regularised RL (lesson 08).

• Richard Sutton and Andrew Barto, Reinforcement Learning: An Introduction, 2nd ed., free PDF: chapter 4 (§4.1–4.7: policy evaluation, improvement, PI, VI, asynchronous DP, GPI); Example 4.1 is the 4×4 gridworld and Example 3.5 the 5×5 one.
• Alekh Agarwal, Nan Jiang, Sham Kakade, Wen Sun, Reinforcement Learning: Theory and Algorithms, free PDF: chapter 1 (contraction, policy iteration, the LP view) with complete proofs.
• Shangtong Zhang, Python code for Sutton and Barto, chapter 4 grid world: compare it with your notebook after you finish the exercises.