# When we have multiple traces, do we average over traces or the total number of times we have visited that state?

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?

• 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.
– nbro
Dec 16, 2020 at 15:19

• 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$. Dec 15, 2020 at 12:46
• 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. Dec 15, 2020 at 12:53