n-Step TD

Imagine learning a route through a maze: updating after every step is quick but short-sighted, while waiting until the exit gives a complete answer but delays learning. n-Step TD sits between those choices. It learns from several real rewards in a row, then uses its current value estimate to fill in the rest of the future.

How the update works
For a state visited at time t, n-step TD waits for n transitions. Its target is the discounted sum of the next n rewards, plus a bootstrapped estimate of the state reached after those transitions:

Gₜ:t+n = Rₜ₊₁ + γRₜ₊₂ + ... + γⁿ⁻¹Rₜ₊ₙ + γⁿ V(Sₜ₊ₙ)

V(Sₜ) ← V(Sₜ) + α [Gₜ:t+n − V(Sₜ)]

Here, n controls the trade-off:

• n = 1 gives ordinary TD(0): immediate updates, but heavily reliant on current—and possibly wrong—value estimates.
• A larger n incorporates more actual rewards before bootstrapping, so credit travels farther along a trajectory.
• If n reaches the episode’s end, the method becomes a Monte Carlo update: no bootstrap, but a delayed and noisier full return.

Why this matters in practice
In a sparse-reward task such as a Gymnasium maze, a goal reward can influence states several moves away much sooner than with one-step TD. Yet n-step TD still updates before an episode finishes, unlike Monte Carlo learning. The cost is that longer returns have more randomness: an unlucky sequence of rewards can move an estimate in the wrong direction, while short returns can perpetuate a bad estimate through repeated bootstrapping. Deep-RL algorithms use the same idea: n-step DQN stores short reward sequences in replay data so useful reward information reaches earlier decisions faster. TD(λ) extends this idea by blending many n-step returns rather than choosing one fixed horizon.