---
title: "Stable Off-Policy Methods with Traces"
module: Approximate Solution Methods
moduleNumber: 3
lessonNumber: 14
order: 314
summary: >
  Off-policy traces get the expected target right, but with $\lambda < 1$ they
  bootstrap, so off-policy plus bootstrapping plus function approximation is the
  deadly triad and the weights can diverge. This lesson carries the two one-step
  fixes to traces: GTD(λ) and GQ(λ) add a second weight vector and a gradient
  correction for true gradient descent on the projected Bellman error, while Emphatic
  TD(λ) reweights updates through a followon trace and interest to recover the
  on-policy stability. It closes with the implementation reality that traces are
  cheap because they are sparse, and with Retrace and V-trace — the clipped-ratio
  descendants that make off-policy traces work at deep-RL scale.
topics: [Approximation]
sources:
  - book: Sutton & Barto
    ref: "Ch. 12 — Eligibility Traces; §12.11 Stable Off-policy Methods with Traces; §12.12 Implementation Issues"
  - book: Sutton & Barto
    ref: "§12.13 Conclusions"
---

This builds on
[off-policy eligibility traces](/reinforcement-learning/approximation/off-policy-eligibility-traces),
which generalized $\lambda$ and $\gamma$ to functions of state, folded the
importance ratio $\rho_t$ into the trace with a control variate, and built
Watkins's Q($\lambda$) and Tree-Backup($\lambda$). Every one of those methods was a
_semi-gradient_ method — correct in expectation, but with no stability guarantee
once it bootstraps off-policy under function approximation. This lesson supplies
the stable methods, then turns to the practical cost of running traces.

## Stable off-policy methods with traces

Everything so far is a semi-gradient method, so with $\lambda < 1$ all of it
bootstraps, and off-policy plus bootstrapping plus function approximation is the
[deadly triad](/reinforcement-learning/approximation/off-policy-and-the-deadly-triad):
the weights can diverge to infinity, as Baird's counterexample showed. The same
two families of one-step fixes from the deadly-triad lesson —
Gradient-TD and Emphatic-TD — extend to carry traces.[^sb-stable] All assume
linear function approximation, $\hat v(s, \mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s)$.

**GTD($\lambda$)** is the trace analogue of TDC, the better of the two Gradient-TD
prediction methods. It follows a true stochastic-gradient direction on the
projected Bellman error, so it is stable even off-policy. It keeps a second
weight vector $\mathbf{v} \in \mathbb{R}^d$ (initialized to $\mathbf{0}$) and a
second step size $\beta > 0$,

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\, \delta_t^s\, \mathbf{z}_t - \alpha \gamma_{t+1}(1 - \lambda_{t+1})\big( \mathbf{z}_t^\top \mathbf{v}_t \big)\, \mathbf{x}_{t+1},
$$

$$
\mathbf{v}_{t+1} \;\doteq\; \mathbf{v}_t + \beta\, \delta_t^s\, \mathbf{z}_t - \beta\big( \mathbf{v}_t^\top \mathbf{x}_t \big)\, \mathbf{x}_t,
$$

with $\delta_t^s$, $\mathbf{z}_t$, and $\rho_t$ defined as above. The extra term in
the $\mathbf{w}$ update — the one with $\mathbf{z}_t^\top \mathbf{v}_t$ — is the
gradient correction that TDC adds to plain TD to make it a true gradient descent;
$\mathbf{v}$ is a slow secondary estimate of the expected TD error.

**GQ($\lambda$)** is the action-value counterpart, the Gradient-TD control method.
It learns $\hat q(s, a, \mathbf{w}) = \mathbf{w}^\top \mathbf{x}(s,a) \approx
q_\pi$, and if $\pi$ is $\varepsilon$-greedy (or otherwise biased toward greedy in
$\hat q$) it serves as a stable control algorithm. Its update mirrors GTD($\lambda$)
but with the average next feature vector under the target policy,

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\, \delta_t^a\, \mathbf{z}_t - \alpha \gamma_{t+1}(1 - \lambda_{t+1})\big( \mathbf{z}_t^\top \mathbf{v}_t \big)\, \bar{\mathbf{x}}_{t+1},
\qquad
\bar{\mathbf{x}}_t \;\doteq\; \sum_a \pi(a \mid S_t)\, \mathbf{x}(S_t, a),
$$

