Value iteration vs policy iteration: two ways to solve an MDP

Value iteration and policy iteration both compute an optimal policy for a known Markov decision process. Value iteration repeats one cheap Bellman optimality update over every state until the values stop changing; policy iteration alternates between solving exactly for the value of the current policy and then switching each state to its best action, and it usually finishes in a handful of iterations that each cost much more. Which one is faster depends on the discount factor, the size of the problem and how you evaluate policies, and the best practical choice is often a hybrid of the two.

Below, both algorithms run on the same small gridworld, with every equation explained, and then we time them. In our seeded runs, value iteration needed 32 sweeps to settle the reference gridworld to eight decimal places while policy iteration needed 4 iterations; on 80 by 80 random grids with a discount of 0.999, value iteration took 1,026 sweeps and 428 ms, policy iteration 25 iterations and 192 ms, and modified policy iteration 86 ms.

A worked example: the reference gridworld#

We use the same 5 by 5 gridworld as the rest of our reinforcement learning series. The agent starts in the bottom-left corner. Entering the top-right cell pays +1 and ends the episode; entering the pit just below and to its left pays $-1$ and also ends it. Three cells are walls. Moves are noisy: the agent goes where it intended with probability 0.8 and slips to each perpendicular direction with probability 0.1. Bumping into a wall or the edge leaves it where it was. Every other move pays 0, and future rewards are discounted by $\gamma =0.9$ per step. If any of those words are unfamiliar, the Markov decision process article builds them up from scratch.

Because we know every transition probability and reward, we do not need to learn anything by trial and error. We can plan: compute, for every cell, the best achievable expected discounted return $V^{\ast }(s)$ and the action that achieves it. The answer, which both algorithms below agree on to nine decimal places, is $V^{\ast }(\text{start})=0.293$. The optimal policy is the one drawn in the right-hand grid of Figure 1: from the start, go up the left column and along the top row; from the bottom row, head right and climb the far column; and from the cell under the pit, step right rather than up into it.

What is value iteration?#

Value iteration turns the Bellman optimality equation, explained in detail in our Bellman equation article, into an update rule. Start from any guess, usually $V_0(s)=0$ for every state, and repeatedly apply

Here $V_k(s)$ is the value estimate of state $s$ after $k$ sweeps, $a$ ranges over the four moves, $P(s^{\prime }\mid s,a)$ is the probability of landing in $s^{\prime }$, $R(s,a,s^{\prime })$ is the reward for that transition, and $\gamma$ is the discount factor. Terminal states keep value 0. In words: each state looks one step ahead, using the current estimates of its neighbours, and takes the best action. One application to every state is called a sweep.

A concrete backup. Take the cell directly below the goal and to the right of the pit, at sweep 1, when all estimates are still zero. Moving up reaches the goal with probability 0.8 (reward +1), slips right into the edge with probability 0.1 (reward 0, stays put), and slips left into the pit with probability 0.1 (reward $-1$). So $Q(\text{up})=0.8-0.1=0.7$, which beats every other action, and $V_1=0.7$. That 0.7 is exactly the largest change in the first sweep of our run. At convergence the same backup reads $V^{\ast }=0.7+0.1\times 0.9\times V^{\ast }$, so $V^{\ast }=0.7/0.91=0.769$, the number in Figure 1.

Why does this converge? The update is a contraction in the maximum norm: for any two value functions, applying it shrinks the largest difference between them by at least a factor $\gamma$ [1, 4]. Written out,

where $\Vert \cdot {\Vert }_{\infty }$ is the largest absolute value over states and $V^{\ast }$ is the optimal value function. So the error falls at least geometrically, from any starting point. In our gridworld it falls much faster than the worst case: after the first few sweeps the error shrank by a factor of about 0.45 per sweep, not 0.9, because most trajectories end in a terminal cell within a few steps.

When should value iteration stop?#

You never see $V^{\ast }$, only the change between sweeps. The standard rule [4] is to stop once

