Returns and Episodes in Reinforcement Learning

One Episode, Two Data Rules

Monte Carlo prediction estimates the value of a state under a policy by collecting episodes that follow that policy and using the returns associated with visits to the state. The important question here is what to do when the same state appears more than once in one episode. First-visit Monte Carlo and every-visit Monte Carlo use the same policy and aim to estimate the same state value, vπ(s). They differ only in which visits contribute returns to the average.

Tracing Visits Through an Episode

Consider an episode in which state S appears at two different time steps. For a generated example, suppose the return associated with the earlier occurrence is 8 and the return associated with the later occurrence is 4. These are two returns associated with visits to S in the same episode. The methods now make different selection decisions: one keeps only the earliest occurrence, while the other keeps both.

First-Visit Monte Carlo

First-visit Monte Carlo examines an episode from its beginning and finds the earliest occurrence of the state being estimated. It records the return associated with that first occurrence and does not record later occurrences of the same state from that episode. Therefore, one episode contributes at most one return for a given state.

1. Choose the state whose value is being estimated.
2. Inspect the episode in time order.
3. Find the earliest visit to that state.
4. Record the return associated with that earliest visit.
5. Stop processing that state for this episode.

Every-Visit Monte Carlo

Every-visit Monte Carlo processes every occurrence of the state in the episode. If a state appears several times, the return associated with each occurrence enters the collection of returns used for the estimate. Consequently, one episode may contribute several returns for one state.

1. Choose the state whose value is being estimated.
2. Inspect every time step in the episode.
3. Identify each visit to that state.
4. Record the return associated with every identified visit.
5. Continue until all occurrences in the episode have been processed.

Same Episode, Different Samples

The distinction is a data-selection rule, not a policy change. Both methods use episodes obtained by following the same policy, and both aim to estimate vπ(s). Their difference is how many returns from each episode enter the average.

More Visits, More Stable Estimates

A small collection of returns can produce an estimate noticeably different from vπ(s). As more relevant visits are collected, the average generally becomes more stable. First-visit Monte Carlo approaches vπ(s) as the number of first visits increases. Every-visit Monte Carlo approaches vπ(s) as the total number of visits increases. Under the stated conditions, both methods converge to the same state value.

For first-visit Monte Carlo, the source describes the standard deviation of estimation error as falling at a rate of 1 / √n, where n is the number of averaged returns. Every-visit Monte Carlo also has quadratic convergence to vπ(s), although its theoretical justification is less direct because repeated returns within one episode are not treated in the same straightforward way.

Counting and Averaging Mistakes

• Counting every occurrence when applying first-visit Monte Carlo

  First-visit Monte Carlo records one return per episode for a given state and stops after the earliest occurrence.

  Fix: Keep only the return associated with the earliest occurrence, which is 8 in this generated example.

• Stopping after the first occurrence when applying every-visit Monte Carlo

  Every-visit Monte Carlo continues through all occurrences of the state in the episode.

  Fix: Record the return associated with each occurrence, such as both 8 and 4.

• Treating the two methods as different policies

  The distinction concerns which returns are selected from the episode, not the policy that generated it.

  Fix: Hold the policy and the episode-generation process conceptually constant, then apply the appropriate return-selection rule.

• Using the wrong number of returns in the average

  The average must correspond to the returns actually collected under the selected method.

  Fix: For first-visit processing, count the recorded first visits. For every-visit processing, count all recorded visits.

• Expecting a small sample to equal vπ(s)

  A small number of returns can produce an estimate noticeably different from the target value.

  Fix: Interpret the estimate as becoming more stable as more relevant visits are collected.

Practice the Selection Rule

The Essential Distinction

1. First-visit Monte Carlo records the return from the first occurrence of a state in each episode.
2. Every-visit Monte Carlo records the return from every occurrence of that state in each episode.
3. If a state appears only once in an episode, both methods record the same return from that episode.
4. The methods use the same policy-generated episodes and aim to estimate the same state value, vπ(s).
5. As the relevant number of visits increases, both methods converge to vπ(s) under the stated conditions.