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$.

This version of value iteration updates state values in place, allowing later states in a sweep to use values just computed for earlier states. In a finite discounted Markov decision process, a sweep in the order $1,\dots ,m$ isThis formula uses the old self-component; solving a self-dependent scalar equation would be a different update convention. The ordinary synchronous update uses only old components throughout.

For $0\le \gamma <1$, let $V_{\ast }$ solve the maximizing Bellman equation and let the initial supremum norm error be $E$. Each component update has error at most $\gamma E$, because its transition probabilities average components whose errors are at most $E$. After every state has been updated once, the whole sweep has error at most $\gamma E$. Repeated full sweeps therefore converge to the same fixed point. The order can affect intermediate values and speed, even though it leaves the fixed point unchanged.