Policy Iteration

The idea behind policy iteration is simple:

1. Take some initial $\pi$ and $v$.
2. Use policy evaluation to update $v$ until it's consistent with $\pi$.
3. Use policy improvement to update $\pi$ until it's greedy with respect to $v$.
4. Repeat steps 2-3 until convergence.

In this method, there are no partial updates:

• During policy evaluation, values are updated for each state, until they are consistent with current policy;
• During policy improvement, policy is made greedy with respect to value function.

Pseudocode