Policy Iteration

Definition

Policy iteration repeats policy evaluation and policy improvement until convergence. Its time complexity is $O(S^2)$ where $S$ and $A$ are the numbers of states and actions respectively.

Compare to Value Iteration, policy iteration requires much fewer iterations to reach optimal policy.

Policy Evaluation

Compute $V^{\pi }$ from the deterministic policy $\pi$. $V_{k+1}(s)\leftarrow \sum _{s^{\prime },r}p(s^{\prime },r|s,\pi (s))[r+\gamma V_k(s^{\prime })]$

Policy Improvement

Improve $\pi$ to ${\pi }^{\prime }$ by greedy policy based on $V^{\pi }$. ${\pi }^{\prime }(s)=\underset{a}{\mathrm{argmax}}\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V^{\pi }(s^{\prime })]=\underset{a}{\mathrm{argmax}}{Q}^{\pi }(s,a)$

Since $Q^{\pi }(s,{\pi }^{\prime }(s))\ge V^{\pi }(s)=\sum _a\pi (a|s)Q^{\pi }(s,a)$, always either ${\pi }^{\prime }$ is strictly better than $\pi$ or ${\pi }^{\prime }$ is optimal when ${\pi }^{\prime }=\pi$ by the Policy Improvement Theorem.

Algorithm

1. Initialize $\forall s,V(s)=0$, and $\forall s,\pi (s)\in \mathcal{A}(s)$ arbitrarily.
2. Update every $V(s)$ from all $V(s^{\prime })$ (full backup) until convergence to $V^{\pi }(s)$. $V(s)\leftarrow \sum _{s^{\prime },r}p(s^{\prime },r|s,\pi (s))[r+\gamma V(s^{\prime })]$
3. Improve $\pi$ by greedy policy based on $V^{\pi }$. $\pi (s)\leftarrow \underset{a}{\mathrm{argmax}}\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma V(s^{\prime })]$
4. If policy is stable, then stop and return $V\approx v_{\ast }$ and $\pi \approx {\pi }_{\ast }$.

Examples