Value Iteration

Definition

Value iteration iteratively updates state-value function until convergence. Its time complexity is $O(S^{2}A)$ where $S$ and $A$ are the numbers of states and actions respectively.

Algorithm

1. Initialize $\forall s,V(s)=0$
2. Update $V(s)$ iteratively from all $V(s^{\prime })$ (full backup) until convergence to $V^{\ast }(s)$. $V(s)\leftarrow {\max }_a\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V(s^{\prime })]$
   • Synchronoius backups: compute $V_{k+1}(s)$ for all $s$ and update simultaneously.
   • Asynchronoius backups: compute $V_{k+1}(s)$ for one $s$ and update it immediately.
3. Compute the optimal policy ${\pi }_{\ast }$ (one-step lookahead) and return it. ${\pi }_{\ast }(s)=\underset{a}{\mathrm{argmax}}\underset{Q^{\ast }(s,a)}{\underbrace{\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V^{\ast }(s^{\prime })]}}$