Every-Visit MC
Imagine reviewing a completed game and asking, “What reward followed each time I was in this situation?” Every-Visit Monte Carlo answers that question by learning from every occurrence of a state, not merely its first appearance in a game or episode.
How the update works
In episodic reinforcement learning, the agent waits until an episode ends, then calculates the return: the total discounted reward received from a particular time step onward. If state s appears three times in one episode, Every-Visit MC treats all three appearances as training examples. For each occurrence at time t, it computes:
Gt = Rt+1 + γRt+2 + γ²Rt+3 + ...
It then updates the estimate V(s) toward the average of all returns observed after visits to s. An incremental implementation avoids storing old returns:
N(s) += 1
V(s) += (G - V(s)) / N(s)Why count every visit?
Consider Blackjack. A player can revisit a similar decision state across many hands, and Every-Visit MC uses each such encounter. In a looping navigation task, a state might occur repeatedly before the agent reaches the goal; this method uses the eventual outcome following each pass through that state. That gives more update data per episode than First-Visit MC, which discards all but the first occurrence of a state in each episode.
Strengths and limits
Every-Visit MC is model-free: it needs no transition probabilities or reward model, only complete sampled episodes. It handles delayed rewards directly because the final outcome is folded into each earlier return. Its main limitation is equally direct: no update is available until the episode finishes. Long, costly, or non-terminating tasks therefore make it impractical without artificial episode boundaries. Repeated visits within one episode also produce correlated returns, so they are not as independent as separate trials. With sufficient exploration and repeated visits under a fixed policy, the averages still approach that policy’s true state values. MC control methods use these estimates to improve the policy, but must preserve exploration; otherwise, untried actions never receive returns and a seemingly good policy can lock in too early.
Every-Visit Monte Carlo (MC) estimates a state’s value by averaging the returns following every occurrence of that state across completed episodes, including repeated visits within the same episode. It is a model-free method that learns directly from observed rewards. Using all visits increases the data used per episode, supporting value estimation and policy improvement without requiring knowledge of environment dynamics.
Imagine judging a route through a maze by replaying the whole trip afterward. Each time you passed through the same hallway, you would ask: “How did the rest of the journey turn out from this visit?” You would count every pass through that hallway, not just the first one.
Every-Visit MC is an AI learning approach built on that idea. After an entire attempt is finished, it looks at every time it encountered a situation and learns from what happened afterward. This is useful when the same situation can appear several times in one game or task: every occurrence becomes another piece of experience about whether things tend to go well from there.