TD(lambda) and Eligibility Traces

Recall that the $n$-step return is

truncating the real trajectory after $n$ steps and bootstrapping off the current value estimate $V$ thereafter. Different $n$ trade bias for variance: small $n$ bootstraps heavily (more bias, less variance), large $n$ approaches the Monte Carlo return (less bias, more variance). Rather than picking one $n$, the $\lambda$-return averages over all of them, weighting the $n$-step return by $(1-\lambda)\lambda^{n-1}$:

The weights $(1-\lambda)\lambda^{n-1}$ form a proper probability distribution over $n = 1, 2, 3, \dots$ (they sum to 1), decaying geometrically, so most of the weight sits on small $n$ when $\lambda$ is small and spreads out toward larger $n$ as $\lambda \to 1$. For an episodic task ending at time $T$, once $t+n \ge T$ the $n$-step return becomes just the full Monte Carlo return $G_t$, and the tail of the geometric series after termination is folded into a single term with weight $\lambda^{T-t-1}$:

Setting $\lambda = 0$ collapses the sum to just $G_{t:t+1}$, the ordinary one-step TD target. Setting $\lambda = 1$ makes every finite-$n$-step term vanish (weight $\to 0$) except the final Monte Carlo term, recovering the full return. This is the forward view: at each time $t$, imagine looking ahead through the rest of the episode to compute $G_t^\lambda$, then update

It is a clean theoretical object but not implementable causally — it requires future rewards not yet observed. The backward view produces the same total updates (under offline, end-of-episode application) using only information available up to the present. It introduces an eligibility trace, a scalar per state (tabular case) or a vector per weight (function approximation case), that records how "eligible" each state/feature is for the current TD error. Every step, all traces decay by a factor $\gamma\lambda$, and the trace for the just-visited state (or the gradient of the value function at the current state, in the function-approximation case) is bumped up. The current one-step TD error is then broadcast to every state/feature in proportion to its trace, not just the current state. This mechanism is what "unifies" $n$-step methods: it lets a single scalar per step implicitly account for corrections that would otherwise require $n$-step lookahead for every $n$ simultaneously.

Tabular forward view (conceptual, offline). For each state visited at time $t$ in an episode, compute $G_t^\lambda$ using the full (or truncated, in continuing tasks) reward sequence, then accumulate $\Delta V(S_t) = \alpha[G_t^\lambda - V(S_t)]$ and apply all updates at the end of the episode. This is correct but requires storing the whole trajectory and is $O(T^2)$ naively (an $n$-step return for every $t$ and every $n$).

Tabular backward view with eligibility traces (online, incremental). This is the practical algorithm: ``` Algorithm: TD(lambda) with eligibility traces (tabular, state-value prediction) Input: policy π to evaluate, step size α ∈ (0,1], discount γ, trace decay λ ∈ [0,1] Initialize V(s) arbitrarily for all s (V(terminal) = 0) for each episode: initialize E(s) = 0 for all s # eligibility traces S ← initial state of episode while S is not terminal: A ← action given by π(S) take action A, observe reward R, next state S' δ ← R + γ V(S') - V(S) # one-step TD error E(S) ← E(S) + 1 # accumulating trace at current state for each state s: V(s) ← V(s) + α δ E(s) E(s) ← γ λ * E(s) S ← S' ``` Two design choices deserve names. The trace update `E(S) ← E(S) + 1` is the accumulating trace; an alternative, the replacing trace, instead sets `E(S) ← 1` on revisits (useful when a state can be revisited within an episode, preventing traces from exploding). The inner loop "for each state s" is what makes the tabular version look $O(|S|)$ per step; in practice only states with nonzero trace need updating, and traces decay to numerical zero after $O(\log_{\gamma\lambda} \epsilon)$ steps, so a sparse active-trace list keeps this efficient.

Linear function approximation (the version that matters for scale). Replace the per-state trace with a trace vector $\mathbf{e} \in \mathbb{R}^d$ matching the weight vector $\mathbf{w}$, and replace "visit state $s$" with "accumulate the feature/gradient vector $\nabla_{\mathbf{w}} \hat{v}(S,\mathbf{w})$": ``` Algorithm: Semi-gradient TD(lambda) (linear function approximation) Input: features x(s) ∈ R^d for all s, step size α, discount γ, trace decay λ Initialize weight vector w arbitrarily (e.g., w = 0) for each episode: e ← 0 # eligibility trace vector, e ∈ R^d S ← initial state while S is not terminal: A ← action given by policy take action A, observe reward R, next state S' v_hat_S ← w · x(S) v_hat_S' ← 0 if S' is terminal else w · x(S') δ ← R + γ v_hat_S' - v_hat_S e ← γ λ e + x(S) # decay, then accumulate gradient (= x(S) for linear) w ← w + α δ * e S ← S' ``` Here $\nabla_{\mathbf{w}} \hat{v}(S,\mathbf{w}) = \mathbf{x}(S)$ because $\hat{v}$ is linear in $\mathbf{w}$; with nonlinear function approximators the same recipe generalizes by accumulating the actual gradient into $\mathbf{e}$, which is exactly the bridge into Semi-Gradient Methods with Function Approximation. Note the update touches every component of $\mathbf{w}$ each step through the trace, but if features are sparse (e.g., one-hot or tile coding) this is cheap since $\mathbf{e}$ is sparse too.

Time and space. The backward-view algorithm performs, per environment step, one TD-error computation and one pass over the eligibility trace (and value/weight vector). Tabular: $O(|S|)$ worst case per step if traces are dense, but $O(k)$ if only $k$ states currently have non-negligible trace, since traces decay geometrically as $(\gamma\lambda)^j$ and can be dropped once below a numerical threshold — after $O(\log_{\gamma\lambda}\epsilon)$ steps a trace is negligible. Linear function approximation: $O(d)$ per step where $d$ is the feature dimension, matching plain semi-gradient TD(0) in per-step cost, and $O(d)$ space for the trace vector, an additive constant-factor overhead. Contrast this with a naive forward-view implementation that recomputes $G_t^\lambda$ using $n$-step returns for every $n$ up to episode length: that costs $O(T)$ work per time step and $O(T^2)$ per episode, plus $O(T)$ space to store the trajectory. Eligibility traces reduce this to $O(1)$ extra work per step (beyond ordinary TD) and $O(d)$ space total — no trajectory storage at all. This constant-time-per-step property is exactly why traces make $\lambda$-averaging usable online, in continuing (non-episodic) tasks, and under strict memory budgets such as embedded control.

Correctness — equivalence of forward and backward views (offline case). The central claim is that, summed over an episode, the backward-view weight updates equal the forward-view weight updates, when updates are accumulated and applied only at the end of the episode (the "offline $\lambda$-return algorithm" matches "offline TD($\lambda$)"). Sketch of the argument for the tabular case: fix a state $s$ and expand the total backward-view update to $V(s)$ over an episode,

more precisely, since the trace for $s$ after being set at some visit time $k$ decays by $\gamma\lambda$ each subsequent step,

Swap the order of summation to instead group by $t$: this says every TD error $\delta_t$ contributes to every earlier visited state $s = S_k$ ($k \le t$) with weight $(\gamma\lambda)^{t-k}$. The classical algebraic identity underlying TD($\lambda$) is that a telescoping sum of discounted one-step TD errors reconstructs the $\lambda$-return exactly:

where $\delta_k = R_{k+1} + \gamma V(S_{k+1}) - V(S_k)$ are ordinary TD errors along the trajectory (assuming $V$ is held fixed during the episode, as in the offline setting). This identity is proved by induction on the horizon: expand $G_t^\lambda$ via its recursive definition $G_t^\lambda = R_{t+1} + \gamma\big[(1-\lambda)V(S_{t+1}) + \lambda G_{t+1}^\lambda\big]$, subtract $V(S_t)$, and observe that the recursion telescopes into exactly the discounted sum of one-step errors above, matching term by term with the trace-weighted broadcast performed by the backward-view algorithm. Consequently, summing $\alpha[G_t^\lambda - V(S_t)]$ over all $t$ where $S_t = s$ (the offline forward-view total update to $s$) equals summing $\alpha\, \delta_k \cdot (\gamma\lambda)^{k-t}$ contributions collected by the eligibility trace — which is precisely $\Delta V(s)$ above. This establishes the forward/backward equivalence exactly, not approximately, for offline updating.

Online updating and the approximation it introduces. In practice, the backward-view algorithm updates $V$ (or $\mathbf{w}$) immediately at each step rather than waiting for episode end. This changes the effective target slightly, because later TD errors $\delta_k$ are computed against an already-updated $V$, not the fixed $V$ used in the offline derivation. The online and offline versions therefore only coincide exactly as $\alpha \to 0$; for finite step sizes they are close but not identical, a discrepancy resolved exactly by the more intricate true online TD($\lambda$) algorithm, which reproduces the online forward-view $\lambda$-return exactly using a modified ("dutch") trace update. Standard TD($\lambda$) with accumulating or replacing traces sacrifices this exact equivalence for simplicity, and in practice the difference is small for reasonable step sizes.

