Value vs Policy Iteration

Value Iteration (VI) iterates the Bellman optimality equation directly with synchronous sweeps over all states: $V_{k+1}(s) = \max_a \sum_{s'} P(s'|s,a)\left[ r(s,a) + \gamma V_k(s') \right]$, where $V_k$ is the estimate at round $k$, $\max_a$ performs an implicit greedy improvement, and $\sum_{s'} P(s'|s,a)[\cdot]$ is the transition-weighted expectation; each sweep is one step of evaluation plus one step of improvement — VI is policy iteration truncated to a single evaluation step. Because the Bellman operator is a $\gamma$-contraction ($\|TV - TU\|_\infty \le \gamma \|V - U\|_\infty$), $V_k \to V^*$ is guaranteed; note intermediate $V_k$ need not be the value function of any single policy — only the final greedy policy w.r.t. $V_k$ is optimal. Policy Iteration (PI) alternates two steps: ① policy evaluation — iterate the current policy's value function $V^{\pi_k}(s) = \sum_{s'} P(s'|s, \pi_k(s))\left[ r(s, \pi_k(s)) + \gamma V^{\pi_k}(s') \right]$ to convergence (or truncated by tolerance); ② policy improvement — greedy update $\pi_{k+1}(s) = \arg\max_a \sum_{s'} P(s'|s,a)\left[ r(s,a) + \gamma V^{\pi_k}(s') \right]$.The improvement theorem guarantees $V^{\pi_{k+1}} \ge V^{\pi_k}$ monotonically, so PI terminates at the optimal policy on finite MDPs (≤ $|A|^{|S|}$ rounds in theory, far fewer in practice).

tabular small-scale MDPs with known model $P, R$ (planning problems) — e.g. grid worlds and robot navigation; also the standard interview question distinguishing the two dynamic-programming schools (contrast with model-free DQN).

naive policy search is exponential in $|A|^{|S|}$; PI turns search into polynomial-level iteration via evaluate-improve cycles, converging in tens of rounds with costlier but fewer iterations; VI is cheap per sweep ($O(|S|^2|A|)$) but needs more sweeps — both are different partitions of the same Bellman fixed-point iteration.

Write the value iteration update and explain each term. Why does VI converge to V*?

What are the two steps of policy iteration? Why does the improvement theorem guarantee monotonic gains?

Compare VI vs PI in complexity and convergence speed. Why does PI need fewer rounds but cost more per round?

Is an intermediate Vk necessarily the value function of some policy? How is the final policy extracted?

Given a small grid-world MDP, manually run 1-2 sweeps of VI/PI to demonstrate the updates.