If you know how the world works, you can plan. The Bellman operators from the previous note are things you can compute: for a given value vector, run one backup over every state and you have applied $\mathcal{T}^\pi$ or $\mathcal{T}^*$. Dynamic programming is the family of algorithms that apply those backups repeatedly and use the contraction property to argue that they get where they are going.

There are two basic moves. Evaluation takes a policy and computes its value function. Improvement takes a value function and produces a better policy by acting greedily with respect to it. Policy iteration alternates the two moves to completion. Value iteration collapses them into a single backup. Almost every practical reinforcement learning algorithm is some approximation of this alternation, which is why Sutton and Barto call the general pattern generalized policy iteration.

Policy evaluation

Given $\pi$, the value function $V^\pi$ is the unique fixed point of $\mathcal{T}^\pi$. There are two ways to compute it.

Direct solve. $v_\pi = (I - \gamma P_\pi)^{-1} r_\pi$. This is exact and costs a linear solve in $|\mathcal{S}|$ unknowns, roughly $O(|\mathcal{S}|^3)$, which is fine for thousands of states and hopeless beyond that.

Iterative policy evaluation. Start from any $v_0$ and iterate

Each sweep costs $O(|\mathcal{S}|^2 |\mathcal{A}|)$ in the dense case. Since $\mathcal{T}^\pi$ is a $\gamma$ contraction, $\|v_k - V^\pi\|_\infty \le \gamma^k \|v_0 - V^\pi\|_\infty$, and to reach accuracy $\epsilon$ from an initial error $\|v_0 - V^\pi\|_\infty \le R_{\max} / (1 - \gamma)$ takes

sweeps. The dependence on $1 / (1 - \gamma)$ inside the log is mild; the $1 / \log(1/\gamma) \approx 1 / (1 - \gamma)$ in front is the real cost of a long horizon.

In place sweeps. The update above uses $v_k$ on the right hand side for every state, which requires two arrays. Using the newest available values instead, so that a state updated early in the sweep is already seen by states updated later, is the Gauss Seidel variant. It converges too, typically faster, and needs one array. The proof is a small modification: each in place update is still a backup of some vector that is componentwise between $v_k$ and $v_{k+1}$, and monotonicity carries the contraction argument through.

The policy improvement theorem

This is the theorem that makes policy iteration work, and it is the one result in this note that is not simply the contraction property again.

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

