Concepts / n-Step Backups

n-Step Backups

The number n specifies how many real rewards are collected before the backup relies on an estimated value at the later state.

  • Programming

From Immediate Rewards to Longer Backups

An estimate of a state can learn from what happens after that state. One-step temporal-difference learning uses the next reward and a later value estimate. Monte Carlo learning waits for the episode to end and uses the complete discounted reward sequence. n-step backups provide the choices between these endpoints: they use several observed rewards, then use a value estimate for the remaining part.

Key point

The number n specifies how many real rewards are collected before the backup relies on an estimated value at the later state.

The Return Horizon

Definition

The full return is the complete discounted reward sequence beginning at a time step and continuing through episode termination. It uses every later reward in that episode, with the appropriate discounting.

Definition

An n-step return truncates the discounted reward sequence after the next n steps. It includes the rewards observed from time t through time t+n-1 explicitly, then uses the value estimate of the state reached after those n steps to represent the missing later terms. That estimate is discounted by γ^n.

S_tearlier stateR_{t+1}explicit rewardR_{t+2}explicit rewardR_{t+n}explicit rewardS_{t+n}later stateV(S_{t+n})estimated remaindernext stepcontinuecontinue to nreachesvalue estimate
Which rewards are included explicitly, and where does the estimate of the later terms enter?

The boundary after the nth step is the key idea. Before that boundary, the backup uses rewards that were actually observed. At the boundary, it stops collecting real rewards and substitutes the later state's value estimate for the unobserved remainder.

A Backup Traced Backward

Worked example

Following a three-step return

An estimate is being updated for state S_t using a three-step backup. The next three rewards are R_{t+1}, R_{t+2}, and R_{t+3}. The state reached after the third step is S_{t+3}. What information forms the backup target?

  1. 1
    Start at the earlier state

    The estimate for S_t is the estimate being reconsidered.

  2. 2
    Collect three observed rewards

    The backup includes R_{t+1}, R_{t+2}, and R_{t+3} explicitly, with their appropriate discounting.

  3. 3
    Reach the boundary state

    After the third step, the backup reaches S_{t+3}.

  4. 4
    Represent the missing remainder

    The value estimate for S_{t+3} stands in for the later terms that have not been included as explicitly observed rewards. Its contribution is discounted by γ^3.

  5. 5
    Update the earlier estimate

    The estimate for S_t is changed using the combined evidence from the three observed rewards and the later estimate.

Result

A three-step backup connects an earlier estimate to a state three steps later. It is not a full return because the episode has not necessarily been followed through termination.

V(S_t)estimate reconsideredn rewardsobserved sequenceS_{t+n}later stateV(S_{t+n})later estimaten-step targetcombined evidenceupdated V(S_t)earlier estimate changesdiscounted rewardsevaluatediscounted remainderupdatesreconsidered estimate
How does information observed at a later state flow backward to update the estimate at the earlier state?

Information flows backward in the backup even though the observed experience moves forward. The later state supplies an estimate of what comes after the observed reward sequence, and that combined target is used to reconsider the earlier state's estimate.

Choosing the Backup Length

BackupObserved rewards usedWaits untilUses a value estimate for the remainder
One-step TDThe next rewardThe next stateYes
n-step TDThe next n rewardsThe state reached after n stepsYes, unless termination occurs before the horizon
Monte CarloAll rewards through episode terminationEpisode terminationNo later value estimate is needed for the completed return

The three backup styles differ by where they stop collecting observed rewards and whether they substitute a later value estimate.

One-step TDone rewardvalue estimateusedn-step TDn rewardsvalue estimateused at boundaryMonte Carlothrough terminationfull returnno later estimatebootstrapsbootstrapsuses complete sequence
What information does each backup use, how many rewards does it wait for, and does it bootstrap?

Changing n changes the distance between the earlier estimate and the later estimate used for comparison. A one-step backup uses the next state. An n-step backup uses a state n steps away. The Monte Carlo endpoint continues through termination instead of stopping at an estimated boundary. These are points on a continuum of backup styles, not three unrelated techniques.

Termination Before the Horizon

An episode may terminate before n steps have been collected. In that case, the n-step return contains all the rewards that actually occur before termination. There is no remaining later portion that needs to be represented by a value estimate, so the n-step return is equal to the ordinary full return.

S_tbackup beginsobserved rewardsepisode ends earlyfull returnall rewards includedfollow episodetermination before n
What happens when the episode terminates before the n-step horizon?
Worked example

A horizon longer than the remaining episode

