Policy Iteration

Intuition: build a policy, then build value function, and then build a better policy, and rinse and repeat until the optimal policy.

Policy iteration is the process of alternating between 2 things:

1. Policy Evaluation With fixed current policy $\pi$, find values with simplified Bellman expectation backups (iterate until values converge)

$v_{i+1}^{\pi }(s)={\sum }_{s^{\prime },r}p(s^{\prime },r|s,\pi (s))[r+\lambda v_i^{\pi }(s^{\prime })]$ Other Notation from CS287 $V_{i+1}^{{\pi }_k}(s)={\sum }_{s^{\prime }}T(s,\pi (s),s^{\prime })[R(s,{\pi }_k(s),s^{\prime })+\gamma V_i^{\ast }(s^{\prime })]$

• Notice that the above is extremely similar, instead of using the $T(s,a,s^{\prime })$ in Value Iteration we can use $T(s,\pi (s),s^{\prime })$ to evaluate a particular policy.
• We are not taking the max because we don’t have a choice, the policy $\pi$ decides the action $a=\pi (s)$

2. Policy Improvement With fixed utilities, find the best action according to one-step lookahead. You basically override the action for the very first action.

• Improve the policy by acting greedily with respect to $v_{\pi }$ (Policy Improvement) ${\pi }^{\prime }=\text{greedy}(v_{\pi })$ ${\pi }^{\prime }(s)=\underset{a\in A}{\mathrm{argmax}}{q}_{\pi }(s,a)$ ${\pi }_{k+1}(s)={\text{argmax}}_a{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)(r+\gamma v_k(s^{\prime }))$ Alternative notation from CS287: ${\pi }_{k+1}(s)={\text{argmax}}_a{\sum }_{s^{\prime }}T(s,a,s^{\prime })[R(s,a,s^{\prime })+\gamma V^{{\pi }_k}(s^{\prime })]$ Repeat steps 1 and 2 until the policy converges, i.e. ${\pi }_k(s)={\pi }_{k+1}(s)$

Policy iteration always converges to the optimal policy ${\pi }_{\ast }$. In terms of comparing with Value Iteration, this is a lot longer it seems, because we need to figure calculate the value function for a particular policy, and then come up with a new policy.

The example below is done with action-value functions, whereas the textbook uses state-value functions. It's essentially the same thing, but in [[Model-Free Control]], we always use q-values, and model-free are where the more interesting problems are. 

Proof

We essentially act greedily with respect to the action-value functions, doing a Bellman Optimality Backup.

This improves the value from any state $s$ over one step, $q_{\pi }(s,{\pi }^{\prime }(s))\ge q_{\pi }(s,\pi (s))$ It therefore improves the value function, $v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s)$

Related

• Value Iteration