Chapter 12: Eligibility Traces | 第十二章：资格迹

📑 目录 / Table of Contents

12.1 λ-回报 / The λ-return
12.2 TD(λ)
12.3 n步截断λ-回报方法
12.4 重做更新：在线λ-回报算法
12.5 真正的在线TD(λ)
12.6 *蒙特卡罗学习中的Dutch迹
12.7 Sarsa(λ)
12.8 可变λ和γ
12.9 *带控制变量的Off-policy迹
12.10 Watkins的Q(λ)到Tree-Backup(λ)
12.11 稳定的Off-policy迹方法
12.12 实现问题 / Implementation Issues
12.13 结论 / Conclusions

引言 / Introduction

Eligibility traces are one of the basic mechanisms of reinforcement learning. They unify and generalize TD and Monte Carlo methods, producing a family of methods spanning from Monte Carlo (λ=1) to one-step TD (λ=0). The mechanism is a short-term memory vector z_t ∈ ℝ^d that parallels the long-term weight vector w_t.

资格迹是强化学习的基本机制之一。它统一并泛化了TD和蒙特卡罗方法，产生从蒙特卡罗(λ=1)到单步TD(λ=0)的方法族。其机制是一个短期记忆向量z_t∈ℝ^d，与长期权重向量w_t并行。

The primary computational advantage: only a single trace vector is required rather than a store of the last n feature vectors. Learning occurs continually and uniformly in time rather than being delayed. The forward view looks ahead to future rewards; the backward view uses eligibility traces to assign credit to past states.

主要计算优势：只需要单个迹向量而非存储最近n个特征向量。学习在时间上持续均匀进行而非延迟。前向视图展望未来奖励；后向视图使用资格迹将功劳分配给过去的状态。

12.1 λ-回报 / The λ-return

A valid update can be done toward any average of n-step returns for different n's, as long as weights are positive and sum to 1. Such an update is called a compound update. The TD(λ) algorithm averages all n-step updates, each weighted proportionally to λⁿ⁻¹, normalized by (1−λ).

只要权重为正且总和为1，就可以对不同n的n步回报进行平均来执行有效更新。这种更新称为复合更新。TD(λ)算法对所有n步更新进行平均，每个更新按λⁿ⁻¹加权，并用(1−λ)归一化。

G_t^λ = (1−λ) Σ_n=1^∞ λⁿ⁻¹ G_t:t+n

When λ=1, the λ-return reduces to the conventional Monte Carlo return G_t. When λ=0, it reduces to the one-step return G_t:t+1. The offline λ-return algorithm makes updates at the end of the episode using this target:

当λ=1时，λ-回报退化为传统蒙特卡罗回报G_t。当λ=0时，退化为单步回报G_t:t+1。离线λ-回报算法在回合结束时使用此目标进行更新：

w_t+1 = w_t + α [G_t^λ − v̂(S_t, w_t)] ∇v̂(S_t, w_t)

12.2 TD(λ)

TD(λ) improves over the offline λ-return algorithm in three ways: (1) updates on every step, (2) computations equally distributed in time, (3) applicable to continuing problems. The eligibility trace is initialized to zero, incremented by the value gradient, then fades:

TD(λ)在三个方面改进离线λ-回报算法：(1)每步更新，(2)计算在时间上均匀分布，(3)适用于持续性任务。资格迹初始化为零，按价值梯度递增，然后衰减：

z₋₁ = 0
z_t = γλz_t−1 + ∇v̂(S_t, w_t)

The TD error: δ_t = R_t+1 + γv̂(S_t+1, w_t) − v̂(S_t, w_t). The weight update:

TD误差：δ_t=R_t+1+γv̂(S_t+1,w_t)−v̂(S_t,w_t)。权重更新：

w_t+1 = w_t + αδ_tz_t

