Body: <p>The algorithm is described as below:</p>
  <p><a href="https://i.sstatic.net/rqfCt.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/rqfCt.png" alt="enter image description here" /></a></p>
  <p><strong>My understanding:</strong> In the third last step, we act greedily w.r.t <span class="math-container">$Q$</span>. Since we use importance sampling, this <span class="math-container">$Q \approx Q_\pi$</span>. However, in the next step, whenever <span class="math-container">$A_t \neq \pi(S_t)$</span>, it means the behavior policy isn't aligned with the target (greedy) policy. Hence, we can't use importance sampling and for such <span class="math-container">$(S_t, A_t)$</span> we simply take the average of <span class="math-container">$Q(S_t, A_t)$</span>. Which means these <span class="math-container">$Q$</span> values aren't estimates of <span class="math-container">$Q_\pi$</span> but rather <span class="math-container">$Q_b$</span>.</p>
  <p>What's been bothering me is when the behavior and target policy eventually align for state <span class="math-container">$S_t$</span>, won't that alignment be incorrect? Because in the previous step, we would be doing:</p>
  <blockquote>
  <p><span class="math-container">$\pi(S_t) = \arg \max [Q_\pi(S_t, a_1), Q_b(S_t, a_2), Q_b(S_t, a_3)]$</span></p>
  </blockquote>
  <p>assuming <span class="math-container">$A(S_t) = \{a_1, a_2, a_3\}$</span> and the true greedy action is <span class="math-container">$a_1$</span>.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-07-15T10:46:25.513Z
Comments.Text: 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
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-07-15T11:03:29.420Z
Comments.Text: 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.
Comments.UserDisplayName: user529295
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-07-15T11:20:56.233Z
Comments.Text: 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.
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><monte-carlo-methods><off-policy-methods>
Title: Doubt in Sutton & Barto's off-policy Monte Carlo control algorithm
UserDisplayName: user529295
ThreadText: # Doubt in Sutton & Barto's off-policy Monte Carlo control algorithm
  
  (Asked by: username_0 on 2021-07-15)
  
  The algorithm is described as below:
  
  [![enter image description here](https://i.sstatic.net/rqfCt.png)](https://i.sstatic.net/rqfCt.png)
  
  **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$.
  
  **Tags:** reinforcement-learning, monte-carlo-methods, off-policy-methods
  > **Comments:**
  > **username_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  
  > **username_0**: 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.  
  > **username_1**: 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.  
  
  ---
  
  ## 0 answers
  
  