Introduction to n-Step TD Methods

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.

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.

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.

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.

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.

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.

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.