First-Visit vs Every-Visit MC Prediction

Why Does This Exist?

Monte Carlo prediction estimates a state's value by averaging the actual returns seen after visiting it: finish episodes, add up each visit's discounted future rewards, divide. The parent method is Monte Carlo methods, and action values get their own treatment at Monte Carlo estimation of action values.

Loops force a decision. In any environment with cycles, the agent can pass through the same state twice in one episode, at step $t_1$ and again at $t_2$, with different remaining futures. Which returns belong in the average for that state? First-visit keeps only the return after the first arrival and discards the rest. Every-visit keeps a return after each arrival. Both converge to the true value with enough episodes, yet on finite data they disagree, and the disagreement is largest exactly where states recur.

This page defines both estimators, shows where their numbers split, and says when the split matters. Control built on these estimates is Monte Carlo control.

The one idea you need first.

A return $G_t$ is the discounted sum of rewards from step $t$ to termination: $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$, with discount $\gamma$ in $[0, 1]$ weighting near rewards over far ones. The state value $V^\pi(s)$ is the expected return from $s$ under policy $\pi$. Monte Carlo replaces that expectation with an average over visits actually seen.

Think of It Like This

How It Actually Works

First-visit: one sample per episode

For state $s$ in an episode, let $\mathcal{T}_1(s)$ be the earliest step with $S_t = s$. Over $M$ episodes the estimate averages the return after that step wherever the state appeared:

$V_{\text{FV}}(s) = \frac{\sum_{e=1}^M \mathbb{I}(s \in \tau^{(e)})\, G_{\mathcal{T}_1^{(e)}(s)}^{(e)}}{\sum_{e=1}^M \mathbb{I}(s \in \tau^{(e)})}$

Here $\mathbb{I}$ is $1$ when the episode visited $s$ and $0$ otherwise. Because each episode donates at most one return and episodes are independent, the samples are independent and identically distributed. The estimator is unbiased at any sample size, $\mathbb{E}[V_{\text{FV}}(s)] = V^\pi(s)$, and converges by the law of large numbers with variance shrinking like $1/M$.

Every-visit: every arrival counts

Now keep all of them. With $\mathcal{T}_{\text{all}}^{(e)}(s)$ the set of every step where $s$ occurs:

$V_{\text{EV}}(s) = \frac{\sum_{e=1}^M \sum_{t \in \mathcal{T}_{\text{all}}^{(e)}(s)} G_t^{(e)}}{\sum_{e=1}^M |\mathcal{T}_{\text{all}}^{(e)}(s)|}$

Returns from two visits in one episode overlap: the earlier return physically contains the later one, $G_{t_a} = R_{t_a+1} + \dots + \gamma^{t_b - t_a} G_{t_b}$. Shared downstream rewards make the samples correlated, so the estimator carries finite-sample bias. It still converges to $V^\pi(s)$ as episodes pile up, and because it harvests more samples per episode its mean squared error is often lower early on.

Both update incrementally without storing history. On each recorded visit with return $G_t$, with $N(s)$ counting recorded visits:

$N(s) \leftarrow N(s) + 1, \qquad V(s) \leftarrow V(s) + \frac{1}{N(s)}\left[G_t - V(s)\right]$

Worked example

Undiscounted, $\gamma = 1.0$. Episode 1 loops: $S_1$ with reward $2$, then $S_2$ with reward $3$, then $S_1$ again with reward $5$, then termination. Working backward, returns are $G_2 = 5.0$ at the second $S_1$, $G_1 = 3.0 + 5.0 = 8.0$ at $S_2$, and $G_0 = 2.0 + 8.0 = 10.0$ at the first $S_1$.

First-visit keeps $10.0$ for $S_1$ and $8.0$ for $S_2$, so $V_{\text{FV}}(S_1) = 10.0$ and $V_{\text{FV}}(S_2) = 8.0$. Every-visit additionally keeps the $5.0$ after the second $S_1$: $V_{\text{EV}}(S_1) = (10.0 + 5.0)/2 = 7.5$ while $V_{\text{EV}}(S_2) = 8.0$.