where $\epsilon$ is the suboptimality you are willing to accept. When the rule fires, the greedy policy with respect to $V_{k+1}$ is guaranteed to be within $\epsilon$ of optimal in every state. With $\gamma =0.9$ and $\epsilon =0.01$, the threshold is $0.01\times 0.1/1.8=0.00056$. The factor $(1-\gamma )$ is the reason value iteration gets expensive as $\gamma \to 1$: the threshold shrinks and the per-sweep contraction weakens at the same time.

The guarantee is conservative. In our run the rule with $\epsilon =0.01$ fired at sweep 17, when the true error was 0.00048, ten times smaller than the $\epsilon /2$ it promises. More striking, the greedy policy was already optimal from sweep 11 onward, six sweeps before the rule fired and 21 sweeps before the largest change fell below $10^{-8}$. This is the general pattern, and Figure 2 shows it: the action ranking settles long before the numbers do.

What is policy iteration?#

Policy iteration, introduced by Howard in 1960 [2], keeps an explicit policy $\pi$ and improves it in rounds. Each round has two steps.

Policy evaluation. Compute the value of following $\pi$ forever. For a fixed policy there is no max, so the Bellman equation is linear:

Here $V^{\pi }$ is the vector of values of all states under $\pi$, $P_{\pi }$ is the state-to-state transition matrix when every state takes the action $\pi$ prescribes, $R_{\pi }$ is the vector of expected one-step rewards under $\pi$, and $I$ is the identity matrix. You can solve this system directly, as we do, or approximately by repeating the fixed-policy update until it settles.

Policy improvement. In every state, switch to the action that is best when the future is valued by $V^{\pi }$:

The policy improvement theorem says the new policy is at least as good as the old one in every state, $V^{{\pi }^{\prime }}(s)\ge V^{\pi }(s)$, and strictly better somewhere unless $\pi$ is already optimal [4, 5]. A finite MDP has finitely many deterministic policies, so policy iteration must stop, and when the policy stops changing it satisfies the Bellman optimality equation. One implementation detail matters: only switch an action when the new one is strictly better, with a small tolerance, or ties can make the policy cycle between equally good actions forever.

On the reference gridworld, starting from the silly policy "always move up", policy iteration goes like this:

Four evaluations, four improvements, done. Each evaluation, though, solved a 25 by 25 linear system, and if you evaluate iteratively instead, to a $10^{-8}$ tolerance, the four evaluations took 123, 87, 26 and 12 sweeps. That is the real trade: fewer, heavier iterations.

Things to try in Figure 1: set the step reward to $-0.1$ and watch the left side of the grid turn negative and the start switch to the bottom-row route; raise the slip to 0.5 and watch the cells beside the pit start walking deliberately into a wall or the edge, so that no slip can carry them into it; push $\gamma$ to 0.999 and watch value iteration need hundreds of sweeps while policy iteration still needs five or six iterations.

Value iteration vs policy iteration: which is faster?#

Counting iterations is misleading, because the iterations are not the same size. A value iteration sweep costs one backup per state and action. A policy iteration step costs a policy evaluation, which is a linear solve (roughly cubic in the number of states if done densely, much cheaper with sparse solvers on grids) or many fixed-policy sweeps, plus one improvement sweep. The right comparison is work done to reach a given accuracy. We measured it three ways.

Modified policy iteration: the dial between them#

Puterman and Shin [3] noticed that the two algorithms are the ends of one family. Modified policy iteration takes a greedy step, then runs only $k$ sweeps of fixed-policy evaluation before improving again:

where $T$ is the Bellman optimality update (one sweep of value iteration) and $T_{\pi }$ is the fixed-policy update for policy $\pi$. With $k=0$ this is value iteration; as $k\to \infty$ it becomes policy iteration. Fixed-policy sweeps are four times cheaper than optimality sweeps in our grid, because they evaluate one action per state instead of four. Counting action-value backups needed to reach $\epsilon =10^{-4}$ on the reference gridworld:

The curve is U-shaped. A few cheap evaluation sweeps per improvement halve the work of value iteration; evaluating each policy to high precision wastes most of the effort on policies you are about to throw away. All variants returned the optimal policy.

How the discount factor changes the answer#

