Every-Visit MC

One Episode, Several Visits

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.

Selecting Returns from an 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.

From Episode to Value Estimate

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.

A Running Average of Samples

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.

Why More Visits Help

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.

First-Visit versus Every-Visit

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.

Mistakes with Repeated States

• Treating First-Visit MC as if it recorded every occurrence of a state.

  First-Visit MC keeps only the return after the state's first occurrence in that episode.

  Fix: Keep the first-occurrence return for First-Visit MC. Use all three returns only when applying Every-Visit MC.

• Thinking the distinction changes the averaging step.

  The important boundary is return selection. Once selected returns are stored, the value estimate is produced by averaging the accumulated list.

  Fix: Ask which returns entered the list before asking how the list is averaged.

• Believing that one First-Visit sample means one sample total.

  The first-visit rule applies within each episode. More episodes can provide more first-visit returns.

  Fix: Collect one qualifying return for s from each episode in which s occurs, then average the accumulated returns.

• Assuming more samples make every individual return equal to vπ(s).

  The estimate approaches vπ(s) through the average of collected returns, while individual episode returns can differ.

  Fix: Track the running average and its decreasing variability rather than comparing each sample directly with vπ(s).

Check Your Understanding

Key Takeaways

1. First-Visit MC learns state values from complete episodes generated by policy π by averaging observed returns.
2. When a state appears repeatedly in one episode, First-Visit MC records only the return after its first occurrence.
3. Every-Visit MC records the return after every occurrence of the state.
4. The evaluation sequence is episode generation, visit identification, return selection, return storage, and averaging.
5. More first visits provide more returns for the average, moving the estimate toward vπ(s); the source describes the error's standard deviation as decreasing as 1/√n.