Semi-gradient TD(λ) for estimating v̂ ≈ v_π ──────────────────────────────────────────── Input: policy π, differentiable v̂: S⁺ × ℝ^d → ℝ Parameters: step size α > 0, trace decay rate λ ∈ [0,1] Initialize w arbitrarily Loop for each episode: Initialize S z ← 0 (d-dimensional vector) Loop for each step: Choose A ~ π(·|S) Take action A, observe R, S' z ← γλz + ∇v̂(S, w) δ ← R + γv̂(S', w) − v̂(S, w) w ← w + αδz S ← S' until S' is terminal

If λ=0, TD(λ) reduces to one-step TD(0). For λ=1 (TD(1)), traces don't decay → Monte Carlo behavior for undiscounted episodic tasks. TD(1) can be performed incrementally and online, unlike classical MC methods. Linear TD(λ) converges on-policy with VE bound:

如果λ=0，TD(λ)退化为单步TD(0)。当λ=1(TD(1))时，迹不衰减→无折扣回合任务的蒙特卡罗行为。TD(1)可以增量在线执行，不同于经典MC方法。线性TD(λ)在on-policy下收敛，VE界：

VE(w_∞) ≤ (1−γλ)/(1−γ) · min_w VE(w)

12.3 n步截断λ-回报方法 / n-step Truncated λ-return Methods

The offline λ-return is not known until episode end. We can truncate after n steps, replacing missing rewards with estimated values:

离线λ-回报直到回合结束才知道。可以在n步后截断，用估计值替代缺失奖励：

G_t:h^λ = (1−λ) Σ_n=1^h−t−1 λⁿ⁻¹ G_t:t+n + λ^h−t−1 G_t:h

This gives rise to Truncated TD(λ) (TTD(λ)). The k-step λ-return can be written as:

这产生了截断TD(λ)（TTD(λ)）。k步λ-回报可写为：

G_t:t+k^λ = v̂(S_t, w_t−1) + Σ_i=t^t+k−1 (γλ)^i−t δ'_i

where δ'_t = R_t+1 + γv̂(S_t+1, w_t) − v̂(S_t, w_t−1). Efficient implementation: per-step computation does not scale with n.

其中δ'_t=R_t+1+γv̂(S_t+1,w_t)−v̂(S_t,w_t−1)。高效实现：逐步计算不随n缩放。

12.4 重做更新：在线λ-回报算法 / Online λ-return Algorithm

Idea: on each time step, go back and redo all updates since the beginning of the episode with the new data. Always use the latest horizon for the truncated λ-return target. Multiple passes over the episode, each at a different horizon h:

思想：在每个时间步，回溯并重做自回合开始以来的所有更新，使用新数据。始终使用最新截断λ-回报目标。对回合进行多次遍历，每次在不同水平h：

w_t+1^h = w_t^h + α [G_t:h^λ − v̂(S_t, w_t^h)] ∇v̂(S_t, w_t^h)

Fully online but computationally complex — passes over the episode on every step. Performs subtly better than the offline algorithm at the end of the episode because bootstrapping uses a more informed weight vector.

完全在线但计算复杂——每步都遍历回合。在回合结束时比离线算法表现略好，因为自举使用了更有信息的权重向量。

12.5 真正的在线TD(λ) / True Online TD(λ)

The online λ-return algorithm is currently the best performing TD algorithm. For linear function approximation, there is an exact efficient implementation called True Online TD(λ):

在线λ-回报算法是目前表现最好的TD算法。对于线性函数近似，有一个精确高效实现称为真正的在线TD(λ)：

w_t+1 = w_t + αδ_tz_t + α(w_t^Tx_t − w_t−1^Tx_t)(z_t − x_t)

z_t = γλz_t−1 + (1 − αλz_t−1^Tx_t)x_t

True Online TD(λ) for estimating w^Tx ≈ v_π ──────────────────────────────────────────── Input: policy π, feature function x: S⁺ → ℝ^d Parameters: step size α > 0, trace decay rate λ ∈ [0,1] Initialize w ∈ ℝ^d Loop for each episode: Initialize state, get feature vector x z ← 0, V_old ← 0 Loop for each step: Choose A ~ π, take A, observe R, x' V ← w^Tx, V' ← w^Tx' δ ← R + γV' − V z ← γλz + (1 − αλz^Tx)x w ← w + α(δ + V − V_old)z − α(V − V_old)x V_old ← V', x ← x' until x' = 0 (terminal)

