= Gauss-Seidel value iteration
{c}
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,\ldots,m$ is
$$
V_i^{\mathrm{new}}=\max_a\left[r(i,a)+\gamma\left(\sum_{j<i}P_{ij}(a)V_j^{\mathrm{new}}+\sum_{j\geq i}P_{ij}(a)V_j^{\mathrm{old}}\right)\right].
$$
This 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\leq\gamma<1$, let $V_*$ 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.
Back to article page