Episode 2 is short: $S_2$ with reward $4$, then $S_1$ with reward $2$. Returns are $2.0$ at $S_1$ and $4.0 + 2.0 = 6.0$ at $S_2$. Incremental updates give first-visit $V_{\text{FV}}(S_1) = 10.0 + (2.0 - 10.0)/2 = 6.0$ and $V_{\text{FV}}(S_2) = 8.0 + (6.0 - 8.0)/2 = 7.0$. Every-visit folds in the extra sample: $V_{\text{EV}}(S_1) = 7.5 + (2.0 - 7.5)/3 = 5.67$, matching $(10.0 + 5.0 + 2.0)/3$, and $V_{\text{EV}}(S_2) = 7.0$. Note $S_2$ agrees under both rules in both episodes, because it never repeated within an episode. The methods split only where states recur.

Code

Both estimators on the exact two episodes above, using only the standard library.

1from typing import Dict, List, Tuple2
3Episode = List[Tuple[str, float]]4
5
6def episode_returns(episode: Episode, gamma: float = 1.0) -> List[Tuple[str, float]]:7    """Return per step, computed backward then restored to forward order."""8    G = 0.09    out: List[Tuple[str, float]] = []10    for state, reward in reversed(episode):11        G = gamma * G + reward12        out.append((state, G))13    out.reverse()14    return out15
16
17def first_visit(episodes: List[Episode], gamma: float = 1.0) -> Dict[str, float]:18    """Average the return after each state's first appearance per episode."""19    total: Dict[str, float] = {}20    count: Dict[str, int] = {}21    for episode in episodes:22        seen = set()23        for state, G in episode_returns(episode, gamma):24            if state not in seen:25                seen.add(state)26                total[state] = total.get(state, 0.0) + G27                count[state] = count.get(state, 0) + 128    return {s: total[s] / count[s] for s in total}29
30
31def every_visit(episodes: List[Episode], gamma: float = 1.0) -> Dict[str, float]:32    """Average the return after every appearance of each state."""33    total: Dict[str, float] = {}34    count: Dict[str, int] = {}35    for episode in episodes:36        for state, G in episode_returns(episode, gamma):37            total[state] = total.get(state, 0.0) + G38            count[state] = count.get(state, 0) + 139    return {s: total[s] / count[s] for s in total}40
41
42episodes: List[Episode] = [[("S1", 2.0), ("S2", 3.0), ("S1", 5.0)], [("S2", 4.0), ("S1", 2.0)]]43fv, ev = first_visit(episodes), every_visit(episodes)44for state in sorted(fv):45    print(f"V_FV({state}) = {fv[state]:.2f}")  # -> V_FV(S1) = 6.00 and V_FV(S2) = 7.0046for state in sorted(ev):47    print(f"V_EV({state}) = {ev[state]:.2f}")  # -> V_EV(S1) = 5.67 and V_EV(S2) = 7.00

The prints match the hand trace: first-visit $6.00$ and $7.00$, every-visit $5.67$ and $7.00$.

Watch Out For

The Quick Version

• First-visit averages the return after a state's first appearance per episode, giving independent samples and a strictly unbiased estimate.
• Every-visit averages after every appearance, harvesting more samples per episode at the price of correlated returns and finite-sample bias.
• Both converge to the true value $V^\pi(s)$ as episodes grow; every-visit often has lower error early because it uses more data.
• The two agree wherever states never repeat within an episode and split only on revisited states: $10.0$ versus $7.5$ after the looping episode here.
• Both need complete episodes and suffer higher variance than bootstrapping methods, since whole-trajectory noise lands in every return.

What to Read Next

• Monte Carlo Methods
• Monte Carlo Action Values
• Monte Carlo Control