n-step Sarsa

Delayed Learning Signal

n-step Sarsa delays an action-value update until rewards from several steps can contribute to the return. The method therefore has two separate ideas to keep distinct: first, it constructs an n-step target; second, it uses that target in an action-value update. The target is a learning quantity supplied to the update rule. It is not the update rule itself.

Target into Update

The n-step target summarizes information from a later portion of the episode. That information can include several successive rewards and, when the episode has not ended within the available range, a later estimated action value Q(Sτ+n, Aτ+n). Once the target has been obtained, the usual action-value update rule from n-step Sarsa uses it to update the earlier action value associated with time τ. In other words, the target answers what learning quantity is available, while the update rule answers how that quantity changes an action value.

Building the Return Window

The n-step target is built from a window that begins with the experience at the update time τ. Rewards from successive steps contribute to that window. If τ + n is still before the terminal time T, the target also includes the discounted later action value Q(Sτ+n, Aτ+n). If the episode ends within the available range, the return stops at the terminal time instead of using that later Q estimate.

Reading τ, T, and n

The pseudocode advances through an episode while storing states, actions, and rewards. At each processing time t, it calculates the update time as τ = t - n + 1. This delay means the algorithm can update an earlier state-action pair only after enough subsequent experience has become available. The value τ identifies which earlier pair is updated, n determines the length of the delayed information window, and T marks when the episode ends.

Action Selection and Tree Backup

During n-step Sarsa, an ε-greedy policy selects actions by combining greedy choice with random action selection. The selected actions become part of the states, actions, and rewards stored for the delayed return. The source also states that, in the stated Tree Backup formulation, the Tree Backup target is used with the usual action-value update rule from n-step Sarsa. Thus, the shared point is the update rule that consumes a target. The difference described at this level is how Tree Backup accounts for alternative actions in its backup, rather than following only the sampled action sequence in the same way.

Tracing a Divergence

Read the pseudocode as an execution trace rather than as isolated lines. A useful debugging trace follows the information in order: the transition that produced the next reward and state, whether that next state was terminal, the computed τ, whether τ was nonnegative, and whether the later Q term belongs in the target. The first incorrect landmark is usually more informative than the final incorrect action value.

Credit Along a Successful Path

The Gridworld example in the source illustrates why n-step methods can learn faster from one successful episode. Suppose an agent follows a sequence of actions and eventually reaches a location of high reward. With one-step Sarsa, only the last action in the sequence leading to that high reward is strengthened by that episode. With n-step Sarsa, the last n actions in the sequence can be strengthened, so information from the high reward travels farther backward through the successful path.

Common Trace Mistakes

• Treating the n-step target as the update itself.

  The target is a quantity used by the usual action-value update rule. It is not the same object as the rule that updates the action value.

  Fix: Track the target first, then track the action-value update for the earlier pair identified by τ.

• Updating the most recent state-action pair instead of the pair at τ.

  The pseudocode calculates τ as t - n + 1, and τ identifies the earlier pair whose n-step information is now available.

  Fix: Recompute τ at each processing time and use it to locate the action value being updated.

• Including a later Q estimate after the episode has already ended.

  When the episode ends within the available range, the return uses rewards up to T instead of a later action value.

  Fix: Compare τ + n with T before deciding whether the later Q term belongs in the target.

• Ignoring the zero-factor product convention.

  The stated convention defines a product of zero factors as 1.

  Fix: Use 1 for a product containing no factors.

• Assuming n-step learning makes every value immediately correct.

  The advantage is that information travels farther backward in one episode, not that every estimate becomes immediately correct.

  Fix: Ask how far the selected n-step return carries information and whether the episode ended before the full window was available.

Trace Practice

Essential Takeaways

1. The n-step target is a learning quantity, while the action-value update rule uses that quantity to change an earlier action value.
2. The target combines several later rewards and, when the episode continues far enough, a later estimated action value.
3. The update time is τ = t - n + 1; n controls the delayed window, and T controls whether the return stops at the episode ending or includes a later Q estimate.
4. A product of zero factors equals 1, and this convention must be applied when the target construction reaches an empty product.
5. n-step methods can carry information from a high reward back through the last n actions of a successful sequence, whereas one-step Sarsa strengthens only the last action from that episode.