The algorithm is described as below:

enter image description here

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$.

  • $\begingroup$ 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 $\endgroup$ Jul 15 at 10:46
  • $\begingroup$ 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. $\endgroup$
    – user529295
    Jul 15 at 11:03
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 15 at 11:20
  • $\begingroup$ This makes sense now. Thanks! $\endgroup$
    – user529295
    Jul 15 at 11:31

Your Answer

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

Browse other questions tagged or ask your own question.