n-Step TD Algorithm and Error Reduction Property

The algorithm updates an earlier state after enough later experience has become available. The state being updated is identified by τ, not simply by the most recently observed time index.

Programming

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.

Key point

The algorithm updates an earlier state after enough later experience has become available. The state being updated is identified by τ, not simply by the most recently observed time index.

Which earlier state Sτ is being updated after the agent has observed n steps of experience?

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.

How do the observed rewards from time τ+1 through τ+n combine with a later value estimate at the endpoint?

Constructing G

Definition

The n-step return G is the target used for the update. It combines the discounted rewards observed from the state at time τ through the n-step boundary. If that boundary occurs before the episode terminates, G also includes a later value estimate. If the episode terminates before the boundary, the continuation value term is absent.

Rule

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.

What happens in order as experience is collected, the n-step return is formed, and V(Sτ) is updated?

Applying the Value Update

Worked example

Moving an Estimate Toward G

Suppose the current estimate is V(Sτ) = 6, the constructed n-step return is G = 10, and the step size is α = 0.5.

1
Find the difference
The difference between the target and the current estimate is G - V(Sτ) = 10 - 6 = 4.
2
Scale the difference
The step size uses half of that difference: α[G - V(Sτ)] = 0.5 × 4 = 2.
3
Apply the update
Add the scaled difference to the current estimate: V(Sτ) becomes 6 + 2 = 8.

Result

The estimate moves from 6 to 8. It moves toward G rather than replacing the old estimate with G.

Formula

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.

How does V(Sτ) change when the n-step return G is above or below the current estimate?

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.

How does the update reduce the gap between the current value estimate and the n-step target?

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.

When an episode terminates before n steps, which terms disappear, and under what condition is the update for Sτ performed?

Implementation Mistakes

Common mistake
Updating when τ is negative
What it looks like
The control flow reaches the value update even though the calculated update index has not become nonnegative.
Why it fails
The algorithm is attempting to update an earlier state that is not yet eligible in its indexing scheme.
Do this instead
Check the eligibility condition before calculating G and updating V(Sτ).
Common mistake
Never updating when τ is nonnegative
What it looks like
The implementation calculates a valid nonnegative τ but skips the update on every pass.
Why it fails
The problem is likely in the condition surrounding the update or in the calculation of τ.
Do this instead
Trace τ and the conditional branch that should lead to return calculation and value updating.
Common mistake
Adding a continuation value after termination
What it looks like
The episode ends before the n-step boundary, but the implementation still adds a later value estimate.
Why it fails
A continuation term is used when the n-step boundary occurs before termination; it is absent when the episode terminates first.
Do this instead
Use the terminal time T to limit the reward sum and omit the continuation value term after termination.
Common mistake
Replacing the estimate with G
What it looks like
```
The implementation assigns V(Sτ) directly to G.
```
Why it fails
The algorithm moves the estimate toward G by the amount α[G - V(Sτ)] rather than replacing the old estimate directly.
Do this instead
```
Apply V(Sτ) ← V(Sτ) + α[G - V(Sτ)].
```

Practice Check

MEDIUM

An implementation has collected enough experience to identify a nonnegative τ. The episode terminated before the n-step boundary. Describe which information belongs in G, state whether a continuation value estimate is included, and write the update that changes V(Sτ).

Hints

Use the terminal time T to decide whether the continuation term is allowed.
The observed discounted rewards remain part of the return.
The update uses the difference between G and the current estimate.

Your attempt (not saved)

What do you think happens?

If G is below the current value estimate and α is in (0, 1], does the update increase or decrease V(Sτ)?

Increase
Decrease
Leave it unchanged in every case

Reveal answer

Answer:

Decrease

When G is below V(Sτ), the difference G - V(Sτ) is negative. Multiplying that difference by α and adding it to the current estimate moves V(Sτ) downward toward G.

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.

At a glance

The algorithm delays updating an earlier state until several steps of experience are available.
The index τ determines which state estimate receives the update.
The return G contains discounted rewards and may contain a later value estimate, but termination removes the continuation term.
The update V(Sτ) ← V(Sτ) + α[G - V(Sτ)] moves the estimate toward the n-step target.
Debugging should begin by checking τ, the terminal time T, and whether the continuation term is used only when allowed.

Related concepts

More concepts starting with N