The eligibility trace (12.11) is called a dutch trace. It produces exactly the same weight vector sequence as the online λ-return algorithm with O(d) per-step complexity (50% more than TD(λ)). Earlier replacing traces are crude approximations to dutch traces.

资格迹(12.11)称为dutch迹。它产生与在线λ-回报算法完全相同的权重向量序列，逐步复杂度O(d)（比TD(λ)多50%）。早期的替换迹是dutch迹的粗略近似。

💡 三种迹类型： 累积迹（TD(λ)使用）、Dutch迹（真正的在线TD(λ)使用，理论基础最好）、替换迹（仅适用于表格/二值特征，已被dutch迹取代）。

12.6 *蒙特卡罗学习中的Dutch迹 / Dutch Traces in MC Learning

Eligibility traces arise even in Monte Carlo learning — they have nothing specific to do with TD. The linear MC algorithm (LMS rule) makes updates only at episode end. By algebraic manipulation, we can derive an equivalent incremental algorithm using dutch traces with O(d) per-step complexity:

资格迹甚至出现在蒙特卡罗学习中——与TD无特定关系。线性MC算法（LMS规则）仅在回合结束时更新。通过代数推导，可以得到使用dutch迹的等价增量算法，逐步复杂度O(d)：

w_T = a_T−1 + αGz_T−1

where a_t and z_t are auxiliary vectors updated incrementally. The trace z_t is exactly the dutch trace with γλ=1. This shows eligibility traces are more fundamental than TD — they arise whenever one tries to learn long-term predictions efficiently.

其中a_t和z_t是增量更新的辅助向量。迹z_t恰好是γλ=1时的dutch迹。这表明资格迹比TD更基本——只要试图高效学习长期预测就会出现。

12.7 Sarsa(λ)

Extension to action values uses the action-value form of n-step returns. Sarsa(λ) has the same update rule as TD(λ): w_t+1 = w_t + αδ_tz_t, but with action-value TD error and eligibility trace:

向动作价值的扩展使用n步回报的动作价值形式。Sarsa(λ)具有与TD(λ)相同的更新规则：w_t+1=w_t+αδ_tz_t，但使用动作价值TD误差和资格迹：

δ_t = R_t+1 + γq̂(S_t+1, A_t+1, w_t) − q̂(S_t, A_t, w_t)
z_t = γλz_t−1 + ∇q̂(S_t, A_t, w_t)

Sarsa(λ) with binary features and linear function approximation ──────────────────────────────────────────── Input: feature function F(s,a), policy π Parameters: α > 0, λ ∈ [0,1] Initialize w, z ∈ ℝ^d Loop for each episode: Initialize S, choose A ~ π(·|S) or ε-greedy z ← 0 Loop for each step: Take A, observe R, S' δ ← R For i in F(S, A): δ ← δ − w_i; z_i ← z_i + 1 (or 1 for replacing) If S' terminal: w ← w + αδz → next episode Choose A' ~ π(·|S') or ε-greedy For i in F(S', A'): δ ← δ + γw_i w ← w + αδz z ← γλz S ← S', A ← A'

Example 12.1: Traces in Gridworld. One-step methods increment only the last action value; n-step methods equally increment the last n actions; eligibility trace methods update all action values with fading credit. The fading strategy is often the best.

例12.1：Gridworld中的迹。单步方法只增加最后一个动作价值；n步方法均匀增加最后n个动作；资格迹方法以衰减功劳更新所有动作价值。衰减策略通常最好。

True Online Sarsa(λ) extends True Online TD(λ) to action values using state-action features x_t=x(S_t,A_t). It outperforms regular Sarsa(λ) with both accumulating and replacing traces on Mountain Car.

