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.
| Step | Operation | Purpose |
|---|---|---|
| Initialize | Set V(s) to zero or any bounded value | Provides a starting estimate |
| Sweep | Apply the Bellman optimality update to every state | Improves all value estimates |
| Measure change | Record the maximum absolute change delta | Tracks progress toward the fixed point |
| Test stopping rule | Stop when delta is below a threshold | Bounds the remaining error |
| Extract policy | Choose the greedy action in each state | Turns values into decisions |
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 factor | Effective horizon | Convergence behavior |
|---|---|---|
| 0.5 | About 2 steps | Very fast, values reflect near rewards |
| 0.9 | About 10 steps | Moderate number of sweeps |
| 0.99 | About 100 steps | Slow, many sweeps for tight tolerance |
| 1.0 | Unbounded | Convergence only under extra conditions, such as guaranteed termination |
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.
| Method | Needs a model | Update style | Typical use |
|---|---|---|---|
| Value iteration | Yes | Full sweeps with maximization | Planning in small known problems |
| Policy iteration | Yes | Full evaluation, then greedy improvement | Few iterations, costly evaluation |
| Q-learning | No | Sampled one-step updates of action values | Learning from interaction |
| Temporal difference learning | No | Sampled bootstrapped updates for a policy | Prediction from experience |
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.
| Situation | Recommended approach | Reason |
|---|---|---|
| Known model, up to millions of states | Tabular value iteration | Exact and simple to implement |
| Known model, huge state space | Fitted or sampled variants | Full sweeps are infeasible |
| Unknown model, simulator available | Q-learning or model-based RL | Transition probabilities are not given |
| Continuous actions | Policy gradient methods | Maximization over actions is hard |
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.