Value iteration applies the Bellman optimality operator directly. It computes the optimal value as a fixed point and obtains policies by greedy extraction.
Optimal value iteration
The algorithm is the simplest fixed-point iteration for \(T_*\).
Definition. Starting from a bounded \(v_0\), value iteration sets \[ v_{k+1}=T_*v_k. \]
Theorem. The iterates satisfy \[ \|v_k-v_*\|_\infty\le\gamma^k\|v_0-v_*\|_\infty. \]
Proof. Use \(v_*=T_*v_*\) and the contraction property: \[ \|v_{k+1}-v_*\|_\infty\le\gamma\|v_k-v_*\|_\infty. \] Iterate the inequality.
Stopping by residual
Bellman residuals give computable stopping rules.
Proposition. If \(\|v_k-T_*v_k\|_\infty\le\varepsilon\), then \[ \|v_k-v_*\|_\infty\le\frac{\varepsilon}{1-\gamma}. \]
Proof. This is the residual bound for a contraction applied to \(T_*\).
Greedy policy loss
A nearly optimal value gives a nearly optimal greedy policy.
Theorem. If \(\pi\) is greedy with respect to \(v\), then \[ \|v_*-v_\pi\|_\infty\le \frac{2\gamma}{1-\gamma}\|v-v_*\|_\infty. \]
Proof. Greediness gives \(T_\pi v=T_*v\). Compare \[ v_*-v_\pi=T_*v_*-T_\pi v_\pi \] by adding and subtracting \(T_*v\) and \(T_\pi v\). The two approximation terms are each bounded by \(\gamma\|v-v_*\|_\infty\) or \(\gamma\|v-v_\pi\|_\infty\). Rearranging yields the standard bound.
Asynchronous updates
Tabular value iteration need not update all states at once.
Remark. Asynchronous value iteration updates selected coordinates using Bellman backups. Under discounted contraction and sufficient repeated updates of every state, the tabular iterates still converge to \(v_*\).
Geometric convergence
Value iteration uses \(V_{k+1}=TV_k\). For bounded rewards, \[ \|V_k-V^*\|_\infty \le\gamma^k\|V_0-V^*\|_\infty \le\frac{\gamma^k}{1-\gamma} \|TV_0-V_0\|_\infty. \] The Bellman residual is observable when the model is known and provides a stopping certificate independent of \(V^*\).
Loss of a greedy policy
Theorem. Let \(\pi_V\) be greedy with respect to \(V\). Then \[ \|V^*-V^{\pi_V}\|_\infty \le\frac{2\gamma}{1-\gamma}\|V-V^*\|_\infty. \] Also, \[ \|V^*-V^{\pi_V}\|_\infty \le\frac{2\gamma}{(1-\gamma)^2}\|TV-V\|_\infty. \]
Proof. Since \(T^{\pi_V}V=TV\), \[ V^*-V^{\pi_V} =TV^*-T^{\pi_V}V^{\pi_V}. \] Insert and subtract \(TV=T^{\pi_V}V\), take sup norms, and obtain \[ \|V^*-V^{\pi_V}\|_\infty \le\gamma\|V^*-V\|_\infty +\gamma\|V-V^{\pi_V}\|_\infty. \] Bound the second term by \(\|V-V^*\|+\|V^*-V^{\pi_V}\|\) and rearrange. The residual form follows from \(\|V-V^*\|\le\|TV-V\|/(1-\gamma)\).
Asynchronous and Gauss--Seidel updates
One need not update every state simultaneously. If each state is updated infinitely often and delays are uniformly bounded, asynchronous contractions still converge to \(V^*\). Using newly updated coordinates immediately gives Gauss--Seidel value iteration, often faster in practice. Fair visitation is essential: a state never updated can retain arbitrary error.
Relative value iteration
In average-reward problems, values are defined only up to an additive constant. Relative value iteration subtracts a reference component: \[ h_{k+1}=Th_k-(Th_k)(s_0)\mathbf1. \] Under unichain or communicating conditions, this can converge in span seminorm to the bias function. Discounted convergence proofs cannot simply be reused because the contraction modulus becomes one.
Numerical stability
When \(\gamma\) is near one, the iteration count scales like \((1-\gamma)^{-1}\log(1/\varepsilon)\), and residual-to-value conversion amplifies errors by the same effective horizon. Multistep lookahead, policy iteration, acceleration, and preconditioning target this poor conditioning, but each must preserve monotonicity or control extrapolation errors.