Next we grew the problem. We generated random square grids of side 10, 20, 40 and 80 (20% walls, 4% pits, one goal, the same slip rule), five per size and discount factor from a fixed seed, and ran each method to the $\epsilon =10^{-3}$ stopping rule (policy iteration to a stable policy, with a sparse direct solver for evaluation). Times are medians over the five grids, measured on one laptop in numpy and scipy; treat them as relative.

Three regularities stand out. First, value iteration's sweep count is driven by the discount factor: from 68 to 1,026 sweeps on the 80 by 80 grids as $\gamma$ goes from 0.9 to 0.999. Second, policy iteration's iteration count hardly depends on $\gamma$ (22 to 25) and grows slowly with size (about 10 at 10 by 10, about 25 at 80 by 80). Third, the crossover is real: at $\gamma =0.9$, value iteration was six times faster than exact policy iteration on the largest grids; at $\gamma =0.999$, policy iteration was more than twice as fast.

The discount factor is not the whole story, though. On the reference gridworld with no step cost, value iteration needed 21, 110 and 160 sweeps for $\gamma$ of 0.9, 0.99 and 0.999. Add a step cost of $-0.04$ and it needed 19, 26 and 29. With no cost and $\gamma$ of 0.99 or more, the optimal policy becomes extremely cautious: the four cells beside the pit deliberately walk into a wall or the edge, so that no slip can carry them into it. The expected episode from the start grows from 10.1 steps to 22.4, and value information takes many more sweeps to travel. A step cost makes the optimal policy finish quickly, and value iteration converges at the speed of that short effective horizon. What sets the pace is how long the optimal policy's episodes last, which $\gamma$ bounds but does not determine.

Theory agrees with the experiment on policy iteration's iteration count. Ye proved that, for a fixed discount factor, policy iteration needs a number of iterations bounded by a polynomial in the number of states and actions, independent of the rewards [8], and Scherrer tightened the bound to $O\left(\frac{m}{1-\gamma }\log \frac{1}{1-\gamma }\right)$ for $m$ state-action pairs [9]. These are worst-case guarantees, hundreds of thousands of iterations or more for our largest grid, and the 25 we observed is typical: policy iteration nearly always converges in a few dozen iterations in practice [4, 5].

Watching value iteration on a larger map#

On a small grid it is hard to see the most important property of value iteration: information travels one step per sweep. Figure 4 runs it on a 30 by 30 terrain with three hills. Entering a cell costs $c\times (0.1+h)$, where $h$ is the hill height at that cell (between 0 and about 1) and $c$ is the cost weight; reaching the goal in the top-right corner pays +1; moves slip as before. The height of the surface is $V_k(s)$.

Reset and run it. Every cell's value starts falling below zero as the per-step costs accumulate, and a green plateau grows outward from the goal, one cell per sweep, bending around the hills. This is exact, not an animation effect: $V_k(s)$ only depends on rewards reachable within $k$ steps, so with the cost weight at 0 the start, 50 moves from the goal, has value exactly 0 until sweep 50 and becomes positive at that sweep. On a large map with sparse rewards, value iteration's sweep count is at least the length of the longest optimal path. That is why it is slow on maze-like problems even when $\gamma$ is modest, and why the order in which you update states matters (see the failure modes below).

How to choose between them#

Code: both algorithms in numpy#

The whole of both algorithms fits in a screen of numpy. P has shape (states, actions, states), R has shape (states, actions) and holds expected immediate rewards, and live marks non-terminal states.

import numpy as np

def value_iteration(P, R, live, gamma, eps=1e-3):
    V = np.zeros(P.shape[0])
    thresh = eps * (1 - gamma) / (2 * gamma)      # stopping rule
    while True:
        Q = R + gamma * P @ V                     # (S, A) one-step lookahead
        V_new = np.where(live, Q.max(axis=1), 0.0)
        if np.abs(V_new - V).max() < thresh:
            return V_new, Q.argmax(axis=1)
        V = V_new

