# Doubt in Sutton & Barto's off-policy Monte Carlo control algorithm

The algorithm is described as below:

My understanding: In the third last step, we act greedily w.r.t $$Q$$. Since we use importance sampling, this $$Q \approx Q_\pi$$. However, in the next step, whenever $$A_t \neq \pi(S_t)$$, it means the behavior policy isn't aligned with the target (greedy) policy. Hence, we can't use importance sampling and for such $$(S_t, A_t)$$ we simply take the average of $$Q(S_t, A_t)$$. Which means these $$Q$$ values aren't estimates of $$Q_\pi$$ but rather $$Q_b$$.

What's been bothering me is when the behavior and target policy eventually align for state $$S_t$$, won't that alignment be incorrect? Because in the previous step, we would be doing:

$$\pi(S_t) = \arg \max [Q_\pi(S_t, a_1), Q_b(S_t, a_2), Q_b(S_t, a_3)]$$

assuming $$A(S_t) = \{a_1, a_2, a_3\}$$ and the true greedy action is $$a_1$$.

• Could you clarify "We simply take the average of $Q(S_t,A_t)$."? What is this average taken over, and where is it used? AFAICS, the only Q update step uses weighed importance sampling. I guess you are making some interpretation of this update function in the case you describe ($\pi(S_t) \neq A_t$ after the update step), but I am not sure what you are thinking Jul 15 at 10:46
• If $\pi(S_t) \neq A_t$, $W$ will always be 1. Hence, when I revisit the $(S_t, A_t)$ in a new episode, my $C(S_t, A_t)$ will increment by 1. And my $Q(S_t, A_t)$ will be the running average. But this $Q$ for $(S_t, A_t)$ is an estimate of $Q_b$ as the behavior policy isn't aligned with target policy. Jul 15 at 11:03
• OK, yes. That's actually covered in the book under weighted importance sampling. The initial estimates in weighted importance sample are biased towards action values of $Q_b$ but will converge on $Q_{\pi}$ - and specifically the first sample will also be an unbiased estimate of $Q_b$. The bias is unwanted but usually preferable to the potentially unbound variance of basic importance sampling. Jul 15 at 11:20
• This makes sense now. Thanks! Jul 15 at 11:31