真正的在线Sarsa(λ)使用状态-动作特征x_t=x(S_t,A_t)将真正的在线TD(λ)扩展到动作价值。在Mountain Car上优于使用累积迹和替换迹的常规Sarsa(λ)。

12.8 可变λ和γ / Variable λ and γ

Generalize bootstrapping and discounting to state-action dependent functions: λ_t=λ(S_t,A_t) and γ_t=γ(S_t). The termination function γ(s) is particularly significant — it changes the return itself:

将自举和折扣泛化为状态-动作相关函数：λ_t=λ(S_t,A_t)和γ_t=γ(S_t)。终止函数γ(s)特别重要——它改变了回报本身：

G_t = R_t+1 + γ_t+1R_t+2 + γ_t+1γ_t+2R_t+3 + ···

A terminal state becomes a state where γ(s)=0, transitioning to the start distribution. This unifies episodic and discounted-continuing cases. The state-based λ-return becomes recursive:

终止状态变为γ(s)=0的状态，转移到起始分布。这统一了回合制和折扣持续性情况。基于状态的λ-回报变为递归：

G_t^λs = R_t+1 + γ_t+1[(1−λ_t+1)v̂(S_t+1,w_t) + λ_t+1G_t+1^λs]

The action-based λ-return comes in Sarsa form or Expected Sarsa form using V̄_t(s) = Σ_a π(a|s)q̂(s,a,w_t).

基于动作的λ-回报有Sarsa形式或Expected Sarsa形式，使用V̄_t(s)=Σ_aπ(a|s)q̂(s,a,w_t)。

12.9 *带控制变量的Off-policy迹 / Off-policy Traces with Control Variates

Incorporate importance sampling into the λ-return. The final state-based λ-return generalizes to off-policy:

将重要性采样纳入λ-回报。最终的基于状态的λ-回报泛化到off-policy：

G_t^λs = ρ_t[R_t+1 + γ_t+1((1−λ_t+1)v̂_t+1 + λ_t+1G_t+1^λs)] + (1−ρ_t)v̂_t

The approximate sum-of-TD-errors form leads to the general accumulating trace update for state values:

TD误差之和的近似形式导致状态价值的通用累积迹更新：

z_t = ρ_t(γ_tλ_tz_t−1 + ∇v̂(S_t, w_t))

For action values (Expected Sarsa form), the eligibility trace is:

对于动作价值（Expected Sarsa形式），资格迹为：

z_t = γ_tλ_tρ_tz_t−1 + ∇q̂(S_t, A_t, w_t)

⚠️ 注意：如果λ<1，所有这些off-policy算法都涉及自举，致命三要素适用（第11.3节），意味着它们仅在表格情况和状态聚合下保证稳定。

12.10 Watkins的Q(λ)到Tree-Backup(λ)

Watkins's Q(λ): decays traces as long as greedy actions are taken, then cuts traces to zero after the first non-greedy action. Tree-Backup(λ) (TB(λ)): the true successor to Q-learning, retaining the absence of importance sampling:

Watkins的Q(λ)：只要采取贪婪动作就衰减迹，在第一个非贪婪动作后将迹截为零。Tree-Backup(λ)(TB(λ))：Q-learning的真正继承者，保持不使用重要性采样：

G_t^λa = R_t+1 + γ_t+1[V̄_t(S_t+1) + λ_t+1π(A_t+1|S_t+1)(G_t+1^λa − q̂(S_t+1,A_t+1,w_t))]

The TB(λ) eligibility trace uses target-policy probabilities:

TB(λ)资格迹使用目标策略概率：

z_t = γ_tλ_tπ(A_t|S_t)z_t−1 + ∇q̂(S_t, A_t, w_t)

12.11 稳定的Off-policy迹方法 / Stable Off-policy Methods with Traces

Four key algorithms achieve stability guarantees under off-policy training (all assume linear function approximation):

四个关键算法在off-policy训练下实现稳定性保证（均假设线性函数近似）：

