One way, then, to find an optimal policy is to find the optimal value function. It is not obvious when to stop the value iteration algorithm. This provides an effective stopping criterion for the algorithm. And in practice, the greedy policy is often optimal long before the value function has converged.
Value iteration is very flexible.
The assignments to V need not be done in strict order as shown above, but instead can occur asynchronously in parallel provided that the value of every state gets updated infinitely often on an infinite run. Updates based on Equation 1 are known as full backups since they make use of information from all possible successor states. The computational complexity of the value-iteration algorithm with full backups, per iteration, is quadratic in the number of states and linear in the number of actions. If there are on average a constant number of next states with non-zero probability then the cost per iteration is linear in the number of states and linear in the number of actions. The number of iterations required to reach the optimal value function is polynomial in the number of states and the magnitude of the largest reward if the discount factor is held constant.