n-Step Bootstrapping: Off-Policy Methods

This builds on n-Step Bootstrapping, which developed the $n$-step return, $n$-step TD prediction, and $n$-step Sarsa for control — all on-policy. Here the target and behavior policies come apart, and the question is how to reuse one policy's data to learn about another over a multi-step window.

Off-policy learning with importance sampling

Off-policy learning estimates values for a target policy $\pi$ while generating data from a different behavior policy $b$ — typically $\pi$ is greedy and $b$ is more exploratory, say $\epsilon$-greedy. To reuse $b$'s data as if it came from $\pi$, we reweight it by the relative probability of the actions actually taken under the two policies. Since an $n$-step return is built from exactly $n$ actions, only those $n$ probabilities matter.¹ The importance-sampling ratio over steps $t$ through $h$ is

A simple off-policy $n$-step TD update just scales the whole $n$-step error by the ratio spanning the $n$ actions of the return:

The logic is direct. If some action in the window would never be taken under $\pi$ (its $\pi$-probability is $0$), the whole $n$-step return gets weight $0$ and is ignored — it is not data $\pi$ would ever have produced. If an action is far likelier under $\pi$ than under $b$, its return is up-weighted, because that action is characteristic of $\pi$ yet rare in the data. When $\pi =b$ (the on-policy case) every ratio is $1$ and the update collapses back to plain $n$-step TD, so this generalizes rather than replaces the earlier rule.

For the action-value version, the ratio starts and ends one step later. Because $n$-step Sarsa updates a state–action pair, the first action $A_t$ is the one being learned about — it is a given, not something to correct for — so importance sampling applies only to the $n-1$ actions that follow:

for $0\le t<T$. We do not care how likely we were to select $A_t$; having selected it, we want to learn fully from whatever followed, correcting only the subsequent actions.

The importance-sampling ratios are what make off-policy training statistically sound, but they are also its weakness. A product of $n$ ratios can swing widely, inflating the variance of the update and forcing a small step size — which is why off-policy learning is generally slower than on-policy. This variance is the motivation for the final method, which achieves off-policy learning with no importance-sampling ratios at all.

The ratio product on real numbers

The variance problem is easiest to see by multiplying an actual product out. Let the target $\pi$ be greedy and the behavior $b$ be $\epsilon$-greedy with $\epsilon =0.1$ over four actions, so on any step where $b$ takes $\pi$'s greedy action, $\pi$ assigns probability $1$ and $b$ assigns $1-\epsilon +\epsilon /4=0.925$, giving a per-step ratio of

For a $4$-step state-value update whose window happens to follow greedy actions throughout, the ratio is ${\rho }_{t:t+3}=1.081^4\approx 1.366$ — a mild up-weighting, since greedy actions are only slightly rarer under $b$ than under $\pi$. But suppose at just one of those four steps the behavior took a non-greedy action, which $\pi$ gives probability $0$. Then that factor is $0/0.025=0$, the whole product collapses to $0$, and the entire $4$-step return is thrown away. The update fires only when every one of the $n$ actions in the window was greedy; the longer the window, the rarer that is. With $\epsilon =0.1$ and four actions, the chance all $4$ steps are greedy is $0.925^4\approx 0.73$, so more than a quarter of $4$-step windows are discarded outright — and at $n=8$, nearly half. Longer lookahead spends more of its data on windows that end up weighted $0$, and concentrates its learning on the few that remain, which is precisely the variance that forces a smaller $\alpha$.

For the action-value version the ratio runs from $t+1$, not $t$: having already chosen $A_t$, we keep its return whatever it was, and correct only the $n-1$ following actions. So ${\rho }_{t+1:t+4}$ over three following greedy steps is $1.081^3\approx 1.263$ — the first action contributes no factor, which is one reason $n$-step Sarsa tolerates off-policy data slightly better than the state-value update does.

The tree-backup algorithm

Is off-policy learning possible without importance sampling? For the one-step case yes — Expected Sarsa and Q-learning already do it, by taking an expectation over next actions instead of sampling one. The $n$-step tree-backup algorithm is the multi-step generalization.

The name comes from its backup diagram. Down the central spine hang the sampled states, rewards, and actions actually experienced. But off each state, to the sides, dangle the actions that were not selected. We have no sampled data for those, so we bootstrap from their current estimated action values and fold them into the target. The update is thus from the entire tree of estimated action values — the sampled spine plus every unselected action hanging off it — not just from the states along the spine.

