Value Iteration

Value iteration solves an MDP by repeatedly applying the Bellman optimality update to every state until the value function stops changing.

One update to rule them

Value iteration is a dynamic-programming method that computes the optimal value function by turning the Bellman optimality equation into an update rule and applying it repeatedly. It folds policy evaluation and improvement into a single step.

The update

Starting from any initial V, repeat for every state: V(s) <- max over a of sum over s' of P(s' | s, a) [ R(s, a, s') + gamma V(s') ]. Each sweep replaces the value of every state with the best one-step lookahead using current estimates. Because the optimality operator is a contraction, V converges to V*.

Extracting the policy

Value iteration converges on values, not policies. After it converges (or when the largest change per sweep falls below a threshold), the greedy policy pi(s) = argmax over a of the same lookahead is optimal or near optimal.

Worked sketch

def value_iteration(states, actions, P, R, gamma, theta=1e-6):
    V = {s: 0.0 for s in states}
    while True:
        delta = 0.0
        for s in states:
            v_old = V[s]
            V[s] = max(
                sum(P[s][a][s2] * (R[s][a][s2] + gamma * V[s2])
                    for s2 in states)
                for a in actions)
            delta = max(delta, abs(v_old - V[s]))
        if delta < theta:
            return V

Trade-offs

Value iteration needs no explicit policy-evaluation loop, so each sweep is cheap, but it may need many sweeps to converge. Policy iteration often needs fewer, more expensive iterations. Both require a known model and full state sweeps, limiting them to modest discrete problems; larger tasks use sampled, approximate variants.