n-Step Bootstrapping

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.

The Differential Return

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

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.

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.

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.

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.

Common Mistakes

• Treating G(n)t as the n-step TD error.

  The return and the TD error are related but are not the same named quantity.

  Fix: Form G(n)t first, then define the n-step TD error using that return.

• Using the wrong later state.

  The later state must be S(t+n), so changing n changes which later estimate appears.

  Fix: Substitute the selected n carefully before writing the expression.

• Dropping the starting-state term.

  The differential form includes both estimated state values, with the starting estimate subtracted.

  Fix: Keep the complete structure R̄ + V̄(S(t+n)) − V̄(S(t)).

• Ignoring the time condition.

  Those are the stated conditions for the displayed formula.

  Fix: Check both inequalities before using the expression.

Practice Check

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.