Answers.Body: <p>This problem bothered me as well and I don't think the answer by Philip Raeisghasem above is satisfactory. Reducing variance is a desired property but one also has to show that the final result is correct.</p>
  <p>Consider the general form of TD update</p>
  <p><span class="math-container">$$
  Q_{t+n}(S_t,A_t) = Q_{t+n-1}(S_t,A_t) + \alpha \Delta
  $$</span></p>
  <p>The desired property for <span class="math-container">$\Delta$</span> is that <em>under the behavior policy</em> <span class="math-container">$\mu$</span> we have</p>
  <p><span class="math-container">$$
  \mathbb E_\mu[\Delta] = 0
  $$</span></p>
  <p>so that we have convergence under the behavior policy and that this expression makes sense for the problem.</p>
  <p>Now consider</p>
  <p><span class="math-container">$$
  \mathbb E_\mu[ \rho_{t+1:t+n} G_{t:t+n}] = \mathbb E_\pi[ G_{t:t+n}]
  $$</span></p>
  <p>We also want to learn the state-action values for the target policy so we <em>would like</em></p>
  <p><span class="math-container">$$
  \mathbb E_\pi[ G_{t:t+n}] = \mathbb E_\pi[Q_{t+n-1}(S_t,A_t)]
  $$</span></p>
  <p>However, under the behavior policy</p>
  <p><span class="math-container">$$
  \mathbb E_\pi[Q_{t+n-1}(S_t,A_t)]= \mathbb E_\mu[ \rho_{t+1:t+n-1} Q_{t+n-1}(S_t,A_t)] 
  $$</span></p>
  <p>Extra steps of importance sampling do not affect the mean, and even though they increase variance, the resulting expression is often simpler. If we add an extra factor of <span class="math-container">$\rho_{t+n}$</span> to the expression for the state-action value we get the desired update rule using
  <span class="math-container">$$
  \Delta = \rho_{t+1:t+n} ( G_{t:t+n} -  Q_{t+n-1})
  $$</span></p>
  <p>Of course, there are modifications of this expression to removed importance sampling expression in the future of individual rewards in the return that are discussed in section 7.4 of Sutton and Barto.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-26T13:44:47.247Z
