Eligibility Traces and TD(λ)

From n-step returns to lambda returns

With a fixed value estimate, an n-step return combines rewards over n steps with a bootstrap at the nth state. The infinite-trajectory lambda return is

$G_t^\lambda=(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_t^{(n)},\qquad G_t^\lambda-V(s_t)=\sum_{l=0}^{\infty}(\gamma\lambda)^l\delta_{t+l}.$

A finite episode needs its final remaining Monte Carlo term. An unnormalized truncation of the infinite mixture is not equivalent. Zero lambda gives one-step TD; larger lambda spreads credit farther into the past.

Backward traces

An accumulating tabular trace is $e_t(s)=\gamma\lambda e_{t-1}(s)+\mathbf1\{s=s_t\}$, followed by $V(s)\leftarrow V(s)+\alpha\delta_t e_t(s)$. Linear approximation replaces the indicator with features $\phi_t$. One TD error updates previously active states or features.

Replacing traces treat repeated visits differently. True-online TD(λ) uses Dutch traces and corrections to match a particular online forward view. Classical equivalence with a fixed-weight, offline lambda return must not be generalized to exact stepwise equivalence under arbitrary online parameter changes.

Connection to GAE

GAE uses the same discounted residual sum for advantage estimation; TD(λ) typically updates values. Similar algebra does not make the optimization objectives identical. Smaller lambda increases bootstrap dependence, while larger lambda retains more future noise. Bias also depends on value accuracy, truncation, and the chosen discounted objective.

Implementation boundaries

Reset traces at episode starts and use zero value after genuine termination. Handle external truncation with the actual final observation and appropriate bootstrap. Off-policy traces require the corresponding algorithm’s importance or truncation corrections.

A short-chain MDP can compare forward mixtures and backward updates under fixed weights, before testing the effect of online updates.

Related reading: GAE and sampling.

Selected references from the source notes

• Reference 1
• Reference 2
• Reference 3