---
title: Off-Policy Eligibility Traces
module: Approximate Solution Methods
moduleNumber: 3
lessonNumber: 13
order: 313
summary: >
  Eligibility traces meet off-policy learning and function approximation — the
  corner where stability gets hard. We first let the bootstrapping and discounting
  parameters vary with state, so a single generalized return covers episodic and
  continuing tasks and folds termination into the discount. Then we fold the
  per-decision importance ratio into the trace with a control-variate correction,
  and build Watkins's Q(λ) and its importance-sampling-free successor
  Tree-Backup(λ) — all correct in expectation, but still semi-gradient, so the
  deadly triad and its fixes wait for the next lesson.
topics: [Approximation]
sources:
  - book: Sutton & Barto
    ref: "Ch. 12 — Eligibility Traces; §12.8 Variable λ and γ; §12.9 Off-policy Traces with Control Variates"
  - book: Sutton & Barto
    ref: "§12.10 Watkins's Q(λ) to Tree-Backup(λ)"
---

The [eligibility-traces lesson](/reinforcement-learning/approximation/eligibility-traces)
completed the on-policy case: the $\lambda$-return as a forward
view, the trace vector $\mathbf{z}_t$ as a backward view, TD($\lambda$) making
the two nearly agree, true online TD($\lambda$) making them agree exactly, and
Sarsa($\lambda$) lifting the whole apparatus to on-policy control. Throughout,
$\lambda$ and $\gamma$ were fixed constants and every step was generated by the
policy being evaluated.

This lesson removes both restrictions. First $\lambda$ and $\gamma$ become
_functions of state and action_, which turns out to unify the episodic and
continuing settings and absorb termination into the discount. Then we learn about
a target policy $\pi$ from behavior policy $b$, which brings the per-decision
importance ratio $\rho_t$ into the trace, with a control variate to limit the
variance. The combination — traces, off-policy data, and a parameterized value
function — is the
[deadly triad](/reinforcement-learning/approximation/off-policy-and-the-deadly-triad)
itself, and convergence is no longer guaranteed. Naming the methods that restore
stability is the job of the
[next lesson](/reinforcement-learning/approximation/stable-off-policy-traces); this
one builds the returns and traces they all rest on.

## Variable λ and γ

To state the final algorithms in their most general form, promote the two
constants to functions.[^sb-varlg] Let $\lambda : \mathcal{S} \times \mathcal{A}
\to [0,1]$ depend on state and action, $\lambda_t \doteq \lambda(S_t, A_t)$, and
let $\gamma : \mathcal{S} \to [0,1]$ depend on state, $\gamma_t \doteq
\gamma(S_t)$. The **termination function** $\gamma$ is the significant one,
because it changes the return itself — the random variable whose expectation we
are estimating. The return is now defined by a running product of per-step
discounts,

$$
G_t \;\doteq\; R_{t+1} + \gamma_{t+1} G_{t+1}
\;=\; \sum_{k=t}^{\infty} \parens{\prod_{i=t+1}^{k} \gamma_i} R_{k+1},
$$

where we require $\prod_{k=t}^{\infty} \gamma_k = 0$ with probability one for
every $t$, so the sums are finite. This single definition lets the episodic
setting be presented as one uninterrupted stream of
experience — no special terminal states, no start distribution, no explicit
termination time. A former terminal state becomes an ordinary state at which
$\gamma(s) = 0$ and which transitions to the start distribution; setting
$\gamma(\cdot) = 1$ everywhere else recovers the classical episodic case exactly.

