--- title: "True Online TD(λ) and Sarsa(λ)" module: Approximate Solution Methods moduleNumber: 3 lessonNumber: 8 order: 308 summary: > Plain TD(λ) makes the forward and backward views nearly agree; this lesson closes the gap. True online TD(λ) uses a dutch trace and a small correction term to produce exactly the same weight sequence as the online λ-return algorithm, at the same memory and only a constant factor more compute — the sharpest statement of the forward/backward duality. The whole apparatus then lifts to control unchanged: Sarsa(λ) threads a single delayed reward back along an entire trajectory in one sweep, and the λ-weighting reappears in modern deep RL as generalized advantage estimation. topics: [Approximation] sources: - book: Sutton & Barto ref: "Ch. 12 — Eligibility Traces; §12.5 True Online TD(λ); §12.6 Dutch Traces" - book: Sutton & Barto ref: "§12.7 Sarsa(λ)" --- This builds on [eligibility traces](/reinforcement-learning/approximation/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**:[^sb-tot] 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 $$ \mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha\,\delta_t\,\mathbf{z}_t + \alpha\,\big( \mathbf{w}_t^\top \mathbf{x}_t - \mathbf{w}_{t-1}^\top \mathbf{x}_t \big)\,( \mathbf{z}_t - \mathbf{x}_t ), $$ 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. > **Theorem (Exact equivalence).** True online TD(λ) produces exactly the same > sequence of weight vectors $\mathbf{w}_0, \ldots, \mathbf{w}_T$ as the online > λ-return algorithm, for linear function approximation. Its memory footprint > equals that of plain TD(λ); its per-step cost is about 50% higher (one extra > inner product in the trace update), but stays $O(d)$. 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, $$ \mathbf{w}_{t+1} \;\doteq\; \mathbf{w}_t + \alpha \big[\, G_t^\lambda - \hat q(S_t, A_t, \mathbf{w}_t) \,\big]\, \nabla \hat q(S_t, A_t, \mathbf{w}_t), $$ 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, $$ \delta_t \;\doteq\; R_{t+1} + \gamma\, \hat q(S_{t+1}, A_{t+1}, \mathbf{w}_t) - \hat q(S_t, A_t, \mathbf{w}_t), $$ and a trace accumulated over state–action gradients, $$ \mathbf{z}_{-1} \doteq \mathbf{0}, \qquad \mathbf{z}_t \;\doteq\; \gamma\lambda\, \mathbf{z}_{t-1} + \nabla \hat q(S_t, A_t, \mathbf{w}_t), \qquad 0 \le t \le T. $$ 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? $$ % caption: Traces in a gridworld. Left: the path an agent takes in one episode; % all rewards are zero except at the goal $G$. One-step Sarsa (center-left) % increments only the last action, the one that entered $G$. n-step Sarsa % (center-right) increments the last $n$ actions equally. Sarsa(λ) (right) % increments every action back to the episode's start, each faded by recency — % the arrows shrink with distance from $G$. The fading strategy is often best. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{2348F2} % ---------- panel 1: path taken ---------- \begin{scope} \foreach \x in {0,...,6} \draw[black] (\x*0.4,0) -- (\x*0.4,2.4); \foreach \y in {0,...,6} \draw[black] (0,\y*0.4) -- (2.4,\y*0.4); \node[anchor=south, font=\scriptsize] at (1.2,2.5) {path taken}; \node[font=\scriptsize] at (1.8,1.0) {G}; \draw[acc, thick, ->] (0.5,1.8) -- (0.85,1.8); \draw[acc, thick, ->] (0.9,1.8) -- (0.9,1.45); \draw[acc, thick, ->] (0.9,1.4) -- (1.25,1.4); \draw[acc, thick, ->] (1.3,1.4) -- (1.3,1.05); \draw[acc, thick, ->] (1.3,1.0) -- (1.62,1.0); \end{scope} % ---------- panel 2: one-step ---------- \begin{scope}[xshift=3.3cm] \foreach \x in {0,...,6} \draw[black] (\x*0.4,0) -- (\x*0.4,2.4); \foreach \y in {0,...,6} \draw[black] (0,\y*0.4) -- (2.4,\y*0.4); \node[align=center, anchor=south, font=\scriptsize] at (1.2,2.5) {one-step Sarsa}; \node[font=\scriptsize] at (1.8,1.0) {G}; \draw[acc, thick, ->] (1.3,1.0) -- (1.62,1.0); \end{scope} % ---------- panel 3: n-step ---------- \begin{scope}[xshift=6.6cm] \foreach \x in {0,...,6} \draw[black] (\x*0.4,0) -- (\x*0.4,2.4); \foreach \y in {0,...,6} \draw[black] (0,\y*0.4) -- (2.4,\y*0.4); \node[align=center, anchor=south, font=\scriptsize] at (1.2,2.5) {n-step Sarsa}; \node[font=\scriptsize] at (1.8,1.0) {G}; \draw[acc, thick, ->] (0.9,1.4) -- (1.25,1.4); \draw[acc, thick, ->] (1.3,1.4) -- (1.3,1.05); \draw[acc, thick, ->] (1.3,1.0) -- (1.62,1.0); \end{scope} % ---------- panel 4: Sarsa(lambda) ---------- \begin{scope}[xshift=9.9cm] \foreach \x in {0,...,6} \draw[black] (\x*0.4,0) -- (\x*0.4,2.4); \foreach \y in {0,...,6} \draw[black] (0,\y*0.4) -- (2.4,\y*0.4); \node[align=center, anchor=south, font=\scriptsize] at (1.2,2.5) {Sarsa(lambda)}; \node[font=\scriptsize] at (1.8,1.0) {G}; % fading arrows: shrink and lighten with distance from G \draw[acc!45, thin, ->] (0.55,1.8) -- (0.8,1.8); \draw[acc!60, ->] (0.9,1.75) -- (0.9,1.5); \draw[acc!75, ->] (0.95,1.4) -- (1.22,1.4); \draw[acc!88, thick, ->] (1.3,1.35) -- (1.3,1.08); \draw[acc, thick, ->] (1.3,1.0) -- (1.62,1.0); \end{scope} \end{tikzpicture} $$ 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. ```algorithm caption: $\textsc{Sarsa}(\lambda)$ — estimate $\hat q \approx q_\ast$ input: a differentiable $\hat q$ with $\hat q(\text{terminal},\cdot,\cdot) = 0$ $\mathbf{w} \gets$ arbitrary (e.g. $\mathbf{0}$) for each episode do initialize $S$; choose $A \sim \varepsilon\text{-greedy}(\hat q(S,\cdot,\mathbf{w}))$ $\mathbf{z} \gets \mathbf{0}$ repeat take action $A$, observe $R$, $S'$ $\mathbf{z} \gets \gamma\lambda\,\mathbf{z} + \nabla\hat q(S,A,\mathbf{w})$ choose $A' \sim \varepsilon\text{-greedy}(\hat q(S',\cdot,\mathbf{w}))$ $\delta \gets R + \gamma\,\hat q(S',A',\mathbf{w}) - \hat q(S,A,\mathbf{w})$ $\mathbf{w} \gets \mathbf{w} + \alpha\,\delta\,\mathbf{z}$ $S \gets S'$ $A \gets A'$ until $S$ is terminal ``` ## 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_.[^true-online] 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] 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.[^deep-traces] 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](/reinforcement-learning/approximation/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. [^sb-tot]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), §12.5 — True Online TD(λ): the online λ-return algorithm and its exact backward implementation with the dutch trace (12.11); §12.6 — Dutch Traces in Monte Carlo Learning: traces arising without TD; §12.7 — Sarsa(λ): the action-value TD error (12.16), the state–action trace, and the gridworld example (Example 12.1). [^true-online]: **van Seijen, H. & Sutton, R. S.** (2014), "True online TD(λ)", _ICML_. **van Seijen, H., Mahmood, A. R., Pilarski, P. M., Machado, M. C. & Sutton, R. S.** (2016), "True online temporal-difference learning", _Journal of Machine Learning Research_ 17, 1–40 — the exact equivalence of true online TD(λ) and the online λ-return algorithm for linear function approximation, and the empirical gains over accumulating and replacing traces. [^gae]: **Schulman, J., Moritz, P., Levine, S., Jordan, M. & Abbeel, P.** (2016), "High-dimensional continuous control using generalized advantage estimation", _ICLR_ — GAE as the exponentially $(\gamma\lambda)$-weighted sum of TD residuals, with $\lambda$ trading bias against variance; the default advantage estimator in PPO. [^deep-traces]: **Kapturowski, S., Ostrovski, G., Quan, J., Munos, R. & Dabney, W.** (2019), "Recurrent experience replay in distributed reinforcement learning" (R2D2), _ICLR_ — n-step and sequence-based returns computed over stored trajectories rather than propagated by an online trace vector.