Policy Iteration (PI) is one of the algorithms for finding the optimal policy (MDP control).

Policy iteration is a model-based algorithm.

The complexity of the algorithm is ${\displaystyle |A|\times |S|\times k}$ where ${\displaystyle k}$ is the number of iterations needed for convergence. Theoretically, the maximum number of iterations is ${\displaystyle |A|^{|S|}}$.

The algorithm converges to the global optimum.

State-action value ${\displaystyle Q}$

State-action value of a policy ${\displaystyle \pi }$, is calculated by taking the specified action ${\displaystyle a}$ immediately, then following the policy

$${\displaystyle Q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s'\in S}P(s'\mid s,a)V^{\pi }(s')}$$

Here, ${\displaystyle R(s,a)}$ is the reward function in MDP and ${\displaystyle P(s'|s,a)}$ is the transition model.

Algorithm

• Set ${\displaystyle i=0}$
• Initialize ${\displaystyle \pi _{0}(s)}$ randomly for all states ${\displaystyle s}$
• While ${\displaystyle i=0}$ or ${\displaystyle |\pi _{i}-\pi _{i-1}|_{1}>0}$ (L1-norm, measures if the policy changed for any state):
  • Compute state-action value of a policy ${\displaystyle \pi _{i}}$, for all ${\displaystyle s\in S}$ and all ${\displaystyle a\in A}$
    $${\displaystyle Q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s'\in S}P(s'\mid s,a)V^{\pi }(s')}$$

    
  • Compute new policy ${\displaystyle \pi _{i+1}}$, for all ${\displaystyle s\in S}$ by choosing the action that returns the maximum state-action value for each specific state
    $${\displaystyle \pi _{i+1}(s)=\arg \max _{a}Q^{\pi _{i}}(s,a)~~~\forall s\in S}$$

    

Explanation

In each iteration, by definition we have

$${\displaystyle \arg \max _{a}Q^{\pi _{i}}(s,a)\geq Q^{\pi _{i}}(s,\pi _{i}(s))=V^{\pi _{i}}(s)~~~\forall s\in S}$$

Proof

$${\displaystyle {\begin{aligned}V^{\pi _{i}}(s)\leq &~\max _{a}Q^{\pi _{i}}(s,a)\\=&~\max _{a}R(s,a)+\gamma \sum _{s'\in S}P(s'|s,a)V^{\pi _{i}}(s')\\=&~\max _{a}R(s,\pi _{i+1}(s))+\gamma \sum _{s'\in S}P(s'|s,\pi _{i+1}(s))V^{\pi _{i}}(s')~~~\leftarrow {\text{by definition the action with the maximum Q value is taken as the new policy}}\\\leq &~\max _{a}R(s,\pi _{i+1}(s))+\gamma \sum _{s'\in S}P(s'|s,\pi _{i+1}(s)){\Big [}\max _{a'}Q^{\pi _{i}}(s',a'){\Big ]}\\=&~\max _{a}R(s,\pi _{i+1}(s))+\gamma \sum _{s'\in S}P(s'|s,\pi _{i+1}(s)){\Bigg [}R(s',\pi _{i+1}(s'))+\gamma \sum _{s''\in S}P(s''|s',\pi _{i+1}(s'))V^{\pi _{i}}(s''){\Bigg ]}\\\vdots &\\\leq &~V^{\pi _{i+1}}\end{aligned}}}$$