Why does First-Visit Monte Carlo Prediction (Policy Evaluation) converge?

Question

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 numbers here without accounting for the fact that the returns after first visiting a state may vary in the effective time horizon they are capturing. Can anybody explain what I am missing or how to bridge this discrepancy?

Answer 1

I've done some more reading and I believe the explanation is that: indeed if the underlying MDP is assumed stationary, and the episodes have finite horizon because each trajectory is guaranteed (almost surely) to reach some absorbing state, then indeed the returns after the first visit to a state are i.i.d. over different episodes.

My confusion came from considering finite-horizon settings where the time horizon $T$ is fixed, rather than dependent on the trajectory of the episode. This case is not what is considered here.