A dynamic programming algorithm that repeatedly applies the Bellman optimality operator to state-value estimates, performing backups across states until the value function converges to the optimal value under contraction properties.

Principle

Exploit the contraction property of the Bellman optimality operator on discounted MDPs: iterative application of the backup V_{k+1}=T[V_k] converges to the unique fixed point V* and yields an optimal policy by greedy extraction.

Demonstration

For a finite MDP with discount gamma in (0,1), initialize V0 arbitrarily and iterate V_{k+1}(s)=max_a{ R(s,a)+gamma sum_{s'} P(s'|s,a) V_k(s') } until sup_s |V_{k+1}(s)-V_k(s)| < tolerance, then derive a greedy policy.

Misapplication

Applying naive value iteration with inappropriate function approximation or on undiscounted problems without ensuring contraction; running with too-large state spaces without approximation leads to impractical runtimes and memory use.

Consequence

Under standard assumptions value iteration converges to the optimal value function and provides an optimal policy via greedy selection; it forms a canonical baseline for planning and reinforcement learning algorithms.

Reversal

Policy iteration alternates explicit policy evaluation with policy improvement and may converge in fewer iterations than value iteration at the cost of more expensive evaluation steps per iteration.

Boundary

Guaranteed for discounted MDPs or situations where the Bellman operator is a contraction; caution required for continuous state spaces, partial observability, or function-approximation regimes where theoretical guarantees weaken.

Semantic Tension

Tension with policy iteration and Q-learning: value iteration performs full backups on values and converges under contraction, whereas policy iteration focuses on alternating evaluation/improvement and Q-learning targets action-values from sampled transitions.

Synthesis

Value Iteration = iterative fixed-point computation applying Bellman backups repeatedly to converge to V*, then extract an optimal policy greedily; practical when exact state models are available and contraction conditions hold.