JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Value Iteration and the Bellman Operator

Why wait for evaluation to finish? Value iteration fuses evaluation and improvement into one update — and the contraction property explains exactly why it always converges.

Collapsing the loop

Policy iteration runs evaluation to convergence before each improvement. But what if you do just one sweep of evaluation and then improve, every time? Take it to the limit — fold the greedy step directly into the backup — and you get value iteration: a single update that simultaneously evaluates and improves. Instead of averaging over the current policy's actions, each backup takes the maximum over actions.

# Value iteration
V = {s: 0.0 for s in S}
repeat:
    delta = 0
    for s in S:
        v_old = V[s]
        # max over actions, not expectation over a fixed policy
        V[s] = max(
            sum(p(s_next, r, s, a) * (r + gamma * V[s_next])
                for (s_next, r) in transitions(s, a))
            for a in actions(s)
        )
        delta = max(delta, abs(v_old - V[s]))
until delta < theta
# recover the optimal policy by acting greedily wrt V
pi_star = {s: argmax_a(...) for s in S}
Value iteration = the Bellman optimality backup applied until convergence; the policy is read off at the end.
An interactive gridworld: watch value estimates ripple outward and settle as the Bellman backup is applied sweep after sweep until convergence.

A grid of states whose value numbers update each iteration until they stop changing.

The Bellman optimality equation

That max-backup is exactly the Bellman optimality equation turned into an update. It states a self-consistency condition the optimal value function must satisfy: the value of a state equals the reward of the best action plus the discounted optimal value of where that action leads. Value iteration is just this equation, used as an assignment, over and over.

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

The Bellman optimality equation turned into an update: each state takes the best action's expected reward plus the discounted next-state value.

The Bellman operator as a map

To understand why this converges, stop thinking about individual states and think about the whole value function as one big vector. The Bellman backup operator is then a function that takes one value-function vector in and gives an updated one out. Value iteration is nothing but applying this operator repeatedly to a starting vector.

Phrasing it as an operator unlocks a powerful piece of mathematics: fixed-point theory. The optimal value function is precisely the fixed point of this operator — the unique vector the operator maps to itself. Convergence of value iteration becomes a question about whether repeatedly applying the operator drives any starting point to that fixed point.

Contraction: why it must converge

Here is the keystone. The Bellman operator is a gamma-contraction in the max-norm: apply it to any two value vectors and the largest gap between them shrinks by at least a factor of gamma (which is below 1). Two estimates can only get closer together, never farther apart.

\lVert T V - T U \rVert_\infty \le \gamma\, \lVert V - U \rVert_\infty

The contraction property in the max-norm: one Bellman backup shrinks the largest gap between any two value vectors by at least a factor of gamma.

By the Banach fixed-point theorem (contraction mapping principle), a contraction has exactly one fixed point, and iterating it from anywhere converges to that point geometrically. So value iteration converges to the unique optimal value function regardless of the initial guess, and the error after each sweep is multiplied by gamma. A gamma near 1 means slow, patient convergence; a smaller gamma means fast convergence but a more short-sighted objective.