In Barto and Sutton's "Introduction to Reinforcement Learning" book, in Section 5.1 (Monte Carlo Prediction), they describe the First-visit (and every-visit) Monte Carlo (MC) methods for policy evaluation in episodic tasks, and write Both first-visit MC and every-visit MC converge to $v_\pi(s)$ as the number of visits (or first visits) to $s$ goes to infinity. This is easy to see for the case of first-visit MC. In this case each return is an independent, identically distributed estimate of $v_\pi(s)$ with finite variance. By the law of large numbers the sequence of averages of these estimates converges to their expected value. In First-visit MC, in each episode, we record the returns from state $s$ starting from the first time step $t$ that state $s$ was visited. If the episode horizon is length $T$ , this return is $$G_t = R_{t+1} + \gamma R_{t+2} + \cdots \gamma^{T-1} R_{T},$$ as we define the value function to be the expected cumulative future discounted reward starting from a given state. I don't understand how first-visit MC is averaging identical samples of $v_\pi(s)$ , when the returns starting at the first visit of state $s$ may be sums of a different number of terms, in each episode. If the time-horizon was infinite, then I would agree that the return samples of a given state in each episode are iid, but this defeats the point of MC methods which, at least in this context (Section 5.1), need a finite time horizon. Thus, I don't see how we can apply the law of large…

Full article content could not be extracted automatically. Read the original below.