where the expectation-form TD error is $\delta_t^a = R_{t+1} + \gamma_{t+1}
\mathbf{w}_t^\top \bar{\mathbf{x}}_{t+1} - \mathbf{w}_t^\top \mathbf{x}_t$ and
$\mathbf{z}_t$ is the action-value off-policy trace. A useful hybrid, HTD($\lambda$),
sits between GTD($\lambda$) and TD($\lambda$): it is a _strict_ generalization of
TD($\lambda$), reducing to it exactly when the behavior policy happens to equal the
target policy (something GTD($\lambda$) does not do), which lets it get by with a
single step size whenever both agree.

**Emphatic TD($\lambda$)** takes the other route to stability — it reweights
updates rather than correcting the gradient. It extends the one-step Emphatic-TD
algorithm to traces, keeps strong off-policy convergence guarantees, and enables
any degree of bootstrapping, at the cost of higher variance and possibly slower
convergence. It needs no second weight vector,

$$
\mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\, \delta_t\, \mathbf{z}_t,
\qquad
\delta_t \;\doteq\; R_{t+1} + \gamma_{t+1}\, \mathbf{w}_t^\top \mathbf{x}_{t+1} - \mathbf{w}_t^\top \mathbf{x}_t,
$$

but the trace itself is scaled by an **emphasis** $M_t \ge 0$ built from a
**followon trace** $F_t \ge 0$ and the per-state **interest** $I_t \ge 0$,

$$
\mathbf{z}_t \;\doteq\; \rho_t \big( \gamma_t \lambda_t\, \mathbf{z}_{t-1} + M_t\, \mathbf{x}_t \big),
\qquad
M_t \;\doteq\; \lambda_t\, I_t + (1 - \lambda_t)\, F_t,
\qquad
F_t \;\doteq\; \rho_{t-1} \gamma_t\, F_{t-1} + I_t.
$$

The followon trace accumulates how much later states "follow on" from states we
care about, and the emphasis it produces steers learning toward the states that
matter under the target policy. The interest $I_t$ lets the user declare which
states the prediction should be accurate at; setting $I_t \equiv 1$ makes every
state equally interesting.

$$
% caption: The followon trace $F_t$ in Emphatic TD. Interest $I=1$ is declared at
% one state; $F_t = \rho_{t-1}\gamma_t F_{t-1} + I_t$ carries that interest forward
% along the trajectory, decaying by $\rho\gamma$ per step, so downstream states that
% follow on from the interesting one inherit emphasis $M_t$ and are learned even
% though their own interest is zero.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=8mm, inner sep=0pt, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st, draw=acc, text=acc, thick] (s0) at (0,0) {s0};
  \node[st] (s1) at (2.3,0) {s1};
  \node[st] (s2) at (4.6,0) {s2};
  \node[st] (s3) at (6.9,0) {s3};
  \draw[->, thick] (s0) -- (s1);
  \draw[->, thick] (s1) -- (s2);
  \draw[->, thick] (s2) -- (s3);
  \node[acc, anchor=south, font=\scriptsize] at (0,0.6) {I = 1};
  \foreach \x in {2.3,4.6,6.9} \node[anchor=south, font=\scriptsize] at (\x,0.6) {I = 0};
  % followon values decaying
  \node[red, anchor=north, font=\scriptsize] at (0,-0.6) {F = 1.0};
  \node[red, anchor=north, font=\scriptsize] at (2.3,-0.6) {F = 0.8};
  \node[red, anchor=north, font=\scriptsize] at (4.6,-0.6) {F = 0.6};
  \node[red, anchor=north, font=\scriptsize] at (6.9,-0.6) {F = 0.5};
  \node[red, anchor=west, font=\scriptsize] at (7.6,0) {emphasis carried forward};
\end{tikzpicture}
$$

