= Value iteration
For a finite discounted <Markov decision process>, <value iteration> repeatedly applies the <Bellman operator>:
$$
V_{n+1}(s)=\max_a\left(r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V_n(s')\right),\qquad0\leq\gamma<1.
$$
The operator is a contraction by factor $\gamma$ in the <supremum norm>, so the iterates converge to its unique <fixed point>, the optimal value. The proof bounds the change of each action value by $\gamma\|V-W\|_\infty$ and uses the same bound after maximization.
In a one-state system with one action giving reward one, $V_{n+1}=1+\gamma V_n$ and the <limit> is $1/(1-\gamma)$. Undiscounted problems require different assumptions; this contraction proof fails at $\gamma=1$.
Back to article page