def policy_iteration(P, R, live, gamma):
    S = P.shape[0]
    pi = np.zeros(S, dtype=int)
    while True:
        P_pi = P[np.arange(S), pi] * live[:, None]   # terminal rows zeroed
        R_pi = R[np.arange(S), pi] * live
        V = np.linalg.solve(np.eye(S) - gamma * P_pi, R_pi)   # evaluation
        Q = R + gamma * P @ V
        better = live & (Q.max(axis=1) > Q[np.arange(S), pi] + 1e-10)
        if not better.any():
            return V, pi
        pi[better] = Q.argmax(axis=1)[better]       # improvement

The strict-improvement test in the last lines is what keeps policy iteration from cycling between tied actions.

Failure modes and common mistakes#

Comparing policies instead of values. On one 80 by 80 grid at $\gamma =0.9$, the greedy policy from value iteration disagreed with policy iteration's in 40% of states, yet both value functions were within about 0.0003 of the exact one. Those states were so far from the goal that every action's value was within the tolerance of every other. Both policies were $\epsilon$-optimal. Test optimality with values, not by diffing actions.

Stopping on a small change with $\gamma$ near 1. A largest change of $10^{-4}$ sounds converged, but the bound on the remaining error scales like $\gamma /(1-\gamma )$ times the change, a factor of 999 at $\gamma =0.999$. Use the $\epsilon (1-\gamma )/(2\gamma )$ rule, not a fixed small number.

Trusting a greedy policy from a rough value function. If your values are off by $\delta$ everywhere, the greedy policy can lose up to $2\gamma \delta /(1-\gamma )$ in value [7]. In practice the loss is usually far smaller, as our sweep-11 result shows, but the bound is the reason approximate dynamic programming with function approximation can be unstable.

Policy cycling on ties. Switching actions whenever another is "at least as good" can loop forever between equally good actions. Switch only on strict improvement.

Ignoring update order. Our value iteration is synchronous: each sweep uses only the previous sweep's values. Updating in place (Gauss-Seidel style) and sweeping states in order of distance from the reward can cut the sweep count sharply on maze-like problems, and prioritised sweeping goes further [5, 6]. Figure 4 shows why: information propagates outward from the reward, so sweeping in that direction moves it many cells per sweep.

Exact evaluation that does not scale. A dense linear solve is cubic in the number of states. With more than a few thousand states, use a sparse solver or switch to modified policy iteration.

From dynamic programming to reinforcement learning#

Both algorithms assume you know the model. Most of reinforcement learning is about what to do when you do not, and almost every method you will meet is one of these two in disguise. Q-learning is sampled, asynchronous value iteration on action values: it replaces the expectation over $s^{\prime }$ with a single observed transition. Actor-critic methods are approximate policy iteration: the critic does policy evaluation, the actor does a soft policy improvement, often by following the policy gradient. Sutton and Barto call this interleaving of evaluation and improvement at any granularity generalised policy iteration [5], and modified policy iteration is its cleanest tabular instance.

Planning also stays useful on its own: with a simulator you trust, dynamic programming gives ground truth to test learning algorithms against, the same discipline that applies when you evaluate RL agents more generally. When the data is a fixed log rather than a simulator, the same backups reappear, with extra care about states the data never visits, in offline reinforcement learning.

Frequently asked questions#

Sources#

1. R. Bellman. Dynamic Programming, 1957. press.princeton.edu
2. R. A. Howard. Dynamic Programming and Markov Processes, 1960. ci.nii.ac.jp
3. M. L. Puterman, M. C. Shin. Modified Policy Iteration Algorithms for Discounted Markov Decision Problems, 1978. doi.org
4. M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1994. doi.org
5. R. S. Sutton, A. G. Barto. Reinforcement Learning: An Introduction (2nd ed.), 2018. incompleteideas.net
6. D. P. Bertsekas. Dynamic Programming and Optimal Control, Vol. II: Approximate Dynamic Programming (4th ed.), 2012. athenasc.com
7. S. P. Singh, R. C. Yee. An upper bound on the loss from approximate optimal-value functions, 1994. doi.org
8. Y. Ye. The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate, 2011. doi.org
9. B. Scherrer. Improved and Generalized Upper Bounds on the Complexity of Policy Iteration, 2016. arxiv.org