Do I really need to do policy evaluation until convergence in policy iteration?

Question

I am currently studying Sutton's book, and I learned that in policy iteration, policy evaluation is done until the value function converges, and then policy improvement is performed.

However, I have seen elsewhere that even without waiting for the value function to converge, and even performing policy evaluation only once, if policy iteration (evaluation and improvement) is repeated, the optimal policy will still be obtained.

I am confused by this. Even if I wrote a simple code for an experiment, I don't understand why policy evaluation needs to be done until convergence. Because I see that the results are the same whether policy evaluation is done 3 times, 2 times, or 1000 times before policy improvement when policy iteration is done repeatedly. Even repeating the process of performing policy evaluation only once and then improvement yields the same results. I don't know how to accept this.

Could you please help me?

Answer 1

I don't understand why policy evaluation needs to be done until convergence

It doesn't need to be, although the resulting algorithm if you cut short of convergence is not strictly policy iteration as it is usually defined. This freedom of choice (how accurately to measure values, when to make changes to improve policy) is the premise behind Generalized Policy Iteration (GPI), which is the supporting theory behind all value-based RL methods. In GPI, it is acknowledged that any combination of approximating current values and then improving policy based on the new approximate values is likely to converge to an optimal control solution eventually.

However, policy iteration with accurate valuation followed by policy improvement in separate stages is supported by a relatively simple and robust proof - the Policy Improvement Theorem, which is shown in the same chapter in Sutton&Barto.

Proofs of convergence for other methods that are based on GPI are harder (e.g. for Q-learning) or still open and unproven (e.g. for Monte Carlo control).

The book will get quite quickly to GPI from where you are in it. Keep reading!