Bellman equations and dynamic programming

Suppose someone hands you the complete rulebook of a world: every transition probability $P(s' \mid s, a)$ and every expected reward $r(s,a)$. You want the best possible policy. In Chapter 3 you learned to evaluate any policy you are given: write down the Bellman expectation equation and solve a linear system. So why not evaluate every policy and keep the best one?

Count them. The gridworld in this chapter’s demo has 22 cells where the agent must choose among 4 actions. That makes $4^{22} \approx 1.8 \times 10^{13}$ deterministic policies. At a million evaluations per second, you would finish in about seven months. Yet the algorithms in this chapter solve that gridworld exactly in about two dozen cheap passes over the grid, which takes a fraction of a millisecond. The trick is an idea Richard Bellman named in the 1950s: dynamic programming (DP). (“Programming” here means planning, as in “linear programming”, not writing code.) It is the mathematical core of everything that follows in this course. Q-learning, actor-critic, PPO and even the critic in RLHF are all approximate, sampled versions of what you will do here exactly.

What you bring from Chapter 3

Here is a quick recap, in the notation of the notation page. A policy $\pi(a \mid s)$ has a state-value function $V^\pi(s)$ (expected return from $s$ if you follow $\pi$) and an action-value function $Q^\pi(s,a)$ (expected return if you take $a$ first and then follow $\pi$). They are related 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).$$

Substituting one into the other gives the Bellman expectation equation:

