Planning with a Model

Introduction

In the previous part, we laid the foundations of reinforcement learning: you now have the tools to describe a decision problem and to say what an optimal solution to it is.

This second part is about planning with a model: evaluating a policy, or finding the best one, in an environment with rules we know. This applies to problems such as video games, chess or Go, and it is a crucial step before learning from experience, without a model, which is the real goal of reinforcement learning.

Where Part 1 left us

Part 1, Modeling the World gave us the basics: an agent in state $S_t$ takes an action $A_t$ , receives a reward $R_{t+1}$ and lands in $S_{t+1}$ , according to the dynamics of the Markov Decision Process (MDP), $p(s', r \mid s, a)$ .

The agent wants to maximize the return, recursively defined by the relation $G_t = R_{t+1} + \gamma\, G_{t+1}$ , or in full, as the discounted sum of all the rewards to come:

G_t = R_{t+1} + \gamma\, R_{t+2} + \gamma^2 R_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}

To evaluate how good a state or a state-action pair is, we defined helper functions: the value functions score states and actions under a policy $\pi$ ,

v_\pi(s) \doteq \mathbb{E}_\pi[G_t \mid S_t = s], \qquad q_\pi(s, a) \doteq \mathbb{E}_\pi[G_t \mid S_t = s, A_t = a],

and their optimal counterparts $v_*(s) = \max_\pi v_\pi(s)$ and $q_*(s, a) = \max_\pi q_\pi(s, a)$ . The state values satisfy the Bellman equations, one per state:

\begin{aligned} v_\pi(s) &= \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)\,\big[r + \gamma\, v_\pi(s')\big] \\ v_*(s) &= \max_a \sum_{s', r} p(s', r \mid s, a)\,\big[r + \gamma\, v_*(s')\big] \end{aligned}

On the four-state altitude map, Part 1 solved these by hand, as a system of equations.

This page teaches you how to solve them on any finite MDP, with algorithms that only need the model $p$ and the recursive structure of these equations. We will study:

Dynamic programming and policy evaluation: computing the value of a policy.
Policy iteration: finding the best policy in three steps: evaluate, improve, repeat.
Value iteration: a shortcut to the optimal behavior: optimize directly, one sweep at a time.
Taking a step back: the pattern behind all three, generalized policy iteration, and why the optimal policy is not unique.

Part 3 will remove the model: Part 3.1, Learning from Experience, with Monte Carlo methods and temporal-difference learning, then Part 3.2, Learning to Act, with SARSA and Q-learning, learn the same values from sampled interactions only. Everything they do is an approximation at scale of what this page computes exactly.

1. Evaluating a policy via dynamic programming

To be able to find an optimal policy, we first need to be able to compare policies. Policy evaluation is the computation of the value function of a policy, in every state. When a model is available, the main technique to do so is to use dynamic programming.

1.1 What dynamic programming is

Dynamic programming (DP) solves a complex problem by breaking it into simpler subproblems, storing their solutions, and reusing them instead of computing them again. Here, “dynamic” refers to the sequential, temporal side of the problem. It applies when a problem has two properties:

optimal substructure: an optimal solution is made of optimal solutions of subproblems;
overlapping subproblems: the same subproblems come back many times, so their solutions are worth caching.

MDPs have both. The Bellman equation is the decomposition link: the value of a state is one step plus the value of the next state. And the value function is the cache: one number per state, computed once, reused by every state that leads there.

The first property has a name in this setting, the principle of optimality:

Principle of optimality

A policy is optimal from a state $s$ if and only if it is optimal from every state $s'$ it can reach from $s$ .

Once the hiker of Part 1 has reached $A$ , whatever happened before, the best the hiker can do is to behave optimally from $A$ . The problem splits into a first step and a smaller problem from the next state, which is exactly the Bellman optimality equation.

DP assumes full knowledge of the MDP: the states, the actions, the dynamics $p$ and $\gamma$ . It is a planning method, used for both problems of section 4.3 of Part 1:

Prediction/evaluation: given the MDP and a policy $\pi$ , compute $v_\pi$ ;
Control: given the MDP, compute $v_*$ and an optimal policy $\pi_*$ .

1.2 Iterative policy evaluation

The Bellman expectation equation gives $|\mathcal{S}|$ linear equations for the $|\mathcal{S}|$ values $v_\pi(s)$ . We could solve the system directly, but that costs about $|\mathcal{S}|^3$ operations, too much for large state spaces.

Instead, we turn the equation into an update rule, and apply it again and again. Starting from any $v_0$ , for instance $0$ everywhere, and computing, for every state,

