##  [Value Iteration](/value-iteration-0) 

 Definition

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

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

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

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

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

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

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

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

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.