two DP algorithms, one fixed point
policy iteration
outer loop over (evaluate, improve)
1. evaluate: V^pi until convergence
V(s) <- sum pi(a) sum P (r + g V(s'))
2. improve: pi(s) <- argmax_a Q(s,a)
greedy w.r.t. current V
3. stop if pi unchanged
few outer iters (5-20)
each inner eval is expensive
guarantee: monotone V improvement
value iteration
one loop, Bellman optimality backup
V(s) <- max_a sum P (r + g V(s'))
applied to every state, every sweep
stop when max_s |dV(s)| < eps
sup-norm contraction by factor g
extract greedy pi from V*
more sweeps (often 100+)
each sweep O(|S| * |A|)
convergence: ||T V - V*|| <= g^k ||V_0 - V*||
both land at V* — different paths, same fixed point (generalized policy iteration)