0
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – nbro
    Commented Dec 16, 2020 at 15:19

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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$. $\endgroup$
    – InvestingScientist
    Commented Dec 15, 2020 at 12:46
  • 1
    $\begingroup$ 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. $\endgroup$
    – David
    Commented Dec 15, 2020 at 12:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .