enter image description here

Above is the algorithm for Policy Iteration from Sutton's RL book. So, step 2 actually looks like value iteration, and then, at step 3 (policy improvement), if the policy isn't stable it goes back to step 2.

I don't really understand this: it seems like, if you do step 2 to within a small $\Delta$, then your estimate of the value function should be pretty close to optimal for each state.

So, why would you need to visit it again after policy improvement?

It seems like policy improvement only improves the policy function, but that doesn't affect the value function, so I'm not sure why you'd need to go back to step 2 if the policy isn't stable.


1 Answer 1


There is a difference between accurate value function estimates, and optimal value functions. An optimal value function is more specifically the value function of an optimal policy.

Value functions are always specific to some policy, which is why you will often see the subscript $\pi$ in e.g. $v_{\pi}(s)$ when there is a defined policy.

The policy evaluation step (step 2) in policy iteration converges to an accurate value function estimate for whatever the current policy is. In general this will not be an optimal value function, except on the last time that step 2 is used, and there is no change to the policy in the next stage policy improvement (step 3).

The policy improvement stage (step 3) can only usefully be run once for any value function estimate. The policy is updated to be greedy with respect to the value function from step 2 - that will always give the same results from the same value function estimate. If the value function is accurate then this new policy is guaranteed to be as good or better than the previous policy. Once step 3 is done, further improvements are only possible if the new policy is accurately evaluated.

Comparison with value iteration

The difference with value iteration is that it never accurately evaluates any interim policies. In value iteration, the implied policy changes every time the maximising action changes due to new value estimates. In the later stages, when the optimal policy has been found and is stable, then the value function will converge to the optimal value function. In value iteration, most of the interim value functions are not accurate, but when it becomes accurate it will also be the optimal value function.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .