True Online TD(λ) and Sarsa(λ)

This builds on eligibility traces, which introduced the λ-return (the forward view) and TD(λ) with its trace vector (the backward view), and showed that the two nearly coincide — plain TD(λ)'s updates approximate the offline λ-return algorithm's but do not equal them, and the gap widens with the step size. This lesson closes that gap exactly, then carries the whole trace apparatus over to control.

True online TD(λ)

The forward-view ideal that TD(λ) approximates is the online λ-return algorithm:¹ on every step, go back and redo all the updates from the start of the current episode, each time using the longest λ-return the newly extended data allows. It is fully online and, at the end of an episode, its bootstrapping weights have absorbed strictly more information than the offline algorithm's — so it performs a shade better than either the offline algorithm or plain TD(λ). Its one defect is cost: each step reprocesses the whole episode so far.

For the linear case, that expensive forward algorithm has an exact, cheap backward implementation — true online TD(λ). The name marks it as truer to the online λ-return ideal than plain TD(λ) is. Writing ${\mathbf{x}}_t\doteq \mathbf{x}(S_t)$, its weight update is

with the dutch trace introduced above in place of the accumulating trace. The extra $\alpha ({\mathbf{w}}_t^{\top }{\mathbf{x}}_t-{\mathbf{w}}_{t-1}^{\top }{\mathbf{x}}_t)({\mathbf{z}}_t-{\mathbf{x}}_t)$ term in the weight update is a small correction that yields the exact equivalence: with it, the online forward view and the trace-based backward view compute the same weights.

The forward view (an average over all future returns, redone from scratch every step) looks unimplementable online; the backward view (one trace vector and a scalar error) is cheap and fully incremental. Yet the two compute identical weights — the sharpest statement of the forward/backward duality. Traces are not specific to TD: the same dutch-trace machinery arises in ordinary Monte Carlo prediction once an $O(d)$-per-step implementation is required, which suggests traces are a general mechanism for learning long-term predictions efficiently.

Sarsa(λ): control

Almost nothing changes to move from prediction to control. Swap state values $\hat{v}(s,\mathbf{w})$ for action values $\hat{q}(s,a,\mathbf{w})$, and the λ-return, the trace, and the update all carry over. The forward view aims each step at the action-value λ-return,

with $G_t^{\lambda }$ now built from action-value $n$-step returns. The temporal-difference method that approximates it is Sarsa(λ). It has the same weight update as TD(λ), ${\mathbf{w}}_{t+1}={\mathbf{w}}_t+\alpha {\delta }_t{\mathbf{z}}_t$, but with the action-value TD error,

and a trace accumulated over state–action gradients,

The trace now decays over recently visited state–action pairs, and a single TD error updates the value of every recent pair in proportion to its surviving trace.

Consider a gridworld example. An agent wanders under all-zero rewards until it reaches a goal cell $G$, where it collects the only reward of the episode. After that one successful episode, what has each method learned?

One-step Sarsa strengthens exactly one action value, the step that entered $G$; every earlier action on the successful path learns nothing this episode. An $n$-step method credits the last $n$ actions equally. Sarsa(λ) credits every action all the way back to the episode's start, faded by recency — the nearer to $G$, the stronger the increment. Spreading credit along the whole path, weighted toward the recent end, propagates a single delayed reward much further per episode than either alternative, and the fading strategy is usually the best of the three. On tasks like Mountain Car, true online Sarsa(λ) — the control counterpart of true online TD(λ), using state–action features — outperforms plain Sarsa(λ) with either accumulating or replacing traces.

Exact online traces and λ in deep RL

The trace idea has several modern descendants.

True online TD(λ) as a published result. The exact-equivalence algorithm above is van Seijen & Sutton (2014), True online TD(λ), ICML, later expanded in van Seijen et al. (2016), True online temporal-difference learning, JMLR.² Their result is the precise one stated here: for linear function approximation, true online TD(λ) with the dutch trace produces the identical weight sequence to the online λ-return algorithm, at the same $O(d)$ memory and only a constant-factor more compute. Empirically they showed it matching or beating plain TD(λ) with accumulating or replacing traces across standard benchmarks, and true online Sarsa(λ) doing the same for control — the outperformance this lesson cites.

Generalized advantage estimation. The λ-weighting reappears at the center of modern policy-gradient methods as generalized advantage estimation (GAE), Schulman et al. (2016), High-dimensional continuous control using generalized advantage estimation, ICLR.³ GAE forms an advantage estimate as an exponentially weighted average of $k$-step TD residuals, ${\hat{A}}_t={\sum }_{l\ge 0}(\gamma \lambda {)}^l{\delta }_{t+l}$ — the same geometric $\lambda$ weighting as the λ-return, applied to advantages rather than returns. The parameter $\lambda$ trades bias against variance exactly as it does here: $\lambda =0$ gives the low-variance, high-bias one-step estimate, $\lambda \to 1$ the high-variance Monte Carlo estimate. GAE is the default advantage estimator inside PPO and is where most practitioners meet $\lambda$ today.

Traces and deep networks. The dutch trace requires linear features, so it does not transfer directly to deep networks, where the accumulating trace is the only option and its interaction with nonlinear approximation is delicate. Practical deep-RL systems mostly abandon per-step traces in favor of truncated or batched λ-returns computed over short rollouts — the same forward-view averaging, evaluated on a fixed horizon inside a minibatch rather than propagated by a running trace vector. Recurrent architectures like R2D2 (Kapturowski et al., 2019, Recurrent experience replay in distributed reinforcement learning, ICLR) compute n-step and λ-style returns over stored sequences.⁴ The forward view, which the trace was invented to implement online, turns out to be the more portable half of the duality once the approximator goes nonlinear.

What the trace unified

Eligibility traces achieve the same unification as $n$-step methods, with a better mechanism. The λ-return is the forward view: average all $n$-step returns under a geometric $\lambda$ weighting, so $\lambda =0$ recovers one-step TD and $\lambda =1$ recovers Monte Carlo, and an intermediate $\lambda$ usually beats both. The trace vector ${\mathbf{z}}_t$ is the backward view: one short-term memory that turns that look-ahead average into an online update, broadcasting each TD error back across recently visited states with the memory of a single feature vector instead of the last $n$. Plain TD(λ) makes the two views nearly agree; true online TD(λ), through the dutch trace, makes them agree exactly. And the whole apparatus lifts to control unchanged — Sarsa(λ) is TD(λ) over state–action pairs, threading a single reward back along an entire trajectory in one sweep.

The next lesson leaves value estimation behind for policy-gradient methods, which parameterize and optimize the policy directly rather than deriving it from learned values — a different answer to the same control problem.