 Value iteration

For a finite discounted Markov decision process, value iteration repeatedly applies the Bellman operator: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 \Vert V-W{\Vert }_{\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$.