policy improvement theorem

The policy improvement theorem is the guarantee that makes reinforcement learning climb rather than wander. It says: take your current policy, evaluate it to get its value function, then build a new policy that acts greedily — picks the highest-value action — with respect to that function. The new policy is never worse than the old one in any state, and unless the old one was already optimal, it is strictly better somewhere.

This single result is the heartbeat of policy iteration: evaluate, then improve, then evaluate the improvement, and so on. Each round either makes genuine progress or signals that you have reached an optimal policy, because no further greedy step can help. The theorem is why estimate values, then act greedily on them is not just a heuristic but a method that provably converges to the best possible behaviour in a finite MDP.