Reinforcement Learning/Policy iteration

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 $|A|\times |S|\times k$ where $k$ is the number of iterations needed for convergence. Theoretically, the maximum number of iterations is $|A{|}^{|S|}$.

The algorithm converges to the global optimum.

State-action value Q

State-action value of a policy $\pi$, is calculated by taking the specified action $a$ immediately, then following the policy$$Q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }\mid s,a)V^{\pi }(s^{\prime })$$Here, $R(s,a)$ is the reward function in MDP and $P(s^{\prime }|s,a)$ is the transition model.

Algorithm

• Set $i=0$
• Initialize ${\pi }_0(s)$ randomly for all states $s$
• While $i=0$ or $|{\pi }_i-{\pi }_{i-1}{|}_1>0$ (L1-norm, measures if the policy changed for any state):
  • Compute state-action value of a policy ${\pi }_i$, for all $s\in S$ and all $a\in A$ $$Q^{\pi }(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }\mid s,a)V^{\pi }(s^{\prime })$$
  • Compute new policy ${\pi }_{i+1}$, for all $s\in S$ by choosing the action that returns the maximum state-action value for each specific state$${\pi }_{i+1}(s)=\arg \underset{a}{\max }{Q}^{{\pi }_i}(s,a)\mathrm{\forall }s\in S$$

Explanation

In each iteration, by definition we have$$\arg \underset{a}{\max }{Q}^{{\pi }_i}(s,a)\ge Q^{{\pi }_i}(s,{\pi }_i(s))=V^{{\pi }_i}(s)\mathrm{\forall }s\in S$$

Proof

$$\begin{array}{cc}{V}^{{\pi }_i}(s)\le & \underset{a}{\max }{Q}^{{\pi }_i}(s,a)\\ =& \underset{a}{\max }R(s,a)+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,a)V^{{\pi }_i}(s^{\prime })\\ =& \underset{a}{\max }R(s,{\pi }_{i+1}(s))+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,{\pi }_{i+1}(s))V^{{\pi }_i}(s^{\prime })\leftarrow \text{by definition the action with the maximum Q value is taken as the new policy}\\ \le & \underset{a}{\max }R(s,{\pi }_{i+1}(s))+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,{\pi }_{i+1}(s))[\underset{a^{\prime }}{\max }{Q}^{{\pi }_i}(s^{\prime },a^{\prime })]\\ =& \underset{a}{\max }R(s,{\pi }_{i+1}(s))+\gamma \sum _{s^{\prime }\in S}P(s^{\prime }|s,{\pi }_{i+1}(s))[R(s^{\prime },{\pi }_{i+1}(s^{\prime }))+\gamma \sum _{s^{″}\in S}P(s^{″}|s^{\prime },{\pi }_{i+1}(s^{\prime }))V^{{\pi }_i}(s^{″})]\\ ⋮& \\ \le & V^{{\pi }_{i+1}}\end{array}$$