Introduction to n-Step TD Methods

A Deliberate Middle Ground

When a learner estimates the value of a state, it must decide how much future experience to use. A one-step TD method uses the next event quickly. A Monte Carlo method waits for the return through the end of the episode. An n-step TD method chooses an intermediate amount of lookahead: it uses the next n rewards, states, and actions, then estimates what comes after them. This makes n-step methods a middle ground based on intermediate bootstrapping.

Building the n-Step Return

The full return for a state at time t is the complete discounted reward sequence from time t through the end of the episode. An n-step return truncates that sequence after n steps. The first n rewards are included explicitly because the learner has observed them. The value estimate for the state reached after those n steps represents the missing later terms. That estimate is discounted by γ^n, so the later portion contributes less according to the same discounting position it would have in the return.

Following One State Forward

Consider the state occupied at time t. An n-step method must follow the experience far enough to collect the next n rewards, states, and actions. Only when those required future events are available can the estimate for the earlier state be updated. The result is a delay of n time steps between the earlier state and its update, except when the episode terminates sooner.

Near episode termination, the learner may not have n future steps available. In that case, the episode ends before the planned lookahead is complete, so the available reward sequence reaches termination sooner. The n-step return then contains the complete remaining sequence rather than waiting for nonexistent future steps.

The Full-Return Boundary

An n-step return equals the ordinary full return when the episode terminates within the chosen n-step lookahead. There are no later terms left to estimate beyond the point of termination. The return therefore includes the entire remaining discounted reward sequence, making the bootstrapped replacement unnecessary.

Choosing the Amount of Lookahead

The position of an n-step method can be understood by comparing how much it observes with how much it bootstraps. A one-step method uses the next event and therefore updates with a short lookahead. A Monte Carlo method uses the full return through episode termination and does not need the same intermediate cutoff. An n-step method uses more than one immediate event but stops before the full return when the episode continues beyond n steps.

Resource Costs of Waiting

Looking farther ahead has practical costs. Updates are delayed because the method must wait for n future time steps. Each time step requires more computation than the earlier methods discussed in the chapter because the method handles a longer sequence. An implementation also needs more memory than a one-step method to retain states, actions, rewards, and sometimes other variables from the last n time steps.

• Update delay: the estimate for an earlier state waits for the required future steps.
• Computation: each time step involves more work than the earlier one-step methods discussed in the chapter.
• Memory: recent states, actions, rewards, and sometimes other variables must be retained for the last n time steps.

Eligibility Traces Later

Eligibility traces are presented as a later way to implement multi-step TD methods. Their role is to connect recent states to later rewards so that multiple prior states can be updated. This addresses the storage and computation challenge created by explicitly retaining a recent sequence for multi-step learning. The source also notes that eligibility traces do not remove every cost: some additional computation beyond one-step methods remains. The detailed treatment belongs to a later chapter, so the key connection here is that eligibility traces offer a more resource-efficient implementation approach.

Check Your Understanding

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

  The n-step return approximates the full return. It includes the first n observed rewards and uses a value estimate to represent the missing later terms.

  Fix: Think of the n-step return as a truncated full return completed by bootstrapping.

• Assuming that every n-step return always uses exactly n rewards.

  Near termination, the episode may end before n future steps are available.

  Fix: Use the complete remaining reward sequence when termination occurs within the selected lookahead.

• Forgetting the update delay.

  The method needs the required future rewards, states, and actions before forming the four-step return.

  Fix: Expect the update after four future steps when those steps exist, with earlier termination handled separately.

• Calling n-step TD a Monte Carlo method because it uses several rewards.

  n-step TD stops after n steps and uses a value estimate for the remaining future when the episode continues.

  Fix: Classify the method by its intermediate bootstrapping boundary, not merely by the number of observed rewards.

Key Takeaways

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 uses a value estimate at the n-step boundary for the missing later terms, discounted by γ^n.
3. If the episode terminates within n steps, the n-step return includes the entire remaining sequence and equals the ordinary full return.
4. N-step methods sit between one-step TD and Monte Carlo methods because they use intermediate bootstrapping.
5. Looking ahead n steps delays updates and increases computation and memory requirements; eligibility traces are a later, more resource-efficient implementation approach for multi-step TD methods.