 Gauss-Seidel value iteration

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.