First-Visit vs Every-Visit Monte Carlo

Monte Carlo prediction estimates the state-value function $v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$ by generating episodes under policy $\pi$ and averaging the observed returns $G_t$ that follow visits to $s$. A visit to state $s$ is any time step $t$ at which $S_t = s$ occurs within an episode. Because an agent following $\pi$ can, in general, pass through the same state more than once in a single episode (this is common in gridworlds with loops, in continuing tasks cut into episodes, or in any MDP without a strict layering structure), an episode can contribute more than one return sample for the same state.

First-visit MC resolves this by looking, for each episode, only at the first time step at which $s$ occurs, and using the return $G_t$ computed from that time step onward. Later occurrences of $s$ in the same episode are ignored for the purposes of updating $V(s)$. The estimator is

where the sum ranges over episodes in which $s$ was visited at least once, $G_i$ is the return from the first visit in episode $i$, and $N(s)$ is the number of such episodes.

Every-visit MC instead uses every occurrence of $s$ within every episode, treating each occurrence as a separate return sample:

where $M(s) \ge N(s)$ counts total visits across all episodes (an episode with $k$ visits to $s$ contributes $k$ terms), and each $G_j$ is the return computed from that particular visit onward. Both estimators are built from the same raw material — sampled trajectories under $\pi$ — and both converge almost surely to $v_\pi(s)$ as the number of episodes tends to infinity, by the Law of Large Numbers applied appropriately. The distinction is entirely about how much of the correlated information within a single episode gets folded into the running average, and this affects bias and variance in finite samples, which is the substance of the rest of this article.

Both algorithms share a common skeleton: generate an episode, walk it backward accumulating the discounted return, and update a running average of returns keyed by state. The only difference is a single conditional check — "have I already processed this state in this episode?" ``` Initialize: V(s) ← arbitrary value for all states s Returns(s) ← empty list, for all states s # or running sum + count Repeat forever (for each episode): Generate an episode following policy π: S_0, A_0, R_1, S_1, A_1, R_2, ..., S_{T-1}, A_{T-1}, R_T G ← 0 visited_in_episode ← empty set() # only used by first-visit for t = T-1 down to 0: G ← γ * G + R_{t+1} if FIRST_VISIT: if S_t not in visited_in_episode: visited_in_episode.add(S_t) append G to Returns(S_t) V(S_t) ← average(Returns(S_t)) else: # EVERY_VISIT append G to Returns(S_t) V(S_t) ← average(Returns(S_t)) ``` Walking the episode backward is what makes the return computation efficient: $G_t = R_{t+1} + \gamma G_{t+1}$, so each step costs $O(1)$ rather than re-summing the whole remaining trajectory, turning a naive $O(T^2)$ computation of all returns into $O(T)$. The first-visit/every-visit distinction is implemented by the `visited_in_episode` set, checked once per state per episode. This is the entire algorithmic difference — everything else (episode generation, backward return accumulation, incremental averaging) is identical. In practice, `average(Returns(s))` is not recomputed from scratch each time; it is maintained incrementally,

where $n(s)$ is incremented each time a (first- or every-) visit return is folded in, avoiding storage of the full list of returns.

Time complexity. Generating an episode of length $T$ costs $O(T)$ environment interactions. Processing it backward to compute all returns and update the visited states costs $O(T)$ as well, since each of the $T$ time steps does $O(1)$ work (one multiply-add for $G$, one set lookup/insert for first-visit, one incremental average update). Over $K$ episodes, the total cost is $O(K \cdot \bar T)$ where $\bar T$ is the mean episode length — identical for both variants, since the only difference is a constant-time set membership check per step.

Space complexity. Maintaining $V(s)$ and a visit counter $n(s)$ for every state requires $O(|\mathcal S|)$ space (using the incremental-mean update, not storing full return lists). The `visited_in_episode` set used by first-visit needs at most $O(T)$ additional space per episode, discarded after each episode. Neither variant needs to store past episodes.

Correctness — every-visit is trivially unbiased in the limit, first-visit is unbiased exactly. First-visit MC. Fix a state $s$. Consider only the episodes in which $s$ is visited at least once, and let $G_i$ be the return from the first visit in the $i$-th such episode. Because each episode is generated independently by re-running the policy in the environment from the start, and because the first-visit return in episode $i$ is a (deterministic, given the trajectory) function of only that episode's randomness, the sequence $G_1, G_2, \dots$ is i.i.d. across episodes, each distributed as the true conditional return distribution given $S_t = s$ (using the Markov property: the distribution of the return following a visit to $s$ depends only on $s$, not on how the episode reached $s$). Hence