算法	类型	关键特点
GTD(λ)	状态价值 Gradient-TD	TDC的资格迹版本；需要辅助向量v和第二长β
GQ(λ)	动作价值 Gradient-TD	用于off-policy控制；使用平均特征向量x̄_t
HTD(λ)	混合状态价值	GTD(λ)和TD(λ)的混合；当b=π时退化为TD(λ)
Emphatic TD(λ)	强调TD	保留强off-policy收敛保证；使用followon迹F_t和emphasis M_t

HTD(λ) is appealing because it is a strict generalization of TD(λ): if behavior=target policy, HTD(λ) becomes TD(λ) (unlike GTD(λ)). Emphatic TD(λ) uses emphasis M_t=γ_tI_t+(1−λ_t)F_t and followon trace F_t=ρ_t−1γ_tF_t−1+I_t.

HTD(λ)有吸引力因为它是TD(λ)的严格泛化：如果行为=目标策略，HTD(λ)变为TD(λ)（GTD(λ)不是）。Emphatic TD(λ)使用emphasis M_t=γ_tI_t+(1−λ_t)F_t和followon迹F_t=ρ_t−1γ_tF_t−1+I_t。

12.12 实现问题 / Implementation Issues

For tabular methods, a naive implementation seems complex (update all states every step). But for typical γ and λ, almost all traces are near zero — only recently visited states have significant traces. In practice, only update the few significant traces → expense is just a few times that of one-step methods.

对于表格方法，朴素实现看似复杂（每步更新所有状态）。但对于典型的γ和λ，几乎所有迹都接近零——只有最近访问的状态有显著迹。实践中只更新少数显著迹→开销仅为单步方法的几倍。

With function approximation (e.g., ANNs), eligibility traces generally cause only a doubling of memory and computation. The tabular case is the worst case for trace complexity.

使用函数近似（如ANN），资格迹通常只导致内存和计算翻倍。表格情况是迹复杂度的最坏情况。

12.13 结论 / Conclusions

Eligibility traces + TD errors provide an efficient, incremental way of shifting between MC and TD methods. Key takeaways:

资格迹+TD误差提供了在MC和TD方法之间切换的高效增量方式。关键要点：

Intermediate λ typically performs best — brings us toward MC but not all the way
True online methods exactly reproduce expensive ideal methods with O(d) complexity
Eligibility traces are the first line of defense against long-delayed rewards and non-Markov tasks
Use traces when data is scarce (online); skip when data is cheap (offline simulation)
The elegant theory connects forward views ↔ backward views via trace equivalences

中间λ通常表现最好——趋向MC但不到达
真正的在线方法以O(d)复杂度精确重现昂贵的理想方法
资格迹是对抗长延迟奖励和非Markov任务的第一道防线
数据稀缺时使用迹（在线）；数据廉价时跳过（离线仿真）
优雅的理论通过迹等价连接前向视图↔后向视图

📋 核心概念速查 / Key Concepts Summary

概念 / Concept	定义 / Definition
资格迹 Eligibility Trace	短期记忆向量z_t，跟踪哪些权重分量对最近状态估值有贡献
λ-回报	所有n步回报的几何加权平均：G^λ=(1−λ)Σλⁿ⁻¹G_t:t+n
前向视图 Forward View	从当前状态展望未来奖励来确定更新目标
后向视图 Backward View	用当前TD误差配合资格迹回溯更新过去状态
Dutch迹	z_t=γλz_t−1+(1−αλz_t−1^Tx_t)x_t，用于真正的在线TD(λ)
累积迹 Accumulating	z_t=γλz_t−1+∇v̂，经典TD(λ)使用
替换迹 Replacing	特征为1时重置为1，否则衰减；已被dutch迹取代
复合更新 Compound Update	多个n步回报的加权平均
终止函数 γ(s)	状态相关的折扣，统一回合制和持续性设定
致命三要素与迹	λ<1时off-policy迹方法仍涉及自举，需要稳定化技术