Then $V^{\pi'}(s) \ge V^\pi(s)$ for every $s$. Moreover, if the hypothesis holds with strict inequality at some state, the conclusion holds with strict inequality at that state.

In words: if switching to $\pi'$ for one step and then following $\pi$ is at least as good as following $\pi$ throughout, then following $\pi'$ throughout is at least as good as following $\pi$ throughout. One step of improvement, made everywhere, compounds into improvement of the whole policy.

Proof. Start from the hypothesis and expand $Q^\pi$ one step:

So $V^\pi \le \mathcal{T}^{\pi'} V^\pi$ componentwise. Apply $\mathcal{T}^{\pi'}$ to both sides. By monotonicity of the operator,

The right hand side converges to the fixed point of $\mathcal{T}^{\pi'}$, which is $V^{\pi'}$, as $k \to \infty$. Componentwise inequalities survive limits, so $V^\pi \le V^{\pi'}$.

For strictness, if $V^\pi(s) < (\mathcal{T}^{\pi'} V^\pi)(s)$ at some $s$, then the chain of inequalities is strict at that state from the first step on, and $V^{\pi'}(s) \ge (\mathcal{T}^{\pi'} V^\pi)(s) > V^\pi(s)$. $\square$

The proof is three lines once the operator language is available, and it is the reason for setting up that language. The same argument written out with nested expectations over trajectories, which is how Sutton and Barto present it, is a page long and harder to check.

Corollary (greedy improvement). Let $\pi'$ be greedy with respect to $Q^\pi$, so $\pi'(s) \in \arg\max_a Q^\pi(s, a)$. Then $Q^\pi(s, \pi'(s)) = \max_a Q^\pi(s, a) \ge Q^\pi(s, \pi(s)) = V^\pi(s)$, the hypothesis holds, and $\pi'$ is at least as good as $\pi$. If $\pi'$ is no better than $\pi$ anywhere, then $V^\pi = \mathcal{T}^* V^\pi$, so $V^\pi$ is the fixed point of the optimality operator and $\pi$ is already optimal.

Policy iteration

Alternate evaluation and greedy improvement:

1. Initialize $\pi_0$ arbitrarily.
2. Evaluate. Compute $V^{\pi_i}$ exactly, by a linear solve or by iterating $\mathcal{T}^{\pi_i}$ to convergence.
3. Improve. Set $\pi_{i+1}(s) \in \arg\max_a \bigl[R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V^{\pi_i}(s')\bigr]$, breaking ties in favor of the current action.
4. If $\pi_{i+1} = \pi_i$, stop. Otherwise return to step 2.

Theorem. Policy iteration terminates after finitely many iterations, and the policy it terminates with is optimal.

Proof. By the corollary, each improvement step produces a policy at least as good as the last, $V^{\pi_{i+1}} \ge V^{\pi_i}$ componentwise. If the policy changes at step 3, then the greedy action is strictly better than the current action at some state (the tie breaking rule ensures a change only happens on strict improvement), so by the strict part of the theorem $V^{\pi_{i+1}} \ne V^{\pi_i}$. The sequence of value functions is therefore strictly increasing in the componentwise partial order as long as the policy keeps changing, and no policy can appear twice. There are only $|\mathcal{A}|^{|\mathcal{S}|}$ deterministic policies, so the loop terminates. When it terminates, $\pi_{i+1} = \pi_i$ means the greedy policy with respect to $V^{\pi_i}$ is $\pi_i$ itself, which by the corollary means $\pi_i$ is optimal. $\square$

The bound $|\mathcal{A}|^{|\mathcal{S}|}$ is astronomically pessimistic. In practice policy iteration converges in a handful of iterations, and there are results (Ye 2011) showing the number of iterations is polynomial in $|\mathcal{S}|$, $|\mathcal{A}|$ and $1 / (1 - \gamma)$ for a fixed discount. The per iteration cost is dominated by the evaluation step.

Value iteration

Instead of evaluating each policy to convergence before improving, do one backup and improve immediately. Since the greedy improvement of $v$ followed by one step of evaluation is exactly $\mathcal{T}^* v$, this is

which is simply iterating the optimality operator. No explicit policy is kept during the iteration; one is read off at the end by acting greedily with respect to the final $v$.

Convergence is Corollary 2 of the previous note: $\|v_k - V^*\|_\infty \le \gamma^k \|v_0 - V^*\|_\infty$ from any $v_0$.

Stopping rule. Run until $\|v_{k+1} - v_k\|_\infty < \epsilon$. Then

Proof. For any $k$, by the triangle inequality and the contraction,

Rearranging, $(1 - \gamma)\|v_{k+1} - V^*\|_\infty \le \gamma \|v_{k+1} - v_k\|_\infty$, and dividing through gives the bound. $\square$

How good is the greedy policy from an approximate value?

Value iteration stops with an approximate $v$, not $V^*$, and the policy actually used is the greedy one with respect to $v$. The final question is how much that costs.

Theorem. Let $v$ be any value vector and $\pi_v$ a greedy policy with respect to $v$. Then

Proof. Since $\pi_v$ is greedy for $v$, $\mathcal{T}^{\pi_v} v = \mathcal{T}^* v$. Then

For the first term, $V^{\pi_v} = \mathcal{T}^{\pi_v} V^{\pi_v}$, so it equals $\|\mathcal{T}^{\pi_v} V^{\pi_v} - \mathcal{T}^{\pi_v} v\|_\infty \le \gamma \|V^{\pi_v} - v\|_\infty \le \gamma\bigl(\|V^{\pi_v} - V^*\|_\infty + \|V^* - v\|_\infty\bigr)$. For the second, $V^* = \mathcal{T}^* V^*$, so it is $\|\mathcal{T}^* v - \mathcal{T}^* V^*\|_\infty \le \gamma \|v - V^*\|_\infty$. Substituting and collecting the $\|V^{\pi_v} - V^*\|_\infty$ terms on the left,

Combined with the stopping rule, stopping value iteration at tolerance $\epsilon$ produces a policy whose value is within $2\gamma^2 \epsilon / (1 - \gamma)^2$ of optimal. The $1 / (1 - \gamma)^2$ is the price of extracting a policy from an approximate value function, and it is the reason the discount factor is so sensitive in practice: at $\gamma = 0.99$ the factor is ten thousand.

There is a second, more encouraging fact hiding here. Because there are finitely many deterministic policies and $V^*$ is fixed, once $v$ is close enough to $V^*$ the greedy policy $\pi_v$ is exactly optimal, not just approximately. Value iteration typically identifies the optimal policy long before the value estimates have converged.

Asynchronous and prioritized variants

Nothing in the convergence proofs requires that every state be updated in each sweep. As long as every state continues to be updated infinitely often, the iterates still converge to $V^*$. This licenses asynchronous dynamic programming, where states are updated in any order, possibly focusing on the ones whose values are changing most (prioritized sweeping) or the ones the agent is actually visiting (real time dynamic programming). The proof of convergence for the asynchronous case is a small extension of the contraction argument: after enough updates that every state has been touched at least once, the sup norm error has shrunk by at least a factor $\gamma$.

The cost of the model

Every backup in this note sums over $s'$ with weights $P(s' \mid s, a)$. That requires the transition kernel as a table, or at least as something you can evaluate, and it makes every sweep scale with the number of states. Two things go wrong at scale. The state space becomes too large to enumerate, which is the curse of dimensionality, and the model is unavailable because the environment is a physical system, a game engine or a market, which is the more common problem. Both push toward the same idea: replace the expectation over $s'$ with a sample of $s'$ drawn by actually taking the action. That is Temporal difference learning.

References

• Sutton, Barto. Reinforcement Learning: An Introduction, 2nd ed. MIT Press, 2018, chapter 4.
• Puterman. Markov Decision Processes. Wiley, 1994, chapter 6.
• Bertsekas, Tsitsiklis. Neuro-Dynamic Programming. Athena Scientific, 1996, chapter 2.
• Ye. The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate. Mathematics of Operations Research, 2011.