Tabular n-step TD algorithm

Waiting Before Updating

The n-Step TD Algorithm does not immediately update the value estimate for the state just observed. Instead, it waits for several steps of experience, uses those rewards to construct an n-step return G, and then updates an earlier state estimate. The state being updated is the state at time τ, not necessarily the state at the current time step.

Finding the Updated State

As experience arrives one step at a time, the algorithm identifies an earlier time index τ. That index determines which state is eligible for an update. The value changed by the update is V(Sτ). The current time step supplies new experience, but τ points back to the state whose return can now be calculated.

Constructing the Return

The n-step return combines discounted rewards collected from time τ through the n-step boundary. If the episode has not terminated by that boundary, the return also includes a discounted later value estimate, V(Sτ+n). This later estimate is the bootstrapped part of the target. If termination occurs before the boundary, the return uses the rewards available up to termination instead of continuing with a later value estimate.

G = discounted rewards from time τ through time τ+n−1, plus a discounted V(Sτ+n) when the n-step boundary occurs before termination

The numerical contributions in this example are illustrative. The important structure is that several rewards are combined first, and a later value estimate is included only when the episode continues far enough for bootstrapping to apply.

Applying the Value Update

Return Versus Procedure

The n-step return equation and the complete n-step TD algorithm are related but not identical. The return describes how to construct the target G from rewards and, when appropriate, a later value estimate. The complete algorithm describes when experience is collected, how τ is identified, when the return can be calculated, how terminal time T affects the calculation, and when the update is performed.

Terminal time T is part of the control flow, not merely a detail of the return formula. While the process is before T, the algorithm gathers the next reward and state. Once termination occurs, it must stop extending the experience and complete the updates that are still pending. The reward sum is also limited by termination, so the algorithm must not bootstrap beyond the terminal point.

From Tables to Function Approximation

The semi-gradient n-step TD algorithm is not presented as an unrelated method. It begins with the tabular n-step TD method, generalizes the n-step return, and uses that generalized return in a function-approximation setting. The key conceptual path is therefore tabular method, generalized return, then semi-gradient method.

Control-Flow Mistakes

• Updating a value when τ is negative.

  A negative τ refers to an earlier index that is not yet available for the algorithm's update scheme.

  Fix: Check the update condition and proceed only when τ is eligible.

• Never updating when τ is nonnegative.

  An eligible state has been identified, but control flow prevents its return from being calculated or its value from being changed.

  Fix: Trace the condition around τ, the return calculation, and the update statement.

• Bootstrapping after the episode has terminated.

  The return should stop at termination and omit the continuation value beyond the terminal point.

  Fix: Use the later value estimate only when the episode continues to the n-step boundary.

• Treating the return equation as the whole algorithm.

  The equation defines the target, while the complete procedure determines when that target can be used.

  Fix: Check both target construction and the surrounding time and termination control flow.

• Replacing V(Sτ) directly with G.

  The tabular update moves the estimate by α[G − V(Sτ)], using a fraction controlled by the step size.

  Fix: Apply the full update expression and verify that α is in (0, 1].

Practice Check

Key Takeaways

1. n-step TD waits for several steps of experience before updating an earlier state estimate.
2. The return G combines discounted rewards and, when the episode continues to the boundary, a discounted later value estimate.
3. The update changes V(Sτ) using V(Sτ) ← V(Sτ) + α[G − V(Sτ)].
4. The return equation is one part of the complete algorithm; τ, terminal time T, eligibility checks, and pending updates belong to the surrounding procedure.
5. Semi-gradient n-step TD extends the tabular method by generalizing the return for function approximation.