Learning State-Value Functions Under a Policy

From Episodes to Evidence

Suppose an agent follows a fixed policy and repeatedly experiences episodes. You want to estimate how valuable a particular state is, but you do not begin with the value itself. Instead, you observe what happens after the agent reaches the state, record the resulting return, and use the collected returns as evidence.

The state value is an expected return. A recorded return is not the value itself; it is one observation used to estimate that value. Monte Carlo state-value estimation therefore learns from complete observed returns rather than from a single outcome. As more returns are collected after visits to the state, their average should converge to the expected value.

Pairing States with Returns

An episode supplies a sequence of states and a completed outcome. For each visit to a state, the return observed after that visit becomes evidence about the state's value. The important pairing is therefore state occurrence with the return that follows it, not state occurrence with a single immediate outcome.

Recognizing a Visit

A visit occurs whenever the agent reaches the state during an episode. If state s appears once, the episode contains one visit to s. If state s appears twice or more, each occurrence is a visit to s. The occurrence's position in the episode matters because first-visit and every-visit methods select those occurrences differently.

Choosing the Visit Rule

First-visit Monte Carlo includes one return per episode containing the state. It deliberately uses only the return after the first occurrence of that state in the episode. Every-visit Monte Carlo includes a return after every occurrence of the state. If the episode returns to the state, both the return after the first occurrence and the return after the later occurrence enter the every-visit average.

Tracing a Repeated State

Following the Episode

The complete process is empirical. A fixed policy generates episodes. Episodes contain visits to states. The outcomes after those visits provide observed returns. The chosen visit rule determines which of those returns are retained, and the retained returns are averaged to estimate the state value.

Mistakes in Return Selection

• Treating the state value as identical to one observed return.

  The state value is an expected return, while each recorded return is only an observation used to estimate it.

  Fix: Collect the relevant observed returns and use their average as the estimate.

• Counting an episode only once even when the state appears more than once.

  Each occurrence of s is a visit, and every-visit MC uses a return after every occurrence.

  Fix: Record the occurrences separately, then apply either the first-visit or every-visit rule.

• Using every occurrence when first-visit MC was selected.

  First-visit MC deliberately limits each episode to the return after the first occurrence of s.

  Fix: Keep only the first occurrence's return from that episode.

• Using only the first occurrence when every-visit MC was selected.

  Every-visit MC treats each occurrence of s as evidence.

  Fix: Include the return after every occurrence of s.

Practice the Selection

Working Rule

1. Follow the fixed policy and observe complete episodes.
2. Identify every occurrence of the state whose value is being estimated.
3. Record the return observed after each occurrence.
4. If using first-visit MC, retain only the return after the first occurrence in each episode.
5. If using every-visit MC, retain the return after every occurrence.
6. Average the retained returns to estimate the state's expected return.

The central decision is not which return looks most representative. It is which occurrences the selected Monte Carlo method allows into the estimate. First-visit MC uses one return per episode containing the state. Every-visit MC uses a return after every occurrence. In both cases, the retained observed returns provide evidence for the state's expected return.