Policy Iteration (using approximate evaluation)

Hence our modified policy iteration is, repeated until convergence:

1. Approximate policy evaluation: repeat fixed number of times $U_{i+1}(s)\leftarrow R(s)+\gamma {\sum }_{s^{\prime }}P(s^{\prime }|s,{\pi }_i(s))U_i(s^{\prime })$
2. Policy improvement: for every state $s$: ${\pi }_{i+1}(s)=\text{arg }\underset{a\in A(s)}{\max }{\sum }_{s^{\prime }}P(s^{\prime }|s,a)U_i(s^{\prime })$