v_{k+1}(s) = \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)\, \big[ r + \gamma\, v_k(s') \big]

One pass over all the states is a sweep. Each sweep replaces the value of every state by a one-step look-ahead on the current values, a Bellman backup, and the sequence $v_0, v_1, v_2, \dots$ converges to $v_\pi$ . In practice, we stop when the largest change of a sweep, $\Delta$ , falls below a small threshold $\theta$ :

Algorithm Iterative policy evaluation

Input: a policy $\pi$ , a threshold $\theta > 0$

$v(s) \leftarrow 0$ for every state $s$
repeat
- $\Delta \leftarrow 0$
- for each state $s$ $s$
  - $v_{\text{old}} \leftarrow v(s)$
  - $v(s) \leftarrow \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \big[ r + \gamma\, v(s') \big]$
  - $\Delta \leftarrow \max\big(\Delta, |v(s) - v_{\text{old}}|\big)$
until $\Delta < \theta$

One sweep costs about $|\mathcal{S}|^2 |\mathcal{A}|$ operations: every state, every action, every next state, but we don’t know how many sweeps are required to converge.

Main example of this lesson: A $4 \times 4$ grid with states $0$ to $15$ , numbered row by row; the corners $0$ and $15$ are terminal. Four actions, up, down, left, right, deterministic; an action that would leave the grid leaves the agent in place. Every step costs $r = -1$ , $\gamma = 1$ , and the policy we study is the equiprobable random one, $\pi(a \mid s) = \frac14$ .

The gridworld of Example 4.1

States 0 to 15, row by row; the corners 0 and 15 are terminal
↑↓Actions up, down, left, right, deterministic (state 9)
↺An action that would leave the grid leaves the agent in place (state 7, right)
−1Reward r = −1 on every step, γ = 1: the return of an episode is minus its number of steps
¼Policy π: the random one, each action with probability ¼

Grey: the two terminal corners. The arrows show the four actions from state 9, and, from state 7, a move right that would leave the grid and leaves the agent in place.

Starting the policy evaluation from $v_0 = 0$ : after one sweep, every non-terminal state is worth $-1$ , the reward of one step, whatever happens later. For state $1$ , next to the terminal corner:

\begin{aligned} v_1(1) &= \tfrac14 \big[ (-1 + v_0(1)) + (-1 + v_0(5)) \\ &\qquad + (-1 + v_0(0)) + (-1 + v_0(2)) \big] = -1 \end{aligned}

After two sweeps, the states next to a terminal corner are worth $-1.75$ (one of their four moves ends the episode) and the others $-2$ . The values keep spreading from the corners, sweep after sweep, up to convergence:

The random policy, evaluated sweep by sweep

Top: the values v_k of the random policy after k sweeps (two arrays), on one color scale for every grid, darker when more negative; the grey corners are terminal. Bottom: the same values, each grid shaded against itself, from its highest to its lowest value. The numbers keep falling up to k = ∞, but from k = 4 the bottom grids barely change: the order between the states is final.

To what values does $v_\pi(s)$ converge? Take a few seconds to think about it.

Answer Open once you have a guess

$v_\pi(s)$ is minus the expected number of steps a random walker needs to fall into a corner: $22$ steps on average from the far corners, although they are only $3$ steps from a terminal state.

The values take a long time to fully settle: about $220$ sweeps to get within $10^{-4}$ of the true $v_\pi$ , the far corners going from $-4$ after $4$ sweeps to $-22$ . However, note that the comparisons between states settle much faster: from $k = 4$ , every state that is better than another under $v_\pi$ is already better under $v_k$ . Keep this in mind for sections 2 and 3.

These large negative values say little about the task: they measure the cost of acting at random. Finding the optimal cost is the job of the next step: improving the policy.

2. Policy iteration: evaluate, improve, repeat

Evaluating a policy is a great step forward, but our true goal is to find the best policy, or one of the best: this is what policy iteration is about.

2.1 Improving a policy

Once we know $v_\pi$ , we can measure what happens if, in one state $s$ , we make a different choice and take a different action $a$ than the policy would, then follow $\pi$ again. That is exactly $q_\pi(s, a)$ , and it follows from $v_\pi$ in one step:

q_\pi(s, a) = \sum_{s', r} p(s', r \mid s, a)\, \big[ r + \gamma\, v_\pi(s') \big]

On the gridworld of section 1.2, under the random policy, moves are deterministic so the sum shrinks and $q_\pi(s, a) = -1 + v_\pi(s'_a)$ , where $s'_a$ is the cell reached by $a$ . Moving down from state $11$ ends the episode, and a terminal state is worth $0$ : $q_\pi(11, \text{down}) = -1 + 0 = -1$ . Moving down from state $7$ lands in state $11$ : $q_\pi(7, \text{down}) = -1 + (-14) = -15$ .

Same first action, but very different values, because $q_\pi$ scores one step of your choice followed by the random policy: from $11$ , that one step ends the episode; from $7$ , it hands the agent back to $14$ more random steps, on average.

q_\pi(7, \text{down}) = \underbrace{-1}_{\substack{\text{one step,} \\ \text{your choice}}} + \underbrace{v_\pi(11)}_{\substack{\text{then } \pi \text{ from } 11 \\ \text{until a corner}}} = -1 + (-14) = -15

The figure below starts with a simpler policy than the random one, up, then left, whose path is easy to follow: there, $q_\pi(7, \text{down}) = -6$ . Switch it to random to find the $-15$ above, as the average of many episodes.

One action of your choice, then the policy

The values v_π of a policy π. By default, π is a fixed policy, easy to follow: up, then left along the top row (small arrows). The orange arrow is the action a, chosen once; from there, the walker follows π (green trail) until it reaches a corner. q_π(s, a) is −1 for the chosen step plus v_π of the cell reached. Switch π to random for the policy of the text: every episode is then different, and q_π is the average of their returns.

The figure already holds the idea of this section. Under the random policy, state $7$ is worth $v_\pi(7) = -20$ ; going down first, then acting at random, is worth $q_\pi(7, \text{down}) = -15$ .

One better choice, made once, saves five steps on average. In general, if $q_\pi(s, a) > v_\pi(s)$ , taking $a$ in $s$ is better than following $\pi$ there (both are expected returns from $s$ ). Changing the policy in that one state should help, but is this always the case, in any order we proceed? The policy improvement theorem says that it is, even when we change it in every state at once.

Policy improvement theorem

Let $\pi$ and $\pi'$ be two deterministic policies such that, for every state $s$ ,

q_\pi(s, \pi'(s)) \ge v_\pi(s).

Then $\pi'$ is at least as good as $\pi$ : $v_{\pi'}(s) \ge v_\pi(s)$ for every $s$ .

The natural candidate here is what we call the greedy policy, which picks in every state the action with the best return one step ahead:

\begin{aligned} \pi'(s) &= \arg\max_a q_\pi(s, a) \\ &= \arg\max_a \sum_{s', r} p(s', r \mid s, a)\, \big[ r + \gamma\, v_\pi(s') \big] \end{aligned}

It satisfies the hypothesis of the theorem by construction. In every state, $v_\pi(s)$ is an average of the action values, weighted by the policy, and a max is at least an average:

q_\pi(s, \pi'(s)) = \max_a q_\pi(s, a) \;\ge\; \sum_a \pi(a \mid s)\, q_\pi(s, a) = v_\pi(s)

So greedifying never hurts.

When does it stop helping? Only when the policy is already optimal:

Optional A stable policy is optimal: why greedifying changes nothing only at the optimum Math needed Compute: arithmetic, a small linear system, applying a formula of the pageend of high school Reason: expectations, inequalities, an argument in words: no new tools, but a chain of reasoningfirst year of university, with a first course in probability Prove: induction, limits, norms, fixed points: a proof, which can be skipped on a first readingabout two years of university math The level says which math is needed, not how long it takes.

If $\pi'$ is only as good as $\pi$ , $v_{\pi'} = v_\pi$ , write the Bellman equation of $v_{\pi'}$ , one step with $\pi'$ , then replace $v_{\pi'}$ by $v_\pi$ :

v_\pi(s) = v_{\pi'}(s) = \sum_{s', r} p(s', r \mid s, \pi'(s))\, \big[ r + \gamma\, v_\pi(s') \big] = \max_a q_\pi(s, a)

In every state, $v_\pi(s) = \max_a \sum_{s', r} p(s', r \mid s, a)\, [r + \gamma\, v_\pi(s')]$ : $v_\pi$ satisfies the Bellman optimality equation, so $v_\pi = v_*$ , and $\pi$ was already optimal.

Exercise 2.1 Proof of the policy improvement theorem Math needed Compute: arithmetic, a small linear system, applying a formula of the pageend of high school Reason: expectations, inequalities, an argument in words: no new tools, but a chain of reasoningfirst year of university, with a first course in probability Prove: induction, limits, norms, fixed points: a proof, which can be skipped on a first readingabout two years of university math The level says which math is needed, not how long it takes.

Let $\pi$ and $\pi'$ be two deterministic policies with $q_\pi(s, \pi'(s)) \ge v_\pi(s)$ in every state. The idea is to unroll the hypothesis: apply it at $s$ , then at the next state, then at the one after, each time taking one more step with $\pi'$ instead of $\pi$ .

Show that $q_\pi(s, \pi'(s)) = \mathbb{E}_{\pi'}\big[ R_{t+1} + \gamma\, v_\pi(S_{t+1}) \mid S_t = s \big]$ . Why can the expectation be taken under $\pi'$ , although $q_\pi$ is defined with $\pi$ ?
Apply the hypothesis at $S_{t+1}$ , and show that $v_\pi(s) \le \mathbb{E}_{\pi'}\big[ R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) \mid S_t = s \big]$ .
Show by induction that, for every $n \ge 1$ ,
$v_\pi(s) \le \mathbb{E}_{\pi'}\big[ R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1} R_{t+n} + \gamma^n v_\pi(S_{t+n}) \mid S_t = s \big]$
Let $n \to \infty$ and conclude that $v_\pi(s) \le v_{\pi'}(s)$ . What is needed for the last term to vanish?

Hint

Question 1: $q_\pi(s, a)$ fixes the first action, then follows $\pi$ . $R_{t+1}$ and $S_{t+1}$ only depend on that first action, and drawing it from the deterministic $\pi'$ means taking $\pi'(s)$ .

Hint

Question 2: in the expectation of question 1, bound $v_\pi(S_{t+1})$ by $q_\pi(S_{t+1}, \pi'(S_{t+1}))$ , and use question 1 again, at $S_{t+1}$ . The inequality survives because $\gamma \ge 0$ .

Hint

Question 4: the tail is $\gamma^n\, \mathbb{E}_{\pi'}[v_\pi(S_{t+n})]$ . When is $v_\pi$ bounded? What if $\gamma = 1$ ?

Checkpoint what you should get

Each application of the hypothesis hands one more step to $\pi'$ ; when $\gamma^n\, \mathbb{E}_{\pi'}[v_\pi(S_{t+n})] \to 0$ , the right-hand side tends to $\mathbb{E}_{\pi'}[G_t \mid S_t = s] = v_{\pi'}(s)$ .

Solution

The whole chain, one line per application of the hypothesis:

\begin{aligned} v_\pi(s) &\le q_\pi(s, \pi'(s)) \\ &= \mathbb{E}_{\pi'}\big[ R_{t+1} + \gamma\, v_\pi(S_{t+1}) \mid S_t = s \big] \\ &\le \mathbb{E}_{\pi'}\big[ R_{t+1} + \gamma\, q_\pi(S_{t+1}, \pi'(S_{t+1})) \mid S_t = s \big] \\ &= \mathbb{E}_{\pi'}\big[ R_{t+1} + \gamma R_{t+2} + \gamma^2 v_\pi(S_{t+2}) \mid S_t = s \big] \\ &\ \ \vdots \\ &\le \mathbb{E}_{\pi'}\big[ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \mid S_t = s \big] = v_{\pi'}(s) \end{aligned}

The second line is where $\pi'$ enters: $q_\pi(s, \pi'(s))$ conditions on the action $\pi'(s)$ , which is the same as drawing the first action from $\pi'$ . After that first step, $v_\pi(S_{t+1})$ still follows $\pi$ .
The third line applies the hypothesis at $S_{t+1}$ , and multiplying by $\gamma \ge 0$ keeps the inequality. The fourth line is question 1 at $S_{t+1}$ : the second action is now drawn from $\pi'$ too.
Each repetition of questions 1 and 2 replaces $\gamma^k v_\pi(S_{t+k})$ by $\gamma^k R_{t+k+1} + \gamma^{k+1} v_\pi(S_{t+k+1})$ , with one more action drawn from $\pi'$ : this is the induction step.
The sum of the rewards tends to the return $G_t$ of $\pi'$ , whose expectation is $v_{\pi'}(s)$ , if the tail $\gamma^n\, \mathbb{E}_{\pi'}[v_\pi(S_{t+n})]$ vanishes: true for $\gamma < 1$ with bounded rewards, since $v_\pi$ is then bounded, or, with $\gamma = 1$ , when $\pi'$ ends the episode with probability 1, since the value of a terminal state is $0$ .

What to notice the take-away

Each line hands one more step from $\pi$ to $\pi'$ , and the hypothesis guarantees that each hand-over can only help. Nothing requires $\pi'$ to be greedy: any policy that does at least as well as $\pi$ one step ahead, in every state, does at least as well for good.

2.2 Policy iteration

Policy iteration alternates the two steps until the policy stops changing:

Evaluate the current policy: compute $v_\pi$ , with the sweeps of section 1.2.
Improve it: make it greedy with respect to $v_\pi$ .
Repeat until the policy is stable: $\pi' = \pi$ .

Algorithm Policy iteration

initialize $\pi$ arbitrarily
repeat
- policy evaluation
  - repeat for each state $s$ $s$
    - $v(s) \leftarrow \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a) \big[ r + \gamma\, v(s') \big]$
  - until convergence
- policy improvement
  - $\pi_{\text{old}} \leftarrow \pi$
  - for each state $s$ $s$
    - $\pi(s) \leftarrow \operatorname{argmax}_a \sum_{s', r} p(s', r \mid s, a) \big[ r + \gamma\, v(s') \big]$
until $\pi = \pi_{\text{old}}$

Policy iteration, with the line being run highlighted, and a schematic run in two pictures. Top, the chain of evaluations (E) and improvements (I). Bottom, the space of value functions and policies: every evaluation brings the values onto the line v = v_π, sweep after sweep; every improvement brings the policy onto the line π = greedy(v), in one step. The two lines meet at (v_*, π_*).

In words: each policy is strictly better than the previous one, unless it is already optimal. And policy iteration always stops: a finite MDP has a finite number of deterministic policies, so policy iteration reaches an optimal one in a finite number of iterations: $v_*$ , which is unique, and an optimal policy, which may not be.

On the gridworld of section 1.2, it goes fast. The greedy policy with respect to the values of the random policy is already optimal: walk to the nearest corner. Better still, it is optimal long before the evaluation has converged: the greedy policy of $v_3$ already is, although $v_3$ is far from $v_\pi$ . The greedy step only reads the ranking of the neighbors of each state, not the values themselves, nor the order of all the states: that is why it settles at $k = 3$ , one sweep before the full order of section 1.2.

One improvement step, after k sweeps of evaluation

The same sweeps as in section 1.2, with, on each grid, the greedy policy of v_k (green arrows, several where actions tie). At k = 0 every action ties: the greedy policy is the random one again. From k = 3, every greedy action leads toward the nearest corner: one improvement step gives an optimal policy, long before the values have converged.

Exercise 2.2 One improvement step on a 3 × 3 grid Math needed Compute: arithmetic, a small linear system, applying a formula of the pageend of high school Reason: expectations, inequalities, an argument in words: no new tools, but a chain of reasoningfirst year of university, with a first course in probability Prove: induction, limits, norms, fixed points: a proof, which can be skipped on a first readingabout two years of university math The level says which math is needed, not how long it takes.

A $3 \times 3$ grid, the terminal state $T$ in the top-left corner, the other states numbered $1$ to $8$ row by row:


$T$	$1$	$2$
$3$	$4$	$5$
$6$	$7$	$8$

Actions up, down, left, right, deterministic; a move off the grid leaves the agent in place; $r = -1$ per step; $\gamma = 1$ . The policy $\pi_0$ is the equiprobable random one.

Evaluation. Write the Bellman equation of $v_{\pi_0}(s)$ . Use the symmetry of the grid to reduce the number of unknowns, and solve the system.
Action values. Compute $q_{\pi_0}(s, a) = -1 + v_{\pi_0}(s'_a)$ for every state, or at least for states $1$ , $4$ , $5$ and $8$ .
Improvement. Compute the greedy policy $\pi'$ . How does it differ from $\pi_0$ ?
Without computation, give $v_{\pi'}$ , and check that $v_{\pi'}(s) \ge v_{\pi_0}(s)$ everywhere.

Hint

With $\pi_0(a \mid s) = \frac14$ : $v(s) = -1 + \frac14 \sum_a v(s'_a)$ , where $s'_a = s$ when the move hits a wall.

Hint

The grid and the random policy are symmetric about the diagonal through $T$ , $4$ and $8$ . Set $v(1) = v(3) = a$ , $v(2) = v(6) = b$ , $v(4) = c$ , $v(5) = v(7) = d$ , $v(8) = e$ : five unknowns.

Hint

Start from state $8$ , which only sees $5$ , $7$ and itself: $e = -1 + \frac14 (2d + 2e)$ , so $e = d - 2$ . Then work your way up.

Checkpoint what you should get

$v_{\pi_0}(1) = -16$ , $v_{\pi_0}(4) = -21.5$ , $v_{\pi_0}(8) = -27$ ; the greedy policy walks straight to $T$ , and $v_{\pi'}(8) = -4$ .

Solution

With the symmetry, reading the neighbors of each representative state (up, down, left, right):
- state $1$ : $a = -1 + \frac14 (a + c + 0 + b)$ (up bounces, down to $4$ , left to $T$ , right to $2$ );
- state $2$ : $b = -1 + \frac14 (b + d + a + b)$ (up and right bounce);
- state $4$ : $c = -1 + \frac14 (a + d + a + d)$ ;
- state $5$ : $d = -1 + \frac14 (b + e + c + d)$ (right bounces);
- state $8$ : $e = -1 + \frac14 (d + e + d + e)$ (down and right bounce).
The last one gives $e = d - 2$ ; then state $5$ gives $b + c = 2d + 6$ , state $1$ gives $a = \frac{2 + 2d}{3}$ , and states $2$ and $4$ give $a = d + 9$ . So $d = -25$ , $a = -16$ , $b = -22.5$ , $c = -21.5$ , $e = -27$ :

$v_{\pi_0}$
$0$ $-16$ $-22.5$
$-16$ $-21.5$ $-25$
$-22.5$ $-25$ $-27$
$q_{\pi_0}(s, a) = -1 + v_{\pi_0}(s'_a)$ , in the order up, down, left, right:
- state $1$ : $-17$ , $-22.5$ , $\mathbf{-1}$ , $-23.5$ ;
- state $2$ : $-23.5$ , $-26$ , $\mathbf{-17}$ , $-23.5$ ;
- state $3$ : $\mathbf{-1}$ , $-23.5$ , $-17$ , $-22.5$ ;
- state $4$ : $\mathbf{-17}$ , $-26$ , $\mathbf{-17}$ , $-26$ ;
- state $5$ : $-23.5$ , $-28$ , $\mathbf{-22.5}$ , $-26$ ;
- state $6$ : $\mathbf{-17}$ , $-23.5$ , $-23.5$ , $-26$ ;
- state $7$ : $\mathbf{-22.5}$ , $-26$ , $-23.5$ , $-28$ ;
- state $8$ : $\mathbf{-26}$ , $-28$ , $\mathbf{-26}$ , $-28$ .
The greedy actions are in bold: left at $1$ , $2$ and $5$ ; up at $3$ , $6$ and $7$ ; up or left (a tie) at $4$ and $8$ . Where $\pi_0$ was uniform over four actions everywhere, $\pi'$ is deterministic, up to two ties: it walks to $T$ along a shortest path.
Each step of $\pi'$ costs $-1$ and gets one cell closer to $T$ , so $v_{\pi'}(s)$ is minus the distance to $T$ :

$v_{\pi'}$
$0$ $-1$ $-2$
$-1$ $-2$ $-3$
$-2$ $-3$ $-4$

Better than $v_{\pi_0}$ in every non-terminal state, as the theorem says. In fact $v_{\pi'} = v_*$ : on this grid, one improvement step is enough.

$v_{\pi_0}$
$0$	$-16$	$-22.5$
$-16$	$-21.5$	$-25$
$-22.5$	$-25$	$-27$

$v_{\pi'}$
$0$	$-1$	$-2$
$-1$	$-2$	$-3$
$-2$	$-3$	$-4$

What to notice the take-away

$v_{\pi_0}(4) = -21.5$ is better than $v_{\pi_0}(2) = -22.5$ , although both are two steps from $T$ : the center has four useful moves, while state $2$ wastes half of its moves against the walls. Under a random policy, the value measures how hard it is to escape, not the distance. One improvement step is not always enough: on Jack’s car rental, below, it takes four.

2.3 A larger example: Jack’s car rental

Let’s take as an example a problem that is not a grid, with random dynamics, and too many states to read as a table.

Jack manages two car rental locations. Each day, customers come to each location to rent cars, and other customers return cars, in random numbers that follow Poisson distributions with known rates (3 and 4 requests a day, 3 and 2 returns). Jack earns $10 per car rented, if he has one. Overnight, he can move up to 5 cars between the two locations, at $2 per car moved. Each location holds at most 20 cars, and $\gamma = 0.9$ .

The state is the number of cars at each location, $21 \times 21 = 441$ states; the action is the number of cars moved overnight, from $-5$ to $+5$ . The dynamics are random but fully known, so $p(s', r \mid s, a)$ can be computed exactly: this is a planning problem. Starting from the policy that never moves any car, policy iteration converges in four improvements, $\pi_4 = \pi_*$ . With 441 states, tables of numbers are no longer readable: the policy becomes a map, and the value function a surface.

Jack's car rental, solved

The optimal policy π_*, one cell per state: its color is the number of cars moved overnight, positive from the first location to the second. Next to it, the optimal value v_* over the same 441 states; drag to turn it. More cars are worth more. The policy mostly sends cars to the second location, which rents more and gets fewer back, and moves a few the other way only when the first location is nearly empty.

Policy iteration already handles problems with hundreds of states. And with that many states, the value function looks less like a table than like a smooth surface: approximating it by a continuous function, instead of storing one number per state, is the idea of Part 4, From Discrete to Continuous.

Interactive Space Jack's car rental, policy iteration

The whole run, from π₀ to π_*: click a state to see its 11 action values, and compare full, exact and truncated evaluation (m = 1 is value iteration).

Open in a new tab ↗

3. Value iteration: optimize directly

Can we go faster than policy iteration? Are there shortcuts to its cumbersome full evaluations? Value iteration is one of them.

3.1 One sweep of the optimality backup

Policy iteration evaluates each policy to convergence before improving it, and section 2.2 showed that this is often wasted work: the greedy policy settles long before the values do.

Value iteration goes to the extreme, and converges directly to the optimal values $v_*$ . It skips the explicit policy, and applies the Bellman optimality equation as an update rule:

v_{k+1}(s) = \max_a \sum_{s', r} p(s', r \mid s, a)\, \big[ r + \gamma\, v_k(s') \big]

Same sweeps as policy evaluation, with a max over the actions instead of an average under $\pi$ . This has the consequence to converge to the optimal value policy (because of the properties of the Bellman equations). When the values have converged, one last greedy sweep extracts the policy:

Algorithm Value iteration

Input: a threshold $\theta > 0$

$v(s) \leftarrow 0$ for every state $s$
repeat
- $\Delta \leftarrow 0$
- for each state $s$ $s$
  - $v_{\text{old}} \leftarrow v(s)$
  - $v(s) \leftarrow \max_a \sum_{s', r} p(s', r \mid s, a) \big[ r + \gamma\, v(s') \big]$
  - $\Delta \leftarrow \max\big(\Delta, |v(s) - v_{\text{old}}|\big)$
until $\Delta < \theta$
return $\pi(s) = \operatorname{argmax}_a \sum_{s', r} p(s', r \mid s, a) \big[ r + \gamma\, v(s') \big]$

Value iteration on the gridworld of section 1.2, in place, one state at a time. The highlighted line is the one being run; on the grid, the state being updated, the neighbors its max reads, and the action that wins. The values settle one ring of cells per sweep; the fourth sweep changes nothing, Δ = 0, and the greedy policy is read off.

A sweep costs the same as a sweep of policy evaluation, about $|\mathcal{S}|^2 |\mathcal{A}|$ operations. Each one is an improvement and a partial evaluation at once. This method is often preferred to Policy Iteration, but its number of sweeps can somletimes be higher.

Exercise 3.1 Value iteration on the 3 × 3 grid Math needed Compute: arithmetic, a small linear system, applying a formula of the pageend of high school Reason: expectations, inequalities, an argument in words: no new tools, but a chain of reasoningfirst year of university, with a first course in probability Prove: induction, limits, norms, fixed points: a proof, which can be skipped on a first readingabout two years of university math The level says which math is needed, not how long it takes.

The grid of Exercise 2.2: terminal $T$ in the top-left corner, states $1$ to $8$ , $r = -1$ per step, $\gamma = 1$ . This time, solve the optimality equation directly, from $v_0(s) = 0$ in every state, with $v_{k+1}(s) = \max_a \big[ -1 + v_k(s'_a) \big]$ and $v_k(T) = 0$ .

Compute $v_1$ . Are all eight values equal? Why does the shape of the grid not matter yet?
Compute $v_2$ . What appears?
Without computing further, what does $v_k$ converge to? After how many sweeps?
Deduce an optimal policy. Which states have several optimal actions? How many deterministic optimal policies are there?

Hint

After one sweep, every successor still has $v_0 = 0$ , including $T$ : nothing yet tells $T$ apart from the other cells.

Hint

In $v_2$ , only the neighbors of $T$ can use $v_1(T) = 0$ ; every other state only sees cells worth $-1$ .

Checkpoint what you should get

$v_1 = -1$ everywhere; $v_2 = -1$ at states $1$ and $3$ , $-2$ elsewhere; $v_*(s) = -\text{dist}(s, T)$ , so $v_*(8) = -4$ , exact after 4 sweeps; ties at states $4$ , $5$ , $7$ , $8$ , so $16$ deterministic optimal policies.

Solution

Every action gives $-1 + 0$ , so $v_1(s) = -1$ for all eight states. After one sweep, the only information available is the immediate reward, the same everywhere; $T$ is not distinguishable yet, since $v_0(T) = 0 = v_0(s)$ .
States $1$ and $3$ are next to $T$ : their best move gives $-1 + v_1(T) = -1$ . Every other state can only reach cells worth $-1$ , hence $-1 + (-1) = -2$ :

$v_2$
$0$ $-1$ $-2$
$-1$ $-2$ $-2$
$-2$ $-2$ $-2$
Each sweep makes one more ring exact: $v_k(s) = -\min(k, \text{dist}(s, T))$ , with dist the number of moves to $T$ . So $v_k$ converges to $v_*(s) = -\text{dist}(s, T)$ , exactly, after $\max_s \text{dist}(s, T) = 4$ sweeps:

$v_*$
$0$ $-1$ $-2$
$-1$ $-2$ $-3$
$-2$ $-3$ $-4$
An optimal action is any move that gets one cell closer to $T$ : left at $1$ and $2$ , up at $3$ and $6$ , and up or left at $4$ , $5$ , $7$ and $8$ , the states off the first row and the first column. That makes $1^4 \times 2^4 = 16$ deterministic optimal policies, plus every random mixture of the tied actions.

$v_2$
$0$	$-1$	$-2$
$-1$	$-2$	$-2$
$-2$	$-2$	$-2$

$v_*$
$0$	$-1$	$-2$
$-1$	$-2$	$-3$
$-2$	$-3$	$-4$

What to notice the take-away

In Exercise 2.2, the greedy policy of $v_{\pi_0}$ had ties at states $4$ and $8$ only; the greedy policy of $v_*$ has ties at $4$ , $5$ , $7$ and $8$ . Both policies are optimal: they just break the ties differently. $v_*$ is unique, $\pi_*$ is not, so algorithms must be compared on the values they reach, not on the actions they pick.

3.2 Why does it converge?

On our grids, value iteration stops after a few sweeps. With $\gamma < 1$ and random dynamics, as in Jack’s car rental, $v_k$ never reaches $v_*$ exactly: it only gets closer at every sweep. That it always converges, and to $v_*$ only, comes from one property of the update, folded below for those who want the math.

Optional Why do these algorithms converge?: the Bellman operator is a contraction Math needed Compute: arithmetic, a small linear system, applying a formula of the pageend of high school Reason: expectations, inequalities, an argument in words: no new tools, but a chain of reasoningfirst year of university, with a first course in probability Prove: induction, limits, norms, fixed points: a proof, which can be skipped on a first readingabout two years of university math The level says which math is needed, not how long it takes.

Write one sweep of value iteration as an operator $\mathcal{T}^*$ that maps a value function to another:

(\mathcal{T}^* v)(s) = \max_a \sum_{s', r} p(s', r \mid s, a)\, \big[ r + \gamma\, v(s') \big]

For $\gamma < 1$ , it is a $\gamma$ -contraction in the max norm, $\|v\|_\infty = \max_s |v(s)|$ :

\| \mathcal{T}^* v_1 - \mathcal{T}^* v_2 \|_\infty \le \gamma\, \| v_1 - v_2 \|_\infty

Proof in two steps. For a fixed $(s, a)$ , the rewards cancel in the difference, and the weights $p(s', r \mid s, a)$ are nonnegative and sum to $1$ : $\big| \sum_{s', r} p(s', r \mid s, a)\, \gamma\, [v_1(s') - v_2(s')] \big| \le \gamma\, \|v_1 - v_2\|_\infty$ . Then, for any two functions of the action, $|\max_a f(a) - \max_a g(a)| \le \max_a |f(a) - g(a)|$ , which carries the bound through the max.

The Banach fixed-point theorem does the rest: a contraction has a unique fixed point, the solution of $v = \mathcal{T}^* v$ , which is the Bellman optimality equation, so that point is $v_*$ . And iterating from any $v_0$ converges to it exponentially fast, $\|v_k - v_*\|_\infty \le \gamma^k \|v_0 - v_*\|_\infty$ . The same argument without the max shows that policy evaluation converges to $v_\pi$ .

With $\gamma = 1$ , as in our gridworlds, the operator is no longer a contraction, and the argument fails. The iterations still converge there because every step costs $-1$ : a policy that never reaches the terminal state is worth $-\infty$ and is never the max, and a policy that reaches it exists. The “Trap” preset of the gridworld Space shows what happens when some states cannot reach it.

4. Taking a step back

Policy iteration and value iteration look like two different algorithms. Before wrapping everything up, let’s take a step back on what they share: the same two processes underneath, and the same answer at the end, a unique optimal value function, with possibly different optimal policies.

4.1 Evaluate and improve: generalized policy iteration

Side by side, the two algorithms that find $\pi_*$ :

Policy iteration: each iteration is a full evaluation followed by a greedy step. It reaches $\pi_*$ in a finite number of iterations: few iterations, each one expensive.
Value iteration: each iteration is one sweep of the optimality backup. It reaches $v_*$ in the limit (exactly, on our grids): many sweeps, each one cheap.

Both are instances of one idea, generalized policy iteration (GPI): two processes that interact, an evaluation that makes the values consistent with the current policy, and an improvement that makes the policy greedy with respect to the current values. Together they converge to the only point that both accept, $v_*$ and $\pi_*$ . Almost every method of Part 3 is GPI with an approximate evaluation.

Generalized policy iteration

Left: the two processes, evaluation and improvement, each one pulling toward its own goal. Right: the same, as two lines that meet at (v_*, π_*). Evaluation moves the values toward the line v = v_π, improvement moves the policy onto the line π = greedy(v). Policy iteration reaches the line v = v_π at every cycle, value iteration takes a single sweep toward it, modified policy iteration takes m.

4.2 One optimal value function, many optimal policies

Exercise 3.1 ended on a fact worth a second example: the optimal value function is unique, the optimal policy is not.

One v*, sixteen optimal policies

The 3 × 3 grid of Exercise 3.1 and its optimal values v_*, which never change. The arrows run through the 16 deterministic optimal policies, which only differ in the four outlined states, where up and left tie; the green band is the path from 8.

In the gambler’s problem of the extra exercises (E.1 and E.2), the ties are not an accident of symmetry: with a fair coin, every policy is optimal.

4.3 Beyond full sweeps

Every algorithm of this page sweeps the whole state set, again and again: fine for 16 states, hopeless for a Rubik’s cube. Updating only some states, in any order, still works, and is the first step toward Part 3.

Optional Asynchronous dynamic programming: sweeps don't scale

Every algorithm so far sweeps the whole state set at each iteration. A $3 \times 3 \times 3$ Rubik’s cube has about $4.3 \times 10^{19}$ states and a fully known model; at a million state updates per second, a single sweep would take more than a million years.

The first step away from sweeps is the in-place update of section 1.2: one array, and each update immediately visible to the next ones. Asynchronous DP goes further: update the states in any order, some more often than others, using whatever values are available. It still converges, under one condition: no state may be ignored forever.

This freedom lets us spend the computation where it helps: order the updates so that information propagates fast (backward from the goal, for instance), skip states that are irrelevant to good behavior, or run the updates while an agent interacts with the environment, on the states it actually visits. But every update still computes $\sum_{s', r} p(s', r \mid s, a)\, [r + \gamma v(s')]$ : the experience decides where to update, the model is still needed to decide what the update is. Part 3 removes that last requirement.

5. Wrap-up

To wrap up, back to the hike of Part 1, solved with the two algorithms of this page.

The hike, solved by dynamic programming

The altitude map of Part 1, γ = 1. Policy iteration starts from π_B: one evaluation, one improvement, and the policy is π_A, which a second cycle confirms. Value iteration starts from v₀ = 0: step through the sweeps and watch the greedy arrows. The start v₀ = 0 is optimistic, and stay, at −1 a step, looks cheap: at B, staying beats the −35 descent until the values have counted 34 stays.

Policy iteration needs two cycles, and the first improvement already gives the optimal policy $\pi_A$ . Value iteration needs 36 sweeps, yet its greedy policy is optimal on the hiker’s path, at $S$ and $A$ , after 5. The long tail is spent on $B$ , a state the optimal hiker never visits: a case for the asynchronous updates of section 4.3.

All three algorithms of this page, on the gridworld and on harder grids, in one Space:

Interactive Space Solving gridworlds by dynamic programming

Policy evaluation, policy iteration and value iteration, one tab each, on the Sutton and Barto gridworld (Example 4.1) and on other presets: walls, a slippery cliff, a trap with no exit.

Open in a new tab ↗

What to try in the Space above

Policy evaluation. Click state 1, then step from $k = 0$ to $k = 2$ : the backup reads the four neighbors, with the walls sending the agent back to itself. Switch between two arrays and in place, and compare the number of sweeps.
Policy iteration. Step from $\pi_0$ to $\pi_1$ : one improvement turns the random walk into the shortest-path policy. From $\pi_1$ to $\pi_2$ , the values do not change any more, but two states still widen their set of greedy actions: there, all four moves are equally good. Change the number of sweeps $m$ to get modified policy iteration.
Value iteration. Compare the sweep counts in the status line: 4 sweeps on this grid (the values are exact after 3, the 4th detects that nothing changes), against more than a hundred for policy iteration, whose cycles each evaluate a policy to convergence. Then try the Walls preset, and watch the values flow around the walls, one ring per sweep.

In a few lines:

Dynamic programming solves the Bellman equations when the model $p$ is known, one sweep over the states at a time, with the value function as the cache of the subproblems.
Policy evaluation iterates the expectation backup and converges to $v_\pi$ ; the order between the states settles long before the values.
Policy improvement: acting greedily with respect to $v_\pi$ never makes the policy worse, and changes nothing only when $\pi$ is already optimal.
Policy iteration alternates full evaluations and greedy improvements, and stops after a finite number of them: few iterations, each one expensive.
Value iteration iterates the optimality backup: many sweeps, each one cheap. Modified policy iteration sits in between, and all three are generalized policy iteration.
$v_*$ is unique; the optimal policy need not be.

The next move, from exact and exhaustive (this page) to sampled, starts in Part 3.1: Learning from Experience and continues in Part 3.2: Learning to Act. There, the agent no longer knows $p$ : Monte Carlo methods, temporal-difference learning, SARSA and Q-learning estimate the same values from the transitions they experience. The last step, from tables to approximate functions, is Part 4: From Discrete to Continuous, where these methods start solving real problems.

Extra exercises

Three exercises to go further, from the lightest to the most mathematical:

E.1, the gambler’s problem on three states: the optimality equation, checked by hand.
E.2, the full gambler’s problem: reasoning about an optimal policy, no new math.
E.3, why a deterministic optimal policy always exists: a proof, built on the contraction of section 3.2.

Exercise E.1 The gambler's problem, reduced Math needed Compute: arithmetic, a small linear system, applying a formula of the pageend of high school Reason: expectations, inequalities, an argument in words: no new tools, but a chain of reasoningfirst year of university, with a first course in probability Prove: induction, limits, norms, fixed points: a proof, which can be skipped on a first readingabout two years of university math The level says which math is needed, not how long it takes.

A gambler bets on a sequence of fair coin flips, $p_h = 0.5$ . Her capital is $s \in \{1, 2, 3\}$ ; she wins when it reaches $4$ and loses when it drops to $0$ . At each flip she stakes an integer amount $a \in \{1, \dots, \min(s, 4 - s)\}$ : heads, her capital becomes $s + a$ ; tails, $s - a$ . The reward is $+1$ on reaching $4$ and $0$ otherwise, and $\gamma = 1$ , so $v_*(s)$ is the probability of winning from $s$ when playing optimally.

Write the Bellman optimality equation for $v_*(s)$ , $s \in \{1, 2, 3\}$ , with $v_*(0) = v_*(4) = 0$ (the $+1$ is counted on the transition that reaches $4$ ).
Check that $v(s) = \frac{s}{4}$ satisfies the equation for every possible stake in every state.
What does this say about the optimal policy? How many deterministic optimal policies are there?
Without computing: how should $v_*$ and the best stakes change when the coin is unfavorable, $p_h < 0.5$ , or favorable, $p_h > 0.5$ ?

Hint

The stakes allowed are $\mathcal{A}(1) = \lbrace 1 \rbrace$ , $\mathcal{A}(2) = \lbrace 1, 2 \rbrace$ , $\mathcal{A}(3) = \lbrace 1 \rbrace$ .

Hint

For question 4: with an unfavorable coin, is it better to flip many times or few times?

Checkpoint what you should get

$v_*(s) = \frac{s}{4}$ , every stake attains the max, and there are $1 \times 2 \times 1 = 2$ deterministic optimal policies.

Solution

$v_*(s) = \max_{a} \Big\lbrace \tfrac12 \big[ \mathbf{1}_{s + a = 4} + v_*(s + a) \big] + \tfrac12\, v_*(s - a) \Big\rbrace$ , with the max over $1 \le a \le \min(s, 4 - s)$ .
With $v(1) = 0.25$ , $v(2) = 0.5$ , $v(3) = 0.75$ :
- $s = 1$ , $a = 1$ : $\frac12 v(2) + \frac12 v(0) = 0.25$ ;
- $s = 2$ , $a = 1$ : $\frac12 v(3) + \frac12 v(1) = 0.375 + 0.125 = 0.5$ ;
- $s = 2$ , $a = 2$ : $\frac12 (1 + 0) + \frac12 v(0) = 0.5$ ;
- $s = 3$ , $a = 1$ : $\frac12 (1 + 0) + \frac12 v(2) = 0.75$ .
Every stake gives back $v(s)$ : the max is over equal numbers, $v = \frac{s}{4}$ is the fixed point, and $v_*(s) = \frac{s}{4}$ .
Every action attains the max, so every policy is optimal: $1 \times 2 \times 1 = 2$ deterministic ones, and any random mixture at $s = 2$ . The reason: with a fair coin, the expected capital after a flip equals the capital before, whatever the stake. The probability of reaching $4$ before $0$ is then $\frac{s}{4}$ , however you bet.
With $p_h < 0.5$ , each flip is a losing bet on average, so $v_*(s) < \frac{s}{4}$ and the gambler should flip as few times as possible: stake big (with $p_h = 0.4$ , the optimal stake at $s = 2$ is $2$ , and $v_* = (0.16, 0.4, 0.64)$ ). With $p_h > 0.5$ , each flip is a winning bet, $v_*(s) > \frac{s}{4}$ , and she should stake small and play many flips (with $p_h = 0.6$ , the optimal stake at $s = 2$ is $1$ ).

What to notice the take-away

With $p_h \neq 0.5$ , the ties disappear and the optimal stakes depend on the coin. In the full problem of Sutton and Barto (Example 4.3, capital up to $100$ , $p_h = 0.4$ ), the plotted optimal policy has a strange sawtooth shape, with an all-in bet at $50$ but a stake of $1$ at $51$ . Part of that shape comes from how ties are broken: many stakes are optimal, and the plot shows one choice among them.

Exercise E.2 The gambler's curious optimal policy Math needed Compute: arithmetic, a small linear system, applying a formula of the pageend of high school Reason: expectations, inequalities, an argument in words: no new tools, but a chain of reasoningfirst year of university, with a first course in probability Prove: induction, limits, norms, fixed points: a proof, which can be skipped on a first readingabout two years of university math The level says which math is needed, not how long it takes.

The full problem of Sutton and Barto (Example 4.3): the gambler of Exercise E.1, with a capital $s \in \{1, \dots, 99\}$ , the goal at $100$ , stakes $a \in \{1, \dots, \min(s, 100 - s)\}$ , and an unfavorable coin, $p_h = 0.4$ . The optimal policy plotted in the book has an odd shape: at capital $50$ it bets everything, but at capital $51$ it stakes only $1$ .

Give an intuitive argument for why staking everything is optimal at $50$ .
At $51$ , the largest stake allowed is $49$ . Why does a stake of $1$ lose nothing there?
Value iteration gives $v_*(51) \approx 0.403$ , attained by both stakes $1$ and $49$ . What does this say about the plot in the book?

Hint

With $p_h < 0.5$ , each flip is a losing bet on average: does the gambler want to play many flips, or few?

Hint

At $51$ , with a stake of $1$ : where is the gambler if the flip is lost? If it is won?

Checkpoint what you should get

$v_*(50) = 0.4$ , attained only by the all-in bet; at $51$ , stakes $1$ and $49$ tie.

Solution

With $p_h < 0.5$ , every flip has a negative expected value: the gambler wants to reach $100$ in as few flips as possible. At $50$ , the largest stake allowed is $50$ , and it reaches the goal in a single flip, with probability $0.4$ . Any smaller stake buys at least one more flip, each a losing bet. So $v_*(50) = 0.4$ , attained by the all-in bet only.
If the flip is lost, the gambler is at $50$ , from which the one-flip shot at the goal is still available; if it is won, she is at $52$ , better still. The small stake keeps the all-in option at $50$ instead of spending it.
The two stakes are equally good: the optimal policy is not unique at $51$ , and the plot shows one tie-break among many, the smallest maximizing stake. Another tie-break draws a different picture, just as optimal. The plot of $\pi_*$ is one answer; $v_*$ is the answer.

What to notice the take-away

Exercise E.1 (fair coin) had every stake tied; with $p_h = 0.4$ , many ties remain. Before reading meaning into the shape of an optimal policy, check whether the algorithm had to break ties to draw it.

Exercise E.3 Why a deterministic optimal policy exists Math needed Compute: arithmetic, a small linear system, applying a formula of the pageend of high school Reason: expectations, inequalities, an argument in words: no new tools, but a chain of reasoningfirst year of university, with a first course in probability Prove: induction, limits, norms, fixed points: a proof, which can be skipped on a first readingabout two years of university math The level says which math is needed, not how long it takes.

Part 1 (section 4.1) stated a theorem: a finite MDP has a deterministic optimal policy, greedy with respect to $v_*$ . This exercise proves it, for $\gamma < 1$ and bounded rewards. Besides the operator $\mathcal{T}^*$ of section 3.2, define, for a policy $\pi$ ,

(\mathcal{T}^\pi v)(s) = \sum_a \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)\, \big[ r + \gamma\, v(s') \big]

Both are $\gamma$ -contractions: the unique fixed point of $\mathcal{T}^*$ is $v_*$ , that of $\mathcal{T}^\pi$ is $v_\pi$ .

Let $\pi_*(s) \in \arg\max_a \sum_{s', r} p(s', r \mid s, a)\, \big[ r + \gamma\, v_*(s') \big]$ , a deterministic policy. Show that $\mathcal{T}^{\pi_*} v_* = v_*$ , and deduce $v_{\pi_*} = v_*$ .
Show that $\mathcal{T}^\pi$ is monotone: if $v \le v'$ in every state, then $\mathcal{T}^\pi v \le \mathcal{T}^\pi v'$ . Show also that $\mathcal{T}^\pi v \le \mathcal{T}^* v$ for every $v$ .
Deduce that $v_\pi \le v_*$ for every policy $\pi$ , so that $\pi_*$ is optimal.
Two actions tie for the argmax in some state. Why do both choices give an optimal policy, and why does $v_*$ not depend on the choice? Compare with the ties of Exercise 3.1.
Where is it used that each $\mathcal{A}(s)$ is finite?

Hint

Question 1: $\pi_*(s)$ is an action that attains the max in $(\mathcal{T}^* v_*)(s)$ .

Hint

Question 3: start from $\mathcal{T}^\pi v_* \le \mathcal{T}^* v_* = v_*$ , and apply $\mathcal{T}^\pi$ to both sides, again and again.

Checkpoint what you should get

$v_* = \mathcal{T}^{\pi_*} v_*$ , so $v_{\pi_*} = v_*$ ; and $v_* \ge \mathcal{T}^\pi v_* \ge (\mathcal{T}^\pi)^2 v_* \ge \cdots \to v_\pi$ .

Solution

By definition of $\pi_*$ , the action $\pi_*(s)$ attains the max: $v_*(s) = (\mathcal{T}^* v_*)(s) = \sum_{s', r} p(s', r \mid s, \pi_*(s))\, \big[ r + \gamma\, v_*(s') \big] = (\mathcal{T}^{\pi_*} v_*)(s)$ . So $v_*$ is a fixed point of $\mathcal{T}^{\pi_*}$ , whose only fixed point is $v_{\pi_*}$ : $v_{\pi_*} = v_*$ .
If $v \le v'$ , then for every $(s, a)$ , $\sum_{s', r} p(s', r \mid s, a)\, [r + \gamma\, v(s')] \le \sum_{s', r} p(s', r \mid s, a)\, [r + \gamma\, v'(s')]$ , because $p \ge 0$ and $\gamma \ge 0$ . Averaging over $a$ with the nonnegative weights $\pi(a \mid s)$ keeps the inequality. And an average is at most a max: $\mathcal{T}^\pi v \le \mathcal{T}^* v$ .
By question 2, $\mathcal{T}^\pi v_* \le \mathcal{T}^* v_* = v_*$ . Applying the monotone $\mathcal{T}^\pi$ again and again: $v_* \ge \mathcal{T}^\pi v_* \ge (\mathcal{T}^\pi)^2 v_* \ge \cdots$ , and this sequence converges to $v_\pi$ , the fixed point of the contraction $\mathcal{T}^\pi$ . So $v_\pi \le v_*$ for every $\pi$ , and with question 1, $v_{\pi_*} = v_* \ge v_\pi$ : $\pi_*$ is optimal, and deterministic by construction.
Either tied action attains the max, so questions 1 to 3 apply to both choices: each gives a deterministic optimal policy. $v_*$ is the fixed point of $\mathcal{T}^*$ , which does not involve any tie-break. This is what Exercise 3.1 showed: several optimal policies, one $v_*$ .
In the definition of $\pi_*$ : over a finite set of actions, the max is always attained by some action. Over an infinite set, the supremum may not be reached, and no greedy action may exist.

What to notice the take-away

The proof never compares policies one by one, there are too many of them: it compares operators. The max of the Bellman optimality equation is attained by a single action in each state, and that is the whole reason a deterministic policy can be optimal.

Planning with a Model

Author

Affiliations

Published

PDF

Introduction

Where Part 1 left us

1. Evaluating a policy via dynamic programming

1.1 What dynamic programming is

1.2 Iterative policy evaluation

2. Policy iteration: evaluate, improve, repeat

2.1 Improving a policy

2.2 Policy iteration

2.3 A larger example: Jack’s car rental

3. Value iteration: optimize directly

3.1 One sweep of the optimality backup

3.2 Why does it converge?

4. Taking a step back

4.1 Evaluate and improve: generalized policy iteration

4.2 One optimal value function, many optimal policies

4.3 Beyond full sweeps

5. Wrap-up

Extra exercises