Answers.LastActivityDate: 2024-10-27T21:57:56.060Z
Answers.LastEditDate: 2024-10-27T21:57:56.060Z
Answers.UserDisplayName: Borun Chowdhury
Answers.Body: <p>Multiplying the entire update by <span class="math-container">$\rho$</span> has the desirable property that experience affects <span class="math-container">$Q$</span> less when the behavior policy is unrelated to the target policy. In the extreme, if the trajectory taken has zero probability under the target policy, then <span class="math-container">$Q$</span> isn't updated at all, which is good. Alternatively, if only <span class="math-container">$G$</span> is scaled by <span class="math-container">$\rho$</span>, taking zero probability trajectories would artificially drive <span class="math-container">$Q$</span> to zero.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-25T23:45:05.860Z
Answers.Text: This answer does show that the behavior is desirable but it's not a proof. How can one prove that this is the right thing to do?
Answers.UserDisplayName: Borun Chowdhury
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-01-26T00:19:29.777Z
Answers.Text: In fact, we also need to realized that the importance sampling factor and the estimate are uncorrelated (I don't yet exactly understand why but in section 7.4 Sutton and Barto say "Notice that the control variate does not change the expected update; the importance sampling ratio has expected value one (Section 5.9) and is uncorrelated with the estimate, so the expected value of the control variate is zero." and the same reasoning would apply here) and since the importance sampling has expectation one, the two updates are equal on expectation.
Answers.UserDisplayName: Borun Chowdhury
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-04-05T20:44:26.283Z
Answers.LastActivityDate: 2019-04-05T20:44:26.283Z
Answers.UserDisplayName: Philip Raeisghasem
Body: <p>In Sutton &amp; Barto's book (2nd ed) page 149, there is the equation 7.11</p>
  
  <p><a href="https://i.sstatic.net/tWlV2.png" rel="noreferrer"><img src="https://i.sstatic.net/tWlV2.png" alt="enter image description here"></a></p>
  
  <p>I am having a hard time understanding this equation.</p>
  
  <p>I would have thought that we should be moving <span class="math-container">$Q$</span> towards <span class="math-container">$G$</span>, where <span class="math-container">$G$</span> would be corrected by importance sampling, but only <span class="math-container">$G$</span>, not <span class="math-container">$G-Q$</span>, therefore I would have thought that the correct equation would be of the form</p>
  
  <p><span class="math-container">$Q \leftarrow Q + \alpha (\rho G - Q)$</span></p>
  
  <p>and not</p>
  
  <p><span class="math-container">$Q \leftarrow Q + \alpha \rho (G - Q)$</span></p>
  
  <p>I don't get why the entire update is weighted by <span class="math-container">$\rho$</span> and not only the sampled return <span class="math-container">$G$</span>.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-05T14:30:08.963Z
Comments.Text: Thank you @nbro for the edit, I was a bit lazy with the equations :)
Comments.UserDisplayName: Antoine Savine
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-04-05T14:31:04.993Z
Comments.Text: Hi Antoine! Please, next time try to at least put some more effort to write these equations! Whenever I can, I try to write them nicely, but I would prefer if every user does it for its own questions/answers, of course!
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><sutton-barto><off-policy-methods><temporal-difference-methods><sarsa>
Title: Understanding the n-step off-policy SARSA update
UserDisplayName: Antoine Savine
ThreadText: # Understanding the n-step off-policy SARSA update
  
  (Asked by: username_0 on 2019-04-05)
  
  In Sutton & Barto's book (2nd ed) page 149, there is the equation 7.11
  
  [![enter image description here](https://i.sstatic.net/tWlV2.png)](https://i.sstatic.net/tWlV2.png)
  
  I am having a hard time understanding this equation.
  
  I would have thought that we should be moving $Q$ towards $G$, where $G$ would be corrected by importance sampling, but only $G$, not $G-Q$, therefore I would have thought that the correct equation would be of the form
  
  $Q \leftarrow Q + \alpha (\rho G - Q)$
  
  and not
  
  $Q \leftarrow Q + \alpha \rho (G - Q)$
  
  I don't get why the entire update is weighted by $\rho$ and not only the sampled return $G$.
  
  **Tags:** reinforcement-learning, sutton-barto, off-policy-methods, temporal-difference-methods, sarsa
  > **Comments:**
  > **username_0**: Thank you @nbro for the edit, I was a bit lazy with the equations :)  
  > **username_1**: Hi Antoine! Please, next time try to at least put some more effort to write these equations! Whenever I can, I try to write them nicely, but I would prefer if every user does it for its own questions/answers, of course!  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2019-04-05. Score: 2 | Accepted answer
  
  Multiplying the entire update by $\rho$ has the desirable property that experience affects $Q$ less when the behavior policy is unrelated to the target policy. In the extreme, if the trajectory taken has zero probability under the target policy, then $Q$ isn't updated at all, which is good. Alternatively, if only $G$ is scaled by $\rho$, taking zero probability trajectories would artificially drive $Q$ to zero.
  
  > **Comments:**
  > **username_2**: This answer does show that the behavior is desirable but it's not a proof. How can one prove that this is the right thing to do?  
  > **username_2**: In fact, we also need to realized that the importance sampling factor and the estimate are uncorrelated (I don't yet exactly understand why but in section 7.4 Sutton and Barto say "Notice that the control variate does not change the expected update; the importance sampling ratio has expected value one (Section 5.9) and is uncorrelated with the estimate, so the expected value of the control variate is zero." and the same reasoning would apply here) and since the importance sampling has expectation one, the two updates are equal on expectation.  
  
  ---
  
  ### Answer by username_2 on 2024-01-26. Score: 1
  
  This problem bothered me as well and I don't think the answer by Philip Raeisghasem above is satisfactory. Reducing variance is a desired property but one also has to show that the final result is correct.
  
  Consider the general form of TD update
  
  $$
  Q\_{t+n}(S\_t,A\_t) = Q\_{t+n-1}(S\_t,A\_t) + \alpha \Delta
  $$
  
  The desired property for $\Delta$ is that *under the behavior policy* $\mu$ we have
  
  $$
  \mathbb E\_\mu[\Delta] = 0
  $$
  
  so that we have convergence under the behavior policy and that this expression makes sense for the problem.
  
  Now consider
  
  $$
  \mathbb E\_\mu[ \rho\_{t+1:t+n} G\_{t:t+n}] = \mathbb E\_\pi[ G\_{t:t+n}]
  $$
  
  We also want to learn the state-action values for the target policy so we *would like*
  
  $$
  \mathbb E\_\pi[ G\_{t:t+n}] = \mathbb E\_\pi[Q\_{t+n-1}(S\_t,A\_t)]
  $$
  
  However, under the behavior policy
  
  $$
  \mathbb E\_\pi[Q\_{t+n-1}(S\_t,A\_t)]= \mathbb E\_\mu[ \rho\_{t+1:t+n-1} Q\_{t+n-1}(S\_t,A\_t)]
  $$
  
  Extra steps of importance sampling do not affect the mean, and even though they increase variance, the resulting expression is often simpler. If we add an extra factor of $\rho\_{t+n}$ to the expression for the state-action value we get the desired update rule using
  $$
  \Delta = \rho\_{t+1:t+n} ( G\_{t:t+n} - Q\_{t+n-1})
  $$
  
  Of course, there are modifications of this expression to removed importance sampling expression in the future of individual rewards in the return that are discussed in section 7.4 of Sutton and Barto.
  
  
  ---
  
  