Concepts / n-Step Backups

n-Step Backups

The full return is the complete discounted reward sequence through episode termination.

  • 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.

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

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.

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.

next stepcontinuecontinue to nreachesvalue estimateS_tearlier stateR_{t+1}explicit rewardR_{t+2}explicit rewardR_{t+n}explicit rewardS_{t+n}later stateV(S_{t+n})estimated remainder
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

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?

Start at the earlier state: The estimate for S_t is the estimate being reconsidered.

Collect three observed rewards: The backup includes R_{t+1}, R_{t+2}, and R_{t+3} explicitly, with their appropriate discounting.

Reach the boundary state: After the third step, the backup reaches S_{t+3}.

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.

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

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.

discounted rewardsevaluatediscounted remainderupdatesreconsidered estimateV(S_t)estimate reconsideredn rewardsobserved sequenceS_{t+n}later stateV(S_{t+n})later estimaten-step targetcombined evidenceupdated V(S_t)earlier estimate changes
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
bootstrapsbootstrapsuses complete sequenceOne-step TDone rewardvalue estimateusedn-step TDn rewardsvalue estimateused at boundaryMonte Carlothrough terminationfull returnno later estimate
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.

follow episodetermination before nS_tbackup beginsobserved rewardsepisode ends earlyfull returnall rewards included
What happens when the episode terminates before the n-step horizon?

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.

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

Check the horizon: Termination occurred before the n-step horizon was reached.

Remove the missing-term concern: Because the episode has ended, there are no later rewards beyond termination that need to be represented.

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

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

Information Checklist

estimate to updatelocates boundary statepart of observed trajectoryexplicit termsdetermines remainderestimated later termsS_tearlier statestatesthrough the horizonactionsalong the experiencerewardsnext n rewardsterminationbefore horizon?V(S_{t+n})if not terminatedn-step returnbackup target
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

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

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

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

  • Counting the later value estimate as an additional observed reward.

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

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

  • Calling every n-step backup Monte Carlo.

    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.

    Fix: Check whether the backup bootstraps from a later value estimate.

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

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

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

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

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

    Fix: 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. The full return contains the complete discounted reward sequence through episode termination.
  2. An n-step return includes the next n observed rewards and then uses a later value estimate for the missing terms.
  3. The later estimate's contribution is discounted by γ^n.
  4. If termination occurs before n steps, the n-step return equals the ordinary full return and needs no later value estimate.
  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.

Key Takeaways

  • 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