An n-step backup is configured with a horizon of n steps, but the episode terminates after fewer than n steps. Decide whether a later value estimate is needed.

  1. 1
    Follow the episode

    Record every reward that occurs from the starting time step until termination.

  2. 2
    Check the horizon

    Termination occurred before the n-step horizon was reached.

  3. 3
    Remove the missing-term concern

    Because the episode has ended, there are no later rewards beyond termination that need to be represented.

  4. 4
    Compare the returns

    The rewards included are the complete discounted reward sequence for the episode.

Result

The n-step return equals the ordinary full return, and no later value-estimate term is needed.

Information Checklist

S_tearlier statestatesthrough the horizonactionsalong the experiencerewardsnext n rewardsterminationbefore horizon?V(S_{t+n})if not terminatedn-step returnbackup targetestimate to updatelocates boundary statepart of observed trajectoryexplicit termsdetermines remainderestimated later terms
Which observed states, rewards, termination information, and value estimates are needed to compute the backup?
  • The earlier state whose estimate is being reconsidered.
  • The sequence of observed states and actions along the experience.
  • The rewards observed during the next n steps, or all remaining rewards if termination occurs first.
  • Information about whether the episode terminated before the n-step horizon.
  • The value estimate at the state reached after n steps when the episode has not terminated.

The central bookkeeping question is: where did the backup stop using observed rewards? If the episode is still continuing at that boundary, the later state's estimate supplies the missing terms. If termination occurred first, the observed sequence already reaches the end of the episode.

Mistakes in Identifying the Backup

  • Common mistake

    Treating an n-step return as a completely different target from the full return.

    What it looks like

    An n-step return is described as unrelated to the complete discounted reward sequence.

    Why it fails

    The n-step return is an approximation to the full return. It uses the first n observed rewards and estimates the remaining part.

    Do this instead

    Describe it as a truncated full-return sequence completed by a later value estimate.

  • Common mistake

    Counting the later value estimate as an additional observed reward.

    What it looks like

    A three-step backup is said to contain four observed rewards because it also uses V(S_{t+3}).

    Why it fails

    The value estimate is not a reward. It represents the missing later terms after the three explicitly observed rewards.

    Do this instead

    Count the rewards separately from the value estimate at the boundary state.

  • Common mistake

    Calling every n-step backup Monte Carlo.

    What it looks like

    A backup that waits for several rewards is labeled Monte Carlo without checking whether it uses a later estimate.

    Why it fails

    Monte Carlo continues through episode termination. An n-step TD backup stops after n rewards when the episode continues and uses a value estimate for the remainder.

    Do this instead

    Check whether the backup bootstraps from a later value estimate.

  • Common mistake

    Assuming n-step always means that exactly n rewards are available.

    What it looks like

    A backup is forced to add a value estimate even when the episode terminated before n steps.

    Why it fails

    If termination occurs first, the return already contains the complete reward sequence through the end of the episode.

    Do this instead

    Use the full observed sequence through termination and omit the later estimate.

  • Common mistake

    Thinking n-step methods stop being TD methods because they use multiple rewards.

    What it looks like

    Only one-step backups are called temporal-difference methods.

    Why it fails

    n-step methods still update an earlier estimate using a later estimate; the comparison point is simply farther away.

    Do this instead

    Focus on the use of a later estimate, not just on the number of rewards.

Check Your Understanding

MEDIUM

An episode continues beyond the next four steps. An estimate for S_t is updated using the next four observed rewards and the value estimate at S_{t+4}. Is this a full return, a one-step TD backup, or a four-step TD backup? Explain what represents the later terms.

Hints
  • Count the explicitly observed rewards.
  • Check whether the episode has terminated.
  • Identify whether a later value estimate is used.

What do you think happens?

An episode terminates after two steps, but the selected backup horizon is five steps. Does the backup need a value estimate for a state five steps later?

  • Yes, always

  • No, because termination occurred first

  • Only if one reward was observed

Reveal answer
Answer:

No, because termination occurred first.

The observed rewards already extend through episode termination, so the n-step return equals the ordinary full return and no later value-estimate terms are needed.

Backup Summary

  1. 1
    The full return contains the complete discounted reward sequence through episode termination.
  2. 2
    An n-step return includes the next n observed rewards and then uses a later value estimate for the missing terms.
  3. 3
    The later estimate's contribution is discounted by γ^n.
  4. 4
    If termination occurs before n steps, the n-step return equals the ordinary full return and needs no later value estimate.
  5. 5
    n-step methods remain TD methods because they update an earlier estimate from a later estimate, even though that later estimate is n steps away.

At a glance

  • The full return follows discounted rewards all the way to episode termination.
  • The n-step return uses n real rewards and a discounted value estimate at the nth next state.
  • The later value estimate supplies an approximation for the missing later terms.
  • Early termination makes the n-step return equal to the ordinary full return.
  • n-step backups are TD methods because an earlier estimate is updated using a later estimate.

Related Topics

Related concepts

More concepts starting with N