$$
% caption: State-dependent termination $\gamma(s)$ unifies the settings. Top: the
% classic episodic view, with a special terminal state and a reset. Bottom: the
% same experience as one continuing stream where the goal state has $\gamma=0$ and
% jumps back to the start; a bootstrapping state has $\gamma \approx 1$. Setting
% $\gamma \equiv 1$ off the goal recovers the episodic case; a constant $\gamma$
% recovers ordinary discounting.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=7mm, inner sep=0pt},
  term/.style={rectangle, draw, fill=black!18, minimum size=7mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % ---- top: episodic view ----
  \node[anchor=west, font=\scriptsize] at (-1.6,2.0) {episodic:};
  \node[st] (a0) at (0,2.0) {s0};
  \node[st] (a1) at (1.6,2.0) {s1};
  \node[st] (a2) at (3.2,2.0) {s2};
  \node[term] (aT) at (4.8,2.0) {T};
  \draw[->, acc, thick] (a0) -- (a1);
  \draw[->, acc, thick] (a1) -- (a2);
  \draw[->, acc, thick] (a2) -- (aT);
  \node[anchor=south, font=\scriptsize, text=black] at (4.8,2.4) {terminal};
  \draw[->, red, thick, dashed] (aT) to[bend right=42] (a0);
  \node[anchor=north, font=\scriptsize, text=red] at (2.4,1.35) {reset to start};
  % ---- bottom: continuing view ----
  \node[anchor=west, font=\scriptsize] at (-1.6,0.0) {continuing:};
  \node[st] (b0) at (0,0.0) {s0};
  \node[st] (b1) at (1.6,0.0) {s1};
  \node[st] (b2) at (3.2,0.0) {s2};
  \node[st, draw=red, text=red, thick] (bg) at (4.8,0.0) {g};
  \draw[->, acc, thick] (b0) -- (b1);
  \draw[->, acc, thick] (b1) -- (b2);
  \draw[->, acc, thick] (b2) -- (bg);
  \node[anchor=south, font=\scriptsize, text=red] at (4.8,0.4) {gamma(g)=0};
  \node[anchor=north, font=\scriptsize, text=black] at (1.6,-0.42) {gamma approx 1};
  \draw[->, red, thick] (bg) to[bend right=42] (b0);
\end{tikzpicture}
$$

State-dependent termination also reaches beyond ordinary episodes to _pseudo
termination_: predicting some quantity as if the stream ended here, without
actually interrupting the Markov process. A discounted return is one such
quantity, so this one construction unifies episodic, discounted-continuing, and
pseudo-terminating prediction. (The undiscounted-continuing case, $\gamma \equiv
1$ with no termination, still needs its own treatment via average reward.)

> **Definition (Termination function).** A map $\gamma : \mathcal{S} \to [0,1]$
> with $\gamma_t \doteq \gamma(S_t)$ that sets the per-step continuation
> probability. The return $G_t = R_{t+1} + \gamma_{t+1} G_t$ discounts future
> rewards by the running product $\prod \gamma_i$; a state with $\gamma(s)=0$
> terminates the return there. It unifies episodic, continuing, and
> pseudo-terminating prediction in one stream of experience.

**A worked return.** Take rewards $R_{t+1}, R_{t+2}, R_{t+3}, \ldots = 1, 1, 1,
\ldots$ and a per-state discount that is $\gamma = 0.9$ everywhere except a goal
state reached at step $t+3$, where $\gamma(g) = 0$. The running product truncates
the sum the moment it hits the zero: the weight on $R_{t+1}$ is $1$, on $R_{t+2}$ is
$\gamma_{t+1} = 0.9$, on $R_{t+3}$ is $\gamma_{t+1}\gamma_{t+2} = 0.81$, and every
later reward is multiplied by $\gamma_{t+1}\gamma_{t+2}\gamma_{t+3} = 0.81 \cdot 0 =
0$. So

$$
G_t = 1 + 0.9\cdot 1 + 0.81\cdot 1 + 0 + 0 + \cdots = 2.71,
$$

a finite return produced with no special terminal state and no episode boundary —
the goal's $\gamma(g) = 0$ truncates the sum. Set $\gamma(g) = 1$ instead and the
same stream keeps accumulating $1 + 0.9 + 0.81 + 0.729 + \cdots = 10$, the ordinary
discounted return of a continuing task. One definition covers both cases.

Making $\lambda$ variable is a change of _solution strategy_, not of the problem:
it sets, state by state, how much to bootstrap. The generalization touches the
$\lambda$-return, which now recurses. In the state-based case, writing the
superscript $s$ to mark that it bootstraps from state values,

$$
G_t^{\lambda s} \;\doteq\; R_{t+1} + \gamma_{t+1}\Big( (1-\lambda_{t+1})\,\hat v(S_{t+1}, \mathbf{w}_t) + \lambda_{t+1}\, G_{t+1}^{\lambda s} \Big).
$$

Read it left to right: the return is the first reward, plus (to the extent we are
not terminating, $\gamma_{t+1}$) a second term that splits by the degree of
bootstrapping — a fraction $1-\lambda_{t+1}$ takes the estimated value at the next
state, and the complementary fraction $\lambda_{t+1}$ recurses into the
$\lambda$-return of the next step. The action-based return has a Sarsa form,

$$
G_t^{\lambda a} \;\doteq\; R_{t+1} + \gamma_{t+1}\Big( (1-\lambda_{t+1})\,\hat q(S_{t+1}, A_{t+1}, \mathbf{w}_t) + \lambda_{t+1}\, G_{t+1}^{\lambda a} \Big),
$$

and an Expected-Sarsa form that bootstraps from the expected value under the
target policy,

$$
G_t^{\lambda a} \;\doteq\; R_{t+1} + \gamma_{t+1}\Big( (1-\lambda_{t+1})\,\bar V_t(S_{t+1}) + \lambda_{t+1}\, G_{t+1}^{\lambda a} \Big),
\qquad
\bar V_t(s) \;\doteq\; \sum_a \pi(a \mid s)\, \hat q(s, a, \mathbf{w}_t).
$$

These recursions are the substrate for everything below. Constant $\lambda,
\gamma$ are the special case $\lambda_t \equiv \lambda$, $\gamma_t \equiv \gamma$,
which collapses each back to the $\lambda$-return of the previous lesson.

## Off-policy traces with control variates

Now the data is off-policy: actions come from a behavior policy $b$ while we
evaluate a target policy $\pi$. For $n$-step methods, importance sampling was
applied _outside_ the return. That has no clean analogue for a full,
non-truncated $\lambda$-return, so we move directly to the modern construction:
fold the per-decision importance ratio into the return itself, with a **control
variate** to hold the variance down.[^sb-cv] The per-step ratio is the usual

$$
\rho_t \;\doteq\; \frac{\pi(A_t \mid S_t)}{b(A_t \mid S_t)}.
$$

The state-based off-policy $\lambda$-return generalizes the recursion above by
scaling the bootstrapped part by $\rho_t$ and adding a correction term that has
zero mean but cancels much of the extra variance,

$$
G_t^{\lambda s} \;\doteq\; \rho_t\Big( R_{t+1} + \gamma_{t+1}\big( (1-\lambda_{t+1})\hat v(S_{t+1},\mathbf{w}_t) + \lambda_{t+1} G_{t+1}^{\lambda s} \big) \Big) + (1-\rho_t)\,\hat v(S_t, \mathbf{w}_t).
$$

The second term $(1-\rho_t)\hat v(S_t, \mathbf{w}_t)$ is the control variate: its
expectation over $A_t \sim b$ is zero (because $\mathbb{E}_b[\rho_t] = 1$), so it
does not bias the target, but when $\rho_t$ is far from $1$ it pulls the return
back toward the current estimate and dampens the swing.

$$
% caption: The control variate at work. Without it (top), a large importance
% ratio $\rho_t$ scales the whole target and the estimate whipsaws far from the
% baseline $\hat v(S_t)$. With the correction $(1-\rho_t)\hat v(S_t)$ (bottom),
% the same ratios produce a target that stays near the baseline; the correction
% has zero mean, so no bias is added.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % ---- top: no control variate ----
  \draw[black, dashed] (0,2.0) -- (7.2,2.0);
  \node[anchor=west, font=\scriptsize, text=black] at (7.25,2.0) {baseline v(St)};
  \node[anchor=east, font=\scriptsize] at (-0.1,2.0) {no CV:};
  \foreach \x/\y in {0.7/3.2, 1.7/0.9, 2.7/2.9, 3.7/1.0, 4.7/3.3, 5.7/1.1} {
    \draw[red, thick] (\x,2.0) -- (\x,\y);
    \fill[red] (\x,\y) circle (1.6pt);
  }
  % ---- bottom: with control variate ----
  \draw[black, dashed] (0,-1.2) -- (7.2,-1.2);
  \node[anchor=west, font=\scriptsize, text=black] at (7.25,-1.2) {baseline v(St)};
  \node[anchor=east, font=\scriptsize] at (-0.1,-1.2) {with CV:};
  \foreach \x/\y in {0.7/-0.75, 1.7/-1.5, 2.7/-0.85, 3.7/-1.45, 4.7/-0.7, 5.7/-1.4} {
    \draw[acc, thick] (\x,-1.2) -- (\x,\y);
    \fill[acc] (\x,\y) circle (1.6pt);
  }
  \node[anchor=south, font=\scriptsize, text=black] at (3.6,3.35) {high variance};
  \node[anchor=north, font=\scriptsize, text=black] at (3.6,-1.65) {variance reduced};
\end{tikzpicture}
$$

**A worked correction.** Suppose at $S_t$ the target policy would take the sampled
action with probability $\pi(A_t \mid S_t) = 0.8$ while the behavior policy took it
with $b(A_t \mid S_t) = 0.2$, so $\rho_t = 0.8/0.2 = 4$. Let the bracketed one-step
target evaluate to $12$ and the current estimate be $\hat v(S_t) = 10$. Without the
control variate the return is $\rho_t \cdot 12 = 48$ — a swing of $+38$ above the
baseline from a single lucky-for-$\pi$ action. With the control variate it is
$4\cdot 12 + (1 - 4)\cdot 10 = 48 - 30 = 18$, a swing of $+8$. The correction has
not changed the _expectation_ (over $A_t \sim b$, $\mathbb{E}[\rho_t] = 1$ so
$\mathbb{E}[(1-\rho_t)\hat v] = 0$), but it has shrunk this particular sample's
excursion from $38$ to $8$. When instead the sampled action is one $\pi$ dislikes,
$\rho_t < 1$, and the same term nudges the target back _up_ toward the baseline —
either way, toward $\hat v(S_t)$.

The value of this form is that the truncated version can be written, to a close
approximation, as a sum of state-based TD errors, exactly as in the on-policy
case. With the per-decision TD error

$$
\delta_t^s \;\doteq\; R_{t+1} + \gamma_{t+1}\, \hat v(S_{t+1}, \mathbf{w}_t) - \hat v(S_t, \mathbf{w}_t),
$$

the return is approximately

$$
G_t^{\lambda s} \;\approx\; \hat v(S_t, \mathbf{w}_t) + \rho_t \sum_{k=t}^{\infty} \delta_k^s \prod_{i=t+1}^{k} \gamma_i \lambda_i \rho_i,
$$

with the approximation becoming _exact_ when the value function does not change.
The product $\prod \gamma_i \lambda_i \rho_i$ is the eligibility-trace weight: it
compounds the same $\gamma \lambda$ decay as before, now multiplied by the
importance ratios along the way. The forward-view update

$$
\mathbf{w}_{t+1} \;=\; \mathbf{w}_t + \alpha \big( G_t^{\lambda s} - \hat v(S_t, \mathbf{w}_t) \big) \nabla \hat v(S_t, \mathbf{w}_t)
\;\approx\; \mathbf{w}_t + \alpha \rho_t \Big( \sum_{k=t}^{\infty} \delta_k^s \prod_{i=t+1}^{k} \gamma_i \lambda_i \rho_i \Big) \nabla \hat v(S_t, \mathbf{w}_t)
$$

already looks like a trace-based TD update: a product of past terms multiplying
present TD errors. Summing this forward-view update over time and applying the
summation-rule rearrangement (the same manipulation used for on-policy TD($\lambda$))
converts it into a backward view driven by a single accumulating trace. The trace
that falls out is the general **accumulating trace with importance sampling**,

$$
\mathbf{z}_t \;\doteq\; \rho_t \big( \gamma_t \lambda_t\, \mathbf{z}_{t-1} + \nabla \hat v(S_t, \mathbf{w}_t) \big),
$$

paired with the usual semi-gradient update $\mathbf{w}_{t+1} = \mathbf{w}_t +
\alpha \delta_t^s \mathbf{z}_t$. In the on-policy case every $\rho_t = 1$ and this
reduces to the ordinary accumulating trace (extended to variable $\lambda,
\gamma$); off-policy, the $\rho_t$ scaling makes the algorithm correct in
expectation. But as a semi-gradient method it is _not_ guaranteed stable — the
next sections repair that.

$$
% caption: Where the importance ratio enters the trace. The trace at $S_t$ decays
% the previous trace by $\gamma_t \lambda_t$, adds the new gradient, and scales the
% whole thing by $\rho_t = \pi(A_t \mid S_t) / b(A_t \mid S_t)$. When $\pi$ agrees
% with $b$, $\rho_t = 1$ and this is the on-policy accumulating trace; a target
% action that $b$ rarely takes gives $\rho_t \gg 1$ and amplifies the trace.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=22mm, minimum height=10mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (prev)  at (0,0)    {prev trace\\z(t-1)};
  \node[box] (decay) at (3.2,0)  {decay by\\gamma(t) lambda(t)};
  \node[box] (grad)  at (3.2,-1.9) {add gradient\\grad v(St)};
  \node[box, draw=acc, text=acc, thick] (scale) at (6.6,0) {scale by\\rho(t)};
  \node[box] (out)   at (9.8,0)  {new trace\\z(t)};
  \draw[->, thick] (prev) -- (decay);
  \draw[->, thick] (grad) -- (decay);
  \draw[->, acc, thick] (decay) -- (scale);
  \draw[->, acc, thick] (scale) -- (out);
  \node[anchor=north, font=\scriptsize, text=black] at (6.6,-0.75) {rho = pi / b};
\end{tikzpicture}
$$

The identical derivation runs for action values. Starting from the Expected-Sarsa
form of the general $\lambda$-return — which works out simpler than the Sarsa form
— the same steps produce the action-value off-policy trace,

$$
\mathbf{z}_t \;\doteq\; \gamma_t \lambda_t\, \rho_t\, \mathbf{z}_{t-1} + \nabla \hat q(S_t, A_t, \mathbf{w}_t),
$$

with the expectation-form action-value TD error

$$
\delta_t^a \;\doteq\; R_{t+1} + \gamma_{t+1}\, \bar V_t(S_{t+1}) - \hat q(S_t, A_t, \mathbf{w}_t),
$$

and the same weight update $\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \delta_t^a
\mathbf{z}_t$. This is an efficient Expected-Sarsa($\lambda$) that runs
on-policy or off-policy; with constant $\lambda, \gamma$ and the ordinary
state-action TD error it becomes exactly the Sarsa($\lambda$) of the previous
lesson. It is probably the best method of its kind — subject, still, to the
stability caveat.

## Watkins's Q(λ) to Tree-Backup(λ)

The oldest way to give Q-learning eligibility traces is **Watkins's Q($\lambda$)**.[^sb-watkins]
Q-learning bootstraps from the greedy action, so its trace should reflect the
future only as long as the agent keeps taking greedy actions. Watkins's rule is
simple: decay the trace by $\gamma\lambda$ in the usual way as long as greedy
actions are taken, but the moment the behavior policy selects the _first
non-greedy action_, cut the trace to zero. Everything after that first
exploratory step is off the greedy path and irrelevant to the greedy target, so
it receives no eligibility.

$$
% caption: Backup diagram for Watkins's Q(lambda). Component backups of increasing
% length are weighted (1-lambda), (1-lambda)lambda, (1-lambda)lambda^2, ..., as in
% any lambda-return; the series ends either at episode termination (weight
% lambda^{T-t-1}, the box) or at the first non-greedy action, whichever comes
% first. After that first non-greedy branch the trace is cut.
\begin{tikzpicture}[>=stealth, font=\scriptsize,
  sn/.style={circle, draw, minimum size=3.2mm, inner sep=0pt},
  an/.style={circle, draw, fill=black, minimum size=1.6mm, inner sep=0pt},
  term/.style={rectangle, draw, fill=black!18, minimum size=4mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[anchor=south, font=\small] at (3.6,3.7) {Watkins's Q(lambda)};
  % column 1: 1-step
  \node[an] (a1) at (0,3.3) {};
  \node[sn] (s1) at (0,2.7) {};
  \draw (a1) -- (s1);
  \node[anchor=north, font=\scriptsize] at (0,2.55) {1-lambda};
  % column 2: 2-step
  \node[an] (a2) at (1.2,3.3) {};
  \node[sn] (s2a) at (1.2,2.7) {};
  \node[an] (a2b) at (1.2,2.2) {};
  \node[sn] (s2b) at (1.2,1.6) {};
  \draw (a2) -- (s2a) -- (a2b) -- (s2b);
  \node[anchor=north, font=\scriptsize] at (1.2,1.45) {(1-lambda)lambda};
  % column 3: 3-step
  \node[an] (a3) at (2.4,3.3) {};
  \node[sn] (s3a) at (2.4,2.7) {};
  \node[an] (a3b) at (2.4,2.2) {};
  \node[sn] (s3b) at (2.4,1.6) {};
  \node[an] (a3c) at (2.4,1.1) {};
  \node[sn] (s3c) at (2.4,0.5) {};
  \draw (a3) -- (s3a) -- (a3b) -- (s3b) -- (a3c) -- (s3c);
  \node[anchor=north, font=\scriptsize] at (2.4,0.35) {(1-lambda)lambda lambda};
  % dots
  \node at (3.5,2.0) {...};
  % OR
  \node[font=\small] at (4.5,2.4) {OR};
  % termination column
  \node[an] (t1) at (5.4,3.3) {};
  \node[sn] (t2) at (5.4,2.7) {};
  \node[an] (t3) at (5.4,2.2) {};
  \node[sn] (t4) at (5.4,1.6) {};
  \node[term] (tT) at (5.4,0.9) {};
  \draw (t1) -- (t2) -- (t3) -- (t4) -- (tT);
  \node[anchor=east, font=\scriptsize] at (5.1,0.9) {lambda to the T-t-1};
  % right: cut at first non-greedy
  \node[an] (r1) at (7.0,3.3) {};
  \node[sn] (r2) at (7.0,2.7) {};
  \node[an] (r3) at (7.0,2.2) {};
  \node[sn] (r4) at (7.0,1.6) {};
  \node[anchor=west, font=\scriptsize] at (7.15,3.3) {St, At};
  \node[anchor=west, font=\scriptsize] at (7.15,2.7) {St+1};
  \node[anchor=west, font=\scriptsize] at (7.15,1.6) {St+2};
  \draw (r1) -- (r2) -- (r3) -- (r4);
  % branch: first non-greedy action
  \node[an] (rb1) at (6.7,1.0) {};
  \node[an] (rb2) at (7.0,1.0) {};
  \node[an, draw=red, fill=red] (rb3) at (7.3,1.0) {};
  \draw (r4) -- (rb1);  \draw (r4) -- (rb2);  \draw[red] (r4) -- (rb3);
  \node[anchor=west, font=\scriptsize, text=red] at (7.5,1.0) {f\/irst non-greedy};
  \node[anchor=north, font=\scriptsize] at (7.0,0.75) {lambda to the n-1};
\end{tikzpicture}
$$

The cut is crude. If exploration is frequent — and early in learning it is — the
trace is repeatedly truncated, so Q($\lambda$) rarely propagates credit more than
a step or two, and much of the benefit of traces is lost. The deeper problem is
that cutting on the first non-greedy action is a hard special case of a more
principled operation, which removes the need for the cut entirely.

The general version is **Tree-Backup($\lambda$)**, abbreviated TB($\lambda$).[^sb-tb]
$n$-step Tree Backup already extended Expected Sarsa to arbitrary target policies
_without any importance sampling_; TB($\lambda$) is its eligibility-trace form, and
it is arguably the true successor to Q-learning because it keeps that appealing
absence of importance sampling while applying to off-policy data. Starting from
the Expected-Sarsa recursion and expanding the bootstrapping case after the tree-backup
pattern, the return weights each action branch by its target-policy probability,

$$
G_t^{\lambda a} \;=\; R_{t+1} + \gamma_{t+1}\Big( \bar V_t(S_{t+1}) + \lambda_{t+1}\, \pi(A_{t+1} \mid S_{t+1})\big( G_{t+1}^{\lambda a} - \hat q(S_{t+1}, A_{t+1}, \mathbf{w}_t) \big) \Big).
$$

$$
% caption: Backup diagram for Tree-Backup(lambda). Every backup fans out to all
% actions at each level: the selected action (solid, continuing down) plus the
% unselected actions (leaf dots), each weighted by its target-policy probability
% pi(a|s). No importance sampling is needed — the target policy enters only
% through these branch weights. Component lengths are weighted 1-lambda,
% (1-lambda)lambda, ... exactly as before, terminating at the box.
\begin{tikzpicture}[>=stealth, font=\scriptsize,
  sn/.style={circle, draw, minimum size=3.2mm, inner sep=0pt},
  an/.style={circle, draw, fill=black, minimum size=1.6mm, inner sep=0pt},
  leaf/.style={circle, draw, fill=black, minimum size=1.2mm, inner sep=0pt},
  term/.style={rectangle, draw, fill=black!18, minimum size=4mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[anchor=south, font=\small] at (3.6,3.9) {Tree Backup(lambda)};
  % helper for a fan of leaves at a state node given coords
  % column 1: 1-step (root fans out)
  \node[an] (c1a) at (0,3.4) {};
  \node[sn] (c1s) at (0,2.8) {};
  \draw (c1a) -- (c1s);
  \node[leaf] at (-0.35,2.35) {}; \node[leaf] at (0.35,2.35) {};
  \draw (c1s) -- (-0.35,2.35);  \draw (c1s) -- (0.35,2.35);
  \node[anchor=north, font=\scriptsize] at (0,1.95) {1-lambda};
  % column 2: 2-step
  \node[an] (c2a) at (1.4,3.4) {};
  \node[sn] (c2s1) at (1.4,2.8) {};
  \node[leaf] at (1.05,2.4) {}; \node[leaf] at (1.75,2.4) {};
  \draw (c2s1) -- (1.05,2.4); \draw (c2s1) -- (1.75,2.4);
  \node[an] (c2a2) at (1.4,2.3) {};
  \node[sn] (c2s2) at (1.4,1.7) {};
  \node[leaf] at (1.05,1.3) {}; \node[leaf] at (1.75,1.3) {};
  \draw (c2s2) -- (1.05,1.3); \draw (c2s2) -- (1.75,1.3);
  \draw (c2a) -- (c2s1) -- (c2a2) -- (c2s2);
  \node[anchor=north, font=\scriptsize] at (1.4,0.95) {(1-lambda)lambda};
  % dots
  \node at (3.1,2.4) {...};
  % termination column
  \node[an] (t1) at (4.6,3.4) {};
  \node[sn] (t2) at (4.6,2.8) {};
  \node[leaf] at (4.25,2.4) {}; \node[leaf] at (4.95,2.4) {};
  \draw (t2) -- (4.25,2.4); \draw (t2) -- (4.95,2.4);
  \node[an] (t3) at (4.6,2.3) {};
  \node[sn] (t4) at (4.6,1.7) {};
  \node[leaf] at (4.25,1.35) {}; \node[leaf] at (4.95,1.35) {};
  \draw (t4) -- (4.25,1.35); \draw (t4) -- (4.95,1.35);
  \node[term] (tT) at (4.6,0.85) {};
  \draw (t1) -- (t2) -- (t3) -- (t4) -- (tT);
  \node[anchor=north, font=\scriptsize] at (4.6,0.6) {lambda to the T-t-1};
  % right labels
  \node[anchor=west, font=\scriptsize] at (5.4,3.4) {St, At};
  \node[anchor=west, font=\scriptsize] at (5.4,2.8) {St+1};
  \node[anchor=west, font=\scriptsize] at (5.4,1.7) {St+2};
  \node[anchor=west, font=\scriptsize] at (5.4,1.0) {ST};
  % legend
  \node[an] (lg1) at (0.2,0.2) {};
  \node[anchor=west, font=\scriptsize] at (0.35,0.2) {selected action};
  \node[leaf] (lg2) at (3.0,0.2) {};
  \node[anchor=west, font=\scriptsize] at (3.15,0.2) {unselected, weight pi(a given s)};
\end{tikzpicture}
$$

Written approximately as a sum of TD errors, the return uses the expectation-based
error $\delta_t^a = R_{t+1} + \gamma_{t+1}\bar V_t(S_{t+1}) - \hat q(S_t, A_t,
\mathbf{w}_t)$ and a trace weighted by the target-policy probability of each
selected action,

$$
\mathbf{z}_t \;\doteq\; \gamma_t \lambda_t\, \pi(A_t \mid S_t)\, \mathbf{z}_{t-1} + \nabla \hat q(S_t, A_t, \mathbf{w}_t).
$$

Compare the three action-value traces. On-policy Sarsa($\lambda$) decays by
$\gamma_t \lambda_t$; the importance-sampling off-policy trace decays by $\gamma_t
\lambda_t \rho_t$; TB($\lambda$) decays by $\gamma_t \lambda_t \pi(A_t \mid S_t)$.
Watkins's Q($\lambda$) is the crude ancestor of that last form: taking a greedy
action makes $\pi(A_t \mid S_t) = 1$ (no extra decay), and taking a non-greedy
action makes $\pi(A_t \mid S_t) = 0$ (the trace vanishes) — which is precisely the
"cut on first non-greedy action" rule, now recovered as a hard special case of the
smooth TB($\lambda$) weighting. TB($\lambda$), together with the standard
semi-gradient update, is the tree-backup trace algorithm; like every semi-gradient
method here, it is not guaranteed stable under off-policy data with a strong
function approximator.

$$
% caption: The three action-value traces share the base decay $\gamma_t \lambda_t$
% and differ only in the off-policy factor. Sarsa($\lambda$) uses none; the
% importance-sampling trace multiplies by $\rho_t$, which can spike far above 1;
% TB($\lambda$) multiplies by $\pi(A_t\mid S_t) \in [0,1]$, which only ever damps
% the trace. Watkins's Q($\lambda$) is TB with a hard 0/1 gate.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  row/.style={draw, minimum width=30mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[row] (a) at (0,2.0) {Sarsa(lambda)};
  \node[row] (b) at (0,0.7) {IS o\/f\/f-policy};
  \node[row, draw=acc, text=acc] (c) at (0,-0.6) {Tree-Backup(lambda)};
  \node[anchor=west, font=\scriptsize] at (2.3,2.0) {decay = gamma lambda};
  \node[anchor=west, font=\scriptsize] at (2.3,0.7) {decay = gamma lambda rho};
  \node[anchor=west, font=\scriptsize, text=acc] at (2.3,-0.6) {decay = gamma lambda pi(A:S)};
  \node[red, anchor=west, font=\scriptsize] at (7.0,0.7) {rho can be big: variance};
  \node[acc, anchor=west, font=\scriptsize] at (7.0,-0.6) {pi in 0..1: only damps};
\end{tikzpicture}
$$

## Where this leaves us

Two generalizations push the trace machinery to its most general form. Variable
$\lambda$ and $\gamma$ turn the constants into functions, unify episodic and
continuing tasks in a single stream, and fold termination into a state-dependent
discount. Control variates fold the importance ratio $\rho_t$ into the trace and
dampen the variance it brings, giving an efficient off-policy TD($\lambda$) and
Expected-Sarsa($\lambda$). Watkins's Q($\lambda$) cuts the trace on the first
non-greedy action; Tree-Backup($\lambda$) replaces that hard cut with a smooth
target-policy weighting and needs no importance sampling at all.

All of it is still semi-gradient, though, so whenever $\lambda < 1$ it bootstraps,
and off-policy plus bootstrapping plus function approximation is the deadly triad —
the weights can diverge. The stabilizing methods, and the practical cost of running
traces, continue in
[stable off-policy methods with traces](/reinforcement-learning/approximation/stable-off-policy-traces).

[^sb-varlg]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), §12.8 — Variable $\lambda$ and $\gamma$: promoting $\lambda$ and $\gamma$ to functions $\lambda_t = \lambda(S_t, A_t)$, $\gamma_t = \gamma(S_t)$; the generalized return (12.17) with the running product $\prod \gamma_i$; the termination function unifying episodic, continuing, and pseudo-terminating prediction; and the recursive generalized $\lambda$-returns for states (12.18), Sarsa (12.19), and Expected Sarsa (12.20)–(12.21).
[^sb-cv]: **Sutton & Barto**, §12.9 — Off-policy Traces with Control Variates: the per-decision importance ratio $\rho_t$ folded into the state-based $\lambda$-return with the control-variate term (12.22); the TD-error approximation (12.23)–(12.24); the general accumulating trace with importance sampling (12.25); and the action-value off-policy return (12.26)–(12.28) yielding the trace (12.29) and an Expected-Sarsa($\lambda$).
[^sb-watkins]: **Sutton & Barto**, §12.10 — Watkins's Q($\lambda$): decay the trace by $\gamma\lambda$ while greedy actions are taken, cut it to zero on the first non-greedy action (backup diagram, Fig. 12.12).
[^sb-tb]: **Sutton & Barto**, §12.10 — Tree-Backup($\lambda$), TB($\lambda$): the eligibility-trace form of $n$-step Tree Backup, requiring no importance sampling; the target-policy-weighted return and the trace $\mathbf{z}_t = \gamma_t \lambda_t \pi(A_t\mid S_t)\mathbf{z}_{t-1} + \nabla\hat q$ (backup diagram, Fig. 12.13).