Off-Policy Eligibility Traces

The eligibility-traces lesson 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 itself, and convergence is no longer guaranteed. Naming the methods that restore stability is the job of the next lesson; 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.¹ 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,

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.

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

A worked return. Take rewards $R_{t+1},R_{t+2},R_{t+3},\dots =1,1,1,\dots$ 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

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,

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,

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

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.² The per-step ratio is the usual

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,

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.

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

the return is approximately

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

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,

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.

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,

with the expectation-form action-value TD error

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

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$).⁴$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,

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,

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.

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.