policy iteration

We evaluate our current best policy $\pi$ and thereby iteratively approximate our value function to the true value of the policy, exactly like in value iteration, but instead of taking the action with the maximum value, we act according to $\pi$.

$$\begin{array}{rl}{V}_{\pi }(s)& =\mathbb{E}[R(s^{\prime },s,\pi (s))+\gamma V(s^{\prime })]\\ & =\sum _{s^{\prime }}P(s^{\prime }\mid s,\pi (s))(R(s^{\prime },s,\pi (s))+\gamma V_{\pi }(s^{\prime }))\\ & =Q_{\pi }(s,a)\end{array}$$

Then, we lock in the value function, and try to iteratively update the policy, so we can take the best action:

$$\begin{array}{rl}\pi (s)& =\arg \underset{a}{\max }\mathbb{E}[R(s^{\prime },s,a)+\gamma V_{\pi }(s^{\prime })])\\ & =\arg \underset{a}{\max }{Q}_{\pi }(s,a)\end{array}$$

The big difference to value iteration is, that we do not need a model of the environment, at least not an explicit one: The information is implicitly in the Q-function, i.e. we can do model-free RL.

Policy iteration is guaranteed to converge to optimality.

If we have a policy $\pi$ and generate an improved version ${\pi }^{\prime }$ by greedily taking actions ${\pi }^{\prime }(s)=\arg {\max }_a{Q}_{\pi }(s,a)$, the value of the improved policy ${\pi }^{\prime }$ is guaranteed to be better because:

$$\begin{array}{rl}{Q}_{\pi }(s,{\pi }^{\prime }(s))& =Q_{\pi }(s,\arg \underset{a}{\max }{Q}_{\pi }(s,a))\\ \underset{Q_{\pi }(s,{\pi }^{\prime }(s))}{\underbrace{\underset{a}{\max }{Q}_{\pi }(s,a)}}& \ge \underset{V_{\pi }(s)}{\underbrace{Q_{\pi }(s,\pi (s))}}\end{array}$$

Local greediness yields global optimality: Because each policy improvement step is locally greedy with respect to the current value function, it can never decrease performance. If there is any state where the greedy action has a higher Q-value than the old policy’s action, then you get a strictly better policy overall. If no improvement is possible in any state, you must already be at an optimal policy.

This iterative process is often done asynchronously with multiple actors evaluating potentially older policies, so updates will kind of be a weighted average.

This is a type of dynamic programming, like value iteration, given perfect information about the environment, we can find the optimal solution by DP. You can just code this algorithm up to solve low dimensional problems (e.g. tic tac toe), without neural nets.

PI Typically converges faster (less iterations) than VI, but requires more computation per iteration.