The target is built from action values only, so no ratios appear. The one-step tree-backup return equals the Expected Sarsa target,

and the general return is defined recursively: at each level the sampled action passes its $\pi$-weight down to the return of the subtree below it, while every unselected action contributes its own bootstrapped value,

for $n\ge 2$. Read the two terms: the sum handles the unselected actions $a\ne A_{t+1}$, each weighted by $\pi (a\mid S_{t+1})$ and evaluated at its current estimate; the last term recurses into the next level, carrying the weight $\pi (A_{t+1}\mid S_{t+1})$ of the action that was taken. Unfolding the recursion, each leaf deep in the tree is weighted by the product of the target-policy probabilities of the sampled actions on the path down to it. The update rule is the usual $n$-step Sarsa one, $Q_{t+n}(S_t,A_t)\leftarrow Q_{t+n-1}(S_t,A_t)+\alpha [G_{t:t+n}-Q_{t+n-1}(S_t,A_t)]$.

Tree backup and $n$-step Sarsa sit at two poles of a broader design space — sample every action (Sarsa, with importance-sampling corrections off-policy) or take an expectation over every action (tree backup, no corrections). The next section builds the algorithm that spans the whole space between them.

The unifying algorithm: n-step Q(σ)

Three action-value methods now sit side by side, and they differ only in how each transition down the spine is treated. $n$-step Sarsa samples every action: each step follows the one action actually taken. The tree-backup algorithm samples none: at every step it branches over all actions and takes an expectation. $n$-step Expected Sarsa samples every step except the last, where it branches. Reading them this way, the choice is made anew at each step — sample this transition, or take the expectation over it — and the three algorithms are just three fixed patterns of that choice.²

Let a per-step switch ${\sigma }_t\in \{0,1\}$ record it: ${\sigma }_t=1$ means sample the action at step $t$ (as in Sarsa), ${\sigma }_t=0$ means take the expectation over actions (as in tree backup). Nothing forbids mixing them within a single backup, or even letting ${\sigma }_t\in [0,1]$ vary continuously as a function of the state or action. The algorithm that carries this switch is $n$-step Q($\sigma$), and it contains all three predecessors as the constant or almost-constant settings of $\sigma$.

The backup diagram shows the unification. Where Sarsa's spine is all sampled transitions and tree backup's is all branched ones, Q($\sigma$) mixes them: each state-to-action transition is either sampled or fully branched according to $\sigma$ at that level.

The Q(σ) return

The formula below has one moving part: a per-step coefficient that interpolates between the sampled action's correction and the expectation over all actions. Everything else is the ordinary $n$-step return. The single return that yields all four cases comes from writing the tree-backup return with a control variate and then sliding between two forms. Recall the tree-backup return branches at every step, weighting the sampled action by $\pi (A_{t+1}\mid S_{t+1})$; the importance-sampling Sarsa return instead reweights the same sampled action by the ratio ${\rho }_{t+1}=\pi (A_{t+1}\mid S_{t+1})/b(A_{t+1}\mid S_{t+1})$. Q($\sigma$) blends the two weights linearly. Writing the horizon as $h=t+n$ and the expected approximate value as ${\bar{V}}_{h-1}(S_{t+1})={\sum }_a\pi (a\mid S_{t+1})Q_{h-1}(S_{t+1},a)$,

for $t<h\le T$. The recursion terminates with $G_{h:h}\doteq Q_{h-1}(S_h,A_h)$ when $h<T$, and with $G_{T-1:T}\doteq R_T$ when $h=T$. The middle factor distinguishes the cases: at ${\sigma }_{t+1}=1$ it is the importance-sampling ratio ${\rho }_{t+1}$, so the bracket becomes the sampled-action correction of $n$-step Sarsa; at ${\sigma }_{t+1}=0$ it is the target probability $\pi (A_{t+1}\mid S_{t+1})$, so the bracket becomes the tree-backup weight. In both cases the trailing $\gamma {\bar{V}}_{h-1}(S_{t+1})$ supplies the expectation over all actions, and the bracket only corrects it toward the sampled action to the degree set by $\sigma$.

Reading the special cases off this one line:

