n-step TD

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.

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.

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.

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.

• Applying importance sampling to the initial action in off-policy n-step Sarsa.

  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.

  Fix: Separate the updated pair at time t from the actions selected after that pair.

• Assuming every action appearing in the return is the action currently being updated.

  The later actions contribute experience to the return, but the update may concern the earlier pair S_t, A_t.

  Fix: Mark the update's state-action pair first, then identify later actions as trajectory evidence.

• Correcting the final action in Expected Sarsa as though the target used only that sampled action.

  Expected Sarsa uses an expectation over the policy's possible actions in the last state.

  Fix: Distinguish a sampled-action target from an expected-action target.

• Treating n-step TD as either a one-step method or a full Monte Carlo method.

  n-step methods use an intermediate lookahead and intermediate bootstrapping.

  Fix: Place the method according to both its lookahead length and the amount of bootstrapping it retains.

• Forgetting that lookahead delays the update.

  The required future rewards, states, and actions are not available yet.

  Fix: 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

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.