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.

Test Your Knowledge: Practice Questions for "Value vs Policy Iteration"

Single choice pitfall questions with instant feedback and mistake tracking.