n-Step Bootstrapping

The differential n-step return is G(n)t = R̄ + V̄(S(t+n)) − V̄(S(t)).

Programming

From Current State to Later State

n-step bootstrapping uses information from a later point in the process to construct a return for the state at time t. When function approximation is used, the return is written in differential form. Instead of treating the target as an isolated absolute quantity, the expression combines an estimate of average reward with the change between two estimated state values.

How do the starting state, the average-reward estimate, and the state n steps later connect across the n-step window?

Key point

The role of n is to determine which later state appears in the expression. For example, when n = 3, the later state is S(t+3), and its estimate is V̄(S(t+3)).

The Differential Return

Formula

Read the expression from left to right. Begin with R̄, an estimate of η(π), the average reward associated with the policy. Then add the estimated value of the state n steps later, V̄(S(t+n)). Finally, subtract the estimated value of the starting state, V̄(S(t)). The result is the differential n-step return G(n)t.

What does each term in G(n)t = R̄ + V̄(S(t+n)) − V̄(S(t)) represent, and how do the terms combine?

Worked example

Substituting a Three-Step Later State

Write the differential return when n = 3.

1
Identify the later state
Replacing n with 3 makes the later state S(t+3).
2
Preserve the structure
The average-reward estimate is added, the later-state estimate is added, and the starting-state estimate is subtracted.
3
Write the expression
The return becomes G(3)t = R̄ + V̄(S(t+3)) − V̄(S(t)).

Result

G(3)t = R̄ + V̄(S(t+3)) − V̄(S(t))

Why Values Appear as a Difference

With function approximation, the return is expressed in differential form. The value contribution is therefore a change from the starting state's estimate to the later state's estimate: V̄(S(t+n)) − V̄(S(t)). This is the form specified for the n-step return in the source material; it combines the average-reward estimate with the difference between two estimated state values.

Why does the function-approximation form use a change between two estimated values?

When the Expression Applies

The displayed differential n-step return applies when n is at least 1 and t+n is less than T. The second condition means that the later state used in the expression occurs before time T. Under these conditions, the expression uses S(t+n) and its estimated value.

What condition makes the displayed differential n-step return applicable?

From Return to TD Error

The n-step return and the n-step TD error are related but distinct quantities. The return is formed first using G(n)t = R̄ + V̄(S(t+n)) − V̄(S(t)). The n-step TD error is then defined using that differential return and the current value estimate. In other words, G(n)t supplies the target used when determining the error; it is not itself the error.

How is the n-step TD error obtained after the differential n-step return has been formed?

Key point

Use this order: first form the differential n-step return, then use that return to define the n-step TD error. Mixing the two names hides the learning sequence.

Common Mistakes

Common mistake
Treating G(n)t as the n-step TD error.
What it looks like
Calling R̄ + V̄(S(t+n)) − V̄(S(t)) the error before forming the error quantity.
Why it fails
The return and the TD error are related but are not the same named quantity.
Do this instead
Form G(n)t first, then define the n-step TD error using that return.
Common mistake
Using the wrong later state.
What it looks like
Writing V̄(S(t+3)) when the chosen step count is n = 2.
Why it fails
The later state must be S(t+n), so changing n changes which later estimate appears.
Do this instead
Substitute the selected n carefully before writing the expression.
Common mistake
Dropping the starting-state term.
What it looks like
```
Writing G(n)t = R̄ + V̄(S(t+n)).
```
Why it fails
The differential form includes both estimated state values, with the starting estimate subtracted.
Do this instead
```
Keep the complete structure R̄ + V̄(S(t+n)) − V̄(S(t)).
```
Common mistake
Ignoring the time condition.
What it looks like
Applying the displayed expression without checking whether n ≥ 1 and t+n < T.
Why it fails
Those are the stated conditions for the displayed formula.
Do this instead
Check both inequalities before using the expression.

Practice Check

EASY

Suppose the step count is n = 4. Write the differential n-step return, identify the starting-state estimate, identify the later-state estimate, and state the condition that must hold for the displayed form to apply.

Hints

Replace n with 4 in S(t+n).
The starting-state estimate is the term that is subtracted.
State both parts of the condition: one involving n and one involving t+n.

Your attempt (not saved)

Worked example

Practice Check Solution

Write the differential return for n = 4 and identify its components.

1
Substitute the step count
The later state becomes S(t+4).
2
Keep the differential structure
Add R̄ and V̄(S(t+4)), then subtract V̄(S(t)).
3
Check applicability
The displayed form requires n ≥ 1 and t+n < T. With n = 4, this requires 4 ≥ 1 and t+4 < T.

Result

G(4)t = R̄ + V̄(S(t+4)) − V̄(S(t)); the starting-state estimate is V̄(S(t)), and the later-state estimate is V̄(S(t+4)).

Key Takeaways

1
With function approximation, the n-step return is written in differential form.
2
The differential return is G(n)t = R̄ + V̄(S(t+n)) − V̄(S(t)).
3
R̄ estimates η(π); V̄(S(t+n)) is the later-state estimate; and V̄(S(t)) is the starting-state estimate that is subtracted.
4
The displayed expression applies when n ≥ 1 and t+n < T.
5
The n-step TD error is defined using the differential n-step return, so form the return before forming the error.

At a glance

The differential n-step return combines an average-reward estimate with a difference between later and starting state-value estimates.
The step count n determines which later state appears in the return.
The displayed formula requires n ≥ 1 and t+n < T.
The n-step TD error is defined after the differential n-step return has been constructed.

Related concepts

More concepts starting with N