What is the intuition behind comparing action values to state values in the policy improvement theorem?

Question

Sutton and Barto, in their book (Reinforcement Learning 2nd Edition) begin the discussion of policy improvement by comparing the action value $q_\pi(s, \pi'(s))$ to the state value $v_\pi(s)$.

What is the intuition behind this comparison?

It seems more natural to me to compare $q_\pi(s, \pi'(s))$ and $q_\pi(s, \pi(s))$. I understand that for deterministic policies $q_\pi(s, \pi(s))$ is the same as $v_\pi(s)$ so mathematically it makes no difference but perhaps conceptually it does?

Answer 1

Working with $v_\pi(s)$ is sometimes simpler because you don't need to worry about which action to take. When you use $q_\pi(s, a)$, the action $a$ need not come from the policy. This applies in general, but to your comment of comparing $q_\pi(s, \pi'(s))$ with $q_\pi(s, \pi(s))$, if you look at the second and remember the definition of the value functions as expectations:

$$v_\pi(s_t) = \mathbb{E}\big[ G_t | S_t = s_t \big]$$

and

$$q_\pi(s_t, a_t) = \mathbb{E}\big[ G_t | S_t = s_t , A_t = a_t \big]$$

, then you can see that $q_\pi(s_t, \pi(s)) \equiv v_\pi(s_t)$. The expectation is over all trajectories. $q_\pi$ allows you to deviate from the trajectories prescribed by a (deterministic) policy, but only for the next timestep after that, you follow the policy.

We need to find a way to evaluate a change to the policy to decide whether that change improved it or not. We could change the policy so that in a certain state $s$ it takes a different action $a'$, but as it is a deterministic policy, it will always choose that action in the future. Now, you have to consider all possible trajectories that go through a state, including those that go through that state multiple times, choosing the action $a'$ every time. It's quite messy.

Instead, you can say that you don't want to change your policy. If you happen to revisit your state in the future as part of your trajectory, you will follow the policy, but just this once you take a different action in the state. If you have an optimal policy, deviating from it will give you worse performance or another optimal policy. However, you cannot expect to get better than the optimal policy. If you do find that deviating from the optimal policy gives you better performance, then the policy wasn't optimal in the first place. You can incorporate that deviation from the policy to get an improved policy.

A similar scenario in driving: Let's pretend that there is no one else on the roads, so no traffic (deterministic policy). You know the best route from home to work, and you take that route every day. This is your policy. You believe that this is the best route to take, so there's no point in changing. One morning, you decide to take a turn, not in your policy. You don't expect to change your preferred route in general, but you do it just this once. You find that taking that turn gets you to work sooner, so your previous route wasn't indeed the best. You just found a better one. Again, this is assuming there is no traffic, i.e. deterministic policy. Even with a stochastic policy, it isn't too difficult to extend this idea. Instead of immediately updating your best route, you collect more observations (more trips to work) to see if it is better in general. Then you can also consider changes to the policy that are not deterministic, e.g. taking this turn only 30% of the times.