Value Iteration

Value iteration applies the Bellman optimality update repeatedly until $V$ stops changing.

``` function value_iteration(MDP, threshold): V[s] = 0 for all s while max_change > threshold: max_change = 0 for each state s: new_V[s] = max over actions a of [R(s,a) + gamma * sum_{s'} P(s'|s,a) * V[s']] max_change = max(max_change, |new_V[s] - V[s]|) V = new_V return V ```

Each iteration is the Bellman update applied to every state in parallel.

Why it converges

The Bellman update is a contraction in $\max$-norm with factor $\gamma$:

By the Banach fixed-point theorem, iteration converges to the unique fixed point — which is $V^*$. Convergence is geometric in $\gamma$: each iteration shrinks distance to the true value by factor $\gamma$.

Complexity

• Time per iteration: $O(|S|^2 |A|)$ — for every state, every action, sum over all next states.
• Iterations to $\epsilon$: $O(\log(1/\epsilon) / (1 - \gamma))$.
• Both quantities scale poorly with state-space size and $\gamma$ near 1.

Policy extraction

Once $V \approx V^*$, the optimal policy is just greedy:

You don't need to converge to $V^*$ exactly — by the policy loss bound, a policy greedy w.r.t. $V$ with $\|V - V^*\|_\infty \leq \epsilon$ has value within $2\epsilon \gamma / (1 - \gamma)$ of optimal. So you can stop early.

Policy iteration

Alternative: alternate between (1) policy evaluation (compute $V^\pi$ exactly by solving a linear system, or approximately) and (2) policy improvement (greedy action w.r.t. current $V$). Converges in fewer iterations than value iteration but each iteration is more expensive (evaluation step).

Modified policy iteration uses inexact evaluation (a few sweeps of the Bellman update) — usually faster than either pure policy iteration or pure value iteration.

Asynchronous variants

Don't update every state every iteration. Prioritized sweeping focuses updates on states whose values have changed most. Real-time dynamic programming updates only states the agent currently expects to visit. All sacrifice some convergence guarantees for vastly better practical performance.