Concepts / Returns and Expected Discounted Rewards

Returns and Expected Discounted Rewards

A return is an observation obtained from what happens after a visit. Monte Carlo estimation uses complete observed returns, rather than trying to estimate the state value from a single outcome.

  • Programming

From State to Evidence

Suppose an agent follows a fixed policy and repeatedly experiences complete episodes. You want to estimate how valuable a particular state is, but the value is not given directly. Monte Carlo state-value estimation takes a direct route: whenever the agent reaches the state, observe what happens afterward, record the resulting return, and use observed returns as evidence about the state's value.

The state value is an expected return. An individual recorded return is not the value itself; it is one observation used to estimate that value. As more returns are collected after visits to the state, their average should converge to the expected value under the policy being followed.

Tracing One Visit

Begin at a particular visit to state s inside an episode. Look at the rewards that occur after that visit and use the resulting complete return as the observation associated with that visit. The return is therefore tied to a position in the episode: starting from an earlier visit gives the outcome of everything that follows from that point, while starting from a later visit gives the outcome from the later point.

Visit to sepisode positionReward 1Reward 2Later rewardsObserved returncomplete episode outcomefollow the episodethencontinuecombine into
How does one visit to a state connect to the subsequent rewards and the complete observed return?
Key point

A return is an observation obtained from what happens after a visit. Monte Carlo estimation uses complete observed returns, rather than trying to estimate the state value from a single outcome.

Repeated Visits in One Episode

A state can appear once, twice, or more in one episode. Each occurrence of state s is a visit to s. The occurrence's position matters because the return associated with that visit begins from that occurrence and reflects what follows it in the episode.

sfirst occurrenceReturn after first sLater episode stepsReturn after later sslater occurrenceepisode continuesreturns to sobserve after first occurrenceobserve after later occurrence
What counts as a visit to a state, and why can different visit positions produce different observed returns?

When an episode returns to s, the return after the first occurrence and the return after the later occurrence are separate observations for every-visit Monte Carlo. First-visit Monte Carlo deliberately keeps only the return after the first occurrence in that episode.

Choosing the Averaging Rule

Worked example

Selecting returns for state s

The observed returns relevant to state s are 5 and 3 under the first-visit rule. Under the every-visit rule, the observed returns are 5, 1, 7, and 3. Which returns belong in each estimate?

  1. 1
    First-visit selection

    Use one return per episode containing s: the return after the first occurrence of s. The selected returns are 5 and 3.

  2. 2
    Every-visit selection

    Use a return after every occurrence of s. The selected returns are 5, 1, 7, and 3.

  3. 3
    Apply the rule before averaging

    The averaging step depends on the visit rule chosen. First decide which observations qualify, then average that selected collection.

Result

First-visit MC averages 5 and 3. Every-visit MC averages 5, 1, 7, and 3.

Episodesreturn 5First-visit set5, 3sreturn 1Every-visit set5, 1, 7, 3sreturn 7sreturn 3containscontainscontainscontainsfirst occurrencesource example's second episodeincludeincludeincludeinclude
When state s appears multiple times in an episode, which occurrences contribute returns to the estimate?
Best practice

Choose the visit rule before collecting or averaging observations. Otherwise, you may accidentally mix first-visit and every-visit data and produce an estimate that follows neither method.

Mistakes in Visit Selection

  • Common mistake

    Treating the state value as if it were one observed return.

    What it looks like

    Using one episode's return as the value of state s.

    Why it fails

    The value is an expected return, while an individual return is only one observation used for estimation.

    Do this instead

    Collect observed returns and use their average according to the selected Monte Carlo visit rule.

  • Common mistake

    Counting a state only once because it is one distinct state.

    What it looks like

    Ignoring the later occurrence when an episode visits s twice.

    Why it fails

    Each occurrence of s is a visit to s. Every-visit MC includes a return after every occurrence.

    Do this instead

    Inspect the episode positions and apply either the first-visit or every-visit rule.

  • Common mistake

    Using every occurrence for first-visit MC.

    What it looks like

    Including both returns after two occurrences of s in one episode.

    Why it fails

    First-visit MC includes one return per episode containing the state.

    Do this instead

    Keep only the return after the first occurrence in each episode.

  • Common mistake

    Using only the first occurrence for every-visit MC.

    What it looks like

    Discarding the return after a later occurrence of s.

    Why it fails

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

    Do this instead

    Include a return after every occurrence of s.

Edge case

If an episode contains s only once, first-visit MC and every-visit MC select the same return from that episode. The distinction appears when the episode contains s more than once.

Check the Selection

EASY

An episode contains state s twice. The return after the first occurrence is 5, and the return after the later occurrence is 1. Another episode contains s once, with return 3. Which returns should be averaged for first-visit MC? Which should be averaged for every-visit MC?

Hints
  • First-visit MC keeps one return per episode containing s.
  • Every-visit MC keeps a return after every occurrence of s.

What do you think happens?

Which return sets should be selected?

  • First-visit: 5 and 3; every-visit: 5, 1, and 3

  • First-visit: 5, 1, and 3; every-visit: 5 and 3

  • Both methods: 5, 1, and 3

Reveal answer
Answer:

First-visit uses 5 and 3. Every-visit uses 5, 1, and 3.

The first-visit rule selects one return from each episode, using the first occurrence of s. The every-visit rule selects both returns from the first episode and the one return from the second episode.

Key Takeaways

  1. 1
    A state value is an expected return; each recorded return is an observation used to estimate it.
  2. 2
    A visit is each occurrence of a state within an episode.
  3. 3
    First-visit Monte Carlo uses one return per episode containing the state, taken after the first occurrence.
  4. 4
    Every-visit Monte Carlo uses a return after every occurrence of the state.
  5. 5
    Select the correct returns first, then average them to form the estimate.

At a glance

  • Monte Carlo state-value estimation learns from complete observed returns.
  • The state value is an expected return, not any single observed return.
  • Every occurrence of a state is a visit, even when the state appears multiple times in one episode.
  • First-visit MC uses only the first occurrence per episode, while every-visit MC uses all occurrences.
  • The visit rule determines which returns belong in the average.

Related Topics

Related concepts

More concepts starting with R