---
title: Dynamic Programming
module: Tabular Solution Methods
moduleNumber: 2
lessonNumber: 1
order: 201
summary: >
  Dynamic programming computes optimal policies when a perfect model of the MDP
  is given, by turning the Bellman equations into assignment statements. We build
  up iterative policy evaluation (the expected update), the policy improvement
  theorem, and the two classic algorithms that alternate them — policy iteration
  and value iteration — worked on the gridworld, a two-state MDP, Jack's car
  rental, and the gambler's problem.
topics: [Tabular Methods]
sources:
  - book: Sutton & Barto
    ref: "Ch. 4 — Dynamic Programming; §4.1 Policy Evaluation (Prediction); §4.2 Policy Improvement"
  - book: Sutton & Barto
    ref: "§4.3 Policy Iteration; §4.4 Value Iteration"
---

**Dynamic programming** (DP) is the collection of algorithms that compute optimal
policies given a _perfect model_ of the environment as a
[Markov decision process](/reinforcement-learning/foundations/markov-decision-processes).[^sb-intro]
That assumption — that the dynamics $p(s',r \mid s,a)$ are fully known — names
what a learning agent lacks, so classical DP is of limited direct use in
reinforcement learning. Its importance is theoretical. DP defines, exactly and by
construction, the optimal value functions and policies
that every model-free method in the rest of the course only _approximates_. Read
this way, [Monte Carlo](/reinforcement-learning/tabular-methods/monte-carlo-methods)
and [temporal-difference learning](/reinforcement-learning/tabular-methods/temporal-difference-learning)
are attempts to achieve the same effect as DP with less computation and without a
model. To understand what they approximate, first see how DP computes it
directly.

Throughout, assume a finite MDP: the state, action, and reward sets
$\mathcal{S}, \mathcal{A}, \mathcal{R}$ are finite, and the dynamics are a known
set of probabilities $p(s',r \mid s,a)$. The single idea behind DP, and behind
reinforcement learning generally, is to use
[value functions](/reinforcement-learning/foundations/value-functions-and-optimality)
to organize the search for good policies.

The plan, in outline: a value function scores how good each state is.
If we knew the _best possible_ score for every state, acting optimally would be
easy: at each state, take the action that leads to the best-scored successors.
So the whole problem reduces to computing those best scores. We already have
optimal policies the moment we have the optimal value functions $v_\ast$ or $q_\ast$,
because they satisfy the Bellman optimality equations

$$
v_\ast(s) = \max_a \sum_{s',r} p(s',r \mid s,a)\big[\, r + \gamma\, v_\ast(s') \,\big],
\qquad
q_\ast(s,a) = \sum_{s',r} p(s',r \mid s,a)\Big[\, r + \gamma \max_{a'} q_\ast(s', a') \,\Big].
$$

DP algorithms are obtained by turning Bellman equations like these into
assignments — into update rules for improving approximations of the desired value
functions. That one move, _equation becomes assignment_, is the whole method.

## Policy evaluation (prediction)

Start with the easier of the two tasks: given a fixed policy $\pi$, compute its
state-value function $v_\pi$. In the DP literature this is **policy evaluation**;
it is also the **prediction** problem. Recall the Bellman equation for $v_\pi$,

$$
v_\pi(s) \;\doteq\; \mathbb{E}_\pi\!\left[\,R_{t+1} + \gamma\, v_\pi(S_{t+1}) \mid S_t = s\,\right]
= \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)\big[\, r + \gamma\, v_\pi(s') \,\big],
$$

for all $s \in \mathcal{S}$. If the dynamics are completely known, this is a system
of $|\mathcal{S}|$ simultaneous linear equations in $|\mathcal{S}|$ unknowns — the
values $v_\pi(s)$. In principle its solution is a straightforward, if tedious,
linear-algebra computation. For our purposes an iterative method is more suitable,
and it is the same move applied to a whole sequence of approximations.

The intuition: start with a rough guess for every state's value, then repeatedly
sharpen it. Each pass replaces every state's guess with a better one computed from
its neighbors' current guesses. Do this enough times and the guesses stop moving —
they have settled onto $v_\pi$. Here is that loop written out.

Consider a sequence of approximate value functions $v_0, v_1, v_2, \ldots$, each a
map from $\mathcal{S}^+$ (the states plus, in an episodic task, a terminal state)
to the reals. The initial $v_0$ is chosen arbitrarily, except that a terminal
state must be given value $0$; each successive approximation is obtained by using
the Bellman equation for $v_\pi$ as an _update rule_:

$$
v_{k+1}(s) \;\doteq\; \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)\big[\, r + \gamma\, v_k(s') \,\big],
\qquad \text{for all } s \in \mathcal{S}.
$$

Clearly $v_k = v_\pi$ is a _fixed point_ of this rule, because the Bellman equation
for $v_\pi$ asserts equality in exactly this case. And the sequence $\{v_k\}$ can be
shown to converge to $v_\pi$ as $k \to \infty$ under the same conditions that
guarantee the existence of $v_\pi$ (either $\gamma < 1$ or guaranteed eventual
termination under $\pi$). This algorithm is **iterative policy evaluation**.[^sb-eval]

> **Definition (Expected update).** Each step of iterative policy evaluation
> replaces the old value of $s$ with a new value built from the old values of $s$'s
> successors and the expected immediate rewards, averaged over _all_ one-step
> transitions possible under $\pi$. Because it is an expectation over every
> possible successor rather than a sample of one, it is called an **expected
> update**. Every DP update is expected.

The expected update is what separates DP from the sampling methods to come. A
Monte Carlo or TD update pushes value toward _one_ sampled successor; the DP update
sweeps _every_ successor, weighted by its probability. That is only possible
because the model $p$ is in hand.

$$
% caption: The expected update for $v_\pi$ backs value up from all successors at
% once. From state $s$ the policy branches over actions $a$ (solid dots) and the
% model branches over next-state/reward pairs $(s',r)$; the new $v(s)$ is the
% probability-weighted average of $r + \gamma\, v(s')$ over the whole tree.
\begin{tikzpicture}[>=stealth, font=\small,
  st/.style={circle, draw, fill=white, minimum size=5mm, inner sep=0pt},
  ac/.style={circle, draw, fill=black, minimum size=2.4mm, inner sep=0pt},
  lf/.style={circle, draw, fill=white, minimum size=4mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[st, label={[text=acc]above:s}] (s) at (0,3) {};
  \node[ac] (a1) at (-2.2,1.7) {};
  \node[ac] (a2) at (0,1.7) {};
  \node[ac] (a3) at (2.2,1.7) {};
  \draw[acc, thick] (s) -- (a1);
  \draw[acc, thick] (s) -- (a2);
  \draw[acc, thick] (s) -- (a3);
  \node[acc, anchor=south west, font=\footnotesize] at (0.55,2.45) {actions};
  \node[lf] (l1) at (-2.8,0.3) {};
  \node[lf] (l2) at (-1.6,0.3) {};
  \node[lf] (l3) at (-0.6,0.3) {};
  \node[lf] (l4) at (0.6,0.3) {};
  \node[lf] (l5) at (1.6,0.3) {};
  \node[lf] (l6) at (2.8,0.3) {};
  \draw[black] (a1) -- (l1);
  \draw[black] (a1) -- (l2);
  \draw[black] (a2) -- (l3);
  \draw[black] (a2) -- (l4);
  \draw[black] (a3) -- (l5);
  \draw[black] (a3) -- (l6);
  \node[anchor=west, font=\footnotesize] at (2.95,0.3) {all (s-prime, r)};
\end{tikzpicture}
$$

To turn the update into a program you might keep two arrays, one for the old
$v_k(s)$ and one for the new $v_{k+1}(s)$, computing each new value from the old
ones. It is simpler, and usually faster, to use one array and update **in place**,
overwriting each value as soon as it is computed, so later updates in the same pass
already see some fresh values. We think of one pass over the whole state set as a
**sweep**. For the in-place version the order of states within a sweep affects the
rate of convergence, and it is the in-place version we normally have in mind.

Formally the iteration converges only in the limit, so in practice we stop it
short: after each sweep, test the largest change in any state's value,
$\max_{s}\, |v_{k+1}(s) - v_k(s)|$, and halt when it drops below a small threshold
$\theta$.

> **Algorithm (Iterative Policy Evaluation, for estimating $V \approx v_\pi$).**
> Input the policy $\pi$ to be evaluated and an accuracy threshold $\theta > 0$.
> Initialize $V(s)$ arbitrarily for all $s \in \mathcal{S}$, with $V(\text{terminal}) = 0$.
> Then repeat sweeps until the values stop moving:

```algorithm
caption: $\textsc{Iterative-Policy-Evaluation}$ — in-place, estimate $V \approx v_\pi$
input: policy $\pi$; threshold $\theta > 0$
initialize $V(s)$ arbitrarily for $s \in \mathcal{S}$, $V(\text{terminal}) = 0$
repeat
  $\Delta \gets 0$
  for each $s \in \mathcal{S}$ do
    $v \gets V(s)$ // remember the old value
    $V(s) \gets \sum_a \pi(a \mid s) \sum_{s',r} p(s',r \mid s,a)\,[\,r + \gamma\,V(s')\,]$
    $\Delta \gets \max(\Delta,\, |v - V(s)|)$ // track the largest change
until $\Delta < \theta$
return $V$
```

### A gridworld sweep

Take the $4 \times 4$ gridworld below.
The nonterminal states are $\mathcal{S} = \{1, 2, \ldots, 14\}$; the two shaded
corner cells are one terminal state. Four actions — `up`, `down`, `right`, `left` —
move the agent deterministically one cell, except that any move off the grid leaves
the state unchanged. Every transition pays reward $-1$ until termination. This is an
undiscounted ($\gamma = 1$), episodic task.

$$
% caption: The $4\times4$ gridworld of Example 4.1. Nonterminal states 1--14 are
% numbered; the two shaded corners are one terminal state. Actions move one cell
% deterministically (a move off-grid stays put), and every transition costs $-1$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % grid
  \foreach \x in {0,...,4} \draw[black] (\x,0) -- (\x,4);
  \foreach \y in {0,...,4} \draw[black] (0,\y) -- (4,\y);
  % shaded terminal corners: top-left (col0,row3) and bottom-right (col3,row0)
  \fill[black] (0,3) rectangle (1,4);
  \fill[black] (3,0) rectangle (4,1);
  % re-draw borders over the shading
  \foreach \x in {0,...,4} \draw[black] (\x,0) -- (\x,4);
  \foreach \y in {0,...,4} \draw[black] (0,\y) -- (4,\y);
  % state numbers, row by row (top to bottom)
  \foreach \x/\lab in {1/1, 2/2, 3/3} \node at (\x+0.5,3.5) {\lab};
  \foreach \x/\lab in {0/4, 1/5, 2/6, 3/7} \node at (\x+0.5,2.5) {\lab};
  \foreach \x/\lab in {0/8, 1/9, 2/10, 3/11} \node at (\x+0.5,1.5) {\lab};
  \foreach \x/\lab in {0/12, 1/13, 2/14} \node at (\x+0.5,0.5) {\lab};
  % reward label to the right
  \node[anchor=west, align=left] at (4.4,2.6) {reward = -1};
  \node[anchor=west, align=left] at (4.4,2.0) {on all transitions};
\end{tikzpicture}
$$

Evaluate the **equiprobable random policy** — each action with probability
$\tfrac{1}{4}$. Initialize $v_0(s) = 0$ everywhere and apply the expected update in
place, sweep after sweep. The first sweep sets every nonterminal state to $-1$
(each of the four equally likely moves costs $-1$ and lands on a state still valued
$0$). Later sweeps let the $-1$ penalties accumulate outward from the terminal
corners, and the estimates fan out toward $v_\pi$.

$$
% caption: Iterative policy evaluation on the $4\times4$ gridworld under the random
% policy. Left to right: $v_0$ (all zero), $v_1$ (every state $-1$), and the limit
% $v_\infty = v_\pi$, whose value at each state is the negation of the expected
% number of steps to termination under the random policy.
\begin{tikzpicture}[>=stealth, font=\scriptsize]
  \definecolor{acc}{HTML}{2348F2}
  % ---------- k = 0 ----------
  \begin{scope}
    \foreach \x in {0,...,4} \draw[black] (\x,0) -- (\x,4);
    \foreach \y in {0,...,4} \draw[black] (0,\y) -- (4,\y);
    \fill[black] (0,3) rectangle (1,4);
    \fill[black] (3,0) rectangle (4,1);
    \foreach \x in {0,...,4} \draw[black] (\x,0) -- (\x,4);
    \foreach \y in {0,...,4} \draw[black] (0,\y) -- (4,\y);
    \foreach \r in {0,1,2,3} \foreach \c in {0,1,2,3} \node at (\c+0.5,\r+0.5) {0};
    \node[acc, anchor=north] at (2,-0.15) {v0};
  \end{scope}
  % ---------- k = 1 ----------
  \begin{scope}[xshift=5.4cm]
    \foreach \x in {0,...,4} \draw[black] (\x,0) -- (\x,4);
    \foreach \y in {0,...,4} \draw[black] (0,\y) -- (4,\y);
    \fill[black] (0,3) rectangle (1,4);
    \fill[black] (3,0) rectangle (4,1);
    \foreach \x in {0,...,4} \draw[black] (\x,0) -- (\x,4);
    \foreach \y in {0,...,4} \draw[black] (0,\y) -- (4,\y);
    % top-left and bottom-right terminals are 0, everything else -1
    \node at (0.5,3.5) {0};
    \foreach \x in {1,2,3} \node at (\x+0.5,3.5) {-1};
    \foreach \x in {0,1,2,3} \node at (\x+0.5,2.5) {-1};
    \foreach \x in {0,1,2,3} \node at (\x+0.5,1.5) {-1};
    \foreach \x in {0,1,2} \node at (\x+0.5,0.5) {-1};
    \node at (3.5,0.5) {0};
    \node[acc, anchor=north] at (2,-0.15) {v1};
  \end{scope}
  % ---------- k = infinity ----------
  \begin{scope}[xshift=10.8cm]
    \foreach \x in {0,...,4} \draw[black] (\x,0) -- (\x,4);
    \foreach \y in {0,...,4} \draw[black] (0,\y) -- (4,\y);
    \fill[black] (0,3) rectangle (1,4);
    \fill[black] (3,0) rectangle (4,1);
    \foreach \x in {0,...,4} \draw[black] (\x,0) -- (\x,4);
    \foreach \y in {0,...,4} \draw[black] (0,\y) -- (4,\y);
    % v_infinity values, row by row top to bottom
    \foreach \x/\v in {0/0, 1/-14, 2/-20, 3/-22} \node at (\x+0.5,3.5) {\v};
    \foreach \x/\v in {0/-14, 1/-18, 2/-20, 3/-20} \node at (\x+0.5,2.5) {\v};
    \foreach \x/\v in {0/-20, 1/-20, 2/-18, 3/-14} \node at (\x+0.5,1.5) {\v};
    \foreach \x/\v in {0/-22, 1/-20, 2/-14, 3/0} \node at (\x+0.5,0.5) {\v};
    \node[acc, anchor=north] at (2,-0.15) {v-inf = v-pi};
  \end{scope}
\end{tikzpicture}
$$

The limit $v_\pi$ gives, at each state, the negation of the expected number of
steps to termination under the random policy. Every one of those numbers satisfies
the Bellman equation exactly: a state's value equals $-1$ plus the average of its
four (in-place, deterministic) neighbors' values.

## Policy improvement

We compute $v_\pi$ in order to find _better_ policies. Suppose we have $v_\pi$ for
a deterministic policy $\pi$, and at some state $s$ we consider deviating — taking
an action $a \ne \pi(s)$ once, then following $\pi$ ever after. The value of that
deviation equals the action-value

$$
q_\pi(s,a) \;\doteq\; \mathbb{E}\!\left[\,R_{t+1} + \gamma\, v_\pi(S_{t+1}) \mid S_t = s,\, A_t = a\,\right]
= \sum_{s',r} p(s',r \mid s,a)\big[\, r + \gamma\, v_\pi(s') \,\big].
$$

The test is whether this is greater or less than $v_\pi(s)$. If it is greater —
taking $a$ once and then following $\pi$ beats following $\pi$ from the start — then
one would expect it to be better still to take $a$ _every_ time $s$ comes up. That
this intuition is correct is the content of a general result.

> **Theorem (Policy improvement).** Let $\pi$ and $\pi'$ be deterministic policies
> such that, for all $s \in \mathcal{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 all $s$.
> If the first inequality is strict at any state, the second is strict there too.

The idea of the proof is simple even if the algebra looks dense. If deviating to
$\pi'$ for _one_ step and then reverting to $\pi$ never hurts, then deviating for
two steps cannot hurt either — apply the same fact at the next state. Keep pushing
the "revert to $\pi$" point one step further into the future and, in the limit, the
agent follows $\pi'$ forever. That limit is $v_{\pi'}$. Here is the same argument as
a telescoping expansion: start from the premise $v_\pi(s) \le q_\pi(s, \pi'(s))$,
expand $q_\pi$ by its definition, and reapply the premise at the successor, again
and again.

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

Each application of the premise trades one step of $\pi$'s continuation for one step
of $\pi'$'s, and in the limit the entire tail is $\pi'$'s — which is $v_{\pi'}(s)$.

The natural way to _use_ the theorem is to improve at every state at once. Consider
the new **greedy policy** $\pi'$ that, in each state, takes the action that looks
best under one step of lookahead on $v_\pi$:

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

By construction $q_\pi(s, \pi'(s)) = \max_a q_\pi(s,a) \ge v_\pi(s)$, so the greedy
policy meets the theorem's condition and is at least as good as $\pi$. Making a new
policy greedy with respect to the value function of the old one is **policy
improvement**.[^sb-improve]

$$
% caption: Policy improvement makes a new policy $\pi'$ greedy with respect to
% $v_\pi$: at each state it selects the action maximizing $q_\pi(s,a)$ (bold bar),
% a one-step lookahead. The policy improvement theorem guarantees $\pi'$ is no
% worse than $\pi$ everywhere.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \draw[black] (-0.3,0) -- (5.6,0);
  \node[anchor=east, font=\scriptsize] at (-0.35,0) {0};
  \foreach \x/\h/\lab in {0.4/1.2/a1, 1.7/1.8/a2, 3.0/2.7/a3, 4.3/1.5/a4} {
    \draw[black, fill=black!8] (\x,0) rectangle (\x+0.8,\h);
    \node[anchor=north, font=\scriptsize] at (\x+0.4,-0.08) {\lab};
  }
  \draw[acc, very thick] (3.0,0) rectangle (3.8,2.7);
  \node[acc, anchor=south, font=\scriptsize] at (3.4,2.72) {greedy};
  \node[anchor=north, font=\scriptsize] at (2.6,-0.55) {action values q(s,a) at a f\/ixed state};
\end{tikzpicture}
$$

What if the greedy $\pi'$ is only as good as $\pi$, not strictly better? Then
$v_{\pi'} = v_\pi$, and the greedy equation reads

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

which is precisely the Bellman optimality equation. So $v_{\pi'} = v_\ast$, and both
$\pi$ and $\pi'$ are optimal. Policy improvement gives a _strictly_ better policy
unless the original one is already optimal. (Everything here extends to stochastic
policies; when several actions tie for the max, any apportioning of probability
among them is a valid greedy policy.)

## Policy iteration

Once a policy $\pi$ is improved to a better $\pi'$, we can evaluate $\pi'$ and
improve it again, and again. This produces a chain of monotonically improving
policies and value functions:

$$
\pi_0 \xrightarrow{\;E\;} v_{\pi_0} \xrightarrow{\;I\;} \pi_1 \xrightarrow{\;E\;} v_{\pi_1} \xrightarrow{\;I\;} \pi_2 \xrightarrow{\;E\;} \cdots \xrightarrow{\;I\;} \pi_\ast \xrightarrow{\;E\;} v_\ast,
$$

where $\xrightarrow{E}$ is an evaluation and $\xrightarrow{I}$ an improvement. Each
policy is a strict improvement over the last (unless already optimal). A finite MDP
has only finitely many deterministic policies, so this chain must reach an optimal
policy and value function in a finite number of iterations. This is **policy
iteration**.[^sb-pi-vi]

$$
% caption: Policy iteration alternates a full policy evaluation (E) with a greedy
% policy improvement (I). Each round produces a strictly better policy until the
% improvement step changes nothing, at which point $\pi = \pi_*$ and $v = v_*$.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=30mm, minimum height=13mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (eval) at (0,0) {evaluate\\V := v-pi};
  \node[box, draw=acc, text=acc, thick] (imp) at (5.4,0) {improve\\pi := greedy(V)};
  \draw[->, acc, thick] (eval.north) .. controls (1.3,1.5) and (4.1,1.5) .. (imp.north)
    node[midway, above, font=\scriptsize] {new policy};
  \draw[->, acc, thick] (imp.south) .. controls (4.1,-1.5) and (1.3,-1.5) .. (eval.south)
    node[midway, below, font=\scriptsize] {new value function};
  \node[anchor=west, align=left, font=\scriptsize] at (8.2,0)
    {stable point:\\pi = pi-star, V = v-star};
  \draw[->, black] (7.05,0) -- (8.1,0);
\end{tikzpicture}
$$

The evaluation of each policy is itself the iterative sweep from before, and it is
started from the value function of the _previous_ policy rather than from scratch.
Because the value function usually changes little from one policy to the next, this
warm start makes evaluation converge much faster.

> **Algorithm (Policy Iteration, for estimating $\pi \approx \pi_\ast$).** Alternate a
> full policy evaluation with a greedy policy improvement until the policy stops
> changing.

```algorithm
caption: $\textsc{Policy-Iteration}$ — evaluation and improvement, estimate $\pi \approx \pi_\ast$
initialize $V(s) \in \mathbb{R}$ and $\pi(s) \in \mathcal{A}(s)$ arbitrarily for all $s$
loop
  repeat // policy evaluation
    $\Delta \gets 0$
    for each $s \in \mathcal{S}$ do
      $v \gets V(s)$
      $V(s) \gets \sum_{s',r} p(s',r \mid s,\pi(s))\,[\,r + \gamma\,V(s')\,]$
      $\Delta \gets \max(\Delta,\, |v - V(s)|)$
  until $\Delta < \theta$
  $\textit{stable} \gets \mathbf{true}$ // policy improvement
  for each $s \in \mathcal{S}$ do
    $\textit{old} \gets \pi(s)$
    $\pi(s) \gets \arg\max_a \sum_{s',r} p(s',r \mid s,a)\,[\,r + \gamma\,V(s')\,]$
    if $\textit{old} \ne \pi(s)$ then
      $\textit{stable} \gets \mathbf{false}$
  if $\textit{stable}$ then
    return $V, \pi$
```

On the $4 \times 4$ gridworld above, greedy-with-respect-to-$v_k$ policies point
toward the terminal corners along shortest paths, and in that small case the greedy
policy becomes optimal after only a few evaluation sweeps — well before $v_k$ has
converged to $v_\pi$. That observation is precisely the opening for the next
algorithm.

### A policy iteration solved by hand

For example, take a two-state MDP with states
$\{L, R\}$ and two actions, `stay` and `switch`, discount $\gamma = 0.9$. The
dynamics are deterministic: `stay` keeps the current state, `switch` moves to the
other. Rewards depend only on the landing state — arriving in $L$ pays $0$,
arriving in $R$ pays $+1$ — so from $L$, `stay` pays $0$ and `switch` pays $+1$;
from $R$, `stay` pays $+1$ and `switch` pays $0$. The optimal policy is obviously
"reach $R$ and stay," but watch policy iteration discover it.

Start from the deliberately bad policy $\pi_0$: `switch` in both states, so the
agent oscillates $L \to R \to L \to \cdots$. Evaluate it. Since the policy is
deterministic the Bellman equations are two linear equations,

$$
v_{\pi_0}(L) = 1 + 0.9\, v_{\pi_0}(R), \qquad
v_{\pi_0}(R) = 0 + 0.9\, v_{\pi_0}(L).
$$

Substitute the second into the first: $v_{\pi_0}(L) = 1 + 0.81\, v_{\pi_0}(L)$, so
$v_{\pi_0}(L) = 1/0.19 \approx 5.263$ and $v_{\pi_0}(R) = 0.9 \times 5.263 \approx
4.737$. Now improve. Compute both action values at each state from $v_{\pi_0}$:

$$
\begin{aligned}
&q_{\pi_0}(L, \texttt{stay}) = 0 + 0.9(5.263) = 4.737, &&q_{\pi_0}(L, \texttt{switch}) = 1 + 0.9(4.737) = 5.263, \\
&q_{\pi_0}(R, \texttt{stay}) = 1 + 0.9(4.737) = 5.263, &&q_{\pi_0}(R, \texttt{switch}) = 0 + 0.9(5.263) = 4.737.
\end{aligned}
$$

The greedy choice at $L$ is `switch` (unchanged), but at $R$ it is `stay`
($5.263 > 4.737$) — the policy changed, so $\pi_1 = (\texttt{switch}, \texttt{stay})$.
Evaluate $\pi_1$: now $R$ is absorbing under the policy, giving
$v_{\pi_1}(R) = 1 + 0.9\, v_{\pi_1}(R) = 10$ and
$v_{\pi_1}(L) = 1 + 0.9(10) = 10$. Improve again:
$q_{\pi_1}(L, \texttt{switch}) = 1 + 0.9(10) = 10$ ties
$q_{\pi_1}(L, \texttt{stay}) = 0 + 0.9(10) = 9$, so $L$ keeps `switch`; and
$q_{\pi_1}(R, \texttt{stay}) = 10 > q_{\pi_1}(R, \texttt{switch}) = 9$, so $R$
keeps `stay`. No action changed: the policy is stable, and $\pi_1 = \pi_\ast$ with
$v_\ast = (10, 10)$. Two evaluations and two improvements, and the chain terminated.

$$
% caption: The two-state policy-iteration trace. Starting from the oscillating
% policy pi-0 (switch, switch), evaluation gives values (5.26, 4.74); improvement
% flips R to stay; re-evaluating the new policy gives (10, 10) and improvement
% changes nothing, so pi-1 is optimal. Each E step solves the linear system, each
% I step takes the greedy action.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=34mm, minimum height=13mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box] (p0) at (0,0) {pi-0 = (switch, switch)};
  \node[box, draw=acc, text=acc] (v0) at (4.6,0) {v = (5.26, 4.74)};
  \node[box, draw=red, text=red] (p1) at (9.2,0) {pi-1 = (switch, stay)};
  \node[box, draw=acc, text=acc] (v1) at (4.6,-2.0) {v = (10, 10)};
  \node[box] (done) at (9.2,-2.0) {stable: pi-1 = pi-star};
  \draw[->, acc, thick] (p0) -- (v0) node[midway, above, font=\scriptsize] {E};
  \draw[->, red, thick] (v0) -- (p1) node[midway, above, font=\scriptsize] {I};
  \draw[->, acc, thick] (p1) -- (v1) node[midway, right, font=\scriptsize] {E};
  \draw[->, red, thick] (v1) -- (done) node[midway, above=1.5pt, font=\scriptsize] {I: no change};
\end{tikzpicture}
$$

The same problem run as value iteration from $v_0 = (0,0)$ needs several sweeps to
crawl the value up toward $10$ ($v_1 = (1,1)$, $v_2 = (1.9, 1.9)$, $v_3 = (2.71,
2.71)$, converging geometrically to $10$ as $\sum_k 0.9^k$), but the greedy policy
it reads off is already $(\texttt{switch}, \texttt{stay})$ after the very first
sweep. This is the general pattern: the greedy policy stabilizes long before the
values do.

### Jack's car rental: policy iteration at scale

The two-state solve fits on a napkin; policy iteration also handles problems with
thousands of states in a handful of iterations. In **Jack's car rental** (Example
4.2), Jack runs two rental locations. Each night he may move up to five cars
between them at a cost of USD 2 per car; each morning, customers arrive at each
location as Poisson random variables (means $3$ and $4$ for requests, $3$ and $2$
for returns) and each car rented pays USD 10. With at most $20$ cars per location,
the state is the pair of overnight inventories — $21 \times 21 = 441$ states — and
the action is the signed number of cars moved, from $-5$ to $+5$. Discount
$\gamma = 0.9$; the task is continuing.[^sb-jack]

Policy iteration starts from the do-nothing policy (never move a car), evaluates it
by solving the $441$-state Bellman system to tolerance, then improves greedily —
each state's new action is the transfer that maximizes expected reward-plus-value
under the known Poisson dynamics. The policy that emerges after the first
improvement already moves cars from the busier location toward the one more likely
to run dry; a few more evaluate–improve rounds refine the transfer thresholds, and
the process converges to the optimal policy in about four iterations.

$$
% caption: The optimal transfer policy for Jack's car rental (schematic of Figure
% 4.2). The axes are the overnight car counts at the two locations; each region is
% labeled with the number of cars to move overnight (negative moves cars the other
% way). The bands are the optimal action thresholds policy iteration converges to.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % axes box
  \draw[black] (0,0) rectangle (5,5);
  \node[anchor=north, font=\scriptsize] at (2.5,-0.15) {cars at location 1};
  \node[rotate=90, anchor=south, font=\scriptsize] at (-0.2,2.5) {cars at location 2};
  % diagonal bands: move more cars near the corners
  \draw[acc, thick] (0,1.6) -- (3.4,5);
  \draw[acc, thick] (0,3.0) -- (2.0,5);
  \draw[red, thick] (1.6,0) -- (5,3.4);
  \draw[red, thick] (3.0,0) -- (5,2.0);
  % region labels
  \node[acc, font=\scriptsize] at (0.6,4.0) {+2};
  \node[acc, font=\scriptsize] at (1.3,3.2) {+1};
  \node[font=\scriptsize] at (2.5,2.5) {0};
  \node[red, font=\scriptsize] at (3.5,1.6) {-1};
  \node[red, font=\scriptsize] at (4.2,0.8) {-2};
\end{tikzpicture}
$$

Jack's rental is the standard demonstration that policy iteration's finite-step
guarantee is not just theoretical comfort: on a $441$-state problem with a
nontrivial stochastic model, it converges in single-digit iterations. That
Poisson-dynamics model carries the arbitrary nonlinearity that direct
optimization struggles with but DP handles without difficulty, because DP only ever
queries the model for one-step transition probabilities.

## Value iteration

A drawback of policy iteration is that each round waits for a full policy
evaluation, itself a protracted iterative computation. Must we wait for exact
convergence to $v_\pi$ before improving? The gridworld says no: the greedy policy
often stops changing long before the values do. So truncate the evaluation.

The extreme case stops policy evaluation after just _one_ sweep — one update of each
state. The result is **value iteration**, which folds improvement and truncated
evaluation into a single update by simply putting a $\max$ where policy evaluation
had a policy-weighted average:

$$
v_{k+1}(s) \;\doteq\; \max_a \sum_{s',r} p(s',r \mid s,a)\big[\, r + \gamma\, v_k(s') \,\big],
\qquad \text{for all } s \in \mathcal{S}.
$$

For arbitrary $v_0$, the sequence $\{v_k\}$ converges to $v_\ast$ under the same
conditions that guarantee $v_\ast$ exists. This is nothing but the Bellman optimality
equation turned into an update rule — the same equation-becomes-assignment move,
now applied to the optimality equation rather than the policy Bellman equation. The
update is identical to iterative policy evaluation's except that it takes the
maximum over all actions instead of averaging over the policy's.

$$
% caption: Value iteration replaces policy evaluation's average over actions
% (left, weighted by $\pi(a\mid s)$) with a $\max$ over actions (right), backing
% up only the single best action's expected value; everything below the action
% layer — the model's branching over $(s',r)$ — is identical.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, fill=white, minimum size=4.5mm, inner sep=0pt},
  ac/.style={circle, draw, fill=black, minimum size=2.2mm, inner sep=0pt},
  lf/.style={circle, draw, fill=white, minimum size=3.6mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % ------- LEFT: evaluation (average) -------
  \begin{scope}
    \node[st, label={[text=acc]above:s}] (s) at (0,2.6) {};
    \node[ac] (a1) at (-1.4,1.5) {};
    \node[ac] (a2) at (0,1.5) {};
    \node[ac] (a3) at (1.4,1.5) {};
    \draw[acc, thick] (s) -- (a1);
    \draw[acc, thick] (s) -- (a2);
    \draw[acc, thick] (s) -- (a3);
    \node[acc, anchor=east, font=\scriptsize] at (-1.75,2.15) {average};
    \foreach \a/\lx in {a1/-1.4, a2/0, a3/1.4} {
      \node[lf] at (\lx-0.4,0.4) (\a l) {};
      \node[lf] at (\lx+0.4,0.4) (\a r) {};
      \draw[black] (\a) -- (\a l);
      \draw[black] (\a) -- (\a r);
    }
    \node[anchor=north, font=\scriptsize] at (0,-0.05) {policy evaluation};
  \end{scope}
  % ------- RIGHT: value iteration (max) -------
  \begin{scope}[xshift=5.6cm]
    \node[st, label={[text=acc]above:s}] (t) at (0,2.6) {};
    \node[ac] (b1) at (-1.4,1.5) {};
    \node[ac] (b2) at (0,1.5) {};
    \node[ac] (b3) at (1.4,1.5) {};
    \draw[acc, thick] (t) -- (b1);
    \draw[acc, thick] (t) -- (b2);
    \draw[acc, thick] (t) -- (b3);
    \draw[red, thick] (-0.62,2.15) arc[start angle=218, end angle=322, radius=0.79];
    \node[red, anchor=south, font=\scriptsize] at (0,2.2) {max};
    \foreach \b/\lx in {b1/-1.4, b2/0, b3/1.4} {
      \node[lf] at (\lx-0.4,0.4) (\b l) {};
      \node[lf] at (\lx+0.4,0.4) (\b r) {};
      \draw[black] (\b) -- (\b l);
      \draw[black] (\b) -- (\b r);
    }
    \node[anchor=north, font=\scriptsize] at (0,-0.05) {value iteration};
  \end{scope}
\end{tikzpicture}
$$

Like policy evaluation, value iteration formally needs infinitely many iterations,
so in practice we stop when a sweep changes the values by less than $\theta$ and read
off a deterministic policy greedy with respect to the final $V$.

```algorithm
caption: $\textsc{Value-Iteration}$ — estimate $\pi \approx \pi_\ast$
input: threshold $\theta > 0$
initialize $V(s)$ arbitrarily for $s \in \mathcal{S}$, $V(\text{terminal}) = 0$
repeat
  $\Delta \gets 0$
  for each $s \in \mathcal{S}$ do
    $v \gets V(s)$
    $V(s) \gets \max_a \sum_{s',r} p(s',r \mid s,a)\,[\,r + \gamma\,V(s')\,]$
    $\Delta \gets \max(\Delta,\, |v - V(s)|)$
until $\Delta < \theta$
return deterministic $\pi$ with $\pi(s) = \arg\max_a \sum_{s',r} p(s',r \mid s,a)\,[\,r + \gamma\,V(s')\,]$
```

Value iteration effectively does one sweep of policy evaluation and one sweep of
policy improvement per pass. More generally, one can interpose several evaluation
sweeps between improvement sweeps; the whole family of _truncated policy iteration_
algorithms is a sequence of sweeps, some using evaluation updates and some using
value-iteration updates. Since the $\max$ is the only difference, they all converge
to an optimal policy for discounted finite MDPs.

### The gambler's problem: value iteration on a probability

A worked value-iteration example that yields a surprising policy is the
**gambler's problem** (Example 4.3). A gambler bets on coin flips: on each flip he
stakes some integer number of dollars from his current capital; heads pays even
money (he gains his stake), tails loses it. The game ends when his capital reaches
USD 100 (win) or USD 0 (lose). The state is the capital $s \in \{1, 2, \ldots,
99\}$; the actions are stakes $a \in \{0, 1, \ldots, \min(s,\, 100 - s)\}$. All
rewards are zero except on the transition that reaches USD 100, which pays $+1$.
The task is undiscounted and episodic, so $v_\ast(s)$ gives the probability of
eventually winning from capital $s$ under optimal play.[^sb-gambler]

Let $p_h$ be the probability of heads. The value-iteration update at each capital
sweeps over all stakes:

$$
v_{k+1}(s) = \max_{0 \le a \le \min(s,\,100-s)} \Big[\, p_h\, v_k(s + a) + (1 - p_h)\, v_k(s - a) \,\Big],
$$

with $v_k(0) = 0$ and $v_k(100) = 1$ held fixed. Run this to convergence for
$p_h = 0.4$ (a losing coin). The value function rises monotonically from $0$ to $1$
in a scalloped curve, and the optimal policy is jagged and non-obvious: at capital
$50$ the gambler stakes everything (a stake of $50$ gives one shot at the goal), at
$51$ he stakes only $1$, and the stake pattern repeats a self-similar structure at
$25$, $75$, and their subdivisions.

$$
% caption: The gambler's problem for heads-probability 0.4 (Sutton \& Barto,
% Figure 4.3). Top: the optimal value function $v_*(s)$ is the probability of
% reaching USD 100 from capital $s$; it rises from 0 to 1 in a scalloped staircase
% that stays below the diagonal $v = s/100$ (a fair-coin gambler would sit on that
% line). The value is capped at $1.0$ because it is a probability. Bottom: the
% optimal stake is jagged, spiking to bet-everything at capital 50 and dropping
% sharply just past it, with self-similar spikes at 25 and 75.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % ---- value function ----
  \begin{scope}
    \draw[->, black] (0,0) -- (5.6,0);
    \node[anchor=north west, font=\scriptsize] at (5.15,-0.28) {capital};
    \draw[->, black] (0,0) -- (0,2.7) node[anchor=south, font=\scriptsize] {v-star};
    % y-axis ticks: 0 and the cap at 1.0 (plotted at height 2.2)
    \draw[black] (-0.08,2.2) -- (0.08,2.2);
    \node[anchor=east, font=\scriptsize] at (-0.12,2.2) {1.0};
    \node[anchor=east, font=\scriptsize] at (-0.12,0) {0};
    % x ticks at 50 and 100
    \node[anchor=north, font=\scriptsize] at (2.5,-0.06) {50};
    \node[anchor=north, font=\scriptsize] at (5.0,-0.06) {100};
    % the cap line v = 1.0 (dashed), curve must not exceed it
    \draw[black, dashed] (0,2.2) -- (5.0,2.2);
    % reference diagonal v = s/100 (fair coin), curve sits below it
    \draw[black] (0,0) -- (5.0,2.2);
    \node[black, anchor=south, font=\scriptsize] at (3.2,1.55) {v = s/100};
    % scalloped staircase value curve, capped at 1.0, below the diagonal
    \draw[acc, very thick]
      (0,0)
      .. controls (0.7,0.12) and (1.1,0.28) .. (1.25,0.40)
      -- (1.35,0.40)
      .. controls (1.7,0.44) and (2.1,0.55) .. (2.5,0.80)
      -- (2.6,0.80)
      .. controls (2.9,0.86) and (3.3,1.02) .. (3.75,1.40)
      -- (3.85,1.40)
      .. controls (4.2,1.56) and (4.6,1.90) .. (5.0,2.2);
    % endpoint dot at the cap
    \fill[acc] (5.0,2.2) circle (1.6pt);
    \node[acc, anchor=south east, font=\scriptsize] at (4.95,2.24) {value};
    \draw[black, dashed] (2.5,0) -- (2.5,0.80);
  \end{scope}
  % ---- policy ----
  \begin{scope}[xshift=6.8cm]
    \draw[->, black] (0,0) -- (5.6,0);
    \node[anchor=north west, font=\scriptsize] at (5.15,-0.28) {capital};
    \draw[->, black] (0,0) -- (0,2.4) node[anchor=south, font=\scriptsize] {stake};
    \node[anchor=north, font=\scriptsize] at (2.5,-0.06) {50};
    \node[anchor=north, font=\scriptsize] at (5.0,-0.06) {100};
    % jagged policy: spikes at 25, 50, 75
    \draw[red, thick] (0,0) -- (1.25,0.9) -- (1.3,0.1) -- (2.45,1.7) -- (2.5,1.9)
       -- (2.55,0.1) -- (3.75,0.9) -- (3.8,0.1) -- (5.0,0.05);
    \node[red, anchor=south, font=\scriptsize] at (2.5,1.92) {bet all at 50};
  \end{scope}
\end{tikzpicture}
$$

The lesson of the gambler's problem is that value iteration recovers optimal
behavior even when that behavior is counterintuitive. A human might bet a steady
fraction; the optimal policy for a losing coin is to make aggressive lump bets that
reach the goal in as few flips as possible, because every extra flip of an
unfavorable coin loses probability. Value iteration finds this by mechanically
sweeping the Bellman optimality update — no insight about coin-flip strategy is
programmed in.

This continues in [Dynamic Programming: Asynchronous DP and Generalized Policy Iteration](/reinforcement-learning/tabular-methods/dp-async-and-gpi), which loosens the full-sweep schedule, names the evaluation-improvement pattern that underlies almost every RL method, and traces DP forward to its modern approximate and neural descendants.

[^sb-intro]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), Ch. 4 — Dynamic Programming: DP as computing optimal policies given a perfect model of a finite MDP, obtained by turning the Bellman optimality equations (4.1)–(4.2) into update rules; classically of limited utility for RL but the theoretical foundation for it.
[^sb-eval]: **Sutton & Barto**, §4.1 — Policy Evaluation (Prediction): the Bellman equation (4.4) as a linear system, iterative policy evaluation (4.5) with its fixed point and convergence, the expected update, in-place sweeps, and the halting test on $\max_s|v_{k+1}(s)-v_k(s)|$; Example 4.1 is the $4\times4$ gridworld.
[^sb-improve]: **Sutton & Barto**, §4.2 — Policy Improvement: the action-value test (4.6), the policy improvement theorem (4.7)–(4.8) with its telescoping proof, and the greedy policy (4.9) whose fixed point is the Bellman optimality equation.
[^sb-pi-vi]: **Sutton & Barto**, §4.3 — Policy Iteration (the $\pi_0 \to v_{\pi_0} \to \pi_1 \to \cdots$ chain and its finite-step convergence) and §4.4 — Value Iteration (update 4.10 as the Bellman optimality equation turned into an assignment, one-sweep truncated evaluation).
[^sb-jack]: **Sutton & Barto**, §4.3, Example 4.2 (Jack's Car Rental) and Figure 4.2: the two-location rental as a continuing finite MDP with Poisson request/return dynamics ($\lambda = 3,4$ requests and $3,2$ returns), USD 10 per rental and USD 2 per car moved, $\gamma = 0.9$, $21 \times 21 = 441$ states, and the sequence of policies policy iteration finds (converging in a few iterations to the optimal transfer policy).
[^sb-gambler]: **Sutton & Barto**, §4.4, Example 4.3 (Gambler's Problem) and Figure 4.3: value iteration on capital states $1$–$99$ with stakes as actions, reward $+1$ only on reaching USD 100, $v_\ast(s)$ as the probability of winning, and the jagged optimal policy for $p_h = 0.4$ (bet-all at capital $50$).