n-step TD

The value of n controls how far the method looks ahead and how much bootstrapping remains in the return. Increasing the lookahead moves the method toward Monte Carlo learning; using a shorter lookahead keeps it closer to one-step TD.

Programming

From One Step to Several

Temporal-difference learning can learn from experience before an episode has finished. One-step methods use a nearby event, while Monte Carlo methods wait for a much longer return. n-step TD methods deliberately occupy the space between these approaches: they look ahead through the next n rewards, states, and actions, then use that information to update an earlier estimate.

Key point

What part of the learning target comes from sampled experience, and how does changing n place the method between one-step TD and Monte Carlo?

A Return Built from Lookahead

Suppose the learner is considering the state occupied at time t. An n-step method follows the trajectory forward and records the rewards, states, and actions encountered during the next n time steps. The estimate for the earlier state is not updated until the required future events are available. In this sense, the method creates a delay of n time steps between the earlier state and its update.

Worked example

Following a three-step lookahead

A learner is at state S_t and chooses action A_t. It uses a three-step method to learn from this part of the trajectory.

1
Start at time t
The learner identifies the earlier state, and possibly its state-action pair, whose estimate will eventually be updated.
2
Collect future experience
The learner records the rewards, states, and actions encountered over the next three time steps.
3
Wait for the required events
The update for the earlier state cannot occur until those three future steps are available.
4
Use the multi-step target
The collected trajectory supplies an intermediate return. The method uses the sampled future experience while retaining the bootstrapping characteristic that places n-step methods between one-step TD and Monte Carlo methods.

Result

The earlier estimate is updated after the three-step lookahead has been collected, rather than immediately after only one step or only after the entire return.

What do you think happens?

If a method looks ahead five time steps, when can the update for the relevant earlier state occur?

Immediately after the current action
After one time step
After five time steps
Only after every possible episode has finished

Reveal answer

Answer:

After five time steps

The source describes a five-step lookahead as creating a delay of five time steps before the relevant update. This is a consequence of waiting until the required future rewards, states, and actions are available.

After looking ahead n time steps, what experience must be retained before the earlier estimate can be updated?

Which Action Gets Corrected

In off-policy n-step Sarsa, the location of the importance-sampling ratio is determined by what the update is changing. The update concerns a state-action pair. The action already selected for that pair is therefore treated differently from the actions that follow it in the trajectory.

The initial selected action is not corrected. Importance sampling is applied to the subsequent actions used to learn from the trajectory, so the ratio begins one step later than it does in n-step TD. The important distinction is between the action that identifies the state-action estimate being updated and the later actions that contribute experience to the return.

Which action is selected for the state-action update, and where does correction begin for later actions?

Costs of Looking Ahead

The extra lookahead is useful, but it is not free. Waiting for n future time steps delays updates. Each time step also requires more computation than the earlier methods discussed in the chapter because the method handles a multi-step sequence rather than only the immediate event.

An implementation needs more memory than a one-step method to record the recent sequence of states, actions, rewards, and sometimes other variables from the last n time steps. The larger n becomes, the more recent trajectory information must be available before the corresponding update can be completed.

Common mistake
Applying importance sampling to the initial action in off-policy n-step Sarsa.
What it looks like
Treating A_t as if it were already one of the later actions in the trajectory.
Why it fails
A_t is the action selected for the state-action pair being updated. The correction applies to subsequent actions, so it begins one step later.
Do this instead
Separate the updated pair at time t from the actions selected after that pair.
Common mistake
Assuming every action appearing in the return is the action currently being updated.
What it looks like
Calling A_{t+1} the action whose state-action estimate is being updated simply because it appears in the trajectory.
Why it fails
The later actions contribute experience to the return, but the update may concern the earlier pair S_t, A_t.
Do this instead
Mark the update's state-action pair first, then identify later actions as trajectory evidence.
Common mistake
Correcting the final action in Expected Sarsa as though the target used only that sampled action.
What it looks like
Applying a correction to the action taken in the last state even though Expected Sarsa averages over all possible actions there.
Why it fails
Expected Sarsa uses an expectation over the policy's possible actions in the last state.
Do this instead
Distinguish a sampled-action target from an expected-action target.
Common mistake
Treating n-step TD as either a one-step method or a full Monte Carlo method.
What it looks like
Assuming that any method using several rewards must wait for the complete return.
Why it fails
n-step methods use an intermediate lookahead and intermediate bootstrapping.
Do this instead
Place the method according to both its lookahead length and the amount of bootstrapping it retains.
Common mistake
Forgetting that lookahead delays the update.
What it looks like
Expecting the estimate for the earlier state to change immediately when the current action is selected.
Why it fails
The required future rewards, states, and actions are not available yet.
Do this instead
Account for the n-step delay and retain the recent trajectory while waiting.

Eligibility Traces Later

The chapter later presents eligibility traces as a more resource-efficient way to implement multi-step TD methods. Their role is to address the storage and computation challenge created by explicitly handling many recent steps. The source describes this later approach as using minimal memory and computational complexity, while still requiring some additional computation beyond one-step methods.

The important connection is not that eligibility traces remove every cost. Rather, they provide a later implementation approach for multi-step credit assignment that avoids explicitly waiting for and storing every separate n-step return in the straightforward way. The detailed treatment belongs to a later chapter, so the current takeaway is the relationship between multi-step learning and resource-efficient implementation.

Check Your Reasoning

MEDIUM

A state-action pair at time t is being updated in an off-policy n-step Sarsa method. The trajectory contains the selected action at time t and several actions afterward. Explain which action is not corrected, where correction begins, and why the later actions are treated differently.

Hints

First identify the state-action pair whose estimate is being updated.
Then separate its selected action from the actions that follow it.
Remember that the source specifies placement, not a numerical ratio.

Your attempt (not saved)

MEDIUM

Compare a one-step TD method, an n-step TD method, and a Monte Carlo method in terms of lookahead, bootstrapping, and update timing.

Hints

One-step methods use a nearby event.
n-step methods wait for the next n rewards, states, and actions.
Monte Carlo methods represent the longer-lookahead extreme in this comparison.

Your attempt (not saved)

Key Takeaways

1
n-step TD methods look ahead through the next n rewards, states, and actions before updating an earlier estimate.
2
They form a middle ground between one-step TD and Monte Carlo methods through intermediate bootstrapping.
3
In off-policy n-step Sarsa, the initial selected action belongs to the state-action pair being updated and is not corrected; importance sampling begins with subsequent actions.
4
Expected Sarsa accounts for all possible actions in the last state, so the action actually taken there does not require correction.
5
Longer lookahead delays updates and increases computation and memory requirements; eligibility traces are introduced later as a more resource-efficient implementation approach.

At a glance

n-step TD uses an intermediate lookahead and an intermediate amount of bootstrapping.
The update for an earlier state is delayed until the required n future steps are available.
For off-policy n-step Sarsa, importance-sampling correction begins after the initial action selected for the updated state-action pair.
Expected Sarsa averages over possible actions in the last state, so it does not correct the action actually taken there.
The extra trajectory storage and computation motivate the later use of eligibility traces.

Related concepts

More concepts starting with N