Policy Improvement

Policy Improvement Theorem

If $q_{\pi }(s,{\pi }^{\prime }(s))\ge v_{\pi }(s)$ for all $s$, then ${\pi }^{\prime }$ is at least as good as $\pi$: $v_{{\pi }^{\prime }}(s)\ge v_{\pi }(s)$ for all $s$.

The greedy policy ${\pi }^{\prime }(s)=\arg {\max }_a{q}_{\pi }(s,a)$ satisfies this condition (by definition of max). Therefore, making the policy greedy w.r.t. its own value function always improves it (or leaves it unchanged if already optimal).

This theorem justifies the improvement step in Policy Iteration and Generalized Policy Iteration.

Appears In

• RL-L02 - Dynamic Programming, RL-Book Ch4 - Dynamic Programming