Convergence. For tabular prediction under a fixed policy, with standard step-size (Robbins–Monro) conditions $\sum_t \alpha_t = \infty$, $\sum_t \alpha_t^2 < \infty$, TD($\lambda$) converges to the true value function $v_\pi$ with probability 1, for any $\lambda \in [0,1]$, since it remains a stochastic approximation to a contraction mapping (the $\lambda$-weighted Bellman operator is a contraction in the same way the one-step Bellman operator is). With linear function approximation and on-policy sampling, semi-gradient TD($\lambda$) converges to a fixed point whose value error is bounded relative to the best representable approximation, with the bound tightening as $\lambda \to 1$ (approaching the Monte Carlo/least-squares projection) at the cost of higher variance — the same bias–variance tension discussed under Bootstrapping and the Bias-Variance Tradeoff.

Consider a tiny 4-state random walk: states $A - B - C - D - \text{Terminal}$, all transitions deterministic left-to-right, reward $0$ everywhere except $+1$ entering the terminal state, $\gamma = 1$. Initialize $V(A)=V(B)=V(C)=V(D) = 0.5$. One episode is observed: $A \to B \to C \to D \to \text{Terminal}$, rewards $0,0,0,1$.

Step-by-step backward-view trace with $\alpha = 0.5$, $\lambda = 0.5$, $\gamma = 1$ (accumulating traces):

(Traces are shown after the decay-then-bump for the just-visited state; note only the final step has nonzero TD error here because all intermediate value estimates were already consistent at $0.5$, deliberately chosen so the single informative error at termination is the only source of learning — this isolates how that one signal fans out backward.) Final values after this episode:

Cross-check against the forward view. The $\lambda$-return for $t=0$ (state $A$) with $\lambda = 0.5$, using $G_{0:1}=0.5$, $G_{0:2}=0.5$, $G_{0:3}=0.5$, $G_{0:4}=G_0=1$ (all intermediate $n$-step returns bootstrap off $V=0.5$ except the full return which sees the actual terminal reward):

Using the episodic form with $T=4$:

computing directly: $(1-\lambda)[\lambda^0 G_{0:1} + \lambda^1 G_{0:2} + \lambda^2 G_{0:3}] + \lambda^3 G_0 = 0.5[0.5 + 0.25\cdot0.5 + 0.125\cdot 0.5] + 0.125 \cdot 1 = 0.5[0.5+0.125+0.0625] + 0.125 = 0.5(0.6875) + 0.125 = 0.34375+0.125=0.46875$. Then $\Delta V(A) = \alpha[G_0^\lambda - V(A)] = 0.5[0.46875 - 0.5] = -0.0156$ — this disagrees with the backward-view result above ($+0.0313$) because backward-view here is applied online (updates mid-episode change later $\delta$'s implicitly through the trace mechanics as derived), while this forward computation assumed a fixed $V=0.5$ throughout (the offline setting). Re-deriving offline (freeze $V$ at $0.5$ throughout, apply forward-view updates only at episode end, matching the backward-view sum-of-TD-errors identity exactly) recovers agreement: summing $(\gamma\lambda)^{k-0}\delta_k$ over $k=0,\dots,3$ with all $\delta_k = 0$ except $\delta_3 = 0.5$ gives $(\gamma\lambda)^3 \cdot 0.5 = 0.125 \cdot 0.5 = 0.0625$, and $\alpha \cdot 0.0625 = 0.03125$ — matching the backward-view update to $V(A)$ found in the table. The apparent mismatch above came from mixing an online backward trace with a naively-recomputed forward return; the theorem guarantees equivalence specifically in the offline (frozen-$V$-during-episode) setting, exactly as the correctness argument states.

TD($\lambda$) and eligibility traces emerged from work connecting animal learning theory, dynamic programming, and stochastic approximation, culminating in the temporal-difference learning framework that underlies most of modern model-free reinforcement learning.

Eligibility traces and TD($\lambda$)-style credit assignment appear wherever an agent must learn from delayed, sparse rewards without waiting for episodes to finish. Classic game-playing systems such as Tesauro's TD-Gammon used TD($\lambda$) with a neural network value function to reach superhuman backgammon play, one of the earliest large-scale demonstrations that bootstrapped, multi-step credit assignment scales. Actor-critic architectures used in robotics and simulated control (walking, manipulation, locomotion) routinely use eligibility-trace-style multi-step targets — including the closely related n-Step Bootstrapping Methods and GAE (generalized advantage estimation) in policy-gradient methods — as a direct descendant of the $\lambda$-return idea for variance reduction. Traces are especially valuable in continuing, non-episodic control tasks such as process control or continual robot operation, where there is no "end of episode" to wait for and only the $O(1)$-per-step backward view is feasible. The conceptual machinery here — a decaying memory of recent activity broadcasting a scalar error signal backward — is also the direct ancestor of the eligibility-trace ideas used in biologically-inspired learning rules and in extending value-based methods to deep networks, the topic taken up next under Semi-Gradient Methods with Function Approximation.

Ask the tutor: How does true online TD(λ) modify the eligibility trace update to make the online and offline views exactly equivalent?