--- title: "n-Step Bootstrapping: Off-Policy Methods" module: Tabular Solution Methods moduleNumber: 2 lessonNumber: 8 order: 208 summary: > Taking the n-step family off-policy raises the same importance-sampling questions Monte Carlo did, now over a window of exactly n actions. We reweight n-step returns by the policy ratio, watch the ratio product inflate variance on real numbers, then build the tree-backup algorithm that learns off-policy with no ratios at all — and finally n-step Q(sigma), one algorithm whose per-step switch recovers Sarsa, tree backup, and Expected Sarsa as special cases. topics: [Tabular Methods] sources: - book: Sutton & Barto ref: "§7.3 n-step Off-policy Learning; §7.5 Off-policy Learning Without Importance Sampling: The n-step Tree Backup Algorithm" - book: Sutton & Barto ref: "§7.6 A Unifying Algorithm: n-step Q(σ)" --- This builds on [n-Step Bootstrapping](/reinforcement-learning/tabular-methods/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](/reinforcement-learning/tabular-methods/td-control-sarsa-and-q-learning) 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 $\varepsilon$-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.[^sb-offpolicy-nstep] The **importance-sampling ratio** over steps $t$ through $h$ is $$ \rho_{t:h} \;\doteq\; \prod_{k=t}^{\min(h,\,T-1)} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}. $$ 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: $$ V_{t+n}(S_t) \;\doteq\; V_{t+n}(S_t) + \alpha\, \rho_{t:t+n-1}\,\big[\, G_{t:t+n} - V_{t+n-1}(S_t) \,\big], \qquad 0 \le t < T. $$ 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_: $$ Q_{t+n}(S_t, A_t) \;\doteq\; Q_{t+n-1}(S_t, A_t) + \alpha\, \rho_{t+1:t+n}\,\big[\, G_{t:t+n} - Q_{t+n-1}(S_t, A_t) \,\big], $$ 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. > **Definition (Off-policy $n$-step return via importance sampling).** Weight the > ordinary $n$-step error by $\rho_{t:t+n-1}$ (for state values) or > $\rho_{t+1:t+n}$ (for action values), the product of $\pi/b$ over the actions > the return spans. On-policy is the special case $\rho \equiv 1$. The cost of > the reweighting is variance: a single large ratio can dominate an update. 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 $\varepsilon$-greedy with $\varepsilon = 0.1$ over four actions, so on any step where $b$ takes $\pi$'s greedy action, $\pi$ assigns probability $1$ and $b$ assigns $1 - \varepsilon + \varepsilon/4 = 0.925$, giving a per-step ratio of $$ \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)} = \frac{1}{0.925} \approx 1.081. $$ 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 $\varepsilon = 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. $$ % caption: The 3-step tree-backup diagram. The central spine (states $S_{t+1}, % S_{t+2}, S_{t+3}$ and sampled actions $A_{t+1}, A_{t+2}$) is the experienced % trajectory; the small dangling dots are the unselected actions at each state. % Each unselected leaf contributes its estimated value, weighted by its % probability under $\pi$; the sampled action passes the weight $\pi(A\mid S)$ % down to the subtree below it. No importance-sampling ratios appear. \begin{tikzpicture}[>=stealth, font=\footnotesize, st/.style={circle, draw, fill=white, minimum size=4mm, inner sep=0pt}, ac/.style={circle, draw, fill=black, minimum size=1.8mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % root state-action \node[ac, label={[font=\scriptsize]above:(St At)}] (r) at (0,4.4) {}; % S_{t+1} \node[st] (s1) at (0,3.4) {}; \draw[black] (r) -- (s1); \node[anchor=east, font=\scriptsize] at (-0.12,3.9) {R}; % actions off S_{t+1}: sampled A_{t+1} straight down, others dangle \node[ac] (u1a) at (-0.9,2.9) {}; \node[ac] (u1b) at (0.9,2.9) {}; \draw[black] (s1) -- (u1a); \draw[black] (s1) -- (u1b); \node[ac] (a1) at (0,2.7) {}; \draw[acc, thick] (s1) -- (a1); \node[acc, anchor=west, font=\scriptsize] at (0.1,2.75) {At+1}; % S_{t+2} \node[st] (s2) at (0,1.9) {}; \draw[black] (a1) -- (s2); \node[anchor=east, font=\scriptsize] at (-0.12,2.35) {R}; \node[ac] (u2a) at (-0.9,1.4) {}; \node[ac] (u2b) at (0.9,1.4) {}; \draw[black] (s2) -- (u2a); \draw[black] (s2) -- (u2b); \node[ac] (a2) at (0,1.2) {}; \draw[acc, thick] (s2) -- (a2); \node[acc, anchor=west, font=\scriptsize] at (0.1,1.25) {At+2}; % S_{t+3} \node[st] (s3) at (0,0.4) {}; \draw[black] (a2) -- (s3); \node[anchor=east, font=\scriptsize] at (-0.12,0.85) {R}; \node[ac] (u3a) at (-0.9,-0.1) {}; \node[ac] (u3b) at (0,-0.1) {}; \node[ac] (u3c) at (0.9,-0.1) {}; \draw[black] (s3) -- (u3a); \draw[black] (s3) -- (u3b); \draw[black] (s3) -- (u3c); \node[align=center, font=\scriptsize] at (2.5,2.0) {the 3-step\\tree-backup\\update}; \end{tikzpicture} $$ The target is built from action values only, so no ratios appear. The one-step tree-backup return equals the Expected Sarsa target, $$ G_{t:t+1} \;\doteq\; R_{t+1} + \gamma \sum_a \pi(a \mid S_{t+1})\, Q_t(S_{t+1}, a), $$ 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, $$ G_{t:t+n} \;\doteq\; R_{t+1} + \gamma \!\! \sum_{a \ne A_{t+1}} \!\! \pi(a \mid S_{t+1})\, Q_{t+n-1}(S_{t+1}, a) \;+\; \gamma\, \pi(A_{t+1} \mid S_{t+1})\, G_{t+1:t+n}, $$ 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) \gets Q_{t+n-1}(S_t, A_t) + \alpha\,[G_{t:t+n} - Q_{t+n-1}(S_t, A_t)]$. > **Algorithm ($n$-step tree backup).** Off-policy control with no > importance-sampling ratios. The target combines the sampled rewards along the > spine with the estimated values of every _unselected_ action at every visited > state, each weighted by its probability under $\pi$; the sampled action carries > its own $\pi$-weight into the deeper tree. Because the correction is an > expectation over actions rather than a reweighting of samples, its variance > stays controlled where importance sampling's grows. 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.[^sb-qsigma] 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$. > **Definition ($n$-step Q($\sigma$)).** A per-step degree of sampling > $\sigma_t \in [0,1]$ selects, transition by transition, between a sampled action > ($\sigma_t = 1$, the Sarsa update) and an expectation over actions > ($\sigma_t = 0$, the tree-backup update). Setting $\sigma_t \equiv 1$ recovers > $n$-step Sarsa, $\sigma_t \equiv 0$ recovers $n$-step tree backup, and > $\sigma_t = 1$ for every step but the last (where $\sigma = 0$) recovers $n$-step > Expected Sarsa. 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. $$ % caption: The four $n$-step action-value backups (4-step case). Sarsa samples % every transition ($\sigma{=}1$ throughout); tree backup branches every % transition ($\sigma{=}0$ throughout); Expected Sarsa samples all but the last, % which branches; Q($\sigma$) mixes per step. The small branches are the % expectation over unselected actions; a straight edge down is a sampled action. \begin{tikzpicture}[>=stealth, font=\footnotesize, st/.style={circle, draw, fill=white, minimum size=3.4mm, inner sep=0pt}, ac/.style={circle, draw, fill=black, minimum size=1.6mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} % ============ helper macro-like manual columns ============ % ---- column 1: Sarsa (all sample) ---- \def\cx{0} \node[ac] (s0) at (\cx,4.0) {}; \node[st] (s1) at (\cx,3.2) {}; \node[ac] (s2) at (\cx,2.4) {}; \node[st] (s3) at (\cx,1.6) {}; \node[ac] (s4) at (\cx,0.8) {}; \draw[black] (s0)--(s1)--(s2)--(s3)--(s4); \node[align=center, font=\scriptsize] at (\cx,4.7) {4-step\\Sarsa}; % ---- column 2: Tree backup (all branch) ---- \def\tx{2.2} \node[ac] (t0) at (\tx,4.0) {}; \node[st] (t1) at (\tx,3.2) {}; \node[ac] (t2) at (\tx,2.4) {}; \node[st] (t3) at (\tx,1.6) {}; \node[ac] (t4) at (\tx,0.8) {}; \draw[black] (t0)--(t1)--(t2)--(t3)--(t4); % branches at each state \foreach \yy in {3.2,1.6}{ \draw[black] (\tx,\yy) -- (\tx-0.55,\yy-0.5); \draw[black] (\tx,\yy) -- (\tx+0.55,\yy-0.5); \node[ac] at (\tx-0.55,\yy-0.5) {}; \node[ac] at (\tx+0.55,\yy-0.5) {}; } \node[align=center, font=\scriptsize] at (\tx,4.7) {4-step\\tree backup}; % ---- column 3: Expected Sarsa (sample, last branches) ---- \def\ex{4.6} \node[ac] (x0) at (\ex,4.0) {}; \node[st] (x1) at (\ex,3.2) {}; \node[ac] (x2) at (\ex,2.4) {}; \node[st] (x3) at (\ex,1.6) {}; \draw[black] (x0)--(x1)--(x2)--(x3); % last state branches \draw[black] (\ex,1.6) -- (\ex-0.55,1.1); \draw[black] (\ex,1.6) -- (\ex,1.1); \draw[black] (\ex,1.6) -- (\ex+0.55,1.1); \node[ac] at (\ex-0.55,1.1) {}; \node[ac] at (\ex,1.1) {}; \node[ac] at (\ex+0.55,1.1) {}; \node[align=center, font=\scriptsize] at (\ex,4.7) {4-step\\Exp. Sarsa}; % ---- column 4: Q(sigma) (mix) ---- \def\qx{7.2} \node[ac] (q0) at (\qx,4.0) {}; \node[st] (q1) at (\qx,3.2) {}; % step 1: sample \node[ac] (q2) at (\qx,2.4) {}; \draw[black] (q0)--(q1)--(q2); \node[anchor=west, font=\scriptsize, text=acc] at (\qx+0.7,2.8) {sample}; \node[st] (q3) at (\qx,1.6) {}; \draw[black] (q2)--(q3); % step 2: branch \draw[black] (\qx,1.6) -- (\qx-0.55,1.1); \draw[black] (\qx,1.6) -- (\qx+0.55,1.1); \node[ac] at (\qx-0.55,1.1) {}; \node[ac] (q4) at (\qx,1.1) {}; \draw[black] (\qx,1.6) -- (\qx,1.1); \draw[black] (\qx,1.6) -- (\qx+0.55,1.1); \node[anchor=west, font=\scriptsize, text=acc] at (\qx+0.7,1.25) {expect}; \node[align=center, font=\scriptsize] at (\qx,4.7) {4-step\\Q(sigma)}; \end{tikzpicture} $$ ### 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)$, $$ G_{t:h} \;\doteq\; R_{t+1} + \gamma\Big(\sigma_{t+1}\,\rho_{t+1} + (1 - \sigma_{t+1})\,\pi(A_{t+1}\mid S_{t+1})\Big)\big(G_{t+1:h} - Q_{h-1}(S_{t+1}, A_{t+1})\big) \;+\; \gamma\,\bar V_{h-1}(S_{t+1}), $$ 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$. ```algorithm caption: $\textsc{Off-policy n-step Q}(\sigma)$ — estimate $Q \approx q_\ast$ or $q_\pi$ input: a behavior policy $b$ with $b(a \mid s) > 0$ for all $s, a$ initialize $Q(s, a)$ arbitrarily for all $s \in \mathcal{S}, a \in \mathcal{A}$ initialize $\pi$ to be $\varepsilon$-greedy wrt $Q$, or a fixed given policy input: step size $\alpha \in (0,1]$; a positive integer $n$ for each episode do initialize and store $S_0 \ne$ terminal choose and store $A_0 \sim b(\cdot \mid S_0)$ $T \gets \infty$ for $t = 0, 1, 2, \ldots$ do if $t < T$ then take action $A_t$; observe and store $R_{t+1}$ and $S_{t+1}$ if $S_{t+1}$ is terminal then $T \gets t + 1$ else: choose and store $A_{t+1} \sim b(\cdot \mid S_{t+1})$ select and store $\sigma_{t+1}$ $\rho_{t+1} \gets \pi(A_{t+1} \mid S_{t+1}) / b(A_{t+1} \mid S_{t+1})$ $\tau \gets t - n + 1$ // time whose estimate is updated now if $\tau \ge 0$ then if $t + 1 \ge T$ then $G \gets R_T$ else: $G \gets Q(S_{t+1}, A_{t+1})$ for $k = \min(t+1, T)$ down to $\tau + 1$ do if $k = T$ then $G \gets R_T$ else: $\bar V \gets \sum_a \pi(a \mid S_k)\, Q(S_k, a)$ $G \gets R_k + \gamma\big(\sigma_k \rho_k + (1 - \sigma_k)\pi(A_k \mid S_k)\big)\big(G - Q(S_k, A_k)\big) + \gamma \bar V$ $Q(S_\tau, A_\tau) \gets Q(S_\tau, A_\tau) + \alpha\,[\,G - Q(S_\tau, A_\tau)\,]$ if $\pi$ is being learned then ensure $\pi(\cdot \mid S_\tau)$ is greedy wrt $Q$ until $\tau = T - 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. $$ % caption: The bias-variance dial that deep RL inherits from $n$-step returns. % Small $n$ (left) means low variance but high bias, because the target leans on % the current, possibly wrong, value estimate; large $n$ (right) means low bias but % high variance from long reward sequences. Deep-RL systems pick a small % intermediate $n$ (A3C, Rainbow, R2D2 sit near $n = 3$ to $20$), the same sweet % spot the random walk found. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} \definecolor{red}{HTML}{C0392B} % axis \draw[->, black] (0,0) -- (7.6,0); \node[font=\scriptsize] at (3.6,-0.75) {n (lookahead depth)}; \draw[black] (0,-0.05) -- (0,0.05); \node[anchor=north, font=\scriptsize] at (0.2,-0.1) {n=1}; \node[anchor=north, font=\scriptsize] at (6.6,-0.1) {n = inf (MC)}; % bias curve: high at left, falls -- labelled at its right end (legend style) \draw[acc, thick] (0.2,3.0) .. controls (2.0,1.0) and (4.0,0.4) .. (6.6,0.3); \node[acc, anchor=west, font=\scriptsize] at (6.7,0.3) {bias}; % variance curve: low at left, rises -- labelled at its right end \draw[red, thick] (0.2,0.3) .. controls (3.0,0.5) and (5.0,1.4) .. (6.6,3.0); \node[red, anchor=west, font=\scriptsize] at (6.7,3.0) {variance}; % explanatory captions in the open interior (upper-mid, clear of both curves) \node[acc, anchor=west, font=\scriptsize] at (2.75,2.75) {bias: from bootstrap}; \node[red, anchor=west, font=\scriptsize] at (2.75,2.3) {variance: from reward}; % sweet spot band \draw[black, dashed] (2.4,0) -- (2.4,3.4); \node[anchor=south, font=\scriptsize, text=black, align=center] at (2.4,3.4) {deep-RL choice\\(n = 3 to 20)}; \end{tikzpicture} $$ **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.[^beyond] ## 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](/reinforcement-learning/approximation/eligibility-traces) 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. [^sb-offpolicy-nstep]: **Sutton & Barto**, §7.3 — n-step Off-policy Learning: the importance-sampling ratio (7.10) and the reweighted updates (7.9), (7.11); and §7.5 — the n-step Tree Backup Algorithm: the recursive tree-backup return (7.15)–(7.16), off-policy without importance sampling. [^sb-qsigma]: **Sutton & Barto**, §7.6 — A Unifying Algorithm: $n$-step Q($\sigma$). A per-step degree of sampling $\sigma_t \in [0,1]$ blends the tree-backup weight $\pi(A_{t+1} \mid S_{t+1})$ and the importance ratio $\rho_{t+1}$ in the return (7.17), unifying $n$-step Sarsa ($\sigma \equiv 1$), $n$-step tree backup ($\sigma \equiv 0$), and $n$-step Expected Sarsa ($\sigma = 0$ on the last step only); the complete off-policy algorithm uses the general $n$-step Sarsa update (7.11). The algorithm is new to the second edition (related work by De Asis, Hernandez-Garcia, Holland, and Sutton, 2017). [^beyond]: Multi-step returns in deep reinforcement learning, past Sutton and Barto's tabular treatment. **A3C**: V. Mnih et al., "Asynchronous methods for deep reinforcement learning," _ICML_ (2016) — $n$-step returns as targets for an actor–critic. **Rainbow**: M. Hessel et al., "Rainbow: Combining improvements in deep reinforcement learning," _AAAI_ (2018) — multi-step ($n$-step) returns among the components driving its gains. **R2D2**: S. Kapturowski et al., "Recurrent experience replay in distributed reinforcement learning," _ICLR_ (2019) — $n$-step recurrent Q-learning. **GAE**: J. Schulman et al., "High-dimensional continuous control using generalized advantage estimation," _ICLR_ (2016) — a $\lambda$-weighted average over all $n$-step returns for the advantage. **Retrace**: R. Munos, T. Stepleton, A. Harutyunyan, M. Bellemare, "Safe and efficient off-policy reinforcement learning," _NeurIPS_ (2016) — per-step ratios clipped at $1$ for a convergent multi-step off-policy return. **V-trace/IMPALA**: L. Espeholt et al., "IMPALA: Scalable distributed deep-RL with importance weighted actor-learner architectures," _ICML_ (2018) — truncated importance ratios for lagged distributed data.