Tabular n-step TD algorithm

The semi-gradient n-step TD algorithm is the function-approximation extension of tabular n-step TD.

Programming

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.

Key point

The method connects two operations: first calculate the return for Sτ, then move V(Sτ) toward that return.

How are rewards from time τ through τ+n−1 combined, and when is the value estimate at time τ+n included?

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.

As experience arrives, which earlier time index τ becomes eligible, and which state value is changed?

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.

Formula, step by step

1
Start with the reward contributions observed after time τ.
2
Discount the reward contributions according to their distance from τ.
3
If the episode is still continuing at the n-step boundary, add the appropriately discounted later value estimate V(Sτ+n).
4
If termination occurred first, stop at the terminal point and omit the continuation value estimate.

Worked example

A three-step target

Suppose the three discounted reward contributions available for Sτ are 2, 1.5, and 0.5. The episode has not terminated at the three-step boundary, and the discounted later value contribution is 3.

1
Combine rewards
The reward portion of the return is 2 + 1.5 + 0.5 = 4.
2
Add the continuation estimate
Because the episode has not terminated at the boundary, include the later value contribution of 3.
3
Form G
The resulting target is G = 4 + 3 = 7.

Result

The n-step return used for Sτ is G = 7.

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

Definition

After G has been calculated, the tabular update is V(Sτ) ← V(Sτ) + α[G − V(Sτ)]. The step size α lies in the interval (0, 1], so the update moves the current estimate partway toward G rather than replacing it directly.

Worked example

Moving toward the return

Suppose V(Sτ) = 4, the calculated return is G = 10, and α = 0.5.

1
Find the difference
G − V(Sτ) = 10 − 4 = 6.
2
Scale the difference
α[G − V(Sτ)] = 0.5 × 6 = 3.
3
Update the estimate
V(Sτ) becomes 4 + 3 = 7.

Result

The updated value estimate is V(Sτ) = 7, not G = 10.

Key point

The update changes the value associated with Sτ. It does not directly replace that value with G; α controls how much of the difference is applied.

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.

What happens at each time step from observing a transition through computing G, updating V(Sτ), and finishing after termination?

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

Part of the method	Tabular n-step TD	Semi-gradient n-step TD
Experience structure	Uses several steps of episode experience	Uses the same multi-step experience structure
Target	Uses an n-step return G	Uses a generalized n-step return
Value representation	Uses tabular state values	Uses a function-approximation value estimate
Conceptual relationship	Base method	Natural function-approximation extension

The semi-gradient method preserves the n-step structure while generalizing the return for 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

Common mistake
Updating a value when τ is negative.
What it looks like
The procedure reaches the update statement before the earlier state has become eligible.
Why it fails
A negative τ refers to an earlier index that is not yet available for the algorithm's update scheme.
Do this instead
Check the update condition and proceed only when τ is eligible.
Common mistake
Never updating when τ is nonnegative.
What it looks like
The implementation calculates τ but places the return calculation or update outside the reachable branch.
Why it fails
An eligible state has been identified, but control flow prevents its return from being calculated or its value from being changed.
Do this instead
Trace the condition around τ, the return calculation, and the update statement.
Common mistake
Bootstrapping after the episode has terminated.
What it looks like
The return includes V(Sτ+n) even though termination occurred before the n-step boundary.
Why it fails
The return should stop at termination and omit the continuation value beyond the terminal point.
Do this instead
Use the later value estimate only when the episode continues to the n-step boundary.
Common mistake
Treating the return equation as the whole algorithm.
What it looks like
The implementation calculates G but does not manage T, τ, or the sequence of pending updates.
Why it fails
The equation defines the target, while the complete procedure determines when that target can be used.
Do this instead
Check both target construction and the surrounding time and termination control flow.
Common mistake
Replacing V(Sτ) directly with G.
What it looks like
```
The update assigns V(Sτ) = G regardless of α.
```
Why it fails
The tabular update moves the estimate by α[G − V(Sτ)], using a fraction controlled by the step size.
Do this instead
Apply the full update expression and verify that α is in (0, 1].

Practice Check

EASY

An implementation has collected enough experience for an earlier state Sτ. The episode has not terminated at the n-step boundary, and the return calculation is complete. Explain which value is updated, what target it moves toward, and why the later value estimate is included.

Hints

The time index in the update is τ, not the current time index.
The target is the n-step return G.
The later value estimate is included because termination has not occurred at the boundary.

Your attempt (not saved)

MEDIUM

A terminal transition occurs before the n-step boundary. List the two changes this causes in the return and in the continuing control flow.