$$V^\pi(s) = \sum_a \pi(a \mid s) \Big[ r(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V^\pi(s') \Big].$$

It is linear in $V^\pi$. In matrix form it reads $V^\pi = r_\pi + \gamma P_\pi V^\pi$, so $V^\pi = (I - \gamma P_\pi)^{-1} r_\pi$. That is how Chapter 3’s demo recomputed values live.

The first formula deserves a name of its own, because we will use it constantly. Given any vector of state values $V$, the quantity $r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V(s')$ is a one-step lookahead. It means: take action $a$, collect the expected reward, then pretend that $V$ correctly scores wherever you land. Every algorithm in this chapter is built from this one computation.

A corridor to think with

Here is the small MDP we will compute by hand all chapter:

   +0.5  ◄──  [ A ]  ◄──►  [ B ]  ◄──►  [ C ]  ──►  +1
  small exit                                     big exit

There are three states, A, B, C, and two actions, left and right. Moves are deterministic. Walking left out of A ends the episode with reward $+0.5$. Walking right out of C ends it with $+1$. Every other move pays 0. (In the lab, the “exit” is an extra absorbing state with value 0.)

From A, should you grab the small prize now or walk two steps for the big one? Walking right earns $+1$ on the third move, worth $\gamma^2 \cdot 1$ today. So it depends on the discount: for $\gamma = 0.9$, $\gamma^2 = 0.81 > 0.5$ and you should walk; for $\gamma = 0.5$, $\gamma^2 = 0.25 < 0.5$ and you should take the small exit. The crossover is at $\gamma = 1/\sqrt{2} \approx 0.71$. This tiny example already shows the central fact: the best action in A depends on what you will do afterwards in B and C. Dynamic programming organizes that dependency.

The Bellman optimality equation

The principle of optimality

Think about driving routes. If the fastest route from Boston to Los Angeles passes through Chicago, then its Chicago-to-LA part must be the fastest route from Chicago to LA. If it weren’t, you could swap in the faster one and beat the “fastest” route. Bellman called this the principle of optimality: an optimal plan, from any point along it onward, is optimal for the problem that starts at that point.

So, to act optimally in $s$ you don’t need to search over whole futures. You need two things:

1. the best value you can get from each possible next state, and
2. a one-step choice of the action that leads to the best mix of immediate reward plus that future value.

Writing it down

Chapter 3 defined the optimal state-value function and optimal action-value function as the best achievable over all policies, and stated the equation they satisfy. Here we derive that equation from the principle of optimality, and then learn to solve it. The definitions are:

$$V^*(s) = \max_\pi V^\pi(s), \qquad Q^*(s,a) = \max_\pi Q^\pi(s,a).$$

The principle of optimality turns into equations. If you take $a$ in $s$ and then behave optimally, you get

$$Q^*(s,a) = r(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V^*(s'),$$

and behaving optimally in $s$ means picking the best $a$: $V^*(s) = \max_a Q^*(s,a)$. Combine the two:

$$V^*(s) = \max_a \Big[ r(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V^*(s') \Big],$$ $$Q^*(s,a) = r(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, \max_{a'} Q^*(s',a').$$

These are the Bellman optimality equations for $V^*$ and $Q^*$. Compare them with the expectation equation above. The only change is that the average over actions, $\sum_a \pi(a \mid s)[\cdots]$, became a maximum, $\max_a [\cdots]$. That small change has a big consequence. The max makes the equation nonlinear, so there is no single matrix inversion that solves it. We need an iterative method, and the rest of the chapter builds two of them.

Solving the corridor by hand

For a small problem you can guess and check. Take $\gamma = 0.9$ and guess “always go right”. Then $V(C) = 1$, $V(B) = 0.9 \cdot 1 = 0.9$, $V(A) = 0.9 \cdot 0.9 = 0.81$. Now check each state against the optimality equation:

State	left: $r + \gamma V(\text{next})$	right: $r + \gamma V(\text{next})$	max	equals guess?
A	$0.5$	$0 + 0.9 \cdot 0.9 = 0.81$	$0.81$	yes
B	$0 + 0.9 \cdot 0.81 = 0.729$	$0 + 0.9 \cdot 1 = 0.9$	$0.9$	yes
C	$0 + 0.9 \cdot 0.9 = 0.81$	$1$	$1$	yes

The guess satisfies the equation in every state. Later in the chapter we prove the equation has exactly one solution, so this is $V^*$. The table’s left and right columns are exactly $Q^*(s, \text{left})$ and $Q^*(s, \text{right})$.

Now repeat with $\gamma = 0.5$. “Always right” gives $V = (0.25, 0.5, 1)$. In A the check fails: $\max(0.5,\ 0.5 \cdot 0.5) = 0.5 \neq 0.25$. The equation itself tells you to switch A to left. With that switch, $V = (0.5, 0.5, 1)$, and every state checks out.

Acting greedily on $V^*$ is optimal

Once you have $V^*$, the optimal policy takes one line. In each state, pick the action with the best one-step lookahead:

$$\pi^*(s) = \arg\max_a \Big[ r(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V^*(s') \Big] = \arg\max_a Q^*(s,a).$$

A policy chosen this way is called greedy with respect to $V^*$. “Greedy” usually sounds short-sighted, so why is it optimal here? Because $V^*$ has already folded the whole future into a single number per state. A one-step lookahead on top of the right value function is a full lookahead. That is the real magic of value functions: they turn long-horizon planning into a one-step decision. (The proof is below, in the contraction section, once we have the tools.)

Three facts follow, and all of them matter later in the course:

• One policy is best everywhere at once. The greedy policy achieves $V^*(s)$ in every state simultaneously. You never have to trade off “good from A” against “good from B”.
• That policy can be deterministic. Randomizing never helps when you know the model. (Stochastic policies matter for exploration and for learning, as in Chapter 7, but not for optimality here.)
• $Q^*$ lets you act without the model. Acting greedily on $V^*$ needs $P$ and $r$ to do the lookahead. Acting greedily on $Q^*$ needs only an argmax over a table. That is why the model-free methods of Chapter 5 learn $Q$ rather than $V$.

Policy evaluation by sweeping

We’ll build up to solving the optimality equation in two steps. The first is a better way to do Chapter 3’s job: computing $V^\pi$ for a fixed policy.

A linear solve costs about $\lvert\mathcal S\rvert^3$ operations. That is fine for 22 states and hopeless for a million. There is a cheaper way. Take the Bellman expectation equation, which $V^\pi$ satisfies exactly, and use it as an update rule on a guess:

$$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] \quad \text{for every } s.$$

One pass of this update over all states is a sweep, and each single-state update is called a backup (information is “backed up” from successor states to their predecessor). Start from $V_0 = 0$ and sweep until nothing changes. This is iterative policy evaluation. You met it briefly at the end of Chapter 3. Here we look at how it behaves, and later in the chapter we prove that it converges.

Worked example: “always left” in the corridor

Take $\gamma = 0.9$ and the policy that always goes left. Each state’s update reads one neighbor:

$$V_{k+1}(A) = 0.5, \qquad V_{k+1}(B) = 0.9\, V_k(A), \qquad V_{k+1}(C) = 0.9\, V_k(B).$$

sweep $k$	$V_k(A)$	$V_k(B)$	$V_k(C)$
0	0	0	0
1	0.5	0	0
2	0.5	0.45	0
3	0.5	0.45	0.405
4	0.5	0.45	0.405

Watch how the information moves. The reward at the left exit reaches A in sweep 1, B in sweep 2, and C in sweep 3. Each sweep pushes news one step further back. In a deterministic chain the values become exact after (chain length) sweeps. When transitions are random, every state feeds back into every other through many paths, so the values only converge in the limit, geometrically fast. You’ll see why in the contraction section.

Iterative policy evaluation
input: P, r, policy π, discount γ, tolerance tol
1. V ← 0  (any start works)
2. repeat:
3.     for every state s:
4.         V_new(s) ← Σ_a π(a|s) [ r(s,a) + γ Σ_s' P(s'|s,a) V(s') ]
5.     Δ ← max_s |V_new(s) − V(s)|
6.     V ← V_new
7. until Δ < tol
8. return V

Policy improvement

Now we have $V^\pi$. Can we use it to find a better policy?

Here is the idea. Stand in state $s$ and consider deviating from $\pi$ for a single step: take action $a$ now, then go back to following $\pi$. The value of that one-step deviation is exactly $Q^\pi(s,a) = r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^\pi(s')$. Suppose some $a$ has $Q^\pi(s,a) > V^\pi(s)$. Then deviating once is better than not deviating. It would be odd if deviating every time you visit $s$ (and doing the same in other states) were worse. It isn’t, and that is the theorem.

∂ Proof of the policy improvement theorem

Let $\pi'$ be deterministic (the stochastic case is the same with an extra average over actions). Write $\mathbb{E}_{\pi'}[\,\cdot \mid s_t = s]$ for the expectation over trajectories that start in $s$ and follow $\pi'$. Start from the assumption and expand $Q^\pi$ one step:

$$V^\pi(s) \le Q^\pi(s, \pi'(s)) = \mathbb{E}_{\pi'}\big[ r_t + \gamma V^\pi(s_{t+1}) \mid s_t = s \big].$$

Apply the assumption again, this time at $s_{t+1}$: $V^\pi(s_{t+1}) \le Q^\pi(s_{t+1}, \pi'(s_{t+1}))$. Then expand that $Q^\pi$ one step:

$$V^\pi(s) \le \mathbb{E}_{\pi'}\big[ r_t + \gamma r_{t+1} + \gamma^2 V^\pi(s_{t+2}) \mid s_t = s \big].$$

Repeating $n$ times:

$$V^\pi(s) \le \mathbb{E}_{\pi'}\Big[ \sum_{j=0}^{n-1} \gamma^j r_{t+j} + \gamma^n V^\pi(s_{t+n}) \,\Big|\, s_t = s \Big].$$

Values are bounded (rewards are bounded and $\gamma < 1$), so the last term is at most $\gamma^n \max_{s''} \lvert V^\pi(s'') \rvert \to 0$. The sum converges to the return of $\pi'$. Letting $n \to \infty$ gives $V^\pi(s) \le V^{\pi'}(s)$.

For strictness, suppose $Q^\pi(s, \pi'(s)) > V^\pi(s)$ at some $s$. Since we now know $V^{\pi'} \ge V^\pi$ everywhere,

$$V^{\pi'}(s) = r(s,\pi'(s)) + \gamma \sum_{s'} P(s' \mid s, \pi'(s)) V^{\pi'}(s') \ge r(s,\pi'(s)) + \gamma \sum_{s'} P(s' \mid s, \pi'(s)) V^{\pi}(s') = Q^\pi(s,\pi'(s)) > V^\pi(s).$$

The natural choice of $\pi'$ is to be greedy everywhere at once:

$$\pi'(s) = \arg\max_a Q^\pi(s,a).$$

This satisfies the theorem’s condition automatically, because $\max_a Q^\pi(s,a) \ge \sum_a \pi(a \mid s) Q^\pi(s,a) = V^\pi(s)$. So greedy improvement never makes things worse.

What if it doesn’t make things better either? Suppose the greedy policy is no better than $\pi$, so $V^{\pi'} = V^\pi$. By the strict part of the theorem, no state can have $\max_a Q^\pi(s,a) > V^\pi(s)$, because that state’s value would have gone up. Combined with $\max_a Q^\pi(s,a) \ge V^\pi(s)$, this gives $V^\pi(s) = \max_a Q^\pi(s,a)$ in every state. Written out, that is exactly the Bellman optimality equation. So $V^\pi = V^*$ and $\pi$ was already optimal. Greedy improvement either strictly improves the policy somewhere or certifies that it is optimal.

Worked example

Improve “always left” in the corridor ($\gamma = 0.9$). From the table above, $V^\pi = (0.5, 0.45, 0.405)$. The one-step lookaheads are:

State	$Q^\pi(s, \text{left})$	$Q^\pi(s, \text{right})$	greedy
A	$0.5$	$0.9 \cdot 0.45 = 0.405$	left
B	$0.9 \cdot 0.5 = 0.45$	$0.9 \cdot 0.405 = 0.3645$	left
C	$0.9 \cdot 0.45 = 0.405$	$1$	right

Only C switches. Notice that B doesn’t switch yet, even though right is ultimately better from B. Under the current policy, C is a poor place to be: its value 0.405 comes from walking all the way back left. Improvement only trusts the current values, so it fixes the state whose problem is visible right now.

Policy iteration

Alternate the two steps: evaluate, improve, evaluate, improve, until the policy stops changing. That is policy iteration (Howard, 1960).

Policy iteration
1. π ← any deterministic policy
2. repeat:
3.     V ← evaluate(π)                                   # policy evaluation
4.     for every state s:                                # policy improvement
5.         π_new(s) ← argmax_a [ r(s,a) + γ Σ_s' P(s'|s,a) V(s') ]
6.             (keep π(s) unless another action is strictly better)
7.     stable ← (π_new == π);  π ← π_new
8. until stable
9. return π, V          # π is optimal and V = V*

Here is the corridor run from “always left” (L = left, R = right):

iteration	policy (A, B, C)	$V^\pi(A)$	$V^\pi(B)$	$V^\pi(C)$	states that switch
0	L, L, L	0.5	0.45	0.405	C
1	L, L, R	0.5	0.45	1	B
2	L, R, R	0.5	0.9	1	A
3	R, R, R	0.81	0.9	1	none: optimal

The good news about the big exit travels backward, one state per iteration, until A is convinced too.

Why it must stop. Each iteration either stops or produces a policy that is at least as good everywhere and strictly better somewhere. So no policy can ever appear twice. There are finitely many deterministic policies ($\lvert\mathcal A\rvert^{\lvert\mathcal S\rvert}$), so the loop must end, and when it ends the policy is optimal. (Exercise 4.4 makes this precise. It also explains line 6: without the “strictly better” rule, round-off can flip a state between two equally good actions forever.) The bound $\lvert\mathcal A\rvert^{\lvert\mathcal S\rvert}$ is absurdly pessimistic. In practice policy iteration converges in a handful of iterations, even on large problems. The catch is that each iteration contains a full policy evaluation.

Value iteration

Policy iteration spends most of its time in step 3, evaluating policies to high precision. Yet early policies are bad and about to be replaced, so precise values for them are wasted effort. What if we evaluate with just one sweep, then improve, then do one more sweep, and so on? Say the current values are $V_k$. The improvement step picks, in each state, the action $a$ with the largest lookahead $r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V_k(s')$. The single evaluation sweep for that new policy, starting from $V_k$, then computes exactly that same lookahead for the chosen action. So the new value is the largest lookahead. Improvement and the one evaluation sweep merge into a single update:

$$V_{k+1}(s) = \max_a \Big[ r(s,a) + \gamma \sum_{s'} P(s' \mid s,a)\, V_k(s') \Big] \quad \text{for every } s.$$

This is value iteration. Look at it closely: it is the Bellman optimality equation, used as an update rule. Policy evaluation turned the expectation equation into an update. Value iteration does the same to the optimality equation.

Value iteration
input: P, r, discount γ, tolerance tol
1. V ← 0  (any start works)
2. repeat:
3.     for every state s:
4.         V_new(s) ← max_a [ r(s,a) + γ Σ_s' P(s'|s,a) V(s') ]
5.     Δ ← max_s |V_new(s) − V(s)|
6.     V ← V_new
7. until Δ < tol
8. π(s) ← argmax_a [ r(s,a) + γ Σ_s' P(s'|s,a) V(s') ]   # extract the greedy policy
9. return V, π

Worked example: value iteration on the corridor

With $\gamma = 0.9$ and $V_0 = 0$, each sweep computes $V_{k+1}(A) = \max(0.5,\ 0.9 V_k(B))$, $V_{k+1}(B) = \max(0.9 V_k(A),\ 0.9 V_k(C))$, and $V_{k+1}(C) = \max(0.9 V_k(B),\ 1)$:

sweep $k$	$V_k(A)$	$V_k(B)$	$V_k(C)$	max change	greedy policy w.r.t. $V_k$
0	0	0	0
1	0.5	0	1	1.0	L, R, R
2	0.5	0.9	1	0.9	R, R, R (already optimal)
3	0.81	0.9	1	0.31	R, R, R
4	0.81	0.9	1	0	R, R, R

Two things to notice.

$V_k$ has a meaning of its own. Starting from $V_0 = 0$, $V_k(s)$ is the best expected discounted return you can collect in $k$ steps from $s$. After one sweep, A knows it can grab 0.5 and C knows it can grab 1. B needs two steps to reach anything. Value iteration solves ever-longer finite-horizon problems, and the horizon grows by one each sweep. Discounting makes the far future matter less and less, which is why the sequence converges.

The policy settles before the values do. After sweep 2, $V_2(A) = 0.5$ is still wrong (the truth is 0.81), yet the greedy policy is already optimal. The argmax only needs the ranking of actions to be right, not the values. Exercise 4.6 turns this into a theorem, and the demo shows it on a bigger problem: the arrows freeze long before the numbers do.

Watch it run

The demo runs value iteration on the gridworld from the introduction. There is a goal worth $+1$ (right edge), a row of four pits worth $-1$, and a three-cell wall. The reward is paid on the step that enters the goal or a pit, and the episode then ends. With slip probability $p$, the agent moves sideways (perpendicular to the intended direction, $p/2$ each way) instead of where it intended. Bumping into a wall or the edge leaves it where it is. Rows are counted from the top and columns from the left; the inspector shows the coordinates of the selected cell. Each cell’s color shows its current value $V_k$, and the arrows show the greedy action(s). When several actions tie, all of them are drawn, so at the start you see crosses: no preference yet. The inspector shows the four one-step lookaheads for the selected cell, with the arithmetic for the best one. You can check every number against the backup formula. The chart plots the max change $\lVert V_{k} - V_{k-1} \rVert_\infty$ on a log axis, together with a dashed line falling like $\gamma^{k}$. The next section explains why that line is there.

AlgorithmValue iterationPolicy iteration

StepPlayReset valuesRandom start

Tap a cell toInspectWallGoal +1Pit −1Restore grid

γ (discount)

slip probability

reward per step

speed

● max change ‖V_k − V_k−1‖_∞- - contraction bound δ₁·γ^k−1

What to try: press Step a few times and watch value spread outward from the goal, one cell per sweep, while the cells next to the pits learn to avoid them. Press Play and note the sweep at which the arrows stop changing, compared with the sweep at which the values converge. Raise slip to 0.3: most cells beside the pits stop walking along them, and several start 'hugging the wall', pushing into a wall or the edge so that only the safe sideways slips move them. Then set the reward per step to −0.1 and watch the agent take the risky shortcut again. Press Random start: the values begin anywhere, yet end at the same V*. Switch to Policy iteration and count iterations versus evaluation sweeps. Tap with Wall/Goal/Pit to redesign the grid.

A few things are worth seeing for yourself. With the defaults ($\gamma = 0.9$, slip $0.1$), value iteration stops (max change below $10^{-6}$) after 24 sweeps, but the arrows stop changing at sweep 10. With slip 0, the value of the cell in row 3, column 1 is exactly $0.9^4 = 0.656$. The goal is 5 moves away, and the reward arrives on the 5th move, so it is discounted 4 times. With slip $0.1$ it falls to $0.387$: the risk of sliding into a pit costs you.

Why it works: the Bellman operator is a contraction

We have three algorithms and some faith that they converge. Now for the proof. It is short and beautiful, and it also answers the questions we skipped. Does the optimality equation have a solution? Is it unique? Is the greedy policy really optimal? How many sweeps do we need?

Operators on value vectors

Think of a value function as a vector $V \in \mathbb{R}^{\lvert\mathcal S\rvert}$. Define two maps from vectors to vectors, the Bellman expectation operator $\mathcal{T}^\pi$ and the Bellman optimality operator $\mathcal{T}^*$:

$$(\mathcal{T}^\pi V)(s) = \sum_a \pi(a \mid s) \Big[ r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V(s') \Big],$$ $$(\mathcal{T}^* V)(s) = \max_a \Big[ r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V(s') \Big].$$

Now everything is compact. The Bellman equations say that $V^\pi$ and $V^*$ are fixed points: $V^\pi = \mathcal{T}^\pi V^\pi$ and $V^* = \mathcal{T}^* V^*$. Iterative policy evaluation is $V_{k+1} = \mathcal{T}^\pi V_k$, and value iteration is $V_{k+1} = \mathcal{T}^* V_k$. The question “does it converge?” becomes “does repeatedly applying the map approach a fixed point?”

Contraction in the sup norm

Measure the distance between two value functions by the largest disagreement in any state, the sup norm:

$$\lVert U - V \rVert_\infty = \max_s \lvert U(s) - V(s) \rvert.$$

Here is why, in words. The backup builds each state’s new value from an average of next-state values (weights $P(s' \mid s,a)$), then multiplies by $\gamma$. Averaging can’t increase the worst-case disagreement, and the factor $\gamma$ shrinks it. The max over actions doesn’t spoil this, because two maxima can’t differ by more than the largest difference between their arguments. The rewards are the same for both guesses, so they cancel.

∂ Proof that the Bellman optimality operator is a γ-contraction

Lemma. For any two functions $f, g$ on a finite set, $\lvert \max_a f(a) - \max_a g(a) \rvert \le \max_a \lvert f(a) - g(a) \rvert$.

Proof. Suppose without loss of generality that $\max f \ge \max g$, and let $a^\dagger$ be a maximizer of $f$. Then $0 \le \max f - \max g = f(a^\dagger) - \max g \le f(a^\dagger) - g(a^\dagger) \le \max_a \lvert f(a) - g(a) \rvert$.

Theorem. $\lVert \mathcal{T}^* U - \mathcal{T}^* V \rVert_\infty \le \gamma \lVert U - V \rVert_\infty$.

Proof. Fix a state $s$. Apply the lemma with $f(a) = r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) U(s')$ and $g(a)$ the same with $V$. The rewards cancel in $f - g$:

$$\lvert (\mathcal{T}^* U)(s) - (\mathcal{T}^* V)(s) \rvert \le \max_a \gamma \Big\lvert \sum_{s'} P(s' \mid s,a) \big(U(s') - V(s')\big) \Big\rvert.$$

The weights $P(s' \mid s,a)$ are nonnegative and sum to 1, so the weighted sum is at most the largest $\lvert U(s') - V(s') \rvert$:

$$\lvert (\mathcal{T}^* U)(s) - (\mathcal{T}^* V)(s) \rvert \le \gamma \max_a \sum_{s'} P(s' \mid s,a) \lvert U(s') - V(s') \rvert \le \gamma \lVert U - V \rVert_\infty.$$

This holds for every $s$. Take the max over $s$ on the left. The same argument without the lemma (an average over $a$ instead of a max) proves it for $\mathcal{T}^\pi$; that’s Exercise 4.3.

Banach’s fixed-point theorem

A map that shrinks all distances by a fixed factor below one has a remarkable property.

∂ Complete proof of Banach's fixed-point theorem

Let $V_{k+1} = \mathcal{T} V_k$, starting from any $V_0$. Write $\lVert \cdot \rVert$ for the sup norm.

Step 1: successive steps shrink geometrically. $\lVert V_{k+1} - V_k \rVert = \lVert \mathcal{T} V_k - \mathcal{T} V_{k-1} \rVert \le \gamma \lVert V_k - V_{k-1} \rVert$, so by induction $\lVert V_{k+1} - V_k \rVert \le \gamma^k \lVert V_1 - V_0 \rVert$.

Step 2: the sequence is Cauchy. For $m > k$, by the triangle inequality and a geometric series,

$$\lVert V_m - V_k \rVert \le \sum_{j=k}^{m-1} \lVert V_{j+1} - V_j \rVert \le \sum_{j=k}^{m-1} \gamma^j \lVert V_1 - V_0 \rVert \le \frac{\gamma^k}{1-\gamma} \lVert V_1 - V_0 \rVert,$$

which goes to 0 as $k \to \infty$, uniformly in $m$.

Step 3: it has a limit. $\mathbb{R}^n$ with any norm is complete: every Cauchy sequence converges. Call the limit $V_\star$.

Step 4: the limit is a fixed point. A contraction is Lipschitz, hence continuous. So $\mathcal{T} V_\star = \mathcal{T}(\lim_k V_k) = \lim_k \mathcal{T} V_k = \lim_k V_{k+1} = V_\star$.

Step 5: it is the only fixed point. If $U = \mathcal{T} U$ and $V = \mathcal{T} V$, then $\lVert U - V \rVert = \lVert \mathcal{T} U - \mathcal{T} V \rVert \le \gamma \lVert U - V \rVert$. Since $\gamma < 1$, this forces $\lVert U - V \rVert = 0$.

Step 6: the rate. $\lVert V_k - V_\star \rVert = \lVert \mathcal{T} V_{k-1} - \mathcal{T} V_\star \rVert \le \gamma \lVert V_{k-1} - V_\star \rVert \le \dots \le \gamma^k \lVert V_0 - V_\star \rVert$.

What this buys us

Apply Banach to $\mathcal{T}^\pi$ and to $\mathcal{T}^*$:

• Policy evaluation converges to $V^\pi$ from any start. You also get, for free, that the Bellman expectation equation has a unique solution. That is the invertibility of $I - \gamma P_\pi$ from Chapter 3, seen from a different angle.
• The optimality equation has exactly one solution, and value iteration converges to it from any start. That’s why the guess-and-check in the corridor was legitimate, and why the demo’s “Random start” always ends at the same values.
• The rate is geometric, with ratio γ. On a log axis, the error falls at least as fast as a straight line with slope $\log_{10} \gamma$ per sweep. The same bound holds for the change between successive sweeps (Step 1 of the proof). The change is what the demo plots, since unlike the error it can be computed without knowing $V^*$, and the dashed line is its bound $\lVert V_1 - V_0 \rVert_\infty \, \gamma^{k-1}$.

How many sweeps does that mean? To shrink the initial error by a factor $\epsilon$, you need $\gamma^k \le \epsilon$, i.e.

$$k \ge \frac{\ln(1/\epsilon)}{\ln(1/\gamma)} \approx \frac{\ln(1/\epsilon)}{1-\gamma}.$$

For $\epsilon = 10^{-6}$, that is 132 sweeps at $\gamma = 0.9$ and 1,375 at $\gamma = 0.99$. The factor $1/(1-\gamma)$ is the effective horizon from Chapter 3 again. Information must travel about that many steps, one step per sweep, before far-away rewards stop mattering.

We still need to close one gap. We defined $V^*$ as “the best over all policies” and then wrote down an equation it should satisfy. Is the unique solution of that equation really the best you can do, and does greedy play achieve it?

∂ Why the fixed point of T* is the optimal value, and greedy play achieves it

Let $V_\star$ be the unique fixed point of $\mathcal{T}^*$. We use two easy properties of the operators.

• Max beats average: $\mathcal{T}^\pi V \le \mathcal{T}^* V$ for every $V$ and every $\pi$ (componentwise).
• Monotonicity: if $U \le V$ componentwise, then $\mathcal{T}^* U \le \mathcal{T}^* V$, because the weights $P(s' \mid s,a)$ are nonnegative.

No policy beats $V_\star$. For any stationary policy $\pi$: $V^\pi = \mathcal{T}^\pi V^\pi \le \mathcal{T}^* V^\pi$. Apply $\mathcal{T}^*$ to both sides of $V^\pi \le \mathcal{T}^* V^\pi$ and use monotonicity: $\mathcal{T}^* V^\pi \le (\mathcal{T}^*)^2 V^\pi$. Chaining, $V^\pi \le (\mathcal{T}^*)^n V^\pi$ for all $n$. The right side converges to $V_\star$ by Banach, so $V^\pi \le V_\star$.

The greedy policy achieves $V_\star$. Let $\pi_g$ be greedy with respect to $V_\star$. By definition of greedy, $\mathcal{T}^{\pi_g} V_\star = \mathcal{T}^* V_\star = V_\star$. So $V_\star$ is a fixed point of $\mathcal{T}^{\pi_g}$. That operator is also a contraction, so its fixed point is unique, and that fixed point is $V^{\pi_g}$. Hence $V^{\pi_g} = V_\star$.

Together: $V_\star = \max_\pi V^\pi = V^*$, and the deterministic greedy policy attains it in every state simultaneously. (A longer argument, in Puterman’s book, shows that even non-stationary or history-dependent policies can’t do better in a finite MDP.)

A stopping rule you can trust. In practice you don’t know $V^*$, but you can see the change $\lVert V_{k+1} - V_k \rVert_\infty$. The contraction property links the two (Exercise 4.5):

$$\lVert V_{k+1} - V^* \rVert_\infty \le \frac{\gamma}{1-\gamma} \lVert V_{k+1} - V_k \rVert_\infty.$$

So to be within $\epsilon$ of $V^*$, stop when the change drops below $\epsilon (1-\gamma)/\gamma$. That threshold is much smaller than $\epsilon$ when $\gamma$ is close to 1.

And policy iteration? It also converges, and usually in far fewer iterations than value iteration has sweeps. It is a classical result (Puterman and Brumelle, 1979) that policy iteration is Newton’s method applied to the equation $V - \mathcal{T}^* V = 0$. Like Newton’s method, it converges very fast once it is close. Each Newton step, however, needs a full policy evaluation. In the demo’s defaults, value iteration takes 24 sweeps, while policy iteration takes 8 iterations but over 300 evaluation sweeps. Which one is cheaper depends on the problem and on how you evaluate.

Generalized policy iteration

Step back and look at the two algorithms side by side. Both alternate two processes that pull against each other:

                 evaluation:  make V consistent with π   (V → V^π)
          ┌───────────────────────────────────────────────────┐
          │                                                   ▼
          π                                                   V
          ▲                                                   │
          └───────────────────────────────────────────────────┘
                 improvement: make π greedy with respect to V

Evaluation makes the value function agree with the policy, and that usually makes the policy no longer greedy. Improvement makes the policy greedy, and that makes the value function out of date. Each step undoes some of the other’s work, yet together they converge to the only pair that is consistent both ways: $V^*$ and a greedy $\pi^*$. Policy iteration runs evaluation to convergence. Value iteration runs one sweep. Modified policy iteration runs $m$ sweeps, anything in between, and works for every $m$. Sutton and Barto call this whole family generalized policy iteration (GPI): any interleaving of (possibly partial) evaluation and (possibly partial) improvement.

The updates don’t even have to be organized into sweeps. Asynchronous DP backs up states one at a time, in any order, using the latest values (Gauss–Seidel taken to its logical end). It still converges as long as every state keeps getting updated. This frees you to spend computation where it matters. Prioritized sweeping updates first the states whose values are changing most. Real-time DP updates the states an agent actually visits as it moves through the world. That last idea, backing up the states along real experience, is a short step from the model-free learning of Chapter 5.

GPI is the pattern behind almost all of reinforcement learning, so it’s worth naming where each later algorithm puts its two halves:

Method	Evaluation	Improvement
Policy / value iteration (this chapter)	exact backups with the model	greedy argmax
SARSA, Q-learning (Ch 5)	sampled backups of $Q$	ε-greedy w.r.t. $Q$
DQN (Ch 6)	a neural $Q$ fitted to sampled backups	greedy w.r.t. the network
Actor-critic (Ch 8)	the critic learns $V^\pi$	a small policy-gradient step for the actor
PPO (Ch 9)	advantage estimates from a critic	a clipped, conservative policy step

What dynamic programming cannot do

DP is exact and elegant, and in practice you almost never get to use it directly. There are two reasons.

It needs the model. Every backup computes $\sum_{s'} P(s' \mid s,a)\, V(s')$, so you must know $P$ and $r$. A robot doesn’t know the physics of its gripper to that precision. A game-playing agent may know the rules but not the opponent. Usually all we can do is try things and see what happens. Chapter 5 replaces the expected backup with a backup from a single sampled transition, which turns DP into learning.

It needs to touch every state, every sweep. One sweep costs about $\lvert\mathcal S\rvert \times \lvert\mathcal A\rvert \times$ (number of possible next states). That is fine for 22 cells and not fine for interesting problems. A robot arm with 10 joints, each discretized into 100 positions, has $100^{10} = 10^{20}$ states. Backgammon has roughly $10^{20}$ positions, and Go about $10^{170}$. Bellman himself coined the name for this: the curse of dimensionality. The number of states grows exponentially with the number of variables that describe a state. Chapter 6 answers it with function approximation: instead of a table with one entry per state, a neural network that generalizes across similar states.

There is also a subtle requirement hiding in the math: $\gamma < 1$. With $\gamma = 1$, the operators are no longer contractions. Values can be infinite in tasks that never end, and the fixed point can stop being unique. Exercise 4.7 explores what goes wrong and what people do instead. Episodic tasks in which every policy eventually terminates are fine. LLM responses are of this kind, which is why LLM RL often uses $\gamma = 1$.

Summary

• The Bellman optimality equation $V^*(s) = \max_a [r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^*(s')]$ says that optimal value is the best one-step lookahead on optimal future value. It is the expectation equation with the average over actions replaced by a max, which makes it nonlinear.
• Acting greedily on $V^*$ (or taking the argmax of $Q^*$) is optimal, in every state at once, with a deterministic policy. Value functions turn long-horizon planning into one-step decisions.
• Iterative policy evaluation applies the expectation backup in sweeps. Information travels one step per sweep, like a relaxation method.
• Policy improvement theorem: acting greedily on $Q^\pi$ gives a policy at least as good everywhere, and strictly better somewhere unless $\pi$ is already optimal. Policy iteration alternates evaluation and improvement and ends in finitely many iterations.
• Value iteration is the optimality equation used as an update. It equals policy iteration with one evaluation sweep, and $V_k$ is the optimal $k$-step value. The greedy policy is often optimal long before the values converge.
• The Bellman operators are γ-contractions in the sup norm. By Banach’s theorem each has a unique fixed point, and iteration reaches it from any start, with error at most $\gamma^k$ times the initial error, which takes about $\ln(1/\epsilon)/(1-\gamma)$ sweeps.
• Generalized policy iteration (interleaved evaluation and improvement, in any proportion and any order) is the template for nearly every RL algorithm in this course, including the ones used to train LLMs.
• DP needs the model and touches every state. Chapter 5 removes the first requirement by sampling, and Chapter 6 tackles the second with function approximation.

Exercises

Exercise 4.1Linear or not?Concept●○○

(a) Which of these can you compute with a single linear solve, given $P$ and $r$: $V^\pi$ for a fixed stochastic policy; $Q^\pi$ for a fixed policy; $V^*$? Explain in one sentence each.

(b) A friend gives you $V^*$ for a gridworld but not the transition probabilities. Can you act optimally? What if they give you $Q^*$ instead?

Solution

(a) $V^\pi$: yes. The expectation equation $V = r_\pi + \gamma P_\pi V$ is linear, so $V^\pi = (I - \gamma P_\pi)^{-1} r_\pi$. $Q^\pi$: yes. Either compute $V^\pi$ first and then $Q^\pi(s,a) = r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^\pi(s')$, or solve the linear system $Q = r + \gamma P \Pi Q$ directly, where $\Pi$ averages over $\pi$. $V^*$: no. The optimality equation contains $\max_a$, which is piecewise linear but not linear, so there is no single matrix to invert. (You could solve it as a linear program, a classic alternative to DP, but not with one linear solve.)

(b) With only $V^*$, acting greedily requires the lookahead $\arg\max_a [r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^*(s')]$, which needs $P$ and $r$. So you can’t, unless you can simulate the environment. With $Q^*$ you just take $\arg\max_a Q^*(s,a)$, and no model is needed. $Q^*$ has the lookahead “built in”. That’s why model-free control (Q-learning, Chapter 5) learns $Q$.

I've done this one

Exercise 4.2Two sweeps of value iteration by handPen & paper●○○

Make the corridor slippery: every move succeeds with probability 0.8, and with probability 0.2 the agent stays where it is (reward 0). Exits pay +0.5 (left of A) and +1 (right of C) only when the move succeeds. Use $\gamma = 0.9$ and $V_0 = 0$.

(a) Write the one-step lookahead $Q(s,a)$ for all six state–action pairs in terms of $V$.

(b) Compute $V_1$ and $V_2$, and the max change after each sweep.

(c) What is the greedy policy with respect to $V_2$? Is it already optimal? (The exact $V^*$ is about $(0.752, 0.857, 0.976)$.)

Hint

For A going left: with probability 0.8 you exit and collect 0.5 (and the exit has value 0); with probability 0.2 you stay in A and are worth γ·V(A).

Solution

(a) Writing $V_A$ for $V(A)$ and so on:

• $Q(A,\text{L}) = 0.8 \cdot 0.5 + 0.2 \cdot 0.9 V_A = 0.4 + 0.18 V_A$
• $Q(A,\text{R}) = 0.9 (0.8 V_B + 0.2 V_A)$
• $Q(B,\text{L}) = 0.9 (0.8 V_A + 0.2 V_B)$
• $Q(B,\text{R}) = 0.9 (0.8 V_C + 0.2 V_B)$
• $Q(C,\text{L}) = 0.9 (0.8 V_B + 0.2 V_C)$
• $Q(C,\text{R}) = 0.8 \cdot 1 + 0.2 \cdot 0.9 V_C = 0.8 + 0.18 V_C$

(b) Sweep 1 ($V_0 = 0$): $V_1(A) = \max(0.4, 0) = 0.4$; $V_1(B) = \max(0, 0) = 0$; $V_1(C) = \max(0, 0.8) = 0.8$. So $V_1 = (0.4, 0, 0.8)$, max change $0.8$.

Sweep 2 (using $V_1$):

• A: L $= 0.4 + 0.18 \cdot 0.4 = 0.472$; R $= 0.9(0 + 0.2 \cdot 0.4) = 0.072$. So $V_2(A) = 0.472$.
• B: L $= 0.9(0.8 \cdot 0.4 + 0) = 0.288$; R $= 0.9(0.8 \cdot 0.8 + 0) = 0.576$. So $V_2(B) = 0.576$.
• C: L $= 0.9(0 + 0.2 \cdot 0.8) = 0.144$; R $= 0.8 + 0.18 \cdot 0.8 = 0.944$. So $V_2(C) = 0.944$.

$V_2 = (0.472, 0.576, 0.944)$, max change $= \max(0.072, 0.576, 0.144) = 0.576$ (at B).

(c) Greedy with respect to $V_2$:

• A: L $= 0.4 + 0.18 \cdot 0.472 = 0.485$; R $= 0.9(0.8 \cdot 0.576 + 0.2 \cdot 0.472) = 0.9 \cdot 0.555 = 0.500$. So A goes right.
• B: R $= 0.9(0.8 \cdot 0.944 + 0.2 \cdot 0.576) = 0.783 >$ L $= 0.9(0.8 \cdot 0.472 + 0.2 \cdot 0.576) = 0.443$. So B goes right.
• C: R $= 0.8 + 0.18 \cdot 0.944 = 0.970 >$ L. So C goes right.

So the greedy policy is already “always right”, which is optimal. At $V^* \approx (0.752, 0.857, 0.976)$, A’s right value $0.752$ beats left, $0.4 + 0.18 \cdot 0.752 = 0.535$. But $V_2(A) = 0.472$ is still far from $0.752$. Once again the policy is right before the values are. (The decision at A is close at $V_2$: 0.500 vs 0.485. One sweep earlier, A would still have chosen left.)

I've done this one

Exercise 4.3The expectation operator is a contractionPen & paper●●○

(a) Prove that $\lVert \mathcal{T}^\pi U - \mathcal{T}^\pi V \rVert_\infty \le \gamma \lVert U - V \rVert_\infty$.

(b) Prove that $\mathcal{T}^\pi$ is monotone: $U \le V$ componentwise implies $\mathcal{T}^\pi U \le \mathcal{T}^\pi V$.

(c) For $\gamma = 1$, give a one-state MDP in which $\mathcal{T}^\pi$ has infinitely many fixed points.

Hint

Write $(\mathcal{T}^\pi U - \mathcal{T}^\pi V)(s)$ as γ times a weighted average of $U(s') - V(s')$. What are the weights, and what do they sum to?

Solution

(a) The rewards cancel:

$$(\mathcal{T}^\pi U - \mathcal{T}^\pi V)(s) = \gamma \sum_{s'} w_s(s') \big(U(s') - V(s')\big), \qquad w_s(s') = \sum_a \pi(a \mid s) P(s' \mid s,a).$$

The weights $w_s(s')$ are nonnegative and $\sum_{s'} w_s(s') = \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s,a) = 1$. So the absolute value is at most $\gamma \sum_{s'} w_s(s') \lvert U(s') - V(s') \rvert \le \gamma \max_{s'} \lvert U(s') - V(s') \rvert = \gamma \lVert U - V \rVert_\infty$. Take the max over $s$.

(b) If $U \le V$, every term $w_s(s')(V(s') - U(s'))$ is $\ge 0$, so $(\mathcal{T}^\pi V - \mathcal{T}^\pi U)(s) \ge 0$ for every $s$.

(c) One state $s$, one action that loops back to $s$ with reward 0, and $\gamma = 1$. Then $(\mathcal{T}^\pi V)(s) = 0 + 1 \cdot V(s) = V(s)$ for every number $V(s)$, so every vector is a fixed point. The “contraction” factor is 1, and Banach’s theorem says nothing. With $\gamma < 1$ the only fixed point is $V(s) = 0$.

I've done this one

Exercise 4.4Policy iteration terminatesPen & paper●●○

Prove that policy iteration, with the rule “switch an action only if the new one is strictly better”, stops after at most $\lvert\mathcal A\rvert^{\lvert\mathcal S\rvert}$ iterations, and that the final policy is optimal. Then explain what could go wrong without the “strictly better” rule.

Hint

Show that the sequence of value functions $V^{\pi_0}, V^{\pi_1}, \dots$ is strictly increasing (in the componentwise partial order) until the policy stops changing. What does that imply about repeats?

Solution

Let $\pi_{k+1}$ be the improved version of $\pi_k$. In every state, $\pi_{k+1}(s)$ is either $\pi_k(s)$, with $Q^{\pi_k}(s, \pi_{k+1}(s)) = V^{\pi_k}(s)$, or a strictly better action, with $Q^{\pi_k}(s, \pi_{k+1}(s)) > V^{\pi_k}(s)$. By the policy improvement theorem, $V^{\pi_{k+1}} \ge V^{\pi_k}$ everywhere. If at least one state switched, the inequality is strict in that state, so $V^{\pi_{k+1}} \ne V^{\pi_k}$.

So while the policy keeps changing, the value functions form a strictly increasing sequence: each is $\ge$ the previous one everywhere and $>$ somewhere. A policy can’t appear twice. If $\pi_j = \pi_k$ with $j < k$, then $V^{\pi_j} = V^{\pi_k}$, contradicting strict increase along $j, j+1, \dots, k$. There are only $\lvert\mathcal A\rvert^{\lvert\mathcal S\rvert}$ deterministic policies, so after at most that many iterations no state switches.

When no state switches, no action beats the current one: $\max_a Q^{\pi}(s,a) = Q^\pi(s, \pi(s)) = V^\pi(s)$ for all $s$. That is the Bellman optimality equation, whose unique solution is $V^*$. So $V^\pi = V^*$ and $\pi$ is optimal.

Without the strict rule, take a state with two actions that are exactly tied in true value. Computed values carry round-off (or come from evaluation stopped at a tolerance), so the argmax can pick action 1 in one iteration and action 2 in the next, then back again. The value never changes, but the policy keeps changing, so “stop when the policy is stable” never fires. The strict rule (switch only if better by more than a tiny threshold) breaks the tie in favor of the incumbent. The lab’s policy_iteration uses a threshold of $10^{-9}$.

I've done this one

Exercise 4.5When can you stop?Pen & paper●●○

(a) Prove that for value iteration $V_{k+1} = \mathcal{T}^* V_k$,

$$\lVert V_{k+1} - V^* \rVert_\infty \le \frac{\gamma}{1-\gamma} \lVert V_{k+1} - V_k \rVert_\infty.$$

(b) With $\gamma = 0.99$, how small must the observed change $\lVert V_{k+1} - V_k \rVert_\infty$ be to guarantee that $V_{k+1}$ is within $0.01$ of $V^*$ in every state?

Hint

Start from $\lVert V_{k+1} - V^* \rVert = \lVert \mathcal{T}^* V_k - \mathcal{T}^* V^* \rVert$, use the contraction, then insert $V_{k+1}$ with the triangle inequality.

Solution

(a) Using $V^* = \mathcal{T}^* V^*$, the contraction, and the triangle inequality:

$$\lVert V_{k+1} - V^* \rVert \le \gamma \lVert V_k - V^* \rVert \le \gamma \big( \lVert V_k - V_{k+1} \rVert + \lVert V_{k+1} - V^* \rVert \big).$$

Move the $\gamma \lVert V_{k+1} - V^* \rVert$ term to the left: $(1-\gamma) \lVert V_{k+1} - V^* \rVert \le \gamma \lVert V_{k+1} - V_k \rVert$. Divide by $1 - \gamma > 0$.

(b) We need $\frac{0.99}{0.01} \Delta \le 0.01$, i.e. $\Delta \le 0.01 \cdot 0.01 / 0.99 \approx 1.0 \times 10^{-4}$. The change must be a hundred times smaller than the accuracy you want. When $\gamma$ is near 1, a small change between sweeps doesn’t yet mean you are close: the values may be creeping slowly toward something far away.

I've done this one

Exercise 4.6The policy converges before the valuesPen & paper●●●

Let $\Delta = \min_s \big( \max_a Q^*(s,a) - \max_{a \notin \mathcal{A}^*(s)} Q^*(s,a) \big)$ be the smallest gap between the best and the second-best action value in any state, where $\mathcal{A}^*(s)$ is the set of optimal actions in $s$ (ignore states where every action is optimal).

(a) Show that if $\lVert V - V^* \rVert_\infty < \Delta / (2\gamma)$, then every greedy action with respect to $V$ is optimal.

(b) Compute $\Delta$ for the corridor with $\gamma = 0.9$. How close to $V^*$ does (a) require $V$ to be? Compare with $V_2 = (0.5, 0.9, 1)$ from the value-iteration table, whose greedy policy is already optimal. What does this tell you about the bound?

Hint

Write $Q_V(s,a) = r(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V(s')$. Bound $\lvert Q_V(s,a) - Q^*(s,a) \rvert$ in terms of $\lVert V - V^* \rVert_\infty$.

Solution

(a) For every $s, a$: $\lvert Q_V(s,a) - Q^*(s,a) \rvert = \gamma \lvert \sum_{s'} P(s' \mid s,a)(V(s') - V^*(s')) \rvert \le \gamma \lVert V - V^* \rVert_\infty < \Delta/2$. Take an optimal action $a^\star$ and a non-optimal action $b$ in state $s$. Then $Q^*(s,a^\star) - Q^*(s,b) \ge \Delta$, and so

$$Q_V(s,a^\star) > Q^*(s,a^\star) - \tfrac{\Delta}{2} \ge Q^*(s,b) + \tfrac{\Delta}{2} > Q_V(s,b).$$

Every optimal action scores strictly higher under $Q_V$ than every non-optimal one, so the argmax of $Q_V$ is an optimal action.

(b) From the guess-and-check table, the gaps are: A: $0.81 - 0.5 = 0.31$; B: $0.9 - 0.729 = 0.171$; C: $1 - 0.81 = 0.19$. So $\Delta = 0.171$, and (a) requires $\lVert V - V^* \rVert_\infty < 0.171 / 1.8 \approx 0.095$. But $V_2$ has error $0.81 - 0.5 = 0.31$ at A, more than three times larger, and its greedy policy is still optimal. The condition is sufficient but not necessary. It guards against the worst case, where all the error lands on exactly the wrong actions. In typical problems the errors are correlated and largely cancel in the comparison between actions. You saw this in the demo and in the lab’s FrozenLake plot.

I've done this one

Exercise 4.7What goes wrong with γ = 1 in a continuing task?Concept●●○

Consider a continuing task (no terminal states) with $\gamma = 1$.

(a) Two states, X and Y. One action moves X → Y and Y → X, with reward +1 each step. What does value iteration from $V_0 = 0$ produce?

(b) Same states, but the rewards are 0. What are the solutions of the Bellman equation?

(c) Why does the corridor still work with $\gamma = 1$? What do people do for genuinely continuing tasks?

Hint

For (a) and (b), write out the Bellman equation for each state with $\gamma = 1$ and run two or three sweeps by hand. For (c), ask whether the optimal corridor policy ever runs forever, and what its return is.

Solution

(a) $V_k(X) = V_k(Y) = k$: each sweep adds 1. The values diverge, because the return is an infinite sum of +1s. There is no finite fixed point to converge to.

(b) The equations are $V(X) = V(Y)$ and $V(Y) = V(X)$, so every vector $(c, c)$ is a solution. The fixed point exists but is not unique. Iteration from $V_0$ stays at $V_0$ forever, so the answer depends on where you started. Both failures are what Exercise 4.3(c) predicts: with $\gamma = 1$ the operator is not a strict contraction.

(c) In the corridor, every sensible policy reaches an exit and the episode ends, so returns are finite sums. Some policies bounce between A and B forever, but they collect 0 and are never optimal, since rewards are nonnegative and exits are reachable. For episodic problems in which the optimal policy terminates and non-terminating policies are bad (sometimes called stochastic shortest-path problems), value iteration with $\gamma = 1$ still converges, though the proof is more delicate. Value iteration on the corridor at $\gamma = 1$ gives $V^* = (1, 1, 1)$ in 3 sweeps. For truly continuing tasks the standard options are: use $\gamma < 1$ (and accept that it changes the objective), or switch to the average-reward formulation, which optimizes the long-run reward per step and uses a “differential” value function relative to that average (Sutton & Barto, section 10.3).

I've done this one

Exercise 4.8Read the demo: risk, patience and hasteExplore the demo●○○

In the demo, use value iteration and press Play after each change (press Restore grid first).

(a) With slip 0, read the value of the cell in row 3, column 1. Explain the number exactly.

(b) Raise slip to 0.3. Which way do the arrows in row 3 (beside the pits) point now? And in the bottom row? Explain both.

(c) Keep slip at 0.3 and set the reward per step to −0.1. What happens to the route, and why?

(d) Set γ to 0.5 (slip 0.1, step reward 0). Why do most cells look almost uncolored, with values near 0?

Solution

(a) $0.656 = 0.9^4$. The shortest route is 5 moves (along row 3 to the goal), the +1 arrives on the 5th move, and the reward on move $j$ is discounted by $\gamma^{j-1}$.

(b) Each move along row 3 or row 5 has a 15% chance of slipping sideways into a pit, which costs $-1$ plus the lost goal. The policy now avoids those moves wherever it can.

• Row 3: four of the five arrows point up. Cell (3,1) leaves the pit-lined row and takes the long route up the left column and along the top row. The detour costs only a few extra steps of discounting. Cell (3,5) steps up out of the row before turning toward the goal. Cells (3,2) and (3,3) sit under the wall, so “up” bumps into it and never moves them up. Its slips, though, move them left or right along the row, and a slip can never send them down into a pit. Only cell (3,4) still risks walking right.
• Row 5 (bottom): the middle four arrows point down, into the edge. The same trick applies: “down” never succeeds, its sideways slips move you along the row, and you can never slip up into a pit. The agent drifts randomly along the row until it reaches a corner column, where going up is safe.

Pushing into a wall on purpose, so that only harmless slips can move you, is a clever, slightly absurd strategy. The agent discovered it from the equations alone.

(c) The route goes back to running straight along the pits. With a cost of $-0.1$ per step, the long detour costs more in step penalties than the pit risk does, so haste wins. Values also become negative far from the goal. The optimal policy depends on the whole reward function, which is why reward design matters so much (Chapter 19 is about what happens when it goes wrong).

(d) With $\gamma = 0.5$ the effective horizon is about 2 steps. A reward 5 steps away is worth $0.5^4 \approx 0.06$ even with no slipping; with slip it’s about 0.002. Far cells barely “see” the goal, and the agent is very myopic. Values also converge fast, in about 16 sweeps, because the contraction factor is small.

I've done this one

Exercise 4.9Read the demo: contraction and the two algorithmsExplore the demo●●○

(a) With the defaults, press Play. At which sweep do the arrows stop changing, and when does value iteration stop? Is the solid curve of max changes above or below the dashed $\gamma^k$ line? Why is that allowed?

(b) Press Random start a few times and play to convergence. What is the same every time, and which theorem promised it?

(c) Set γ to 0.99 and play (raise the speed). Compare the number of sweeps with the bound from the text, which says about 1,375 sweeps are needed to shrink the error by $10^{-6}$.

(d) Switch to Policy iteration with the defaults and play. Compare iterations and evaluation sweeps with value iteration’s sweep count. Which one did less total work here?

Hint

For (a) and (c), reread the note “Why the demo’s curve falls faster than the dashed line”.

Solution

(a) The arrows freeze at sweep 10, and value iteration stops after 24 sweeps (max change below $10^{-6}$). The solid curve lies on or below the dashed line. The contraction gives only an upper bound. Here the error shrinks faster, because probability leaks into the terminal goal and pits at every step (the effective rate is $\gamma\rho$ with $\rho < 1$).

(b) The final values and arrows are identical every time. Banach’s theorem says $\mathcal{T}^*$ has a unique fixed point and that iteration reaches it from any start. The first deltas are larger (the random start is far from $V^*$), but the slope on the log plot is the same.

(c) It takes about 90 sweeps, far fewer than 1,375. The bound assumes the worst case, a state from which you never terminate. Here every good path ends at the goal quickly, so the error decays at the rate $\gamma\rho$, not $\gamma$. Problems with long or endless trajectories do approach the bound.

(d) Policy iteration stabilizes after 8 iterations, but those iterations use a little over 300 evaluation sweeps in total (each evaluation is warm-started from the previous values and run to a tight tolerance). Value iteration needs 24 sweeps. On this small, quickly-mixing grid, value iteration does less work. Policy iteration wins when evaluation is cheap relative to the number of iterations saved, for example when you can evaluate by an exact linear solve on a modest number of states, or when convergence is slow because γ is near 1. Modified policy iteration, with a few evaluation sweeps per improvement, sits between the two.

I've done this one

Exercise 4.10Code: the three DP algorithmsCode●●○

In the lab (exercises/04-dynamic-programming/), fill in dp.py:

1. Task 1 q_from_v(P, R, V, gamma): the one-step lookahead.
2. Task 2 policy_evaluation(P, R, policy, gamma): synchronous sweeps until the max change is below tol.
3. Task 3 greedy_policy(P, R, V, gamma): one-hot argmax policy.
4. Task 4 value_iteration(P, R, gamma): returns V, the greedy policy, and the per-sweep max changes.
5. Task 5 policy_iteration(P, R, gamma): evaluate, improve with the strict-improvement rule, stop when stable.

The tests check the corridor tables from this chapter (including the value-iteration deltas [1.0, 0.9, 0.31, 0.0] and the policy sequence LLL → LLR → LRR → RRR). They also check the contraction property, convergence from a random start, and agreement with a brute-force search over all 256 policies of a tiny slippery grid. Then run python run.py to solve the slippery 8×8 FrozenLake and plot convergence for three values of γ.

Hint

With arrays P of shape (S, A, S) and V of shape (S,), P @ V has shape (S, A). Policy evaluation is then (policy * q_from_v(...)).sum(axis=1), and value iteration replaces the weighted sum with .max(axis=1).

Solution

The reference is in solutions/dp.py. Here are the key lines.

• Task 1 is one line: return R + gamma * (P @ V).
• Task 2 loops V_new = (policy * q_from_v(P, R, V, gamma)).sum(axis=1). It computes delta = np.max(np.abs(V_new - V)), replaces V, and breaks when delta < tol. Computing the whole V_new before replacing V is what makes it synchronous. The test test_task2_policy_evaluation_is_synchronous checks that after one sweep only A has a value.
• Task 3: best = np.argmax(q_from_v(...), axis=1), then set policy[np.arange(S), best] = 1.
• Task 4 is Task 2 with .max(axis=1) in place of the policy-weighted sum, appending each delta to deltas.
• Task 5: evaluate; compute Q; current = argmax(policy), best = argmax(Q); switch = Q[rows, best] > Q[rows, current] + 1e-9. If nothing switches, stop; otherwise use np.where(switch, best, current) as the new actions.

run.py with the reference solution reports $V^*(\text{start}) \approx 0.415$ for 8×8 FrozenLake at $\gamma = 0.99$. Value iteration takes 662 sweeps to reach a change of $10^{-10}$, though its greedy policy is optimal from sweep 127. Policy iteration needs 10 evaluations. The middle panel shows the optimal policy often aiming away from holes, preferring to slide along a safe row than to risk the ice next to a hole.

I've done this one

Further reading

• Sutton & Barto (2018), Reinforcement Learning: An Introduction, ch. 4. The standard treatment of DP for RL, with the gambler’s problem and Jack’s car rental as extra worked examples. Section 4.6 is the origin of the term “generalized policy iteration”.
• David Silver (2015), UCL RL course, lecture 3: Planning by Dynamic Programming. Slides and video. A compact second explanation of this chapter, including the contraction argument.
• Agarwal, Jiang, Kakade & Sun (2019–2022), Reinforcement Learning: Theory and Algorithms. Free book; its first chapter proves this chapter’s results crisply, with convergence rates for both value and policy iteration. Read it when you want the theory to research standard.
• Puterman (1994), Markov Decision Processes: Discrete Stochastic Dynamic Programming. The reference for MDP theory: optimality of deterministic Markov policies, modified policy iteration, average-reward criteria, and policy iteration as Newton’s method.
• Bertsekas (2019), Reinforcement Learning and Optimal Control. DP from the control-theory side, with a strong emphasis on approximation in value and policy space, which bridges to Chapters 6–9.
• Szepesvári (2010), Algorithms for Reinforcement Learning. A short, mathematically tidy monograph (free PDF). Its opening chapter covers MDPs, Bellman operators and their contraction properties in a few dense pages.

Next, in Chapter 5, we throw away the model: the agent can only act and observe. You’ll see that TD learning and Q-learning are this chapter’s backups, run on single sampled transitions instead of full expectations.