Every-Visit MC

Monte Carlo policy evaluation learns a state-value function from complete episodes generated by a policy π. It does not use a model of the environment. Instead, it observes what return followed a state and uses those observed returns to estimate the state's value. The central question for this article is what to do when the same state appears more than once in one episode.

Suppose an episode encounters state s at several time steps. Each occurrence has a return that follows it. First-Visit MC selects only the return after the first occurrence of s in that episode. Every-Visit MC selects the returns after all occurrences of s in that episode. The selection happens separately for each state, so a later visit to s does not affect the First-Visit sample for s, even though it may still be selected by Every-Visit MC.

The evaluation process has two separate parts. First, the method selects returns from an episode according to its visit rule. Second, it averages the selected returns collected across episodes. For First-Visit MC, each episode contributes at most one return to the list for a particular state. Once that return has been appended, the value estimate V(s) is the average of the accumulated list.

The same separation clarifies the difference between First-Visit and Every-Visit MC. The averaging operation is not the defining difference: both methods use returns from episodes generated by π, and the stored returns are averaged. The difference is which returns are allowed into the stored list before averaging.

Imagine collecting First-Visit returns for state s across several complete episodes. Each new first visit supplies one more sample for the list associated with s. The current V(s) is the average of all those stored samples. A new episode can therefore change the estimate, but it does not replace the previous evidence.

Every additional First-Visit sample gives the average more information about the returns that follow state s under policy π. As more first visits are collected, the estimate moves toward vπ(s), the value associated with that policy. The source describes the error's standard deviation as decreasing as 1/√n, where n represents the number of collected samples. Thus, additional samples reduce variability, although the reduction becomes slower as the sample count grows.

Both methods learn from complete episodes generated by policy π, and both use observed returns rather than a model of the environment. Their difference is how repeated appearances of a state are counted. First-Visit MC selects one return per state per episode. Every-Visit MC uses every return following a visit to that state. Consequently, repeated visits create one First-Visit sample but potentially several Every-Visit samples within the same episode.