First-Visit MC

Imagine learning which squares are promising in a maze by playing complete games and looking back at how each game ended. First-Visit Monte Carlo is a simple way to do that: for each state, it learns only from the first time that state appeared in a completed episode.

In an episode such as start → hallway → hallway → exit, the hallway was visited twice. First-Visit MC uses the return following the first hallway visit, and ignores the second for that episode. The return is the total discounted reward from that point onward:

G_t = R_(t+1) + γR_(t+2) + γ²R_(t+3) + ...

For a fixed policy, the algorithm stores all—or, more practically, a running average of—the returns observed after each state’s first visit. That average becomes V(s), the estimated long-term value of starting in state s and then following the policy. Unlike temporal-difference methods, it does not bootstrap from another current value estimate: it waits for the actual episode outcome.

The rule prevents one episode that loops through a state repeatedly from contributing many correlated samples for that same state. Every-visit MC instead uses a return after every occurrence. Both approaches converge to the correct value under standard conditions—complete episodes and sufficient repeated coverage—but first-visit MC gives each state at most one sample per episode, making its interpretation especially clean.

First-Visit MC can also improve a policy: estimate Q(s,a) from the first occurrence of each state–action pair, then choose actions with the highest estimated return while preserving exploration. In a Gymnasium blackjack task, for example, it can learn whether to hit or stick from full hands rather than a known model of the deck.

• It works naturally for episodic tasks with clear endings.
• It assigns credit using real outcomes, useful when no environment dynamics are known.
• It cannot update until an episode finishes; a long or non-terminating task makes learning slow or impractical.
• Without exploration, states or actions never tried receive no trustworthy estimate.