Stable Off-Policy Methods with Traces

This builds on 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: 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.¹ 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 $0$) and a second step size $\beta >0$,

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 $\epsilon$-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,

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,

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$,

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.

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.²

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.

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.³

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.⁴ 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 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.