Value iteration

On this page 7

Value iteration is a dynamic programming algorithm that computes the optimal value function of a Markov decision process by repeatedly applying the Bellman optimality update to every state until the values stop changing. In reinforcement learning, it is the classic planning method for problems where the transition probabilities and rewards are fully known.

Once the values have converged, an optimal policy is obtained by choosing, in each state, the action with the highest expected return. Value iteration is guaranteed to converge for a discount factor below one, and its ideas underpin many model-free methods, including Q-learning and the deep Q-network.

How value iteration applies the Bellman optimality update

Value iteration works by turning the Bellman optimality equation into an assignment that is applied over and over. For each state s, the new value is the maximum over actions of the expected immediate reward plus the discounted value of the next state, using the current estimates: V(s) is set to the maximum over a of the sum of P(s’ | s, a) times [R(s, a, s’) + gamma V(s’)].

Each full pass over the state space is called a sweep. The algorithm starts from an arbitrary value function, often all zeros, and keeps sweeping until the largest change in any state value falls below a small threshold. Because every sweep looks one step ahead and maximizes, information about rewards spreads backward through the state space, one transition per sweep.

The steps of the standard procedure are summarized in the table below.

StepOperationPurpose
InitializeSet V(s) to zero or any bounded valueProvides a starting estimate
SweepApply the Bellman optimality update to every stateImproves all value estimates
Measure changeRecord the maximum absolute change deltaTracks progress toward the fixed point
Test stopping ruleStop when delta is below a thresholdBounds the remaining error
Extract policyChoose the greedy action in each stateTurns values into decisions
Steps of the value iteration procedure

Why value iteration converges

Value iteration converges because the Bellman optimality operator is a contraction mapping in the maximum norm. With a discount factor gamma below one, each application shrinks the distance between any two value functions by at least a factor of gamma, so the sequence approaches a unique fixed point, which is the optimal value function V*.

This property gives practical error bounds. If the maximum change in a sweep is delta, the distance from the current estimate to V* is at most delta times gamma divided by one minus gamma. A greedy policy can become optimal well before the values converge, because only the ranking of actions matters for decisions.

The discount factor strongly affects how many sweeps are required, as the following table shows.

Discount factorEffective horizonConvergence behavior
0.5About 2 stepsVery fast, values reflect near rewards
0.9About 10 stepsModerate number of sweeps
0.99About 100 stepsSlow, many sweeps for tight tolerance
1.0UnboundedConvergence only under extra conditions, such as guaranteed termination
Discount factor and convergence speed

The effective horizon of roughly one divided by one minus gamma explains the pattern: the longer the agent looks ahead, the more sweeps are needed for distant rewards to propagate back.

Value iteration compared with policy iteration and model-free methods

Value iteration and policy iteration are the two classic dynamic programming methods for solving a known Markov decision process. Policy iteration alternates full policy evaluation with policy improvement, while value iteration effectively performs one evaluation step per improvement, folding both into a single maximization.

Model-free algorithms such as Q-learning and SARSA follow the same Bellman logic but replace exact expectations with sampled transitions. The table below contrasts these families.

MethodNeeds a modelUpdate styleTypical use
Value iterationYesFull sweeps with maximizationPlanning in small known problems
Policy iterationYesFull evaluation, then greedy improvementFew iterations, costly evaluation
Q-learningNoSampled one-step updates of action valuesLearning from interaction
Temporal difference learningNoSampled bootstrapped updates for a policyPrediction from experience
Value iteration and related reinforcement learning methods

In practice, policy iteration often needs fewer iterations, but each one is more expensive. Value iteration is simpler to implement and is usually preferred when the action space is small and an approximate answer is acceptable.

Computational cost and practical variants

One synchronous sweep of value iteration costs on the order of S squared times A operations, where S is the number of states and A the number of actions, because each state-action pair sums over possible next states. Sparse transition models reduce this cost considerably, but the method still requires enumerating every state.

Several variants improve efficiency while keeping the same fixed point:

  • Asynchronous (Gauss-Seidel) value iteration updates states in place, so later states in a sweep already use fresh values, which usually speeds convergence.
  • Prioritized sweeping updates first the states whose values are likely to change most, focusing computation where it matters.
  • Real-time dynamic programming updates only states visited along simulated trajectories from a start state.
  • Fitted value iteration replaces the table with a function approximator, extending the idea to large or continuous state spaces at the cost of convergence guarantees.

The table below helps decide when value iteration is the appropriate tool.

SituationRecommended approachReason
Known model, up to millions of statesTabular value iterationExact and simple to implement
Known model, huge state spaceFitted or sampled variantsFull sweeps are infeasible
Unknown model, simulator availableQ-learning or model-based RLTransition probabilities are not given
Continuous actionsPolicy gradient methodsMaximization over actions is hard
When to use value iteration

Limitations and common mistakes

The main limitation of value iteration is the curse of dimensionality: the number of states grows exponentially with the number of state variables, so tabular sweeps quickly become impractical. It also assumes a complete and accurate model, which real environments rarely provide.

  • Stopping too early: a loose threshold with a high discount factor leaves large errors in long-horizon values.
  • Using gamma equal to one in tasks without guaranteed termination, which can make values diverge.
  • Forgetting terminal states: terminal values must stay fixed, or reward leaks past the end of an episode.
  • Confusing values with policies: the output is a value function, and the policy must be extracted by a separate greedy step.

In plain words

Picture a board game in which every square has a score that says how good it is to stand there. At first, nobody knows the scores. Value iteration fills them in by looking one move ahead from each square and asking which move leads to the best next square.

Repeating this many times lets good news from the goal spread backward across the board. When the scores stop changing, the best move from any square is simply the one pointing to the highest-scoring neighbor.

A real-world example

A warehouse engineering team plans routes for a mobile robot on a grid of 2,500 cells. Some cells are shelves, the floor near the loading dock is slippery, and each move succeeds with a known probability of 0.9. The team models the problem as a Markov decision process with a reward of minus one per move, a large positive reward at the delivery station and a discount factor of 0.95.

Running value iteration with a tolerance of 0.001 converges in a few hundred sweeps, taking well under a second on a laptop. The greedy policy extracted from the values tells the robot which direction to take from every cell, including detours that avoid slippery zones. When shelves are rearranged, the team simply reruns the computation, and the robot receives an updated optimal routing table within seconds.