n-Step TD Algorithm and Error Reduction Property

Why Delay the Update

The n-Step TD Algorithm does not immediately update the value estimate for the current state after one transition. Instead, it waits for several steps of experience, uses that information to construct an n-step return G, and then updates an earlier state estimate. The central idea is to connect two operations: first calculate the return for the state at time τ, then move V(Sτ) toward that return.

Finding the Update Index

The time index τ identifies the state whose estimate is eligible for updating. The algorithm first gathers the next reward and state while t is still before the episode's terminal time T. It then identifies τ. Only an eligible τ proceeds to return calculation and value-function updating.

Constructing G

G = discounted rewards from time τ+1 through the n-step boundary, plus a discounted later value estimate when the boundary occurs before termination

The important distinction is whether the episode has already ended. Continuing episodes provide both observed reward information and a later value estimate. An episode that ends early provides only the rewards that were actually observed before termination; there is no continuation value beyond the terminal point.

Applying the Value Update

V(Sτ) ← V(Sτ) + α[G - V(Sτ)]

The step size α controls how much of the difference is applied. The source specifies that α lies in the interval (0, 1], so the update uses a fraction controlled by α of the gap between G and the current estimate. The old estimate is not directly replaced by G.

Understanding Error Reduction

The update reduces the gap between the current estimate and the constructed n-step target whenever α is in (0, 1]. The amount changed is α[G - V(Sτ)]. Thus, if G is above V(Sτ), the estimate increases; if G is below V(Sτ), the estimate decreases; and if they are equal, the update makes no change.

Terminal Episodes

The terminal time T controls both the reward sum and the end of the repeated process. The algorithm gathers the next reward and state only while t is before T. When an episode terminates before the n-step boundary, the n-step return contains the discounted rewards that were observed, but not a continuation value estimate beyond termination.

Implementation Mistakes

• Updating when τ is negative

  The algorithm is attempting to update an earlier state that is not yet eligible in its indexing scheme.

  Fix: Check the eligibility condition before calculating G and updating V(Sτ).

• Never updating when τ is nonnegative

  The problem is likely in the condition surrounding the update or in the calculation of τ.

  Fix: Trace τ and the conditional branch that should lead to return calculation and value updating.

• Adding a continuation value after termination

  A continuation term is used when the n-step boundary occurs before termination; it is absent when the episode terminates first.

  Fix: Use the terminal time T to limit the reward sum and omit the continuation value term after termination.

• Replacing the estimate with G

  The algorithm moves the estimate toward G by the amount α[G - V(Sτ)] rather than replacing the old estimate directly.

  Fix: Apply V(Sτ) ← V(Sτ) + α[G - V(Sτ)].

Practice Check

Key Takeaways

1. The n-Step TD Algorithm waits for several steps of experience before updating an earlier state estimate.
2. τ identifies the state Sτ whose value estimate is updated; only an eligible nonnegative τ should proceed to the update.
3. The n-step return G combines discounted observed rewards and, when the n-step boundary occurs before termination, a later value estimate.
4. The update moves V(Sτ) toward G by α[G - V(Sτ)] rather than replacing the old estimate directly.
5. The terminal time T, the continuation term, and the condition on τ are essential control-flow checkpoints.