Value Iteration

Value iteration is an algorithm for solving sequential decision problems represented as a Markov decision process (MDP). It repeatedly updates estimates of the best achievable long-term reward until they approach the optimal value function. A decision rule can then be extracted from these estimates. The method belongs to dynamic programming and provides a basic planning procedure in reinforcement learning. Its classical form assumes known transition probabilities and rewards rather than learning them directly through interaction. (incompleteideas.net)

Mathematical setting

Consider a finite MDP with states $S$, available actions $A(s)$, transition probabilities $P(s'\mid s,a)$, expected immediate rewards $r(s,a)$, and discount factor $0\leq\gamma<1$. For each state–action pair, $P(\cdot\mid s,a)$ is a probability distribution over successor states. The Markov property means that the current state and action contain the information needed to determine the next-state distribution. (web.stanford.edu)

A policy specifies how actions are chosen. Its discounted value is the expected value of accumulated rewards:

With bounded rewards, discounting makes this infinite series absolutely convergent. The optimal value $V^*(s)=\sup_\pi V^\pi(s)$ satisfies the optimality form of the Bellman equation:

This equation separates the immediate reward from the best attainable continuation value. (web.stanford.edu)

Update rule and policy extraction

Define the Bellman optimality operator $T$ by

Starting from any finite initial value vector $V_0$, value iteration applies the recurrence relation

Each update evaluates every available action through one-step lookahead and retains the largest result. This is a full backup: it averages over all possible successor states, rather than using a single sampled transition. (inst.eecs.berkeley.edu)

In synchronous value iteration, every entry of $V_{k+1}$ is computed using only $V_k$. A typical implementation initializes values to zero, performs complete sweeps through the states, and stops when a specified accuracy criterion is met. With zero initialization, $V_k$ also represents the optimal return for a $k$-step horizon with zero terminal payoff. Thus successive iterations extend the planning horizon. (inst.eecs.berkeley.edu)

For a computed value function $V$, a greedy policy selects

Any such policy is optimal when $V=V^*$. Ties permit more than one optimal action; selecting one consistently yields a deterministic policy. (wanghemath.github.io)

Convergence and stopping criteria

The central convergence result is that $T$ is a contraction mapping under the maximum norm, defined by $\|V\|_\infty=\max_s|V(s)|$:

Consequently, the Banach fixed-point theorem establishes a unique fixed point $V^*$ and convergence from every initial vector. The value error satisfies

This is geometric convergence, although it becomes slower as $\gamma$ approaches one. (wanghemath.github.io)

Because $V^*$ is unknown, implementations commonly monitor the Bellman residual,

It provides the computable bound

For synchronous iteration, $\delta(V_k)=\|V_{k+1}-V_k\|_\infty$. Therefore, stopping when this difference is at most $(1-\gamma)\varepsilon$ guarantees that $V_k$ has maximum-norm error at most $\varepsilon$. Small changes between sweeps must be interpreted relative to the discount factor. Value accuracy and greedy-policy performance are distinct quantities; the selected policy can become optimal before the numerical values have fully converged. (wanghemath.github.io)

Computational cost and variants

For $n$ states and at most $m$ actions per state, a dense transition model requires $O(n^2m)$ arithmetic operations per sweep, expressed in big-O notation. If each state–action pair has at most $d$ possible successors, the cost becomes $O(nmd)$. The value vectors require $O(n)$ storage, separately from storage for the model. Sparsity therefore substantially affects computational complexity. (cs.cmu.edu)

In-place updates immediately reuse newly computed values. Asynchronous variants update selected states instead of performing uniform sweeps. In the discounted setting, convergence can be maintained when every state continues to receive updates; implementations using delayed information also require suitable restrictions on that delay. Such methods allow computation to concentrate on relevant regions of the state space. (incompleteideas.net)

Related methods and limitations

Policy iteration alternates evaluation of a fixed policy with greedy improvement. Value iteration avoids completing each policy evaluation and instead repeatedly performs optimality backups. Modified policy iteration occupies an intermediate position by performing a limited number of evaluation updates before improving the policy. (incompleteideas.net)

Large or continuous state spaces often require function approximation, producing fitted or approximate value-iteration methods. Their approximation step changes the operator, so the classical tabular contraction guarantee does not automatically apply. Divergence is possible for some combinations of updates and approximators. (see.stanford.edu)

The discounted proof also does not extend unchanged to $\gamma=1$. Undiscounted problems require additional assumptions, while finite-horizon problems use time-indexed backward recursion. Average-cost formulations employ related methods such as relative value iteration, with different convergence conditions. (web.stanford.edu)

References

1. 3 Value Iteration — Introduction to Artificial Intelligenceinst.eecs.berkeley.edu
2. Value Iterationcs.cmu.edu
3. 11 Value Iteration — Reinforcement Learning: A Mathematical Introductionwanghemath.github.io
4. Algorithm 2 discounted value iterationweb.stanford.edu
5. CertRL: Formalizing Convergence Proofs for Value and Policy Iteration in Coqarxiv.org
6. Machine Learning — Lecture 17see.stanford.edu
7. The Divergence of Reinforcement Learning Algorithms with Value-Iteration and Function Approximationarxiv.org
8. An Empirical Algorithm for Relative Value Iteration for Average-Cost MDPsweb.stanford.edu