$$
% caption: The two stability strategies for traces. Gradient-TD (GTD/GQ) adds a
% second weight vector v and a correction term to follow a true gradient on the
% projected Bellman error. Emphatic-TD keeps one weight vector but scales the
% trace by an emphasis M built from the followon trace F and interest I. Both take
% the unstable semi-gradient trace method and return the off-policy convergence
% guarantee.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=30mm, minimum height=13mm, align=center, font=\scriptsize},
  hub/.style={draw, thick, minimum width=34mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[hub, draw=red, text=red] (unstable) at (0,2.3) {semi-gradient trace\\(unstable of\/f-policy)};
  \node[box, draw=acc] (grad) at (-3.3,-0.2) {Gradient-TD\\GTD(lambda), GQ(lambda)\\second vector v + correction};
  \node[box, draw=acc] (emph) at (3.3,-0.2) {Emphatic-TD\\ETD(lambda)\\emphasis M, follo\/won F};
  \node[hub, draw=acc, text=acc] (stable) at (0,-2.5) {stable of\/f-policy\\with traces};
  \draw[->, thick] (unstable) -- (grad);
  \draw[->, thick] (unstable) -- (emph);
  \draw[->, acc, thick] (grad) -- (stable);
  \draw[->, acc, thick] (emph) -- (stable);
\end{tikzpicture}
$$

The two strategies differ even on-policy. With every $\rho_t = 1$, Emphatic
TD($\lambda$) is _not_ identical to conventional TD($\lambda$), and the difference
matters for guarantees: Emphatic TD($\lambda$) is proven to converge for _all_
state-dependent $\lambda$ functions, whereas TD($\lambda$) is guaranteed
convergent only for _constant_ $\lambda$ — Yu's counterexample shows a variable
$\lambda$ on which TD($\lambda$) fails. So the emphatic weighting is not only an
off-policy correction; it also provides convergence across the full
variable-$\lambda$ family, which the plain method cannot claim.

## Implementation issues

A naive reading makes traces look expensive: every state (or state-action pair)
seems to need its value and its trace updated on every step, which in the tabular
case would be far more work than a one-step method. In practice it is not, because
for typical $\lambda$ and $\gamma$ the traces of almost all states are almost
always essentially zero. Only the handful of recently visited states carry a trace
significantly above zero, and only those need updating to closely approximate the
algorithm.[^sb-impl]

$$
% caption: Sparse traces. For typical $\lambda, \gamma$ the trace decays
% geometrically, so only the few most recently visited states hold a trace above a
% small threshold (shaded, the active set); the rest are negligible and can be
% skipped. A tabular implementation tracks only the active few, costing a small
% constant multiple of a one-step update.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  % axes
  \draw[->, black] (0,0) -- (8.4,0);
  \node[anchor=north east, font=\scriptsize] at (8.4,-0.08) {states, oldest to newest};
  \draw[->, black] (0,0) -- (0,3.2);
  \node[anchor=south, font=\scriptsize, rotate=90] at (-0.3,1.6) {trace magnitude};
  % threshold line
  \draw[black, dashed] (0,0.55) -- (8.0,0.55);
  \node[anchor=west, font=\scriptsize, text=black] at (3.5,0.82) {threshold};
  % bars: rising toward the right (most recent = largest)
  \foreach \i/\h in {0/0.06,1/0.09,2/0.14,3/0.22,4/0.34,5/0.52,6/0.8,7/1.25,8/1.9,9/2.9} {
    \pgfmathsetmacro{\xx}{0.35+\i*0.78}
    \ifdim \h pt>0.55pt
      \fill[acc!25] (\xx-0.22,0) rectangle (\xx+0.22,\h);
      \draw[acc] (\xx-0.22,0) rectangle (\xx+0.22,\h);
    \else
      \fill[black] (\xx-0.22,0) rectangle (\xx+0.22,\h);
      \draw[black] (\xx-0.22,0) rectangle (\xx+0.22,\h);
    \fi
  }
  \node[acc, anchor=south, font=\scriptsize] at (6.6,2.95) {active set (updated)};
  \node[black, anchor=south west, font=\scriptsize] at (0.15,0.95) {negligible (skipped)};
\end{tikzpicture}
$$

Keeping only the significant traces makes the cost of tabular eligibility traces
typically a small multiple — a few times — that of a one-step method, the exact
factor depending on $\lambda$, $\gamma$, and the cost of the other computations.
The tabular case is in a sense the _worst_ case for trace overhead. Once function
approximation is used the relative penalty shrinks: with an artificial neural
network and backpropagation, adding traces roughly _doubles_ the memory and
computation per step, since the trace vector is simply another vector the size of
$\mathbf{w}$. Truncated $\lambda$-return methods offer another efficient route on
conventional computers, though they always demand some extra memory.

There is also the choice of trace _vector_ itself, carried over from the on-policy
lesson but now more consequential off-policy. The **accumulating trace**
$\mathbf{z}_t = \gamma_t \lambda_t \mathbf{z}_{t-1} + \nabla \hat v$ adds the new
gradient on top of the decayed old trace and is the general form derived above. The
**dutch trace** of true online methods folds a step-size term into the increment to
achieve exact forward/backward equivalence. The older **replacing trace**, defined for
binary features by overwriting the visited component to $1$ rather than incrementing
it, guards against the runaway growth accumulating traces can suffer when a feature
recurs quickly. Off-policy, the $\rho_t$ factors amplify traces further, so the
choice of trace vector and the variance it induces is not a cosmetic detail.

| Trace | Update (linear, feature $\mathbf{x}_t$) | Where it comes from |
| --- | --- | --- |
| Accumulating | $\mathbf{z}_t = \gamma_t \lambda_t \mathbf{z}_{t-1} + \mathbf{x}_t$ | general TD($\lambda$); off-policy scales by $\rho_t$ |
| Dutch | $\mathbf{z}_t = \gamma_t \lambda_t \mathbf{z}_{t-1} + (1 - \alpha \gamma_t \lambda_t \mathbf{z}_{t-1}^\top \mathbf{x}_t)\mathbf{x}_t$ | true online TD($\lambda$), exact equivalence |
| Replacing | set trace of active binary feature to $1$ | older method, tames accumulation blowups |

## Retrace and V-trace in deep RL

The off-policy trace of this lesson scales by the raw ratio $\rho_t$, which is
the source of its variance problem: a product of ratios can explode when
the behavior policy rarely takes actions the target policy favors. Two developments
after Sutton and Barto tame that product directly, and both are now standard in
large-scale RL.

**Retrace($\lambda$)** (Munos, Stepleton, Harutyunyan, and Bellemare 2016, _NeurIPS_,
"Safe and Efficient Off-Policy Reinforcement Learning") replaces $\rho_t$ in the
trace with the **clipped** ratio $\lambda \min(1, \rho_t)$. Clipping at $1$ caps the
per-step amplification so the trace can never blow up, no matter how far $b$ is from
$\pi$ — the property Retrace calls _safe_. Yet when the two policies agree the
clipped ratio stays near $1$, so it does not needlessly cut traces short the way
Watkins's Q($\lambda$) does — the property it calls _efficient_. Retrace sits exactly
between the two crude ancestors this lesson built: it keeps the smooth,
importance-sampling-style correction but bounds it, and Munos et al. proved it
convergent (the same paper that established convergence of the tabular Watkins's
Q($\lambda$) this lesson mentions). Sutton and Barto cite this result
directly.[^retrace]

$$
% caption: How Retrace bounds the trace factor. The raw importance ratio (red) rises
% without limit as the target/behavior probability gap grows; Retrace's clipped
% factor min(1, rho) (blue) is capped at 1, so the trace product cannot explode,
% while still tracking rho when the policies nearly agree (rho near 1).
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \draw[black, ->] (0,0) -- (6.4,0) node[anchor=north east, font=\scriptsize] {ratio rho};
  \draw[black, ->] (0,0) -- (0,3.4) node[anchor=south east, font=\scriptsize] {trace factor};
  % raw rho: y = x (up to 3)
  \draw[red, thick] (0,0) -- (3.0,3.0);
  \node[red, anchor=west, font=\scriptsize] at (3.1,3.0) {raw rho};
  % clipped min(1,rho): rises to 1 then flat
  \draw[acc, very thick] (0,0) -- (1.0,1.0) -- (6.0,1.0);
  \node[acc, anchor=south, font=\scriptsize] at (4.2,1.05) {min(1, rho): capped};
  % marker at rho=1
  \draw[black, dashed] (1.0,0) -- (1.0,1.0);
  \node[anchor=north, font=\scriptsize, text=black] at (1.0,-0.05) {rho = 1};
\end{tikzpicture}
$$

**V-trace** (Espeholt et al. 2018, _ICML_, "IMPALA: Scalable Distributed Deep-RL
with Importance Weighted Actor-Learner Architectures") carries the same clipping
into a distributed setting where many actors generate experience on slightly stale
policies while a central learner updates. V-trace uses two separately clipped
ratios: one, $\bar\rho = \min(\bar{c}_\rho, \rho_t)$, weights the temporal-difference
error and controls the fixed point the value function converges to; another,
$c_i = \min(\bar{c}, \rho_i)$, forms the trace product and controls the speed of
convergence. Splitting the two clips lets IMPALA correct for the lag between actor
and learner policies without the variance of an unclipped product — the same
control-variate-and-clip philosophy as Retrace, engineered for throughput at
scale.[^vtrace] Both methods are the direct descendants of the off-policy trace
derived here: keep the $\rho_t$ correction that makes the target right in
expectation, but bound the product that makes its variance dangerous.

## What off-policy traces buy, and where the walls are

Traces plus TD errors give a cheap, incremental way to slide along the whole
continuum from one-step TD to Monte Carlo, and the two generalizations of this
lesson push that 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 efficient off-policy TD($\lambda$) and Expected-Sarsa($\lambda$).
Watkins's Q($\lambda$) cuts the trace on the first non-greedy action; TB($\lambda$)
replaces that hard cut with a smooth target-policy weighting and needs no
importance sampling at all.

Two limits remain. The first is variance: every off-policy method built
on importance sampling inherits its variance, and $\rho_t$ products can be large.
Control variates reduce it; they do not remove it. The second is stability: whenever
$\lambda < 1$ the algorithms bootstrap, so the deadly triad applies, and the plain
semi-gradient forms can diverge under function approximation. That is what
GTD($\lambda$), GQ($\lambda$), and Emphatic TD($\lambda$) are for — the trace-carrying
descendants of the gradient-TD and emphatic fixes, trading a second weight vector or
an emphasis reweighting for the convergence guarantee. Off-policy learning splits
into two halves: correcting the _expected value_ of the targets, which off-policy
traces handle well, and correcting the _distribution_ of updates, which is the hard
half these stable methods address.

The [policy-gradient lesson](/reinforcement-learning/approximation/policy-gradient-methods)
takes a different route to control entirely, optimizing a parameterized policy
directly instead of deriving one from learned values — sidestepping the deadly
triad rather than repairing it.

[^sb-stable]: **Sutton & Barto**, §12.11 — Stable Off-policy Methods with Traces: GTD($\lambda$) (analogue of TDC, update 12.30), GQ($\lambda$) (Gradient-TD control with average next feature $\bar{\mathbf{x}}_t$), HTD($\lambda$) as a strict TD($\lambda$) generalization, and Emphatic TD($\lambda$) with emphasis $M_t$, followon trace $F_t$, and interest $I_t$; Emphatic TD($\lambda$) converges for all state-dependent $\lambda$ while TD($\lambda$) is guaranteed only for constant $\lambda$ (Yu's counterexample).
[^sb-impl]: **Sutton & Barto**, §12.12 — Implementation Issues: for typical $\lambda, \gamma$ almost all traces are near zero, so only the few significant ones need updating; the tabular case is the worst case, and function approximation (e.g. an ANN with backpropagation) roughly doubles per-step memory and computation. §12.13 — Conclusions: eligibility traces as the first line of defense for long-delayed rewards and non-Markov tasks.
[^retrace]: **Munos, Stepleton, Harutyunyan, and Bellemare (2016)**, "Safe and Efficient Off-Policy Reinforcement Learning", _Advances in Neural Information Processing Systems (NeurIPS)_: introduces Retrace($\lambda$), which replaces the importance ratio in the trace with the clipped factor $\lambda\min(1,\rho_t)$ — bounded (safe) yet not needlessly truncating when policies agree (efficient) — and proves convergence, including for the tabular Watkins's Q($\lambda$). Cited by Sutton & Barto (§12.10, Bibliographical Remarks).
[^vtrace]: **Espeholt, Soyer, Munos, et al. (2018)**, "IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures", _ICML_: introduces V-trace, using two separately clipped importance ratios — one weighting the TD error (setting the fixed point) and one forming the trace product (setting convergence speed) — to correct for policy lag between distributed actors and a central learner without unbounded variance.