• $\sigma \equiv 1$ (Sarsa). Every factor is ${\rho }_{t+1}$; the expected value and the $-Q_{h-1}(S_{t+1},A_{t+1})$ term combine into the ordinary sampled bootstrap, reweighted for off-policy by the importance ratios.
• $\sigma \equiv 0$ (tree backup). Every factor is $\pi (A_{t+1}\mid S_{t+1})$, and the return is the recursive tree-backup return of the previous section — no ratios anywhere.
• ${\sigma }_t=0$ only at the last step (Expected Sarsa). The final transition branches into $\bar{V}$; the earlier steps sample. On-policy this is $n$-step Expected Sarsa.

The algorithm

Because Q($\sigma$) uses the general off-policy $n$-step Sarsa update, it needs the behavior policy $b$, the importance ratios ${\rho }_k$, and the per-step ${\sigma }_k$ stored alongside the states, actions, and rewards. As with every method in this chapter, the update for time $\tau$ fires only at wall-clock time $\tau +n$, and all storage can be indexed modulo $n+1$. The return is built by the recursion above, unrolled from the horizon back to $\tau +1$.

Q($\sigma$) unifies the chapter: $n$-step Sarsa, $n$-step tree backup, and $n$-step Expected Sarsa all fall out of one return by the setting of a single switch. The practical hope is that an intermediate $\sigma$ — mostly sampling, but branching where the target and behavior policies diverge — could keep tree backup's low variance where it matters while retaining Sarsa's cheap, sample-based updates elsewhere.

n-step returns in deep reinforcement learning

The integer $n$ became a standard hyperparameter in deep reinforcement learning, where its bias–variance tradeoff is tuned as routinely as a learning rate. Every system below uses a multi-step return in place of a one-step target for exactly the reason the random walk gave: an intermediate $n$ propagates reward faster than one-step bootstrapping without inheriting Monte Carlo's variance.

Multi-step returns in value-based and actor–critic deep RL. The asynchronous actor–critic A3C (Mnih et al., 2016, ICML) computes an $n$-step return (up to a rollout length, typically $n=5$ or $20$) as the target for both its value and policy updates, so a reward reaches the states that led to it within a single rollout rather than trickling back one bootstrap at a time. Rainbow (Hessel et al., 2018, AAAI), the study that combined the strongest DQN improvements, found multi-step returns (an $n$-step target inside Q-learning, usually $n=3$) to be one of the components contributing most to its gains — a direct transplant of $n$-step Sarsa's target into a deep off-policy learner. R2D2 (Kapturowski et al., 2019, ICLR) runs an $n$-step ($n=5$) recurrent Q-learner over stored sequences and set records on the Atari benchmark. In each case the $n$ is the same $n$: how many real rewards to accumulate before bootstrapping from the value estimate.

Interpolating over all $n$, and safe off-policy corrections. The tree-backup and importance-sampling machinery of this chapter also has deep-RL descendants. Generalized advantage estimation (Schulman et al., 2016, ICLR) does not commit to a single $n$ at all: it forms an exponentially-weighted average of every $n$-step return with a parameter $\lambda$, so $\lambda =0$ recovers the one-step estimate and $\lambda =1$ the Monte Carlo one — the eligibility-trace idea the next lesson builds, applied to the advantage used by policy-gradient methods like PPO. On the off-policy side, the variance of the $n$-step ratio product described above is controlled in practice exactly as tree backup suggested — by replacing raw ratios with bounded corrections. Retrace($\lambda$) (Munos et al., 2016, NeurIPS) clips each per-step ratio at $1$, yielding a multi-step off-policy return that is low-variance and provably convergent, and the V-trace target of IMPALA (Espeholt et al., 2018, ICML) truncates the ratios to correct for the lag between distributed actors and the learner. Sutton and Barto's own tree-backup construction is the tabular ancestor of these: an off-policy multi-step return whose correction is an expectation over actions, so its variance stays controlled where a product of ratios would explode.³

What n unified

The whole chapter turns on one integer. Set $n=1$ and every method here is its one-step ancestor — TD(0), Sarsa(0), Expected Sarsa, Q-learning. Let $n$ grow and the same equations reach further into the future, trading the bias of a raw bootstrap for the variance of longer reward sequences, until at $n=\infty$ they become Monte Carlo. The random walk showed that an intermediate $n$ usually performs best, and the tree-backup construction showed that even the off-policy machinery fits the same $n$-step frame.

One question remains for the next lesson: all of these methods commit to a fixed $n$ chosen in advance. The eligibility-trace view shows how to average over all $n$ at once, smoothly and with bounded memory — but this lesson already laid the conceptual groundwork: a return that looks $n$ steps ahead and then bootstraps, with one-step TD and Monte Carlo as its two extremes.