When discussing why the policy improvement theorem is true, when we do Monte Carlo control by updating greedily, it says on page 98 of Sutton and Barto's book (2nd edition) that:

$$ \begin{aligned} q_{\pi_{k}}\left(s, \pi_{k+1}(s)\right) &= q_{\pi_{k}}\left(s, \underset{a}{\arg \max } q_{\pi_{k}}(s, a)\right) \\ &= \max _{a} q_{\pi_{k}}(s, a) \\ & \geq q_{\pi_{k}}\left(s, \pi_{k}(s)\right) \\ & \geq v_{\pi_{k}}(s) \end{aligned} $$

I don't understand why the last inequality is not an equality.

The policy improvement theorem was derived on page 78 for deterministic policies.

So, the $\pi_{k}(s)$ we see in $q_{\pi_k}(s, \pi_{k}(s))$ is a fixed action, call it $a'$. Then, in this case, since $v_{\pi_k}(s)= \sum_a \pi_k(a|s) q_{\pi_k}(s, a) = 1 * q_{\pi_k}(s, a') = q_{\pi_k}(s, a')$ (where the second equality is because the probability of all other actions is 0), shouldn't the last inequality be an equality? When is it possible that we have a greater than relation?


You are right that the strict equality $q_\pi(s,\pi(s)) = v_\pi(s)$ is generally true for a deterministic policy $\pi$.

The $\geq$ inequality is also correct, of course, and it could be that the authors' intention was to show that $\pi_{k+1}$ and $\pi_k$ satisfy the condition for the policy improvement theorem:

Let $\pi$ and $\pi'$ be any pair of deterministic policies such that, for all $s\in\mathcal{S}$, $$q_\pi(s,\pi'(s))\geq v_\pi(s)\tag{4.7}$$

So they kinda relaxed the equality to show that the condition is satisfied "word-for-word" for $\pi'=\pi_{k+1}$ and $\pi=\pi_k$.

Although, I must say that they don't seem to be consistent in this - for example, they keep the strict equality at the derivation at the bottom of the page 78. So it might as well be that you've discovered a typo in Sutton and Barto.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.