Answers.Body: <blockquote>
    <p>Why don't they just update the value with a weight for the value from previous episodes <span class="math-container">$\alpha$</span> and a weight <span class="math-container">$1- \alpha$</span> for the new episode return as it is done in TD-Learning?</p>
  </blockquote>
  
  <p>In my opinion, this is a mistake in the book. I went back and checked that this is still the same in the <a href="http://incompleteideas.net/book/RLbook2018.pdf" rel="nofollow noreferrer">finished second edition</a>, and it is still there.  </p>
  
  <p>Keeping all returns and taking averages works fine in a prediction scenario with a fixed policy, and it is somewhat simpler and more intuitive to explain as "this is the mean value" (efficiency can come later, after comprehension). However, the pseudo-code is incorrect for a control scenario where older returns (that you still refer in the list) will not reflect the current policy, so will be biased.</p>
  
  <p>In practice, no-one really uses the MC Control algorithms as written. Nearly always a learning rate parameter, <span class="math-container">$\alpha$</span> is used to update estimates. </p>
  
  <blockquote>
    <p>What is the difference?</p>
  </blockquote>
  
  <p>In a <em>prediction</em> scenario, where you want to evaluate a fixed policy, it would be slightly more efficient to use a count of samples for each <span class="math-container">$s,a$</span> pair and variable <span class="math-container">$\alpha = \frac{1}{N(s,a)}$</span> which is mathematically identical to keeping a list and taking the average as needed.</p>
  
  <p>In a control scenario using a list of old return values is not only memory inefficient, it is also sample inefficient as you would need samples from each improved policy to outnumber the older samples in order to remove sampling bias due to using returns from initial worse policies. A fixed, or slowly decaying <span class="math-container">$\alpha$</span> is a simple and efficient way of "forgetting" the old return values as they become less relevant to the task.</p>
  
  <p>Another way to achieve similar forgetting may be to have a maximum size for each <span class="math-container">$Returns(s,a)$</span> list. However, that is not mentioned in the MC Control pseudocode.</p>
  
  <p>Perhaps I am missing something, as the book has been through significant review process. However, it may be that this detail is overlooked because the <em>basic</em> MC Control scenarios are not as interesting as all the extensions and combinations with TD, where you will find the book does use a learning rate <span class="math-container">$\alpha$</span> - including when making comparison charts of MC vs TD approaches etc. The explicit list of returns and averaging over them for control only occurs in a couple of places in the text in this pseudocode, and is not mentioned again.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-06-06T18:58:41.563Z
Answers.LastActivityDate: 2019-06-06T19:11:58.547Z
Answers.LastEditDate: 2019-06-06T19:11:58.547Z
Answers.UserDisplayName: Neil Slater
Body: <p>In Sutton &amp; Barto's <a href="http://incompleteideas.net/book/bookdraft2017nov5.pdf" rel="nofollow noreferrer">Reinforcement Learning: An Introduction</a>,  in page 83 (101 of the pdf), there is a description of first-visit MC control. In the phase where they update <span class="math-container">$Q(s, a)$</span>, they do an average of all the returns <span class="math-container">$G$</span> for that state-action pair. </p>
  
  <p>Why don't they just update the value with a weight for the value from previous episodes <span class="math-container">$\alpha$</span> and a weight <span class="math-container">$1- \alpha$</span> for the new episode return as it is done in TD-Learning?</p>
  
  <p>I have also seen other books (for example, <a href="https://sites.ualberta.ca/~szepesva/papers/RLAlgsInMDPs.pdf" rel="nofollow noreferrer">Algorithms for RL</a> (page 22) where they update it using <span class="math-container">$\alpha$</span>. What is the difference?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-06T18:16:03.530Z
Comments.Text: there's no difference it's the same thing. Incremental update is more appropriate because you don't have to save returns in the memory .
Comments.UserDisplayName: Brale
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-06-06T18:43:06.473Z
Comments.Text: @Brale_ Thanks for your comment. Can you mathematically show why it is the same in an answer?
Comments.UserDisplayName: Miguel Saraiva
Tags: <reinforcement-learning><monte-carlo-methods><sutton-barto>
Title: Why is an average of all returns used to update the value in the first-visit MC control?
UserDisplayName: Miguel Saraiva
ThreadText: # Why is an average of all returns used to update the value in the first-visit MC control?
  
  (Asked by: username_0 on 2019-06-06)
  
  In Sutton & Barto's [Reinforcement Learning: An Introduction](http://incompleteideas.net/book/bookdraft2017nov5.pdf), in page 83 (101 of the pdf), there is a description of first-visit MC control. In the phase where they update $Q(s, a)$, they do an average of all the returns $G$ for that state-action pair.
  
  Why don't they just update the value with a weight for the value from previous episodes $\alpha$ and a weight $1- \alpha$ for the new episode return as it is done in TD-Learning?
  
  I have also seen other books (for example, [Algorithms for RL](https://sites.ualberta.ca/~szepesva/papers/RLAlgsInMDPs.pdf) (page 22) where they update it using $\alpha$. What is the difference?
  
  **Tags:** reinforcement-learning, monte-carlo-methods, sutton-barto
  
  > **Comments:**
  > **username_1**: there's no difference it's the same thing. Incremental update is more appropriate because you don't have to save returns in the memory .  
  > **username_0**: @Brale_ Thanks for your comment. Can you mathematically show why it is the same in an answer?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-06-06. Score: 1 | Accepted answer
  
  > Why don't they just update the value with a weight for the value from previous episodes $\alpha$ and a weight $1- \alpha$ for the new episode return as it is done in TD-Learning?
  
  In my opinion, this is a mistake in the book. I went back and checked that this is still the same in the [finished second edition](http://incompleteideas.net/book/RLbook2018.pdf), and it is still there.
  
  Keeping all returns and taking averages works fine in a prediction scenario with a fixed policy, and it is somewhat simpler and more intuitive to explain as "this is the mean value" (efficiency can come later, after comprehension). However, the pseudo-code is incorrect for a control scenario where older returns (that you still refer in the list) will not reflect the current policy, so will be biased.
  
  In practice, no-one really uses the MC Control algorithms as written. Nearly always a learning rate parameter, $\alpha$ is used to update estimates.
  
  > What is the difference?
  
  In a *prediction* scenario, where you want to evaluate a fixed policy, it would be slightly more efficient to use a count of samples for each $s,a$ pair and variable $\alpha = \frac{1}{N(s,a)}$ which is mathematically identical to keeping a list and taking the average as needed.
  
  In a control scenario using a list of old return values is not only memory inefficient, it is also sample inefficient as you would need samples from each improved policy to outnumber the older samples in order to remove sampling bias due to using returns from initial worse policies. A fixed, or slowly decaying $\alpha$ is a simple and efficient way of "forgetting" the old return values as they become less relevant to the task.
  
  Another way to achieve similar forgetting may be to have a maximum size for each $Returns(s,a)$ list. However, that is not mentioned in the MC Control pseudocode.
  
  Perhaps I am missing something, as the book has been through significant review process. However, it may be that this detail is overlooked because the *basic* MC Control scenarios are not as interesting as all the extensions and combinations with TD, where you will find the book does use a learning rate $\alpha$ - including when making comparison charts of MC vs TD approaches etc. The explicit list of returns and averaging over them for control only occurs in a couple of places in the text in this pseudocode, and is not mentioned again.
  
  
  ---
  
  