// the one-minute version
n-step methods form a continuum between one-step TD and Monte Carlo. The n-step return contains n observed rewards, then bootstraps from V(St+n). Larger n moves delayed information farther per update but increases delay and variance. n-step Sarsa extends the idea to on-policy control. Off-policy n-step learning corrects sampled actions with products of importance ratios; control variates reduce variance. Tree Backup uses target-policy expectations for branches not sampled and needs no importance ratios. Q(σ) unifies Sarsa and Tree Backup by mixing sampling (σ=1) with expectation (σ=0) at each step.
Asha's TD learner notices a delivery reward, but the useful news crawls backward one junction per repeated trip. Monte Carlo can send the full outcome to every earlier state, yet waits for termination and inherits the randomness of the whole route. She needs a dial rather than a binary choice. An n-step return observes several real transitions, then asks the current value function to summarize everything beyond them.
01 Deriving the n-step return
One-step TD uses Rt+1+γV(St+1). Two-step TD substitutes one more reward before bootstrapping. In general:
If termination occurs before t+n, omit the bootstrap and stop at the terminal reward. The update is V(St)←V+α[Gt:t+n−V]. With n=1 it is TD(0); when n spans the remaining episode it is Monte Carlo.
Fig 1 — n controls how much sampled reality appears before the value estimate resumes the prediction.
02 Bias, variance, delay, and speed of credit
Small n bootstraps heavily: targets arrive quickly and usually have lower variance, but inherit current value bias. Large n uses more actual rewards and moves credit farther, but waits longer and accumulates environmental randomness.
In the 19-state random walk, intermediate n often reaches low prediction error faster than either extreme. But n and α interact: a long return can require a smaller step size. There is no universally optimal n.
A four-step reward at Asha's delivery point can update a junction four transitions earlier after one trip. One-step TD needs repeated propagation; a 40-step target may include irrelevant traffic noise from much later.
03 Online implementation and the τ index
An n-step method must wait n transitions before updating time τ=t−n+1. Store the recent states, actions, and rewards in circular arrays. After reaching terminal time T, continue the loop long enough to flush pending updates through τ=T−1.
Most implementation bugs are indexing bugs: Rt+1 follows At; the reward sum runs from τ+1 through min(τ+n,T); bootstrapping occurs only if τ+n<T. Write a hand-worked three-step episode before optimizing code.
04 n-step Sarsa
n-step Sarsa samples the next n−1 actions under the policy and bootstraps from the nth state–action pair. Update Q(St,At) toward this return, then keep the policy ε-greedy with respect to Q.
The method remains on-policy because both the sampled middle actions and final bootstrap action come from the same behavior being evaluated.
05 Off-policy n-step correction
If behavior b differs from target π, the sampled actions between the updated pair and bootstrap boundary need correction:
The ratio begins at t+1 because the update is already conditioned on At. Products create the same variance problem as off-policy MC, though over n−1 rather than the entire episode. If π assigns zero to one sampled action, the update becomes zero.
06 Per-decision control variates
Instead of multiplying one ratio onto the full return, derive the correction recursively at each decision. Add the target-policy expectation as a control variate so that sampling error is corrected toward a known conditional mean.
The pattern is “sampled contribution plus expected correction.” When the sampled action is surprising under π, its ratio adjusts the difference from the expected value rather than multiplying every unrelated term. This can reduce variance while preserving the target expectation.
07 Tree Backup without importance sampling
Tree Backup follows the sampled action branch but includes expected contributions of actions not taken. At each state, non-sampled actions contribute π(a|s)Q(s,a); the sampled branch continues recursively weighted by its target probability.
Because it constructs a target-policy expectation directly, it needs no behavior probabilities or importance ratios. This is attractive when behavior is unknown, but it requires computing values for all actions at each backed-up state.
08 Q(σ): one equation connecting the family
Q(σ) chooses at each step how much to sample the next action. σ=1 gives Sarsa-like sampling; σ=0 gives Tree-Backup-style expectation. Intermediate σ blends them, and σ may vary by time or state.
This makes the central design axis explicit: sampled backups are cheap and can adapt to the exact trajectory but have action-selection variance; expected backups cost more and reduce variance. The best mixture can change as estimates improve.
common catches & gotchas
- Assuming larger n is always better — It moves credit farther but raises delay, storage, and variance.
- Forgetting the terminal flush — Pending pre-terminal states still need updates after T is observed.
- Including Aₜ in the importance product — The update is conditioned on the current action; correction begins with later sampled actions.
- Calling Tree Backup model-based — It expects over actions using Q and π, not over unknown environment transitions.
- Comparing n without retuning α — Longer returns usually change the stable step-size range.
- Ignoring action-set cost — Expected methods may be impractical when summing over a huge action space.
09 Questions master's students should answer
Does n-step TD bootstrap?
Yes, unless the episode ends before the boundary. It observes n rewards and then uses V(Sₜ₊ₙ) or Q(Sₜ₊ₙ,Aₜ₊ₙ).
Why can intermediate n learn faster?
It propagates reward multiple steps per update while retaining some low-variance bootstrapping. The best balance depends on task stochasticity, representation, and α.
Why does Tree Backup avoid importance sampling?
It builds the target-policy expectation explicitly over unchosen actions and weights the sampled continuation by target probability, so it does not need behavior-to-target likelihood ratios.
What does σ control?
Whether each next-action component is sampled (1), expected (0), or mixed. It controls action-sampling variance, not environment-transition variance.
How much memory is required?
O(n) recent states, actions, and rewards with a circular buffer. Eligibility traces later reproduce mixtures of many n-step returns with a different backward-view memory.
10 Key takeaways
- n-step returns interpolate between one-step TD and Monte Carlo.
- Increasing n reduces bootstrap dependence but raises sampling variance and update delay.
- n-step Sarsa extends sampled multi-step targets to on-policy action-value control.
- Off-policy sampled paths require target/behavior correction and coverage.
- Per-decision control variates correct deviations around target expectations.
- Tree Backup performs multi-step expected action backups without importance sampling.
- Q(σ) exposes sampling versus expectation as a continuous design choice.
targets
off-policy
implementation
11 Wrapping up and source trail
Asha can now choose how far each real experience carries credit. Chapter 8, planning and learning with tabular methods, asks how to multiply the value of scarce real experience by learning a model and generating simulated transitions.
These are independent companion notes written in original language. Primary references: the authors' book page, the author-hosted open-access draft, the MIT Press edition page, and the official contents.