Policy Iteration

Rather than compute optimal utility values, policy iteration looks through the space of possible policies. We start from some initial policy ${\pi }_0$ and do:

1. Policy evaluation: given a policy ${\pi }_i$, calculate $U_i(s)$ Given a policy, the choice of action in a given state is fixed so compute for every state:

$$U_i(s)=R(s)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,{\pi }_i(s))U_i(s^{\prime })$$

Abstract

We have lots of simultaneous equations again, but this is now linear! (no max)

2. Policy improvement: given $U_i(s)$, compute ${\pi }_{i+1}$ Calculate a new policy ${\pi }_{i+1}$ by applying:

$${\pi }_{i+1}(s)=\text{arg }\underset{a\in A(s)}{\max }\sum _{s^{\prime }}P(s^{\prime }|s,a)U_i(s^{\prime })$$

for each state $s$. (we do a one-step MEU lookahead)

We perform both of these until convergence, the iteration will terminate when there is no improvement in utility from one iteration to the next. (at this point the utility $U_i$ is a fixed point of the Bellman update and so ${\pi }_i$ must be optimal)