Answers.Body: <p>For every visit MC you create a list for each state. Every time you enter a state you calculate the returns for the episode and append these returns to a list. Once you have done this for all the episode you want to average over you simply calculate the value of a state to be the average of this list of returns for the state.</p>
  <p>First visit MC is almost the same except that you only append the returns to the state returns list for the first time you visit the state in an episode.</p>
  <p>Your workings are correct, you average over the number of times you have visited the state (in every visit MC). So, in your example, you would get the value of HOUSE to be 0, as you stated. If you were doing first visit MC then the returns for episode 1 would be 2 and the returns for episode 2 would be -2, which you would then average over the two first visits to again give you 0 (this would not always be the case that they are equal after 2 episodes but in the limit both methods do converge to the true state value function).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-15T12:46:00.050Z
Answers.Text: as a follow up, the case you mentioned for First Visit, if $\gamma = 1$, would I include the discounted return of all future states also? Your approach of only including the immediate reward for the given state suggests that you are assuming $\gamma = 0$.
Answers.UserDisplayName: InvestingScientist
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-15T12:53:30.393Z
Answers.Text: For first visit you do exactly what you have done for every visit, except you _only_ do it for the first time you enter the state. I didn't assume $\gamma = 1$ -- in first visit you take the discounted (here $\gamma = 1 so no discounting) returns for HOUSE's first visit which, for episode 1, was 3 + 2 - 4 + 4 - 3 = 2 -- this is because you only calculate the returns from your first visit.
Answers.UserDisplayName: David
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-15T12:30:27.413Z
Answers.LastActivityDate: 2020-12-15T12:30:27.413Z
Answers.UserDisplayName: David
Body: <p>I am confused about the workings of the first- and every-visit MC.</p>
  <p>My first question is, when we have multiple traces, do we average over traces or the total number of times we have visited that state?</p>
  <p>So, in the example:</p>
  <p><span class="math-container">$$\tau_1 = \text{House} +3, \text{House} +2, \text{School} -4, \text{House} +4, \text{School} -3, \text{Holidays}$$</span>
  <span class="math-container">$$\tau_2 = \text{House} -2, \text{House} +3, \text{School} -3, \text{Holidays},$$</span></p>
  <p>where we have states of either House, Holidays, or School, with the numerical values being the immediate rewards.</p>
  <p>For every-visit MC to find the state value of HOUSE, with <span class="math-container">$\gamma$</span>=1, my intuition would be to create a return list, R, that looks like the following</p>
  <p><span class="math-container">$$R_1=[3+2−4+4−3, 2−4+4−3, 4−3]= [2, −1, 1]$$</span>
  <span class="math-container">$$R_2=[−2+3−3, 3−3]=[−2, 0]$$</span></p>
  <p><span class="math-container">$$R_1+R_2=[2,−1, 1,−2, 0]$$</span></p>
  <p>which, when averaged over 5 visits, is 0 and the correct answer, but I would like if you could confirm if the methodology is correct?</p>
  <p>However, another approach would be to compute the average returns for each trace. Which is correct?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-16T15:19:43.660Z
Comments.Text: To me, this post is not fully clear. Although you already accepted an answer, and I understand that answer, I don't understand everything in this post. For example, in your trajectories, what would it mean to sum a state and a number, as you do in $\tau_1$ (e.g. House + 3)? What does that mean? Maybe you can formulate that part more clearly, because that's not very clear.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><markov-decision-process><monte-carlo-methods><model-based-methods>
Title: When we have multiple traces, do we average over traces or the total number of times we have visited that state?
UserDisplayName: InvestingScientist
ThreadText: # When we have multiple traces, do we average over traces or the total number of times we have visited that state?
  
  (Asked by: username_0 on 2020-12-15)
  
  I am confused about the workings of the first- and every-visit MC.
  
  My first question is, when we have multiple traces, do we average over traces or the total number of times we have visited that state?
  
  So, in the example:
  
  $$\tau\_1 = \text{House} +3, \text{House} +2, \text{School} -4, \text{House} +4, \text{School} -3, \text{Holidays}$$
  $$\tau\_2 = \text{House} -2, \text{House} +3, \text{School} -3, \text{Holidays},$$
  
  where we have states of either House, Holidays, or School, with the numerical values being the immediate rewards.
  
  For every-visit MC to find the state value of HOUSE, with $\gamma$=1, my intuition would be to create a return list, R, that looks like the following
  
  $$R\_1=[3+2−4+4−3, 2−4+4−3, 4−3]= [2, −1, 1]$$
  $$R\_2=[−2+3−3, 3−3]=[−2, 0]$$
  
  $$R\_1+R\_2=[2,−1, 1,−2, 0]$$
  
  which, when averaged over 5 visits, is 0 and the correct answer, but I would like if you could confirm if the methodology is correct?
  
  However, another approach would be to compute the average returns for each trace. Which is correct?
  
  **Tags:** reinforcement-learning, markov-decision-process, monte-carlo-methods, model-based-methods
  
  > **Comments:**
  > **username_1**: To me, this post is not fully clear. Although you already accepted an answer, and I understand that answer, I don't understand everything in this post. For example, in your trajectories, what would it mean to sum a state and a number, as you do in $\tau_1$ (e.g. House + 3)? What does that mean? Maybe you can formulate that part more clearly, because that's not very clear.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-12-15. Score: 2 | Accepted answer
  
  For every visit MC you create a list for each state. Every time you enter a state you calculate the returns for the episode and append these returns to a list. Once you have done this for all the episode you want to average over you simply calculate the value of a state to be the average of this list of returns for the state.
  
  First visit MC is almost the same except that you only append the returns to the state returns list for the first time you visit the state in an episode.
  
  Your workings are correct, you average over the number of times you have visited the state (in every visit MC). So, in your example, you would get the value of HOUSE to be 0, as you stated. If you were doing first visit MC then the returns for episode 1 would be 2 and the returns for episode 2 would be -2, which you would then average over the two first visits to again give you 0 (this would not always be the case that they are equal after 2 episodes but in the limit both methods do converge to the true state value function).
  
  > **Comments:**
  > **username_0**: as a follow up, the case you mentioned for First Visit, if $\gamma = 1$, would I include the discounted return of all future states also? Your approach of only including the immediate reward for the given state suggests that you are assuming $\gamma = 0$.  
  > **username_2**: For first visit you do exactly what you have done for every visit, except you _only_ do it for the first time you enter the state. I didn't assume $\gamma = 1$ -- in first visit you take the discounted (here $\gamma = 1 so no discounting) returns for HOUSE's first visit which, for episode 1, was 3 + 2 - 4 + 4 - 3 = 2 -- this is because you only calculate the returns from your first visit.  
  
  ---
  
  