Value Iteration in RL

Value iteration finds the best value of every state by repeating one rule: assume the next values are right, then take the best action under that assumption. Repeat until nothing moves.

Two Bellman optimality sweeps with discount 0.8 move values from [0, 0] to [2, 10] to [8, 10], flipping the greedy choice at s1

Why Does This Exist?

Policy iteration finds the optimal policy in two alternating phases: evaluate the current policy until its values converge, then improve it. The evaluation phase is the wasteful part. It solves values to many decimals for a policy about to be thrown away, when the greedy choices usually settle long before the digits do.

Value iteration cuts evaluation down to a single sweep. Every pass applies the Bellman optimality backup with a max over actions, merging evaluation and improvement into one update. It works purely in value space and extracts the policy once, at the end.

This page covers the backup, why it converges, and the stopping rule, with a hand-computed three-state example. The recursion itself is Bellman equations, the family it belongs to is dynamic programming, and the two-phase sibling is policy iteration.

The one idea you need first

An MDP supplies states, actions, transition probabilities, and rewards. Value iteration needs all of them: without the model it cannot look one step ahead, and the whole method collapses. The full setup is MDP foundations.

Think of It Like This

Posting the best rumour in every village

Every village posts one number: the best fortune anyone can reach from there. Each morning, every village phones its neighbours, adds the road reward minus a travel tax, and posts the best offer heard. Nobody waits for distant villages to finish thinking; everyone updates from yesterday's board at once.

Day one, only villages next to the gold mine post anything real. Day two, their neighbours catch on and repost higher numbers. The wave of good news travels one road per day until no board changes overnight. Only then does anyone carve the final signposts, by pointing each village at the neighbour that gave it the winning offer.

Where the analogy stops: rumours degrade with retelling in unpredictable ways, while the backup shrinks errors by exactly the discount factor each sweep, which is what guarantees the boards settle instead of oscillating.

How It Actually Works

For a finite MDP with discount $\gamma$ in $[0, 1)$ , the optimal values satisfy the Bellman optimality equation: each state's value equals the best action's immediate reward plus discounted next values. Value iteration turns that identity into an update, starting from zeros and sweeping all states:

$V_{k+1}(s) = \max_a \left[ \mathcal{R}(s, a) + \gamma \sum_{s'} \mathcal{P}(s' \mid s, a) \, V_k(s') \right]$

Here $\mathcal{R}(s, a)$ is the expected immediate reward and $\mathcal{P}(s' \mid s, a)$ the transition probability. The max is the whole difference from policy evaluation: instead of scoring the current policy's action, each sweep scores the best action under yesterday's values.

Convergence is guaranteed because the backup is a contraction: one sweep shrinks the worst error across states by at least factor $\gamma$ . With $\gamma = 0.8$ , the distance to optimal drops twenty percent or more per sweep, from any starting values. Sweeps stop when the largest change falls below a threshold $\theta$ , and the policy comes out with one greedy lookahead per state.

Worked example

States $s_1$ , $s_2$ , plus terminal $s_3$ fixed at $0.0$ , with $\gamma = 0.8$ . From $s_1$ , action $a_1$ leads to $s_2$ for reward $0$ , action $a_2$ ends the episode for reward $2$ . From $s_2$ , action $a_1$ ends for reward $10$ , action $a_2$ returns to $s_1$ for reward $1$ .

Sweep 1 from $[0.0, 0.0]$ : at $s_1$ , candidates are $0.0$ and $2.0$ , so $V_1(s_1) = 2.0000$ favouring $a_2$ . At $s_2$ , candidates are $10.0$ and $1.0$ , so $V_1(s_2) = 10.0000$ .

Sweep 2 from $[2.0, 10.0]$ : at $s_1$ , $a_1$ now offers $0.0 + 0.8 \times 10.0 = 8.0000$ against $2.0$ , so $V_2(s_1) = 8.0000$ and the greedy choice flips to $a_1$ . At $s_2$ , $a_2$ offers $1.0 + 0.8 \times 2.0 = 2.6000$ against $10.0$ , so $V_2(s_2) = 10.0000$ .

Sweep 3 changes nothing: $s_1$ stays $\max(8.0, 2.0) = 8.0$ and $s_2$ stays $\max(10.0, 7.4) = 10.0$ . Optimal values $[8.0, 10.0, 0.0]$ , optimal policy $a_1$ everywhere.

Code

The example as a compact sweep loop, with type hints, matching the numbers above:

1V: dict[int, float] = {0: 0.0, 1: 0.0, 2: 0.0}2outcomes: dict[tuple[int, int], list[tuple[int, float]]] = {3    (0, 0): [(1, 0.0)],4    (0, 1): [(2, 2.0)],5    (1, 0): [(2, 10.0)],6    (1, 1): [(0, 1.0)],7}8gamma = 0.89
10for sweep in range(3):11    V = {12        s: max(13            sum(r + gamma * V[ns] for ns, r in outcomes[(s, a)])14            for a in (0, 1)15        ) if s != 2 else 0.016        for s in V17    }18    print(f"sweep {sweep + 1} [{V[0]:.1f}, {V[1]:.1f}]")19    # -> sweep 1 [2.0, 10.0]20    # -> sweep 2 [8.0, 10.0]21    # -> sweep 3 [8.0, 10.0]

Watch Out For

Stopping loose when the discount sits near 1

The sweep change $\Delta$ understates the distance to optimal by a factor of $1 - \gamma$ . With $\gamma = 0.99$ , stopping at $\Delta < 0.05$ can leave the extracted policy nearly 10 units of return from optimal, because errors compound over long horizons. The symptom is values that look settled while the greedy policy keeps making shortsighted moves.

Fix it by scaling the threshold: to keep the policy within tolerance $\delta$ of optimal, stop at $\theta$ near $\delta (1 - \gamma) / (2\gamma)$ , not at a round number that ignores $\gamma$ .

Running it with no model to back up from

The backup sums over next states weighted by transition probabilities, so it needs the MDP on paper. On a grid demo that is a given; on a robot with dozens of sensors it is the entire problem. The symptom is code that runs on the toy task and cannot even start on the real one, because no table of $\mathcal{P}$ exists.

Fix it by switching families: model-free methods like Q-learning replace the sum over the model with samples from the world. Value iteration is the planning answer for a known model, not a learning answer for an unknown one.

The Quick Version

Value iteration truncates policy evaluation to one sweep, fusing evaluation and improvement into a single max backup.
The backup is a contraction with factor $\gamma$ , so values converge geometrically from any start.
In the worked MDP, sweep 1 gives [2.0, 10.0], sweep 2 flips $s_1$ to the delayed path for [8.0, 10.0], sweep 3 confirms.
The policy is extracted once at the end with a greedy lookahead, never maintained during sweeps.
Calibrate the stopping threshold against $\gamma$ , and remember the method needs a known model to run at all.