so $V^{\text{first}}(s) = \frac{1}{N(s)}\sum_i G_i$ is an average of i.i.d. unbiased samples: it is itself unbiased for every fixed $N(s)$, and by the Strong Law of Large Numbers,

Its variance is exactly $\mathrm{Var}(G_i)/N(s)$, the textbook rate for an i.i.d. average. Every-visit MC. Now every occurrence of $s$ within an episode contributes a term, and these terms are not independent: if $s$ is visited at $t$ and again later at $t'$ in the same episode, the return from $t'$ is a sub-trajectory of the return from $t$ (they share the same future dynamics after $t'$, and are correlated through the shared random seed of that one episode continuing from $s$ each time). So within one episode, multiple visits to $s$ give correlated, not i.i.d., samples of the return distribution. This means that for a finite number of episodes, $V^{\text{every}}(s)$ can be a biased estimator of $v_\pi(s)$ — repeated visits from unusually long or short episodes get overweighted relative to a pure i.i.d. average. Despite this, every-visit MC is still consistent: as the number of episodes $K \to \infty$, the fraction of total visits contributed by any single episode shrinks, the law of large numbers still applies across episodes (only within an episode is there correlation, and each episode itself is drawn i.i.d.), and

This convergence result appears in the original analyses of MC prediction and is the standard justification cited for using either variant interchangeably in the large-sample regime.

Bias-variance intuition. First-visit trades away data (ignoring later same-episode visits) in exchange for a clean i.i.d. sample and zero finite-sample bias. Every-visit uses strictly more of the available data per episode, which typically reduces variance for a fixed number of episodes (more samples averaged), but at the cost of a finite-sample bias induced by intra-episode correlation. As $K \to \infty$ both the bias (for every-visit) and the variance gap shrink, and the two estimators become statistically indistinguishable. In episodic tasks where states rarely or never repeat within an episode (e.g., strictly acyclic state spaces, or games where you naturally never return to an exact past state), first-visit and every-visit produce identical numbers, since $N(s) = M(s)$ for every state.

Consider three toy episodes generated under some fixed policy in a small MDP with discount $\gamma = 1$ (episodic, undiscounted for simplicity), where state $s = X$ is the state of interest and it can recur within an episode.

First-visit MC for X: use only the first occurrence in each episode.

Three episodes, three samples, one per episode — exactly the i.i.d. structure the correctness argument relies on.

Every-visit MC for X: use every occurrence.

Five samples from three episodes — episode 1 and episode 3 each contribute two correlated terms (the second visit's return is nested inside the first visit's return in episode 1, and directly adjacent in episode 3). Notice the two estimates disagree substantially (4.67 vs. 3.2) with only three episodes — this is the finite-sample bias/variance difference made concrete. As more episodes accumulate, assuming the policy and environment are fixed, both numbers will drift toward the same true value $v_\pi(X)$; the gap you see here is exactly the sampling artifact the theory predicts, not an error in either method.

Monte Carlo methods for sequential decision-making trace back to the broader Monte Carlo simulation tradition in physics and statistics, later adapted into the reinforcement-learning framework that formalized first-visit and every-visit as two distinct, analyzable estimators for policy evaluation.

Monte Carlo prediction, in either its first-visit or every-visit form, is the conceptual seed for a large swath of practical model-free reinforcement learning. It underlies Monte Carlo Control, where the same return-averaging machinery is combined with an $\varepsilon$-greedy or exploring-starts policy improvement step to learn optimal behavior directly from experience, without ever building a model of the environment's transition probabilities. This matters in domains like game-playing agents, robotic control from raw episodic rollouts, and any setting where a full transition model is infeasible to specify but complete episodes can be simulated or observed. The bias-variance tradeoff between first-visit and every-visit also foreshadows a recurring theme in RL: the tension between using data efficiently (every-visit, more samples per episode) versus using it in a statistically clean way (first-visit, valid independence for variance estimates). This same tension reappears, in different guises, in eligibility traces, in the design of Temporal-Difference Learning methods that blend MC and bootstrapping, and in modern policy-gradient estimators that must decide how to weight correlated trajectory samples. Every-visit MC's approach — using all the data, tolerating correlation — is philosophically close to how eligibility traces later generalize MC and TD into a single spectrum (TD(λ)), making the first-visit/every-visit distinction a genuine conceptual stepping stone rather than a historical footnote. Production RL libraries that implement tabular MC baselines (used for benchmarking and for small, well-understood MDPs before scaling to deep function approximation) typically expose both variants, precisely because the choice affects convergence behavior and variance in small-sample regimes common in early-stage experimentation.

Ask the tutor: Can you show how first-visit vs every-visit MC estimators behave differently when I add a policy-improvement step on top, moving from prediction to control?