---

 
 **更新方式有on-line和off-line两种**。对于on-line方式，是当场更新，只要增量计算出来了，下一步就把 $V(S_t)$更新了，也就是这一次和下一次更新$V(S_t)$的估计值时，所面对的 $V(S_t)$基准值都不一样。而对于[off-line](https://zhida.zhihu.com/search?content_id=3296674&content_type=Article&match_order=2&q=off-line&zhida_source=entity)方式，更新却始终放在每个episode的结尾，在episode过程中产生的增量都累积起来等着。这和on-line有什么区别呢？当然有，这意味着最终更新的时候，面对的$V(S_t)$ 基准值是固定的。
 
 
 
 ---
 
 eligibility traces，是把 n-step 思想高效实现为==online backward view== 的机制。

前向视角使用 $\lambda$-return：

$$
G_t^\lambda=(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}G_{t:t+n}
$$
后向视角维护资格迹：
$$
z_t=\gamma\lambda z_{t-1}+\nabla \hat v(S_t,w_t)  
$$
更新：
$$
w_{t+1}=w_t+\alpha\delta_t z_t  
$$
直观含义是：最近访问过、且对当前预测有贡献的状态或特征获得更高“资格”，当 TD error 出现时，这些状态或特征承担更大信用分配。

统一 forward view 与 backward view，并引出 true online $TD(\lambda)$，使在线更新与前向 $\lambda-return$ 更精确一致。

---
下面默认讨论**固定策略 $\pi$ 下的价值预测问题**，即估计
$$
v_\pi(s)=\mathbb{E}_\pi[G_t\mid S_t=s],  
\qquad  
G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots  
$$
其中 ($\gamma\in[0,1]$) 是折扣因子。$Eligibility \ Traces$ 是 TD 学习中的基本机制之一；在 $TD(\lambda)$ 中，$\lambda$正是 $trace-decay$ 参数。**Sutton 和 Barto 将其解释为连接 TD 与 Monte Carlo 的桥梁：从机制上看，trace 是某个状态或动作曾经出现过的临时记录，使相关参数在之后出现 TD error 时“有资格”被更新。**

---
## 1. 为什么需要 Eligibility Traces？

TD(0) 的更新是一步自举：
$$
\delta_t
=
R_{t+1}+\gamma V(S_{t+1})-V(S_t),  
$$
$$
V(S_t)\leftarrow V(S_t)+\alpha\delta_t.  
$$
$TD(0)$ 的问题在于：当前 TD error 只直接更新当前状态 $S_t$。如果奖励在很久之后才出现，信用需要一层一层向前传播，传播速度可能较慢。

Monte Carlo 方法相反，直接用完整回报 $G_t$ 更新：
$$
V(S_t)\leftarrow V(S_t)+\alpha(G_t-V(S_t)).  
$$
Monte Carlo 的问题是：必须等到轨迹结束才能知道 $G_t$，而且回报方差通常更大。

**$TD(\lambda)$的核心思想**是：==不要只使用一步 TD，也不要只等完整 MC 回报，而是把不同长度的 $n-step return$ 按权重混合==。Eligibility traces 则提供了这种混合目标的在线、增量实现方式。David Silver 的课程讲义也将 forward view 解释为把所有 $n-step\ returns$ 用 $(1-\lambda)\lambda^{n-1}$ 加权组合，并指出 backward view 提供在线机制。([UNIST NLP Lab](https://nlp.io.kr/arxiv/AI2023/slides_RL/MC-TD.pdf "Lecture 4: Model-Free Prediction"))

---

## 2. $n-step\ return$ 与 **$\lambda-return$**

先定义 n-step return：
$$
G_{t:t+n}
=
R_{t+1}  
+\gamma R_{t+2}  
+\cdots  
+\gamma^{n-1}R_{t+n}  
+\gamma^n V(S_{t+n}).  
$$
特殊情形：
$$
G_{t:t+1}=R_{t+1}+\gamma V(S_{t+1}),  
$$
这就是 $TD(0)$ 的一步目标。

若一直展开到 episode 结束，则得到 **Monte Carlo return**：
$$
G_t
=
R_{t+1}  
+\gamma R_{t+2}  
+\cdots  
+\gamma^{T-t-1}R_T.  
$$

$TD(\lambda)$ 的 forward view 使用 $\lambda-return$：
$$
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{T-t-1}  
\lambda^{n-1}G_{t:t+n}  
+  
\lambda^{T-t-1}G_t.  
$$
其中：
$$
(1-\lambda)\lambda^{n-1}  
$$
是第 $n-step\ return$ 的权重。

因此，$\lambda$ 控制“看多远”：

|     $\lambda$ | 含义                | 结果                 |
| ------------: | ----------------- | ------------------ |
|   $\lambda=0$ | 只看一步              | 退化为 TD(0)          |
| $0<\lambda<1$ | 多步 return 的指数加权平均 | TD 与 MC 的折中        |
|   $\lambda=1$ | 使用完整回报            | ==接近 Monte Carlo== |


从 forward view(向前看，看next state) 看，$TD(\lambda)$ 的更新为：
$$
V(S_t)\leftarrow V(S_t)+\alpha\bigl(G_t^\lambda-V(S_t)\bigr).  
$$
问题在于：$G_t^\lambda$ 依赖未来奖励和未来状态，因此一般需要等到之后的轨迹信息出现。Sutton 和 Barto 明确指出，forward view 是理论视角；其缺点是“acausal”，因为它在当前时刻需要未来信息。Backward view 则给出因果的、增量的在线机制。

---

## 3. Eligibility Trace 的定义
对每个状态 $s$，维护一个 trace：
$$
E_t(s)\ge 0.  
$$
最经典的是 ==**accumulating trace**==：
$$
E_t(s)
=
\gamma\lambda E_{t-1}(s)  
+  
\mathbb{1}\{S_t=s\}.  
$$
初始：
$$
E_0(s)=0.  
$$
含义是：

1. 每经过一个时间步，所有 trace 按 $\gamma\lambda$ 衰减；
   
2. 当前访问的状态 $S_t$ 的 trace 增加 1；
   
3. 因此最近访问过、访问频率较高的状态具有更大的 trace。
   

Silver 讲义把 eligibility trace 解释为同时结合 **recency heuristic** 与 **frequency heuristic**：**最近出现的状态更应负责，频繁出现的状态也更应负责**。其 backward $TD(\lambda)$ 公式正是
$$
E_t(s)=\gamma\lambda E_{t-1}(s)+\mathbb{1}(S_t=s).  
$$
([UNIST NLP Lab](https://nlp.io.kr/arxiv/AI2023/slides_RL/MC-TD.pdf "Lecture 4: Model-Free Prediction"))

若某个状态 $s$ 只在时间 $k$被访问一次，则之后有：
$$
E_t(s)=  
\begin{cases}  
0, & t<k,\\
(\gamma\lambda)^{t-k}, & t\ge k.  
\end{cases}  
$$
所以 trace 本质上是一个**指数衰减的信用分配权重(credit assignment weight)**。

---

## 4. ==$TD(\lambda)$ 的 backward view 更新

TD error 仍然是一阶 TD error：
$$
\delta_t
=
 R_{t+1}  
+  
\gamma V(S_{t+1})
-
V(S_t).  
$$
**但 $TD(\lambda)$ 不只更新$S_t$，而是更新所有 trace 非零的状态**：
$$
V(s)  
\leftarrow  
V(s)  
+  
\alpha \delta_t E_t(s),  
\qquad \forall s.  
$$
也就是说，当前 TD error $\delta_t$ 会按照 $E_t(s)$ 的大小，向过去访问过的状态分配。Silver 讲义的 backward-view $TD(\lambda)$ 也给出相同形式：==为每个状态保存 eligibility trace，并按 $\delta_tE_t(s)$更新每个状态价值。==([UNIST NLP Lab](https://nlp.io.kr/arxiv/AI2023/slides_RL/MC-TD.pdf "Lecture 4: Model-Free Prediction"))
这就是 backward view 的底层机制：
$$
\text{当前误差}  
\quad \delta_t  
\quad  
\times  
\quad  
\text{过去状态的资格权重}  
\quad E_t(s).  
$$
因此，$TD(\lambda)$的更新不是简单地“更新当前状态”，而是：
$$
\text{用当前一步 TD error，按指数衰减权重更新整条近期访问路径。}  
$$
---

## 5. Forward view 与 backward view 的等价关系

关键恒等式是：
$$
G_t^\lambda - V(S_t)
=
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
$$
==这说明：$\lambda-return$ 相对于当前价值估计的误差，可以分解为未来一串 TD errors 的指数加权和。Silver 讲义给出了这个 telescoping 关系：
$$
G_t^\lambda - V(S_t)
=
\delta_t  
+  
\gamma\lambda\delta_{t+1}  
+  
(\gamma\lambda)^2\delta_{t+2}  
+\cdots  
$$
([UNIST NLP Lab](https://nlp.io.kr/arxiv/AI2023/slides_RL/MC-TD.pdf "Lecture 4: Model-Free Prediction"))

若状态 $s$在时间 $t$ 被访问一次，则 backward view 在整条 episode 中对它累计的更新为：
$$
\sum_{k=t}^{T-1}  
\alpha\delta_k E_k(s)
=
 \sum_{k=t}^{T-1}  
\alpha\delta_k(\gamma\lambda)^{k-t}

=
	\alpha\bigl(G_t^\lambda - V(S_t)\bigr)(前向视角).  
$$
这正好等于 forward view 中用 $\lambda-return$ 做的一次更新。
因此：
$$
\boxed{  
\text{Eligibility traces 是 } \lambda\text{-return 的在线实现机制。}  
}  
$$
更准确地说，在 episode 内先累计更新、最后统一应用的 **offline $TD(\lambda)$** 中，forward view 与 backward view 的总更新严格等价；在线逐步更新时，由于 $V^\pi$ 在 episode 中不断变化，传统 $TD(\lambda)$ 与 forward view 一般只近似等价。PMLR 上 van Seijen 和 Sutton 的 True Online $TD(\lambda)$论文指出，传统 $TD(\lambda)$ 的 forward-view 等价性只对 offline 版本精确成立，online 版本只是近似；True Online $TD(\lambda)$ 通过新的 forward view 和新的 trace 形式实现在线精确等价。([Proceedings of Machine Learning Research](https://proceedings.mlr.press/v32/seijen14.html "True Online TD(lambda)"))

---
## 6. $TD(\lambda)$ 的算法流程：表格型预测版本

给定策略 $\pi$，估计 $V^\pi$。

初始化：
$$
V(s)\ \text{任意},\qquad E(s)=0,\ \forall s.  
$$
每个 episode 开始时：
$$
E(s)=0,\qquad \forall s.  
$$
每一步：

1. 观察当前状态 $S_t$，执行策略 $\pi$，得到 $R_{t+1},S_{t+1}$；
   
2. 计算 TD error：
$$
\delta_t
=
R_{t+1}  
+  
\gamma V(S_{t+1})
-
V(S_t).  
$$
3. 更新当前状态的 trace：
$$
E(S_t)\leftarrow E(S_t)+1.  
$$
4. 对所有状态更新价值：
$$
V(s)  
\leftarrow  
V(s)  
+  
\alpha\delta_tE(s).  
$$
5. 衰减所有 traces：
   
$$
E(s)\leftarrow \gamma\lambda E(s).  
$$
伪代码：

```text
Initialize V(s) arbitrarily

For each episode:
    Initialize E(s) = 0 for all s
    Initialize S

    Repeat until terminal:
        Take action according to policy π
        Observe R, S'

        δ = R + γ V(S') - V(S)      # terminal state has V(S') = 0

        E(S) = E(S) + 1             # accumulating trace

        For all states s:
            V(s) = V(s) + α δ E(s)
            E(s) = γ λ E(s)

        S = S'
```

Sutton 和 Barto 的 backward-view TD\lambda 也采用同样机制：每个状态都有 eligibility trace，当前 TD error 会触发对所有最近访问状态的比例更新。

---

## 7. $\lambda$的作用：偏差—方差与信用传播距离

$\lambda$ 控制 trace 的衰减速度：
$$
E_t(s)\propto(\gamma\lambda)^{\text{time since visit}}.  
$$
因此：
### $\lambda=0$
$$
E_t(s)=\mathbb{1}\{S_t=s\}.  
$$
只有当前状态被更新：
$$
V(S_t)\leftarrow V(S_t)+\alpha\delta_t.  
$$
这就是 $TD(0)$。Silver 讲义也指出，当 $\lambda=0$时，$TD(\lambda)$精确退化为 $TD(0)$。([UNIST NLP Lab](https://nlp.io.kr/arxiv/AI2023/slides_RL/MC-TD.pdf "Lecture 4: Model-Free Prediction"))
### $0<\lambda<1$
过去状态仍然会被当前 TD error 更新，但影响随时间指数衰减。这通常带来：
$$
\text{比 TD(0) 更快的长程信用传播}  
$$
同时避免完全 Monte Carlo 的高方差。
### $\lambda=1$
在 episodic setting 下，TD(1) 的总更新与 Monte Carlo 更新密切相关。Silver 讲义给出 telescoping 结果：当 $\lambda=1$ 时，一串折扣 TD errors 会相消为
$$
G_t-V(S_t).  
$$
因此 $TD(1)$ 在 offline 情况下等价于 Monte Carlo 型更新。([UNIST NLP Lab](https://nlp.io.kr/arxiv/AI2023/slides_RL/MC-TD.pdf "Lecture 4: Model-Free Prediction"))

---

## 8. Accumulating traces、Replacing traces、Dutch traces

### 8.1 Accumulating trace

经典定义：
$$
E_t(s)
=
\gamma\lambda E_{t-1}(s)  
+  
\mathbb{1}\{S_t=s\}.  
$$
如果同一状态短时间内反复访问，trace 会不断累加，可能大于 1。
优点：明确记录访问频率。
==缺点：在有循环、较大 $\lambda$、较大学习率时，trace 可能过大，导致更新不稳定。

---

### 8.2 Replacing trace

Replacing trace 对当前访问状态不是加 1，而是重置为 1：
$$
E_t(S_t)=1.  
$$
其他状态仍然衰减：


$$
E_t(s)=\gamma\lambda E_{t-1}(s),\qquad s\ne S_t.  
$$
Sutton 和 Barto 明确区分了 accumulating traces、replacing traces 和 dutch traces：accumulating traces 在重复访问时继续增加，replacing traces 则重置为 1。

**Replacing trace 的直观含义是：一个状态最近被访问过即可，不允许因为短时间内重复访问而无限增加资格权重。**

---
### 8.3 Dutch trace 与 True Online $TD(\lambda)$

Dutch trace 介于 accumulating 与 replacing 之间。在 tabular 情形中，Sutton 和 Barto 给出形式：
$$
E_t(S_t)
=
(1-\alpha)\gamma\lambda E_{t-1}(S_t)+1.  
$$
Dutch traces 与 True Online $TD(\lambda)$关系密切。True Online $TD(\lambda)$ 使用一种不同于传统 accumulating/replacing traces 的 trace 形式，并保持与 online forward view 的**精确等价**；PMLR 论文还指出其计算复杂度与 $TD(\lambda)$同阶。 ([Proceedings of Machine Learning Research](https://proceedings.mlr.press/v32/seijen14.html "True Online TD(lambda)"))

---
## 9. 函数逼近下的 Eligibility Traces

若使用线性函数逼近：
$$
\hat v(s,w)=w^\top x(s),  
$$
则**不再为每个状态维护 trace，而是为参数维护 trace 向量**：
$$
e_t
=
\gamma\lambda e_{t-1}  
+  
\nabla_w \hat v(S_t,w).  
$$
线性情况下：
$$
\nabla_w \hat v(S_t,w)=x(S_t),  
$$
所以：
$$
e_t
=
\gamma\lambda e_{t-1}  
+  
x(S_t).  
$$
TD error 为：
$$
\delta_t
=
 R_{t+1}  
+  
\gamma \hat v(S_{t+1},w_t)
-
\hat v(S_t,w_t).  
$$
参数更新：
$$
w_{t+1}
=
w_t  
+  
\alpha\delta_t e_t.  
$$
这说明，**在函数逼近中，eligibility trace 不再只是“状态是否近期访问”的记录，而是“哪些参数近期参与了价值预测”的记录。** 也就是说，trace 标记的是参数层面的信用资格：
$$
\text{某个参数最近越强地影响预测，越有资格接收当前 TD error。}  
$$
---

## 10. $TD(\lambda)$ 与 $Sarsa(\lambda)$、$Q(\lambda)$的关系

$TD(\lambda)$ 通常指**状态价值预测**：
$$
V(s).
$$
控制问题中，可以把 eligibility traces 加到动作价值方法中。

例如 $Sarsa(\lambda)$ 维护：
$$
E(s,a)  
$$
并更新：
$$
Q(s,a)  
\leftarrow  
Q(s,a)+\alpha\delta_tE(s,a),  
$$
其中：
$$
\delta_t
=
 R_{t+1}  
+  
\gamma Q(S_{t+1},A_{t+1})
-
Q(S_t,A_t).  
$$
Sutton 和 Barto 也指出，几乎任何 TD 方法，例如 Sarsa 或 Q-learning，都可以与 eligibility traces 结合，形成更一般的方法。

不过需要注意：on-policy 的 $Sarsa(\lambda)$ 理论与实践都相对自然；off-policy 的 $Q(\lambda)$更复杂(importance sampling)，$Watkins’s Q(\lambda)$、$Peng’s Q(\lambda)$等版本处理 trace 截断和离策略修正的方式不同。

---

## 11. 底层机制总结

Eligibility traces 可以理解为 TD 学习中的一个**指数衰减信用分配滤波器**：
$$
\boxed{  
\text{trace 记录“哪些过去状态/参数有资格对当前误差负责”。}  
}  
$$
**$TD(\lambda)$的核心不是改变 TD error 的形式，而是改变 TD error 的分配方式**：
$$
\boxed{  
\delta_t  
\text{ 不只更新当前状态，而是按 }  
E_t(s)  
\text{ 更新近期访问过的所有状态。}  
}  
$$
从 forward view 看：
$$
TD(\lambda)  
\approx  
\text{用 } \lambda\text{-return 更新价值函数。}  
$$
从 backward view 看：
$$
TD(\lambda)

\text{用 eligibility traces 在线累积未来 TD errors 的影响。}  
$$
最关键的等价式是：
$$
\boxed{  
G_t^\lambda - V(S_t)
=
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
}  
$$
这条式子揭示了 $TD(\lambda)$ 的本质：  
**$\lambda-return$ 的多步目标，可以由一串单步 TD errors 加权累积得到；eligibility trace 正是实现这种加权累积的机制。**

---
下面从**预测问题**开始推导，即在固定策略 $\pi$ 下估计状态价值函数 $v_\pi(s)$。这样可以先把 Eligibility Traces 与 $TD(\lambda)$的数学结构讲清楚；控制问题中的 $Sarsa(\lambda)$、$Q(\lambda)$ 只是把同样机制从状态 $(s)$ 推广到状态—动作对 $(s,a)$。==Eligibility traces 是 TD 学习中进行**时间信用分配**的核心机制：当前 TD error 不只更新当前状态，还会按 trace 权重更新过去访问过的状态；($\lambda$) 控制这种向过去传播的衰减速度。**==这个观点与 Sutton、Barto 的教材和 Silver 的强化学习讲义一致：$TD(\lambda)$可以看成 TD 与 Monte Carlo 的连续插值，forward view 适合理论解释，backward view 适合在线实现。**([Stanford University](https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf?utm_source=chatgpt.com "Reinforcement Learning: An Introduction"))

# 1. 问题设定：价值预测

考虑 Markov reward process 或固定策略 $\pi$诱导出的 Markov chain。时间步为
$$
S_0,R_1,S_1,R_2,S_2,\dots  
$$
折扣回报为
$$
G_t
=
R_{t+1}  
+  
\gamma R_{t+2}  
+  
\gamma^2R_{t+3}  
+\cdots,  
$$
其中
$$
0\le \gamma \le 1.  
$$
状态价值函数定义为
$$
v_\pi(s)
=
\mathbb{E}_\pi[G_t\mid S_t=s].  
$$
目标是用函数 $V(s)$近似 $v_\pi(s)$。

---

# 2. $TD(0)$：一步自举的基础形式

$TD(0)$使用一步 bootstrap target：
$$
R_{t+1}+\gamma V(S_{t+1}).  
$$
TD error 定义为
$$
\delta_t
=
 R_{t+1}  
+  
\gamma V(S_{t+1})
-
V(S_t).  
$$
$TD(0)$ 的**表格**更新为
$$
V(S_t)  
\leftarrow  
V(S_t)  
+  
\alpha \delta_t.  
$$
也就是
$$
V(S_t)  
\leftarrow  
V(S_t)  
+  
\alpha  
\Bigl[  
R_{t+1}  
+  
\gamma V(S_{t+1})
-
V(S_t)  
\Bigr].  
$$
$TD(0)$ 的核心是：用下一状态的当前估计 $V(S_{t+1})$ 构造目标。这个目标不需要等到 episode 结束，因此可以在线更新；但由于只进行一步传播，远期奖励向早期状态传播较慢。**TD 学习使用相邻时刻预测差异构造增量误差信号，这种 bootstrap 机制正是 TD 区别于普通监督式序列学习的关键。**([Stanford University](https://web.stanford.edu/group/pdplab/pdphandbook/handbookch10.html "9 Temporal-Difference Learning"))

---

# 3. $Monte\ Carlo$ 与 $TD(0)$的差异

$Monte\ Carlo$ 更新使用完整回报：
$$
V(S_t)  
\leftarrow  
V(S_t)  
+  
\alpha  
\bigl[  
G_t
-
V(S_t)  
\bigr].  
$$
$TD(0)$ 使用一步目标：
$$
G_{t:t+1}
=
R_{t+1}  
+  
\gamma V(S_{t+1}).  
$$
二者差异如下：

| 方法            | 更新目标                        | 是否自举 | 是否需等 episode 结束 | 典型性质           |
| ------------- | --------------------------- | ---: | --------------: | -------------- |
| TD(0)         | $R_{t+1}+\gamma V(S_{t+1})$ |    是 |               否 | 方差较低，但目标依赖当前估计 |
| Monte Carlo   | $G_t$                       |    否 |               是 | 目标不自举，但方差较高    |
| $TD(\lambda)$ | 多个 n-step returns 的加权平均     | 部分自举 |           可在线实现 | TD 与 MC 的连续折中  |

$TD(\lambda)$ 的目的就是在 $TD(0)$ 与 Monte Carlo 之间构造一个连续族。

---

# 4. $n-step \ return$：从一步 TD 到多步 TD

定义 $n-step\ return$：
$$
G_{t:t+n}
=
R_{t+1}  
+  
\gamma R_{t+2}  
+  
\cdots  
+  
\gamma^{n-1}R_{t+n}  
+  
\gamma^n V(S_{t+n}).  
$$
展开写为
$$
G_{t:t+n}
=
\sum_{i=1}^{n}  
\gamma^{i-1}R_{t+i}  
+  
\gamma^n V(S_{t+n}).  
$$
特殊情况：
$$
G_{t:t+1}
=
R_{t+1}  
+  
\gamma V(S_{t+1}),  
$$
这就是 $TD(0)$的 target。

如果 $n$ 一直到 episode 终止，且终止状态价值取0，则
$$
G_{t:T}
=
R_{t+1}  
+  
\gamma R_{t+2}  
+  
\cdots  
+  
\gamma^{T-t-1}R_T,  
$$


这就是 Monte Carlo return。
所以 $n-step\ return$ 是 TD(0) 与 Monte Carlo 之间的中间对象：(n) 越大，越少依赖 bootstrap，越接近 Monte Carlo。

---

# 5. $\lambda-return$：对所有 $n-step\ return$ 做指数加权平均

$TD(\lambda)$的 ==**forward view**== 使用 $\lambda-return$。对于 continuing task，可以写成
$$
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
G_{t:t+n},  
\qquad 0\le \lambda <1.  
$$
其中第 $n-step\ return$ 的权重是
$$
(1-\lambda)\lambda^{n-1}.  
$$
权重和为
$$
(1-\lambda)\sum_{n=1}^{\infty}  
\lambda^{n-1}
=
(1-\lambda)\frac{1}{1-\lambda}=1
$$
因此 $G_t^\lambda$是所有 $n-step\ returns$ 的凸组合。


在 episodic task 中，若 episode 在 T 终止，常写为
$$
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{T-t-1}  
\lambda^{n-1}G_{t:t+n}  
+  
\lambda^{T-t-1}G_t.  
$$
**最后一项 $\lambda^{T-t-1}G_t$ 对应完整 Monte Carlo return，保证有限 episode 中所有权重仍然加和为 1。** 


$$
(1-\lambda)\sum_{n=1}^{T-1}\lambda^{n-1}=(1-\lambda)(1+\lambda+\lambda^2+\cdots+\lambda^{T-2})=(1-\lambda)\frac{1-\lambda^{N-1}}{1-\lambda}
=1-\lambda^{N-1}
$$


Sutton 和 Barto 的资格迹章节把 $TD(\lambda)$ 的 forward view 描述为对所有 $n-step\ backups$ 的加权平均；Silver 讲义也给出同样的 $\lambda-return$ 解释。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---
# 6. $\lambda$ 的极端情况

## 6.1 $\lambda=0$

有
$$
G_t^0
=
 G_{t:t+1}
=
R_{t+1}  
+  
\gamma V(S_{t+1}).  
$$
因此 $TD\lambda$ 退化为 $TD(0)$。

---

## 6.2 $\lambda\to 1$

当 $\lambda$ 趋近于 1 时，长 $n-step\ return$ 的权重增加，目标越来越接近 Monte Carlo return。

在 episodic setting 中，$\lambda=1$时：
$$
G_t^\lambda
=
G_t.  
$$
因此 $TD(1)$ 与 Monte Carlo 更新密切相关；准确说，在 offline forward-view 形式下，$TD(1)$ 给出的总体更新等价于 Monte Carlo 型更新。Silver 讲义明确指出 $\lambda=0$ 对应$TD(0)$，$\lambda=1$ 对应 Monte Carlo 型极限。([UNIST NLP Lab](https://nlp.io.kr/arxiv/AI2023/slides_RL/MC-TD.pdf?utm_source=chatgpt.com "Lecture 4: Model-Free Prediction"))

---

# 7. 递归形式：$\lambda-return$ 的 Bellman-like 展开
先写 continuing case：
$$
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}G_{t:t+n}.  
$$
注意
$$
G_{t:t+1}
=
R_{t+1}  
+  
\gamma V(S_{t+1}),  
$$
而对于 ($n\ge 2$)，
$$
G_{t:t+n}
=
R_{t+1}  
+  
\gamma G_{t+1:t+n}.  
$$
因此
$$
\begin{aligned}  
G_t^\lambda  
&=  
(1-\lambda)G_{t:t+1}  
+  
(1-\lambda)  
\sum_{n=2}^{\infty}  
\lambda^{n-1}G_{t:t+n}  
\\  
&=  
(1-\lambda)  
\bigl[  
R_{t+1}+\gamma V(S_{t+1})  
\bigr]  
+  
(1-\lambda)  
\sum_{n=2}^{\infty}  
\lambda^{n-1}  
\bigl[  
R_{t+1}  
+  
\gamma G_{t+1:t+n}  
\bigr].  
\end{aligned}  
$$
拆开奖励项：
$$
\begin{aligned}  
G_t^\lambda  
&=  
(1-\lambda)R_{t+1}  
+  
(1-\lambda)\gamma V(S_{t+1})  
\\  
&\quad+  
(1-\lambda)  
\sum_{n=2}^{\infty}  
\lambda^{n-1}R_{t+1}  
+  
(1-\lambda)\gamma  
\sum_{n=2}^{\infty}  
\lambda^{n-1}G_{t+1:t+n}.  
\end{aligned}  
$$
奖励项权重为
$$
(1-\lambda)  
+  
(1-\lambda)  
\sum_{n=2}^{\infty}\lambda^{n-1}
=
 (1-\lambda)  
\sum_{n=1}^{\infty}\lambda^{n-1}
=1
$$
所以奖励项合并为
$$
R_{t+1}.  
$$
最后一项令 $m=n-1$，则
$$
G_{t+1:t+n}
=
G_{t+1:t+1+m},  
$$
并且
$$
\sum_{n=2}^{\infty}  
\lambda^{n-1}G_{t+1:t+n}
=
\lambda  
\sum_{m=1}^{\infty}  
\lambda^{m-1}  
G_{t+1:t+1+m}.  
$$

于是
$$
(1-\lambda)  
\sum_{m=1}^{\infty}  
\lambda^{m-1}  
G_{t+1:t+1+m}
=
G_{t+1}^\lambda.  
$$
因此得到递归形式：
$$
G_t^\lambda
=
R_{t+1}  
+  
\gamma  
\Bigl[  
(1-\lambda)V(S_{t+1})  
+  
\lambda G_{t+1}^\lambda  
\Bigr].  
$$
这个式子说明：$\lambda-return$ 在下一时刻混合了两种目标：
$$
(1-\lambda)V(S_{t+1})  
$$
和
$$
\lambda G_{t+1}^\lambda.  
$$
**也就是：==以权重 $1-\lambda$ 停止展开并 bootstrap==，以权重 $\lambda$ 继续向未来展开（和Markov process 联系起来了）。**

---

# 8. 关键推导一：$n-step\ return$ 与 $TD\ errors$ 的关系

定义固定价值函数 $V$ 下的==**TD error**==：
$$
\delta_k
=
 R_{k+1}  
+  
\gamma V(S_{k+1})
-
V(S_k).  
$$
现在证明：
$$
G_{t:t+n}
-
 V(S_t)
=
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k.  
 
$$
右侧展开：
$$
\begin{aligned}  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k  
&=  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}  
\Bigl[  
R_{k+1}  
+  
\gamma V(S_{k+1})
-
 V(S_k)  
\Bigr]  
\\  
&=  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}R_{k+1}  
+  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t+1}V(S_{k+1})
-
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}V(S_k).  
\end{aligned}  
$$
第二个价值项改指标，令$j=k+1$，则
$$
\sum_{k=t}^{t+n-1}  
\gamma^{k-t+1}V(S_{k+1})
=
\sum_{j=t+1}^{t+n}  
\gamma^{j-t}V(S_j).  
$$
第三项为
$$
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}V(S_k)
=
V(S_t)  
+  
\sum_{k=t+1}^{t+n-1}  
\gamma^{k-t}V(S_k).  
$$
==两项相减后，中间状态价值全部 telescoping 抵消==，只剩
$$
\gamma^nV(S_{t+n})-V(S_t).  
$$
所以
$$
\begin{aligned}  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k  
&=  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}R_{k+1}  
+  
\gamma^nV(S_{t+n})
-
 V(S_t)  
\\  
&=  
G_{t:t+n}
-
V(S_t).  
\end{aligned}  
$$
证毕。

这个恒等式非常重要：**多步 return 相对当前价值估计的误差，可以分解成一串折扣 TD errors 的和。**

---

# 9. 关键推导二：$\lambda-return$ 与 TD errors 的关系

从 continuing case 开始：
$$
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
G_{t:t+n}.  
$$
两边减去 $V(S_t)$。由于权重和为 1：
$$
V(S_t)
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}V(S_t).  
$$
因此
$$
\begin{aligned}  
G_t^\lambda - V(S_t)  
&=  
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
\bigl[  
G_{t:t+n}-V(S_t)  
\bigr].  
\end{aligned}  
$$
代入上一节结论：
$$
G_{t:t+n}-V(S_t)
=
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k.  
$$
得到
$$
\begin{aligned}  
G_t^\lambda - V(S_t)  
&=  
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k.  
\end{aligned}  
$$
**交换求和顺序。** 固定某个 $k\ge t$，令
$$
m=k-t.  
$$
$\delta_k=R_{k+1}+ \gamma V(S_{k+1})-V(S_k).$ 会出现在所有满足
$$
n\ge m+1  
$$
的 $n-step\ return$ 中。==因此 $\delta_k$ 的总权重为==
$$
(1-\lambda)  
\sum_{n=m+1}^{\infty}  
\lambda^{n-1}
=
 (1-\lambda)\lambda^m  
\sum_{j=0}^{\infty}\lambda^j
=
 (1-\lambda)\lambda^m\frac{1}{1-\lambda}
=
\lambda^m.  
$$
同时还有折扣项
$$
\gamma^{k-t}=\gamma^m.  
$$
所以
$$
\delta_k  
$$
的总权重为
$$
(\gamma\lambda)^{k-t}.  
$$
==因此得到核心恒等式：==
$$
G_t^\lambda
-
V(S_t)
=
\sum_{k=t}^{\infty}  
(\gamma\lambda)^{k-t}\delta_k.  
 
$$
在有限 episodic case 中，若终止时 $V(S_T)=0$，同样有
$$
G_t^\lambda
-
 V(S_t)
=
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
$$
**Silver 讲义中也给出这一telescoping关系：$\lambda-return$ 相对当前估计的误差等于未来 TD errors 的指数加权和；这是 forward view 与 backward view 等价的核心代数基础。**([UNIST NLP Lab](https://nlp.io.kr/arxiv/AI2023/slides_RL/MC-TD.pdf?utm_source=chatgpt.com "Lecture 4: Model-Free Prediction"))

---

# 10. 从核心恒等式推出 Eligibility Trace

上一节得到：
$$
G_t^\lambda
-
 V(S_t)
=
\delta_t  
+  
\gamma\lambda\delta_{t+1}  
+  
(\gamma\lambda)^2\delta_{t+2}  
+\cdots.  
$$
==如果采用 forward view，那么状态 $S_t$的更新是==
$$
\Delta V(S_t)
=
 \alpha  
\bigl[  
G_t^\lambda
-
V(S_t)  
\bigr].  
$$
**代入 ==TD error== 分解**：
$$
\Delta V(S_t)
=
\alpha  
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
$$
**这说明：状态 $S_t$ 最终应该接收未来所有 TD errors 的影响**，其中时间 $k$ 的 TD error 权重是
$$
(\gamma\lambda)^{k-t}.  
$$
**但是在线学习在时间 $k$ 只能看到当前 $\delta_k$，不能回到过去重新计算所有 $S_t$。因此需要一个机制，在时间 $k$ 记录哪些过去状态应该接收当前 $\delta_k$。**

于是定义：
$$
E_k(s)
=
\sum_{t=0}^{k}  
(\gamma\lambda)^{k-t}  
\mathbb{1}\{S_t=s\}.  
$$
**这个量就是状态 $s$在时间$k$的 eligibility trace**。

eligibility trace vector for each state

含义是：
$$
E_k(s)=
\text{状态 }s\text{ 在过去各次访问的指数衰减权重之和。}  
$$
如果状态 $s$ 在时间 $t$ 被访问过，那么到时间 $k$ 时，这次访问留下的资格权重为
$$
(\gamma\lambda)^{k-t}.  
$$
如果状态 $s$ 多次被访问，则 trace 是所有访问痕迹的累加。

---
# 11. Eligibility Trace 的递推形式

由定义
$$
E_k(s)
=
\sum_{t=0}^{k}  
(\gamma\lambda)^{k-t}  
\mathbb{1}\{S_t=s\},  
$$
可以推出递推。
先写 $E_{k-1}(s)$：
$$
E_{k-1}(s)
=
\sum_{t=0}^{k-1}  
(\gamma\lambda)^{k-1-t}  
\mathbb{1}\{S_t=s\}.  
$$
两边乘以 $\gamma\lambda$：
$$
\gamma\lambda E_{k-1}(s)
=
\sum_{t=0}^{k-1}  
(\gamma\lambda)^{k-t}  
\mathbb{1}\{S_t=s\}.  
$$
而
$$
E_k(s)
=
\sum_{t=0}^{k-1}  
(\gamma\lambda)^{k-t}  
\mathbb{1}\{S_t=s\}  
+  
\mathbb{1}\{S_k=s\}.  
$$
所以$$
\boxed{  
E_k(s)
=
\gamma\lambda E_{k-1}(s)  
+  
\mathbb{1}\{S_k=s\}.  
}  
$$这就是 accumulating eligibility trace。

Sutton 与 Barto 的课件和 Silver 讲义都给出同样形式：**每一步先让所有 traces 按 $\gamma\lambda$ 衰减，再把当前访问状态的 trace 增加 1；这就是 backward-view $TD(\lambda)$ 的机制。**([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---

# 12. 从 trace 推出 backward-view $TD(\lambda)$

时间 $k$ 的 TD error 是
$$
\delta_k
=
 R_{k+1}  
+  
\gamma V(S_{k+1})
-
V(S_k).  
$$
由于$E_k(s)$表示状态$s$对当前 TD error 的资格权重，因此更新为
$$
E_k(s)
=
\sum_{t=0}^{k-1}  
(\gamma\lambda)^{k-t}  
\mathbb{1}\{S_t=s\}  
+  
\mathbb{1}\{S_k=s\}.  
$$
$$

V(s)  
\leftarrow  
V(s)  
+  
\alpha \delta_k [E_k(s)],  
\qquad \forall s.  
$$
这就是 backward-view $TD(\lambda)$。

把所有时间步的更新累计起来：
$$
\sum_{k=0}^{T-1}  
\alpha\delta_k E_k(s).  
$$
若某状态 $s$ 只在时间 $t$ 被访问一次，即 $S_t=s$，那么
$$
E_k(s)=
\begin{cases}  
0, & k<t,\\  
(\gamma\lambda)^{k-t}, & k\ge t.  
\end{cases}  
$$
于是对这个状态的总更新为
$$
\sum_{k=t}^{T-1}  
\alpha\delta_k  
(\gamma\lambda)^{k-t}
=
 \alpha  
\bigl[  
G_t^\lambda
-
V(S_t)  
\bigr].  
$$
这正好等于 forward view 的更新。
因此：
$$
\boxed{  
\text{Backward view 中的 eligibility trace 正是 forward view 中 }\lambda\text{-return 的在线实现。}  
}  
$$
Silver 讲义的 forward/backward equivalence 也用这一形式说明：**若状态只在某一步被访问一次，backward $TD(\lambda)$ 在整个 episode 结束后累计的误差正好等于 $\lambda-return$ 误差。**([UNIST NLP Lab](https://nlp.io.kr/arxiv/AI2023/slides_RL/MC-TD.pdf?utm_source=chatgpt.com "Lecture 4: Model-Free Prediction"))

---

# 13. $TD(\lambda)$ 的完整表格算法

对每个状态 $s$，维护两个量：
$$
V(s),\qquad E(s).  
$$
初始化：
$$
V(s)\ \text{任意},\qquad E(s)=0.  
$$
每个 episode 开始时：
$$
E(s)=0,\qquad \forall s.  
$$
每一步：
$$
\delta

 R  
+  
\gamma V(S')
-
V(S),  
$$
$$
E(S)  
\leftarrow  
E(S)+1,  
$$
$$
V(s)  
\leftarrow  
V(s)  
+  
\alpha\delta E(s),  
\qquad \forall s,  
$$
$$
E(s)  
\leftarrow  
\gamma\lambda E(s),  
\qquad \forall s.  
$$
伪代码：

```c
Initialize V(s) arbitrarily for all s

For each episode:
    Initialize E(s) = 0 for all s
    Initialize S

    Repeat until terminal:
        Take action according to fixed policy π
        Observe R, S'

        δ = R + γV(S') - V(S)
        E(S) = E(S) + 1

        For all states s:
            V(s) = V(s) + α δ E(s)
            E(s) = γλE(s)

        S = S'
```

若 $S'$是终止状态，则通常令
$$
V(S')=0.  
$$
**这个算法形式正是 on-line tabular $TD(\lambda)$ 的标准 backward view。Sutton 与 Barto 的资格迹课件也以相同结构给出：计算 TD error，增加当前状态 trace，然后用 $\delta e(s)$ 更新所有状态，最后衰减 traces。**([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---

# 14. Trace 的机制解释：为什么当前误差可以更新过去状态？

设一条轨迹为
$$
S_0,S_1,S_2,\dots,S_t.  
$$
在时间 $t$ 发生 TD error：
$$
\delta_t
=
R_{t+1}  
+  
\gamma V(S_{t+1})
-
V(S_t).  
$$
**这个误差表示：从 $S_t$ 看，当前预测与一步后 bootstrap 目标之间不一致。**
但 $S_t$ 本身可能是由更早状态转移而来。例如
$$
S_{t-4}\to S_{t-3}\to S_{t-2}\to S_{t-1}\to S_t(current \ time\ step).  
$$
**如果 $S_t$ 的价值估计发生误差，那么更早状态的估计也可能应该调整，因为早期状态的价值依赖未来状态价值。Eligibility trace 就把这种依赖关系以指数衰减形式保留下来：**
$$
E_t(S_{t}) \approx 1,  
$$
$$
E_t(S_{t-1}) \approx \gamma\lambda,  
$$
$$
E_t(S_{t-2}) \approx (\gamma\lambda)^2.  
$$
因此当前 TD error 对过去状态的影响为
$$
\delta_t,  
\quad  
\gamma\lambda\delta_t,  
\quad  
(\gamma\lambda)^2\delta_t,  
\quad \dots  
$$
这正好对应 forward-view 恒等式中的权重。
PDPLab 的 TD 学习章节也将 eligibility traces 描述为 TD 学习中进行 ==**temporal credit assignment** ==的主要机制：**当前误差对过去预测的 credit 或 blame 分配由 trace 决定，$\lambda$越大，较早预测获得的更新越大。**([Stanford University](https://web.stanford.edu/group/pdplab/pdphandbook/handbookch10.html "9 Temporal-Difference Learning"))

---

# 15. $\gamma$ 与 $\lambda$ 的不同作用

trace 衰减因子是
$$
\gamma\lambda.  
$$
但 $\gamma$ 和 $\lambda$ 的含义不同。
## 15.1 $\gamma$：任务目标中的时间折扣
$$
\gamma  
$$
属于 return 定义：
$$
G_t
=
R_{t+1}  
+  
\gamma R_{t+2}  
+  
\gamma^2R_{t+3}  
+\cdots.  
$$
**它决定远期奖励在目标函数中的重要性。**
## 15.2 $\lambda$：学习算法中的 trace 衰减
$$
\lambda  
$$
**属于学习算法，控制 TD error 向过去传播多远。**
$$
\lambda=0  
$$
表示只更新当前状态；
$$
\lambda\approx 1  
$$
表示让较早状态也显著接收当前误差信号。
因此
$$
\gamma\lambda  
$$
同时体现：

1. 远期奖励本身在任务目标中被 $\gamma$ 折扣；
   
2. 当前误差向过去传播时被 $\lambda$额外衰减。
---

# 16. 偏差—方差角度理解 $\lambda$

$\lambda$ 控制 bootstrap 程度。

当$\lambda=0$时，目标为
$$
R_{t+1}+\gamma V(S_{t+1}).  
$$
==**这个目标只依赖一步采样，方差较低；但由于使用 $V(S_{t+1})$ 作为 bootstrap，若当前价值估计不准，则目标存在估计偏差。**==

当
$$
\lambda=1  
$$
时，目标接近完整 return：
$$
G_t.  
$$
==**这个目标不依赖 bootstrap，因此在固定策略的 episodic prediction 中具有更弱的 bootstrap 偏差；但它包含整条随机轨迹的奖励，方差通常更高。**==
中间值
$$
0<\lambda<1  
$$
**在两者之间折中。$TD(\lambda)$常被描述为 TD 与 Monte Carlo backups 的混合；Tanner 和 Sutton 关于 $TD(\lambda)$ networks 的论文也指出，$\lambda$ 可以理解为指定 TD 与 Monte Carlo backups 的混合程度。**([ICML](https://icml.cc/Conferences/2005/proceedings/papers/112_TDLambdaNetworks_TannerSutton.pdf?utm_source=chatgpt.com "Temporal-Difference Networks with Eligibility Traces"))

---
# 17. Accumulating Trace
前面推导出的 trace 是 accumulating trace：
$$
E_t(s)
=
\gamma\lambda E_{t-1}(s)  
+  
\mathbb{1}\{S_t=s\}.  
$$
若同一状态被频繁访问，trace 会不断累加。例如状态 $s$ 在 $(t-2,t-1,t)$ 连续出现，则
$$
E_t(s)
=
1  
+  
\gamma\lambda  
+  
(\gamma\lambda)^2.  
$$
如果 $\gamma\lambda$ 接近 1，这个值可能明显大于 1。

因此 accumulating trace 同时包含两种因素：

1. **recency**：越近的访问权重越大；

2. **frequency**：访问次数越多，总 trace 越大。
Silver 讲义也把 eligibility trace 解释为结合 recency 与 frequency 的机制：最近访问、频繁访问的状态更有资格接收当前 TD error。([UNIST NLP Lab](https://nlp.io.kr/arxiv/AI2023/slides_RL/MC-TD.pdf?utm_source=chatgpt.com "Lecture 4: Model-Free Prediction"))

---
# 18. Replacing Trace

**Accumulating trace 在某些循环任务中可能过大。Replacing trace 的修改是：当前访问状态的 trace 不加 1，而是直接设为 1。**
定义为
$$
E_t(s)
=
\begin{cases}  
1, & s=S_t,\\  
\gamma\lambda E_{t-1}(s), & s\ne S_t.  
\end{cases}  
$$
也就是
$$
E_t(S_t)=1.  
$$
**Replacing trace 的含义是：状态最近被访问过即可，不让短时间内的重复访问无限积累资格权重。**

**Sutton 与 Barto 的课件明确区分 accumulating traces 与 replacing traces：accumulating traces 对当前状态加 1，而 replacing traces 在访问状态时把 trace 设为 1；课件也指出 accumulating traces 中频繁访问状态的 eligibility 可以大于 1，并可能带来收敛或稳定性问题。**([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---

# 19. 函数逼近下的 Eligibility Traces

表格情形中，每个状态有一个 $V(s)$。函数逼近情形中，价值函数写为
$$
\hat v(s,w).  
$$
参数为
$$
w\in\mathbb{R}^d.  
$$
==此时 trace 不再是状态 trace，而是参数 trace==：
$$
e_t  
\in\mathbb{R}^d.  
$$
半梯度 $TD(\lambda)$的 accumulating trace 为
$$
e_t
=
\gamma\lambda e_{t-1}  
+  
\nabla_w \hat v(S_t,w_t).  
$$
TD error 为:
$$
\delta_t
=
 R_{t+1}  
+  
\gamma \hat v(S_{t+1},w_t)
-
\hat v(S_t,w_t).  
$$
参数更新为:
$$
w_{t+1}
=
w_t  
+  
\alpha\delta_t e_t.   
$$
如果是线性函数逼近：
$$
\hat v(s,w)
=
w^\top x(s),  
$$
则
$$
\nabla_w \hat v(s,w)
=
x(s),  
$$
所以
$$
e_t
=
\gamma\lambda e_{t-1}  
+  
x(S_t),  
$$
$$
w_{t+1}
=
w_t  
+  
\alpha\delta_t e_t.  
$$
这说明函数逼近下的 trace 表示：哪些参数最近参与了价值预测，以及参与强度是多少。**PDPLab 的 TD 学习章节也从梯度形式解释了 eligibility trace：trace 是过去预测梯度的指数衰减和，当前 TD error 乘以该 trace 后产生参数更新。**([Stanford University](https://web.stanford.edu/group/pdplab/pdphandbook/handbookch10.html "9 Temporal-Difference Learning"))

---

# 20. Forward View 与 Backward View 的精确等价条件

需要区分三种说法。
## 20.1 Offline $TD(\lambda)$
**Offline forward view 中，先用当前固定的$V$计算所有**
**$$G_t^\lambda,$$**
**然后在 episode 结束后统一更新。此时 forward view 与 backward view 的累计更新可以严格等价。**

核心原因是：前面推导的恒等式
$$
G_t^\lambda
-
V(S_t)=

\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k  
$$
**假设用于计算所有 $\delta_k$ 的价值函数 $V$ 在这一段推导中是固定的。**

## 20.2 Conventional online $TD(\lambda)$

实际算法中，参数每一步都更新：
$$
V_{t+1}\ne V_t.  
$$
**因此后续 TD error $\delta_{t+1},\delta_{t+2},\dots$ 使用的价值函数已经改变。于是，传统 online $TD(\lambda)$ 与 classical forward view 不再严格等价，而通常是近似匹配。**

van Seijen 和 Sutton 的 True Online $TD(\lambda)$ 论文页面明确指出：传统 $TD(\lambda)$ 与 forward view 的等价性对 offline 版本是精确的；**online 版本中逐步更新通常更实用，但与 conventional forward view 只近似匹配，因为 conventional forward view 假定 episode 内估计不变。**([Microsoft](https://www.microsoft.com/en-us/research/publication/true-online-td%CE%BB/?lang=ko-kr "True Online TD(λ) - Microsoft Research"))

## 20.3 True Online $TD(\lambda)$

True Online $TD(\lambda)$ 修改了 forward view 与 trace 形式，使在线逐步更新也能与新的 online forward view 精确等价。Microsoft Research 页面说明，该算法使用一种不同于 conventional accumulating traces 和 replacing traces 的新 eligibility trace (**Dutch Traces**)，整体计算复杂度与 $TD(\lambda)$ 相同。([Microsoft](https://www.microsoft.com/en-us/research/publication/true-online-td%CE%BB/?lang=ko-kr "True Online TD(λ) - Microsoft Research"))

---
# 21. True Online $TD(\lambda)$ 的 Dutch Trace 直观形式

在线函数逼近下，True Online $TD(\lambda)$ 常使用 dutch trace。线性价值函数
$$
\hat v(s,w)=w^\top x(s)  
$$
下，**dutch trace** 的典型形式为
$$
e_t
=
\gamma\lambda e_{t-1}  
+  
\alpha  
\bigl[  
1
-
\gamma\lambda e_{t-1}^\top x_t  
\bigr]  
x_t,  
$$
有些等价写法把$\alpha$ 吸收到更新形式中。其目的不是简单记录访问频率，而是修正在线更新过程中 $w_t$ 已经改变所带来的 forward/backward mismatch。**True Online Temporal-Difference Learning 的后续 JMLR 论文也强调，true online 方法与 forward view 在任意步长下保持精确等价，而传统方法只在小步长下近似这种关系。**([Journal of Machine Learning Research](https://www.jmlr.org/papers/volume17/15-599/15-599.pdf?utm_source=chatgpt.com "True Online Temporal-Difference Learning"))

---
# 22. $TD(\lambda)$ 与 $Sarsa(\lambda)$

预测问题估计
$$
V(s).  
$$
控制问题通常估计
$$
Q(s,a).  
$$
$Sarsa(\lambda)$ 的 eligibility trace 定义为
$$
E_t(s,a)
=
\gamma\lambda E_{t-1}(s,a)  
+  
\mathbb{1}\{S_t=s,A_t=a\}.  
$$
TD error 为
$$
\delta_t
=
 R_{t+1}  
+  
\gamma Q(S_{t+1},A_{t+1})
-
Q(S_t,A_t).  
$$
更新为
$$
Q(s,a)  
\leftarrow  
Q(s,a)  
+  
\alpha\delta_tE_t(s,a).  
$$
**这与 $TD(\lambda)$ 完全同构，只是 trace 的对象从状态 $s$ 变成状态—动作对 $(s,a)$。Sutton 与 Barto 的资格迹课件也指出，控制问题中的 $Sarsa(\lambda)$保存的是 state-action pair 的 eligibility。**([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---

# 23. $TD(\lambda)$ 的本质总结

$TD(\lambda)$有两个等价视角。
## 23.1 Forward view

Forward view 说：
$$
TD(\lambda ) 
$$
用的是
$$
G_t^\lambda  
$$
作为更新目标，而
$$
G_t^\lambda  
$$
是所有 $n-step\ returns$ 的指数加权平均。
因此：
$$
\lambda=0  
\Rightarrow TD(0),  
$$
$$
\lambda=1  
\Rightarrow Monte\ Carlo.  
$$
---
## 23.2 Backward view

Backward view ：
当前 TD error
$$
\delta_t  
$$
**不只更新当前状态，而是更新所有过去访问过且 trace 非零的状态**：
$$
V(s)  
\leftarrow  
V(s)  
+  
\alpha\delta_tE_t(s).  
$$
trace 递推为
$$
E_t(s)
=
\gamma\lambda E_{t-1}(s)  
+  
\mathbb{1}\{S_t=s\}.  
$$
所以 eligibility trace 是一个**指数衰减的历史访问记忆**。

---

## 23.3 核心代数关系

最核心的推导结论是：
$$
\boxed{  
G_t^\lambda
-
 V(S_t)
=
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
}  
$$
这条式子说明：
$$
\lambda\text{-return 的误差}
=
\text{未来 TD errors 的指数加权和}.  
$$
Backward view 只是把这条式子在线化：  
**在未来 TD error 还没有出现时，先为过去状态保留 trace；当未来 TD error 出现时，用 trace 决定哪些过去状态应该被更新。**
因此，Eligibility Traces 的严格机制可以概括为：
==**Eligibility trace 是把 forward-view 多步目标转化为 backward-view 在线更新的数学工具。**==
$TD(\lambda)$的严格机制可以概括为：
$TD(\lambda)$用 trace 实现的、介于 $TD(0)$ 与 Monte Carlo 之间的多步 TD 学习算法。

---

下面把 **forward view（前向视角）** 与 **backward view（后向视角）** 放在 $TD(\lambda)$ / eligibility traces 的框架中解释。核心关系是：

- **forward view 定义“应该更新成什么目标”；**
- **backward view 给出“如何在线实现这个目标”。**

在 Sutton 与 Barto 的教材中，**forward view 被描述为更偏理论的视角，用来理解 eligibility traces 到底计算了什么**；**backward view 是更机制化的视角，用 eligibility trace 在线实现这些更新**。相关讲义也明确说：forward view 是理论视角，backward view 是机制视角。([Stanford University](https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf?utm_source=chatgpt.com "Reinforcement Learning: An Introduction"))

---
# 1. 基本设定

考虑固定策略 $\pi$ 下的价值预测问题。状态序列为：
$$
S_0,R_1,S_1,R_2,S_2,\dots  
$$
折扣回报为：
$$
G_t
=
R_{t+1}  
+  
\gamma R_{t+2}  
+  
\gamma^2R_{t+3}  
+\cdots.  
$$
价值函数为：
$$
v_\pi(s)
=
\mathbb E_\pi[G_t\mid S_t=s].  
$$
TD 学习用估计函数 $V(s)$ 近似 $v_\pi(s)$。

one step TD error 为：
$$
\delta_t
=
 R_{t+1}  
+  
\gamma V(S_{t+1})
-
V(S_t).  
$$
$TD(0)$的更新是：
$$
V(S_t)  
\leftarrow  
V(S_t)  
+  
\alpha\delta_t.  
$$
$TD(0)$只用一步 bootstrap target：
$$
R_{t+1}+\gamma V(S_{t+1}).  
$$
Monte Carlo 则使用完整回报 $G_t$。$TD(\lambda)$的 forward view 和 backward view 正是用来解释：如何在 $TD(0)$ 与 Monte Carlo 之间连续插值。Sutton 与 Barto 的资格迹章节也把 eligibility traces 解释为连接 TD 与 Monte Carlo 的基本机制。([Stanford University](https://web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf?utm_source=chatgpt.com "Reinforcement Learning: An Introduction"))

---
# 2. Forward view：向未来看，定义更新目标

## 2.1 n-step return

Forward view 从某个状态 $S_t$ 出发，向未来看 1步、2 步、$\dots$、n步，构造不同长度的 return。
n-step return 定义为：
$$
G_{t:t+n}
=
R_{t+1}  
+  
\gamma R_{t+2}  
+  
\cdots  
+  
\gamma^{n-1}R_{t+n}  
+  
\gamma^n V(S_{t+n}).  
$$
紧凑写法为：
$$
G_{t:t+n}
=
\sum_{i=1}^{n}  
\gamma^{i-1}R_{t+i}  
+  
\gamma^nV(S_{t+n}).  
$$
特殊情况：
$$
G_{t:t+1}
=
R_{t+1}  
+  
\gamma V(S_{t+1}),  
$$
这就是 $TD(0)$ 的 target。

如果n一直延伸到 episode 终止，且终止状态价值为 0，则得到 Monte Carlo return：
$$
G_t
=
R_{t+1}  
+  
\gamma R_{t+2}  
+  
\cdots  
+  
\gamma^{T-t-1}R_T.  
$$
所以 n-step return 是 $TD(0)$ 和 Monte Carlo 之间的中间对象。

---
## 2.2 $\lambda-return$

Forward view 的关键是把所有 $n-step\ returns$ 做指数加权平均。

continuing task 中：
$$
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
G_{t:t+n},  
\qquad 0\le \lambda <1.  
$$
权重为：
$$
(1-\lambda)\lambda^{n-1}.  
$$
权重和为：
$$
\sum_{n=1}^{\infty}  
(1-\lambda)\lambda^{n-1}=1
$$
因此 $G_t^\lambda$ 是所有 $n-step\ returns$ 的加权平均。Sutton 与 Barto 的资格迹讲义中也直接把 forward view of $TD(\lambda)$ 描述为 “averaging all n-step backups”**，并用$\lambda^{n-1}$加权。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))
episodic task 中，若 episode 于 $T$ 终止，则常写为：
$$
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{T-t-1}  
\lambda^{n-1}  
G_{t:t+n}  
+  
\lambda^{T-t-1}G_t.  
$$
$$
where \ \ \ (1-\lambda)\sum^{T-t-1}_{n=1}\lambda^{n-1}=1-\lambda^{T-t-1}
$$
最后一项使用完整 Monte Carlo return，保证有限 episode 中权重仍然正确归一化。
Forward-view $TD(\lambda)$ 的更新形式是：
$$
V(S_t)  
\leftarrow  
V(S_t)  
+  
\alpha  
\bigl[  
G_t^\lambda
-
V(S_t)  
\bigr].  
$$
这就是 forward view 的含义：
$$
\boxed{  
\text{从 }S_t\text{ 向未来看，计算一个 }\lambda\text{-return，然后用它更新 }V(S_t)。  
}  
$$
---
# 3. $\lambda$ 的含义(credit assignment)
当
$$
\lambda=0  
$$
时：
$$
G_t^0
=
G_{t:t+1}
=
R_{t+1}  
+  
\gamma V(S_{t+1}).  
$$
因此 $TD(\lambda)$ 退化为 $TD(0)$。
当
$$
\lambda\to 1  
$$
时，长步数 return 的权重增大，目标越来越接近 Monte Carlo return。
在 episodic setting 下，$\lambda=1$ 时：
$$
G_t^\lambda=G_t.  
$$
因此 $TD(1)$ 接近(approximate) Monte Carlo 型更新。Sutton 与 Barto 讲义中也明确说明：$\lambda=0$ 得到 $TD(0)$，$\lambda=1$ 得到 Monte Carlo 相关形式，并且 $TD(1)$ 仍然可以增量在线实现。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---
# 4. Forward view 的递归形式
从
$$
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
G_{t:t+n}  
$$
出发。注意：
$$
G_{t:t+1}
=
R_{t+1}  
+  
\gamma V(S_{t+1}),  
$$
并且当$n\ge 2$ 时：
$$
G_{t:t+n}
=
R_{t+1}  
+  
\gamma G_{t+1:t+n}.  
$$
因此：
$$
\begin{aligned}  
G_t^\lambda  
&=  
(1-\lambda)G_{t:t+1}  
+  
(1-\lambda)  
\sum_{n=2}^{\infty}  
\lambda^{n-1}G_{t:t+n}  
\\  
&=  
(1-\lambda)  
\bigl[  
R_{t+1}+\gamma V(S_{t+1})  
\bigr]  
\\  
&\quad+  
(1-\lambda)  
\sum_{n=2}^{\infty}  
\lambda^{n-1}  
\bigl[  
R_{t+1}+\gamma G_{t+1:t+n}  
\bigr].  
\end{aligned}  
$$
把 $R_{t+1}$ 的系数合并：
$$
(1-\lambda)\sum_{n=1}^{\infty}\lambda^{n-1}=1.  
$$
所以：
$$
G_t^\lambda
=
R_{t+1}  
+  
\gamma  
\left[  
(1-\lambda)V(S_{t+1})  
+  
\lambda G_{t+1}^\lambda  
\right].  
$$
即：
$$
\boxed{  
G_t^\lambda
=
R_{t+1}  
+  
\gamma  
\bigl[  
(1-\lambda)V(S_{t+1})  
+  
\lambda G_{t+1}^\lambda  
\bigr].  
}  
$$
这个递归式说明：$\lambda-return$ 在下一状态处有两种选择：
$$
1-\lambda:  
\quad  
\text{停止展开，用 }V(S_{t+1})\text{ bootstrap};  
$$
$$
\lambda:  
\quad  
\text{继续展开，使用 }G_{t+1}^\lambda.  
$$
**因此 $\lambda$ 控制 bootstrap 与 Monte Carlo 展开的混合比例。**

---

# 5. Backward view：向过去看，==分配当前 TD error==

Forward view 的问题是：计算
$$
G_t^\lambda  
$$
==**需要未来奖励和未来状态。也就是说，在时间 ($t$) 当下，通常不能立即知道完整的 $G_t^\lambda$。**==

Backward view 的思路相反：
- ==**不从过去状态向未来等待 return，而是在当前 TD error 出现时，把它分配给过去访问过的状态。**==

为此引入 ==**eligibility trace**==：
$$
E_t(s).  
$$
**它表示状态 $s$ 在时间 $t$ 对当前 TD error 的“资格”或“责任权重”。**
经典 accumulating trace 定义为：
$$
E_t(s)
=
\gamma\lambda E_{t-1}(s)  
+  
\mathbb 1\{S_t=s\}.  
$$
也就是说：

1. 每一步所有 trace 乘以 $\gamma\lambda$ 衰减；
   
2. 当前访问状态 $S_t$ 的 trace 增加 1；
   
3. ==当前 TD error $\delta_t$ 按 $E_t(s)$ **分配给所有状态**。==
   

$Backward-view\ TD(\lambda)$ 更新为：
$$
V(s)  
\leftarrow  
V(s)  
+  
\alpha\delta_tE_t(s),  
\qquad \forall s.  
$$
Sutton 与 Barto 讲义中也给出同样机制：**每一步衰减所有 traces，增加当前状态 trace，然后用 $\delta_t e_t(s)$更新所有状态；该讲义把 backward view 形象表述为“把 $\delta_t$ 向过去喊出去，声音强度随时间距离按 $\gamma\lambda$ 衰减”。**([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---

# 6. Eligibility trace 的显式展开

由递推式：
$$
E_t(s)
=
\gamma\lambda E_{t-1}(s)  
+  
\mathbb 1\{S_t=s\},  
$$
并令
$$
E_{-1}(s)=0,  
$$
可展开为：
$$
E_t(s)
=
\sum_{k=0}^{t}  
(\gamma\lambda)^{t-k}  +
\mathbb 1\{S_k=s\}.  
$$
推导如下。

先写：
$$
E_t(s)
=
\gamma\lambda E_{t-1}(s)  
+  
\mathbb 1\{S_t=s\}.  
$$
再展开 $E_{t-1}(s)$：
$$
E_{t-1}(s)
=
\gamma\lambda E_{t-2}(s)  
+  
\mathbb 1\{S_{t-1}=s\}.  
$$
代回：
$$
E_t(s)
=
(\gamma\lambda)^2E_{t-2}(s)  
+  
\gamma\lambda\mathbb 1\{S_{t-1}=s\}  
+  
\mathbb 1\{S_t=s\}.  
$$
继续展开：
$$
E_t(s)
=
\sum_{k=0}^{t}  
(\gamma\lambda)^{t-k}  
\mathbb 1\{S_k=s\}.  
$$
因此，如果状态 $s$ 在 $k$ 时刻被访问过，那么到 $t$ 时刻，其残留 trace 为：
$$
(\gamma\lambda)^{t-k}.  
$$
**这就是“向过去分配当前 TD error”的数学形式。**

---

# 7. [Forward view 与 backward view 的核心等价推导](http://www.incompleteideas.net/book/7/node5.html#eqgoal)

关键恒等式是：
$$
\boxed{  
G_t^\lambda - V(S_t)
=
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
}  
$$
它说明：
$$
\lambda\text{-return 误差}
=
\text{未来 TD errors 的指数加权和}.  
$$
这条式子是 forward view 与 backward view 连接起来的桥。

---

## 7.1 第一步：证明 $n-step\ return$ 与 TD errors 的关系

先证明：
$$
\boxed{  
G_{t:t+n}-V(S_t)
=
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k.  
}  
$$
右边展开：
$$
\begin{aligned}  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k  
&=  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}  
\left[  
R_{k+1}  
+  
\gamma V(S_{k+1})
-
 V(S_k)  
\right]  
\\  
&=  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}R_{k+1}  
\\  
&\quad+  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t+1}V(S_{k+1})
-
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}V(S_k).  
\end{aligned}  
$$
第二个价值项改指标，令 $j=k+1$：
$$
\sum_{k=t}^{t+n-1}  
\gamma^{k-t+1}V(S_{k+1})
=
\sum_{j=t+1}^{t+n}  
\gamma^{j-t}V(S_j).  
$$
第三项是：
$$
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}V(S_k)
=
V(S_t)  
+  
\sum_{j=t+1}^{t+n-1}  
\gamma^{j-t}V(S_j).  
$$
二者相减后，中间项抵消：
$$
\sum_{j=t+1}^{t+n}  
\gamma^{j-t}V(S_j)
=
 \left[  
V(S_t)  
+  
\sum_{j=t+1}^{t+n-1}  
\gamma^{j-t}V(S_j)  
\right]
=
\gamma^nV(S_{t+n})-V(S_t).  
$$
所以：
$$
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k
=
 \sum_{k=t}^{t+n-1}  
\gamma^{k-t}R_{k+1}  
+  
\gamma^nV(S_{t+n})
-
V(S_t).  
$$
而
$$
G_{t:t+n}
=
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}R_{k+1}  
+  
\gamma^nV(S_{t+n}).  
$$
因此：
$$
G_{t:t+n}-V(S_t)
=
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k.  
$$
证毕。

---
## 7.2 第二步：从 $n-step\ return$ 推到 $\lambda-return$

continuing case 中：
$$
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}G_{t:t+n}.  
$$
由于权重和为 1：
$$
V(S_t)
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}V(S_t).  
$$
所以：
$$
\begin{aligned}  
G_t^\lambda - V(S_t)  
&=  
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
\left[  
G_{t:t+n}-V(S_t)  
\right]  
\\  
&=  
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k.  
\end{aligned}  
$$
**交换求和顺序。** 固定某个 $k\ge t$，令
$$
m=k-t.  
$$
$\delta_k$ 会出现在所有满足
$$
n\ge m+1  
$$
的 n-step return 中。因此 $\delta_k$ 的 $\lambda$ 权重为：
$$
(1-\lambda)  
\sum_{n=m+1}^{\infty}  
\lambda^{n-1}
=
 (1-\lambda)\lambda^m  
\sum_{j=0}^{\infty}\lambda^j
=
\lambda^m.  
$$
同时 TD error 自身还有折扣：
$$
\gamma^{k-t}
=
\gamma^m.  
$$
所以总权重为：
$$
(\gamma\lambda)^m
=
(\gamma\lambda)^{k-t}.  
$$
因此：
$$
\boxed{  
G_t^\lambda - V(S_t)
=
\sum_{k=t}^{\infty}  
(\gamma\lambda)^{k-t}\delta_k.  
}  
$$
episodic case 中：
$$
\boxed{  
G_t^\lambda - V(S_t)
=
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
}  
$$
这个 telescoping 关系也出现在资格迹讲义中：forward view 和 backward view 对 offline 更新等价；online 更新在小步长时近似等价。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---

# 8. 由核心恒等式推出 backward view

Forward view 对时间$t$访问的状态$S_t$的更新($\lambda - return$)是：
$$
\Delta V(S_t)
=
\alpha  
\left[  
G_t^\lambda - V(S_t)  
\right].  
$$
代入核心恒等式：
$$
\Delta V(S_t)
=
\alpha  
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
$$
这说明：
$$
S_t  
$$
应该接收未来每个 TD error $\delta_k$的影响，权重为：
$$
(\gamma\lambda)^{k-t}.  
$$
==**但是在时间 $k$ 发生时，不能回到过去重新执行 forward-view 更新。== Backward view 的办法是：在时间 $k$ 保存每个过去状态的 trace：**
$$
E_k(s)
=
\sum_{t=0}^{k}  
(\gamma\lambda)^{k-t}  
\mathbb 1\{S_t=s\}.  
$$
**当前 TD error $\delta_k$ 到来时，直接更新所有状态**：
$$
\Delta V_k(s)
=
\alpha\delta_k E_k(s).  
$$
展开 $E_k(s)$：
$$
\Delta V_k(s)
=
\alpha\delta_k  
\sum_{t=0}^{k}  
(\gamma\lambda)^{k-t}  
\mathbb 1\{S_t=s\}.  
$$
**这表示：当前 TD error $\delta_k$ 被分配给所有过去访问过的 $S_t=s$，并且距离越远权重越小。**

这正好实现了 forward view 中：
$$
\alpha  
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k  
$$
的更新。

---

# 9. Offline 情况下的严格等价
设一个 episode 为：
$$
S_0,S_1,\dots,S_T.  
$$
Forward view 的总更新可以写为：
$$
\Delta_{\text{forward}}(s)
=
\sum_{t=0}^{T-1}  
\alpha  
\mathbb 1\{S_t=s\}  
\left[  
G_t^\lambda - V(S_t)  
\right].  
$$
代入：
$$
G_t^\lambda - V(S_t)
=
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
$$
得到：
$$
\Delta_{\text{forward}}(s)
=
\sum_{t=0}^{T-1}  
\alpha  
\mathbb 1\{S_t=s\}  
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
$$
交换求和顺序：
$$
\Delta_{\text{forward}}(s)
=
\sum_{k=0}^{T-1}  
\alpha\delta_k  
\sum_{t=0}^{k}  
(\gamma\lambda)^{k-t}  
\mathbb 1\{S_t=s\}.  
$$
括号内正是：
$$
E_k(s)
=
\sum_{t=0}^{k}  
(\gamma\lambda)^{k-t}  
\mathbf 1{S_t=s}.  
$$
所以：
$$
\Delta_{\text{forward}}(s)
=
\sum_{k=0}^{T-1}  
\alpha\delta_k E_k(s).  
$$
这正是 backward view 的累计更新：
$$
\Delta_{\text{backward}}(s)
=
\sum_{k=0}^{T-1}  
\alpha\delta_kE_k(s).  
$$
因此：
$$
\boxed{  
\Delta_{\text{forward}}(s)
=
\Delta_{\text{backward}}(s).  
}  
$$
这就是 forward view 与 backward view 的等价性。

但该等价性严格依赖一个条件：episode 中用于计算 $\delta_k$ 和 $G_t^\lambda$的价值函数 $V$ 固定不变，即 offline updating。Sutton 与 Barto 讲义明确指出，forward theoretical view 与 backward mechanistic view 对 offline updating 等价；online updating 在小 $\alpha$ 下相似。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---

# 10. Online 情况下为什么不完全等价？

实际 $TD(\lambda)$ 通常每一步更新：
$$
V_{t+1}\ne V_t.  
$$
于是：
$$
\delta_t
=
 R_{t+1}  
+  
\gamma V_t(S_{t+1})
-
V_t(S_t)  
$$
使用的是当前时刻的 $V_t$。
但后续：
$$
\delta_{t+1}
=
 R_{t+2}  
+  
\gamma V_{t+1}(S_{t+2})
-
V_{t+1}(S_{t+1})  
$$
使用的是已经更新过的 $V_{t+1}$。

**传统 forward view 的 $\lambda-return$ 推导通常假设 episode 内的 $V$ 不变。因此在线更新会破坏严格代数等价。**

**True Online $TD(\lambda)$ 的论文正是针对这个问题：传统 online $TD(\lambda)$ 与 conventional forward view 只近似匹配，因为 conventional forward view 假定 episode 内估计不变；true online $TD(\lambda)$ 引入新的 forward view 和新的 eligibility trace，使在线算法与 forward view 在任意步长下保持精确等价。**([Proceedings of Machine Learning Research](https://proceedings.mlr.press/v32/seijen14.pdf?utm_source=chatgpt.com "True Online TD(λ) - Proceedings of Machine Learning Research"))
因此需要区分：
$$
\boxed{  
\text{传统 TD($\lambda$)：offline forward/backward 精确等价；online 情况通常近似等价。}  
}  
$$
$$
\boxed{  
\text{True Online TD($\lambda$)：重新定义 online forward view 后，可实现精确等价。}  
}  
$$


---

# 11. Forward view 与 backward view 的对照

| 维度            | Forward view                                         | Backward view                              |
| ------------- | ---------------------------------------------------- | ------------------------------------------ |
| 基本方向          | 从当前状态向未来看                                            | 从当前 TD error 向过去分配                         |
| 核心对象          | $\lambda-return\ G_t^\lambda$                        | eligibility trace $E_t(s)$                 |
| 更新形式          | $V(S_t)\leftarrow V(S_t)+\alpha(G_t^\lambda-V(S_t))$ | $V(s)\leftarrow V(s)+\alpha\delta_tE_t(s)$ |
| 是否需要未来信息      | 需要未来 rewards / states                                | 不需要，在线更新                                   |
| 理论作用          | 说明 $TD(\lambda)$ 目标是什么                               | 说明 $TD(\lambda)$ 如何实现                      |
| 与 MC/TD(0) 关系 | 直接体现 $n-step\ return$ 混合                             | 通过 trace 衰减体现                              |
| 精确等价条件        | offline、固定 $V$                                       | offline 累计更新与 forward view 等价              |

---

# 12. 一个时间轴例子

设某状态在时间 t 被访问：
$$
S_t=s.  
$$
那么在 forward view 中，它的更新目标为：

$$
G_t^\lambda - V(S_t)
=
\delta_t  
+  
\gamma\lambda\delta_{t+1}  
+  
(\gamma\lambda)^2\delta_{t+2}  
+  
\cdots.  
$$
也就是说，未来 TD errors 按权重影响 $S_t$：
$$
\delta_t:  
1,  
$$
$$
\delta_{t+1}:  
\gamma\lambda,  
$$
$$
\delta_{t+2}:  
(\gamma\lambda)^2,  
$$
$$
\delta_{t+3}:  
(\gamma\lambda)^3.  
$$
在 backward view 中，状态 $s$ 在时间 $t$ 的 trace 为 1：
$$
E_t(s)=1.  
$$
下一步衰减为：
$$
E_{t+1}(s)=\gamma\lambda.  
$$
再下一步：
$$
E_{t+2}(s)=(\gamma\lambda)^2.  
$$
所以当 $\delta_{t+2}$ 出现时，它对$s$的更新权重正好是：
$$
(\gamma\lambda)^2.  
$$
这与 forward view 完全一致。
因此：
$$
\boxed{  
\text{forward view 中“未来 TD errors 对过去状态的影响”，在 backward view 中由 trace 自动保存。} } 
$$
---

# 13. 与 $TD(0)$、Monte Carlo 的关系

## 13.1 ($\lambda=0$)

Trace 递推为：
$$
E_t(s)=\gamma\cdot 0\cdot E_{t-1}(s)+\mathbb 1\{S_t=s\}.  
$$
所以：
$$
E_t(s)=\mathbb 1\{S_t=s\}.  
$$
只有当前状态有 trace，更新为：
$$
V(S_t)  
\leftarrow  
V(S_t)  
+  
\alpha\delta_t.  
$$
即 TD(0)。

---
## 13.2 ($\lambda=1$)

Trace 衰减为：
$$
E_t(s)=\gamma E_{t-1}(s)+\mathbb 1\{S_t=s\}.  
$$
过去状态保留更长时间。Forward view 中：
$$
G_t^\lambda  
$$
接近完整 Monte Carlo return。episodic 情况下，($\lambda=1$) 对应 Monte Carlo 型目标。
因此：
$$
\boxed{  
\lambda\text{ 越小，越接近一步 TD；}  
}  
$$
$$
\boxed{  
\lambda\text{ 越大，越接近 Monte Carlo。}  
}  
$$

---

# 14. 函数逼近下的 backward view

若使用参数化价值函数：
$$
\hat v(s,w),  
$$

则 trace 不再是每个状态一个标量，而是参数向量：
$$
e_t\in\mathbb R^d.  
$$
Semi-gradient $TD(\lambda)$ 的 trace 为：
$$
e_t
=
\gamma\lambda e_{t-1}  
+  
\nabla_w \hat v(S_t,w_t).  
$$
TD error 为：
$$
\delta_t
=
 R_{t+1}  
+  
\gamma \hat v(S_{t+1},w_t)
-
\hat v(S_t,w_t).  
$$
参数更新为：
$$
w_{t+1}
=
w_t  
+  
\alpha\delta_t e_t.  
$$
若是线性函数逼近：
$$
\hat v(s,w)=w^\top x(s),  
$$
则：
$$
\nabla_w \hat v(s,w)=x(s),  
$$
所以：
$$
e_t
=
\gamma\lambda e_{t-1}  
+  
x(S_t).  
$$
这说明，在函数逼近中，eligibility trace 记录的是“哪些参数最近参与了预测”，而不是单纯记录“哪些状态最近出现”。

---

# 15. 控制问题中的 backward view：$Sarsa(\lambda)$

预测问题保存状态 trace：
$$
E_t(s).  
$$
控制问题中，$Sarsa(\lambda)$ 保存状态—动作 trace：

$$
E_t(s,a)
=
\gamma\lambda E_{t-1}(s,a)  
+  
\mathbb 1\{S_t=s,A_t=a\}.  
$$
TD error 为：
$$
\delta_t
=
R_{t+1}  
+  
\gamma Q(S_{t+1},A_{t+1})
-
Q(S_t,A_t).  
$$
更新为：
$$
Q(s,a)  
\leftarrow  
Q(s,a)  
+  
\alpha\delta_tE_t(s,a).  
$$
Sutton 与 Barto 资格迹讲义中也给出了$Sarsa(\lambda)$ 的形式：为 state-action pairs 保存 eligibility，并用 $\delta_t e_t(s,a)$ 更新 $Q(s,a)$。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---

# 16. 常见误解澄清

## 16.1 Backward view 不是“反向运行环境”

Backward view 并不需要知道过去状态的逆转移，也不需要从 $S_{t+1}$ 反推 $S_t$。它**只是保存过去访问事件的 trace，然后用当前 TD error 更新这些过去状态**。

---

## 16.2 Forward view 不是实际在线算法

Forward view 更像目标定义：
$$
\text{如果未来全部可见，那么应该用什么 target 更新 }S_t。  
$$
由于 $G_t^\lambda$依赖未来奖励，forward view 通常不直接作为在线算法实现。

---
## 16.3 Eligibility trace 不是经验回放

Eligibility trace 保存的是指数衰减权重：

$$
E_t(s)
=
\sum_{k=0}^{t}  
(\gamma\lambda)^{t-k}  
\mathbb 1\{S_k=s\}.  
$$


它不保存完整 transition 数据，也不重新采样过去经验。经验回放是把历史 transition 存入 buffer 后重新训练；**eligibility trace 是在当前 TD error 出现时，按衰减权重即时更新过去相关状态或参数。**

---

# 17. 总结

Forward view：
$$
\boxed{  
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
G_{t:t+n}  
}  
$$
表示从当前状态向未来看，把所有 (n)-step returns 做指数加权平均。因此它回答：
$$
\boxed{  
\text{TD($\lambda$) 到底想用什么目标更新当前状态？}  
}  
$$
Backward view：
$$
\boxed{  
E_t(s)
=
\gamma\lambda E_{t-1}(s)  
+  
\mathbb 1\{S_t=s\}  
}  
$$
$$
\boxed{  
V(s)  
\leftarrow  
V(s)  
+  
\alpha\delta_tE_t(s)  
}  
$$
表示当前 TD error 按 eligibility trace 分配给过去访问过的状态。因此它回答：
$$
\boxed{  
\text{如何在线、增量地实现 forward view 的更新？}  
}  
$$
二者的桥梁是：
$$
\boxed{  
G_t^\lambda - V(S_t)
=
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
}  
$$
这条式子说明：
$$
\boxed{  
\lambda\text{-return 误差}

\text{未来 TD errors 的指数加权和}.  
}  
$$
所以，forward view 和 backward view 的本质关系是：

$$
\boxed{  
\text{forward view 把 TD($\lambda$) 表达为多步 return 的加权平均；}  
}  
$$
$$
\boxed{  
\text{backward view 用 eligibility traces 把同一个加权结构在线实现出来。}  
}  
$$


这里的“改变累加次序”本质上是：**同一个二维索引集合中的项没有变，只是从“先按 (n) 分组”改成“先按 (k) 分组”**。在有限求和中，这只是重新排列；在无限求和中，需要满足非负项或绝对收敛等条件，才能合法交换求和次序。Fubini/Tonelli 型定理正是处理这类“能否交换累加、积分次序”的标准工具：非负项可用 Tonelli 思路，绝对可和项可用 Fubini 思路。([Wikipedia](https://en.wikipedia.org/wiki/Fubini%27s_theorem?utm_source=chatgpt.com "Fubini's theorem"))

---

# 1. 先用一个有限二维求和说明

考虑：
$$
\sum_{n=1}^{3}\sum_{k=1}^{n}a_{n,k}.  
$$
按照原来的顺序，先固定 (n)，再枚举 (k)：


$$
\sum_{n=1}^{3}\sum_{k=1}^{n}a_{n,k}
=
\sum_{k=1}^{1}a_{1,k}  
+  
\sum_{k=1}^{2}a_{2,k}  
+  
\sum_{k=1}^{3}a_{3,k}.  
$$


展开为：


$$
a_{1,1}  
+  
a_{2,1}+a_{2,2}  
+  
a_{3,1}+a_{3,2}+a_{3,3}.  
$$


这些项对应二维索引集合：


$$
D={(n,k):1\le n\le 3,\ 1\le k\le n}.  
$$


把所有点列出来：

$$
(1,1),  
$$
$$
(2,1),(2,2),  
$$
$$
(3,1),(3,2),(3,3).  
$$
现在改变累加次序，即先固定 (k)，再找所有满足条件的 (n)。

对于 k=1，可取：


$$
n=1,2,3.  
$$

对于 k=2，可取：


$$
n=2,3.  
$$


对于 k=3，可取：


$$
n=3.  
$$


所以同一个和也可以写成：


$$
\sum_{k=1}^{3}\sum_{n=k}^{3}a_{n,k}.  
$$


展开为：


$$
a_{1,1}+a_{2,1}+a_{3,1}  
+  
a_{2,2}+a_{3,2}  
+  
a_{3,3}.  
$$


项完全相同，只是顺序不同。

因此：


$$
\boxed{  
\sum_{n=1}^{3}\sum_{k=1}^{n}a_{n,k}
=
\sum_{k=1}^{3}\sum_{n=k}^{3}a_{n,k}.  
}  
$$


这个过程的关键不是机械地“交换两个求和号”，而是重新描述索引区域：


$$
1\le k\le n\le 3  
$$


等价于：


$$
1\le k\le 3,\qquad k\le n\le 3.  
$$


---

# 2. 一般有限三角区域的换序

一般形式：


$$
\sum_{n=1}^{N}\sum_{k=1}^{n}a_{n,k}.  
$$


索引条件是：


$$
1\le n\le N,\qquad 1\le k\le n.  
$$

也就是：


$$
1\le k\le n\le N.  
$$


如果改成先固定 (k)，则 (k) 最小为 1，最大为 (N)：


$$
1\le k\le N.  
$$


在固定 (k) 后，(n) 必须满足：


$$
k\le n\le N.  
$$


所以：


$$
\boxed{  
\sum_{n=1}^{N}\sum_{k=1}^{n}a_{n,k}
=
\sum_{k=1}^{N}\sum_{n=k}^{N}a_{n,k}.  
}  
$$


有限求和中，这个操作总是合法，因为只是有限多个项的重新排列。

---

# 3. $TD(\lambda)$ 推导中为什么要改变累加次序？

在 $TD(\lambda)$的 forward-view 推导中，会遇到类似表达式：

$$
G_t^\lambda - V(S_t)
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k.  
$$


这里有两层求和：

外层：


$$
n=1,2,3,\dots  
$$


表示 (n)-step return 的步数。

内层：


$$
k=t,t+1,\dots,t+n-1  
$$


表示第 n-step return 中包含哪些 TD error。

所以原式的索引集合是：


$$
D

{(n,k): n\ge 1,\ t\le k\le t+n-1}.  
$$


这个条件可以改写。

由

$$
k\le t+n-1  
$$


得到：


$$
n\ge k-t+1.  
$$


同时：
$$
k\ge t.  
$$
所以同一个索引集合也可以写成：


$$
D

{(n,k): k\ge t,\ n\ge k-t+1}.  
$$

也就是说：

原来是先固定 ($n$)，然后 ($k$) 从 ($t$) 到 ($t+n-1$)。

换序后是先固定 ($k$)，然后 ($n$) 从 ($k-t+1$) 到 ($\infty$)。

因此：


$$
\boxed{  
\sum_{n=1}^{\infty}  
\sum_{k=t}^{t+n-1}  
(\cdots)
=
\sum_{k=t}^{\infty}  
\sum_{n=k-t+1}^{\infty}  
(\cdots).  
}  
$$


Sutton 与 Barto 的 eligibility trace 讲义中在说明 forward view 与 backward view 等价时，也正是通过这种重排：把“对每个访问时刻向未来累加 TD error”改写成“对每个 TD error 向过去分配”。([www-anw.cs.umass.edu](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf?utm_source=chatgpt.com "Chapter 7: Eligibility Traces"))

---

# 4. 具体推导：从原式换序到 TD error 加权和

从：


$$
G_t^\lambda - V(S_t)
=
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k  
$$


开始。

把所有项写成二维索引形式：

$$
(1-\lambda)  
\sum_{n=1}^{\infty}  
\sum_{k=t}^{t+n-1}  
\lambda^{n-1}\gamma^{k-t}\delta_k.  
$$


换序后：


$$
(1-\lambda)  
\sum_{k=t}^{\infty}  
\sum_{n=k-t+1}^{\infty}  
\lambda^{n-1}\gamma^{k-t}\delta_k.  
$$


对于固定的 (k)，$\gamma^{k-t}\delta_k$ 与 (n) 无关，所以可以提出内层求和：



$$
\sum_{k=t}^{\infty}  
\gamma^{k-t}\delta_k  
\left[  
(1-\lambda)  
\sum_{n=k-t+1}^{\infty}  
\lambda^{n-1}  
\right].  
$$


现在计算括号。

令：

[  
$$
m=k-t.  
$$
]

则内层求和从：

[  
$$
n=m+1  
$$
]

开始：


$$
(1-\lambda)  
\sum_{n=m+1}^{\infty}  
\lambda^{n-1}.  
$$


展开：


$$
(1-\lambda)  
\left(  
\lambda^m+\lambda^{m+1}+\lambda^{m+2}+\cdots  
\right).  
$$


这是几何级数：


$$
\lambda^m+\lambda^{m+1}+\lambda^{m+2}+\cdots
=
 \lambda^m  
\left(  
1+\lambda+\lambda^2+\cdots  
\right)
=
\frac{\lambda^m}{1-\lambda}.  
$$


因此：

$$
(1-\lambda)  
\sum_{n=m+1}^{\infty}  
\lambda^{n-1}
=
 (1-\lambda)\frac{\lambda^m}{1-\lambda}
=
\lambda^m.  
$$


代回 ($m=k-t$)：


$$
(1-\lambda)  
\sum_{n=k-t+1}^{\infty}  
\lambda^{n-1}
=
\lambda^{k-t}.  
$$


所以：


$$
G_t^\lambda - V(S_t)
=
\sum_{k=t}^{\infty}  
\gamma^{k-t}\delta_k  
\lambda^{k-t}.  
$$


即：


$$
\boxed{  
G_t^\lambda - V(S_t)
=
\sum_{k=t}^{\infty}  
(\gamma\lambda)^{k-t}\delta_k.  
}  
$$


这就是 $TD(\lambda)$ 中最关键的等价式：$\lambda-return$ 误差可以写成未来 TD errors 的指数加权和。

---

# 5. 为什么换序后 (n) 的下界是 ($k-t+1$)？

这是最容易混淆的地方。

原条件是：


$$
k\le t+n-1.  
$$

把它解成关于 (n) 的不等式：


$$
k-t+1\le n.  
$$


所以固定某个 TD error$\delta_k$后，需要问：


$$
\delta_k\text{ 出现在哪些 }n\text{-step return 里面？}  
$$

答案是：只要 (n)-step return 能看到时间 (k)，就包含 $(\delta_k)$。

从 (t) 出发的 (n)-step return 覆盖 TD error：


$$
\delta_t,\delta_{t+1},\dots,\delta_{t+n-1}.  
$$


所以 $(\delta_k)$ 被包含的条件是：

$$
k\le t+n-1.  
$$


等价于：


$$
n\ge k-t+1.  
$$


例如：

- $(\delta_t)$ 出现在所有 $(n\ge 1)$的 return 中；
  
- $(\delta_{t+1})$出现在所有 $(n\ge 2)$ 的 return 中；
  
- $(\delta_{t+2})$ 出现在所有 $(n\ge 3)$ 的 return 中；
  
- 一般地，$(\delta_k)$ 出现在所有 $(n\ge k-t+1)$的 return 中。
  

这就是换序后的内层求和范围。

---

# 6. 有限 episode 情况下的换序

若 episode 在 (T) 终止，则相关求和是有限的：


$$
\sum_{n=1}^{T-t-1}  
\sum_{k=t}^{t+n-1}  
a_{n,k}.  
$$


索引条件为：


$$
1\le n\le T-t-1,  
\qquad  
t\le k\le t+n-1.  
$$


等价于：


$$
t\le k\le T-2,  
\qquad  
k-t+1\le n\le T-t-1.  
$$

所以：


$$
\boxed{  
\sum_{n=1}^{T-t-1}  
\sum_{k=t}^{t+n-1}  
a_{n,k}
=
\sum_{k=t}^{T-2}  
\sum_{n=k-t+1}^{T-t-1}  
a_{n,k}.  
}  
$$


如果把最后的完整 Monte Carlo return 也纳入统一处理，边界会多出终止项；但换序的思想不变：先确定二维索引区域，再用另一种顺序枚举同一个区域。

---

# 7. 无限求和中为什么需要谨慎？

有限求和中，换序总是合法。

无限求和中，不能无条件改变累加次序。原因是无穷级数的“和”是极限，改变顺序可能改变极限，甚至导致收敛性变化。

标准充分条件有两个：

## 7.1 所有项非负

若：


$$
a_{n,k}\ge 0,  
$$


则可以交换求和次序。这对应 Tonelli 型结论：非负项不存在正负抵消导致的顺序敏感问题。([Wikipedia](https://en.wikipedia.org/wiki/Fubini%27s_theorem?utm_source=chatgpt.com "Fubini's theorem"))

## 7.2 绝对收敛

若：
$$
\sum_{n,k}|a_{n,k}|<\infty,  
$$
则可以交换求和次序。这对应 Fubini 型结论：绝对可和时，改变累加顺序不会改变总和。([Wikipedia](https://en.wikipedia.org/wiki/Fubini%27s_theorem?utm_source=chatgpt.com "Fubini's theorem"))

在 $TD(\lambda)$ 的理论推导中，若考虑折扣因子与 trace 参数满足：


$$
0\le \gamma\lambda<1,  
$$


并且 TD error 有界：


$$
|\delta_k|\le C,  
$$


则有：


$$
\sum_{k=t}^{\infty}  
|(\gamma\lambda)^{k-t}\delta_k|  
\le  
C  
\sum_{k=t}^{\infty}  
(\gamma\lambda)^{k-t}
=
\frac{C}{1-\gamma\lambda}  
<\infty.  
$$


因此对应级数绝对收敛，换序是合法的。

---

# 8. 用一句话概括

“改变累加次序”不是简单把两个求和号互换，而是：


$$
\boxed{  
\text{先确定所有被累加的索引点，再用另一种顺序枚举同一批索引点。}  
}  
$$


在 $TD(\lambda)$ 推导中，原来的累加方式是：


$$
\text{固定 }n\text{，看这个 }n\text{-step return 包含哪些 }\delta_k。  
$$


改变次序后变成：


$$
\text{固定 }k\text{，看这个 TD error }\delta_k\text{ 被哪些 }n\text{-step return 包含。}  
$$


于是：

$$
(1-\lambda)  
\sum_{n=1}^{\infty}  
\lambda^{n-1}  
\sum_{k=t}^{t+n-1}  
\gamma^{k-t}\delta_k  
$$


变成：

$$
\sum_{k=t}^{\infty}  
\gamma^{k-t}\delta_k  
\left[  
(1-\lambda)  
\sum_{n=k-t+1}^{\infty}  
\lambda^{n-1}  
\right],  
$$

再由几何级数得到：


$$
\boxed{  
G_t^\lambda - V(S_t)
=
\sum_{k=t}^{\infty}  
(\gamma\lambda)^{k-t}\delta_k.  
}  
$$


这一步就是 forward view 推导 backward view 的代数核心。



---

下面给出 $TD(\lambda)$的完整更新过程**。默认讨论最标准的 **on-policy policy evaluation**：策略 ($\pi$) 固定，目标是估计状态价值函数 $(v_\pi(s))$。这是 $TD(\lambda)$ 最基础、最清晰的形式；$Sarsa(\lambda)$、$Q(\lambda)$ 等控制算法是在此基础上把 trace 从状态 (s) 推广到状态—动作对 ($(s,a)$)。Sutton 与 Barto 的资格迹讲义把 $TD(\lambda)$ 的 backward view 描述为：每一步计算 TD error，增加当前状态的 eligibility trace，然后用 $\delta_t e_t(s)$ 更新所有状态；同时 trace 按 $(\gamma\lambda)$ 衰减。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf "Chapter7.ppt"))

---

# 1. 问题设定

给定一个固定策略 $\pi$，轨迹为：
$$
S_0,A_0,R_1,S_1,A_1,R_2,S_2,\dots  
$$
状态价值函数为：
$$
v_\pi(s)
=
\mathbb E_\pi  
\left[  
G_t\mid S_t=s  
\right],  
$$
其中：
$$
G_t
=
R_{t+1}  
+  
\gamma R_{t+2}  
+  
\gamma^2R_{t+3}  
+\cdots.  
$$
$TD(\lambda)$ 要学习一个估计函数：


$$
V(s)\approx v_\pi(s).  
$$


算法维护两个主要量：
$$
V(s)  
$$
和
$$
e(s).  
$$
其中 (e(s)) 是状态 (s) 的 eligibility trace。

---

# 2. $TD(\lambda)$ 的核心更新公式

每个时间步 $t$，先计算一步 TD error：


$$
\boxed{  
\delta_t
=
 R_{t+1}  
+  
\gamma V_t(S_{t+1})
-
V_t(S_t).  
}  
$$


如果 $S_{t+1}$ 是终止状态，则令：


$$
V_t(S_{t+1})=0.  
$$

然后更新当前状态的 trace：


$$
\boxed{  
e_t(s)
=
\gamma\lambda e_{t-1}(s)  
+  
\mathbb 1\{S_t=s\}.  
}  
$$


最后对所有状态做价值更新：


$$
\boxed{  
V_{t+1}(s)
=
V_t(s)  
+  
\alpha \delta_t e_t(s),  
\qquad \forall s.  
}  
$$

这三条式子就是 tabular $TD(\lambda)$ 的主体。现代论文也常把 $TD(\lambda)$ 描述为 backward view 的算法实现：维护一个 trace 向量，作为过去状态或过去梯度的短期记忆，然后用当前 TD error 给过去访问状态分配信用。([arXiv](https://arxiv.org/html/2312.12972v1 "From Past to Future: Rethinking Eligibility Traces"))

---

# 3. 逐步算法：tabular accumulating-trace $TD(\lambda)$

## 3.1 初始化

对所有状态 ($s\in\mathcal S$)，初始化：

$$
V(s)\ \text{任意},  
$$
$$
e(s)=0.  
$$
例如：
$$
V(s)=0,\qquad e(s)=0.  
$$
选择超参数：
$$
\alpha>0,  
\qquad  
0\le \gamma\le 1,  
\qquad  
0\le \lambda\le 1.  
$$

其中：

- ($\alpha$)：学习率；
  
- ($\gamma$)：回报折扣因子；
  
- ($\lambda$)：trace 衰减参数。
  

---

## 3.2 每个 episode 开始

在每个 episode 开始时，清空所有 traces：


$$
e(s)=0,\qquad \forall s.  
$$


然后初始化起始状态：


$$
S_0=s_0.  
$$


---

## 3.3 每个时间步的更新

在时间 (t)，状态为 ($S_t$)。
### 第一步：根据策略选择动作


$$
A_t\sim \pi(\cdot|S_t).  
$$


执行动作，观察：


$$
R_{t+1},S_{t+1}.  
$$


---

### 第二步：计算 TD error

$$
\delta_t
=
 R_{t+1}  
+  
\gamma V(S_{t+1})
-
V(S_t).  
$$
若 $S_{t+1}$是 terminal，则使用：
$$
V(S_{t+1})=0,  
$$
因此：
$$
\delta_t
=
R_{t+1}
-
V(S_t).  
$$


---

### 第三步：更新当前状态的 eligibility trace

经典 accumulating trace 为：


$$
e(S_t)\leftarrow e(S_t)+1.  
$$


此时当前状态的 trace 被增加，表示当前状态对当前以及未来 TD error 有资格接收更新。

---

### 第四步：对所有状态更新价值函数

对所有状态 (s)：


$$
V(s)\leftarrow V(s)+\alpha\delta_t e(s).  
$$


也就是说，不只是 $S_t$ 被更新，所有 trace 非零的历史状态都会被更新。trace 越大，当前 TD error 对该状态的影响越大。

---

### 第五步：衰减所有 traces

对所有状态 (s)：


$$
e(s)\leftarrow \gamma\lambda e(s).  
$$


这一步表示：随着时间流逝，过去状态的资格逐渐衰减。

---

### 第六步：进入下一状态


$$
S_t\leftarrow S_{t+1}.  
$$


如果 ($S_{t+1}$) 是 terminal，则 episode 结束。

Sutton 与 Barto 的 on-line tabular TD(\lambda) 伪代码正是这个结构：初始化 ($V(s)$) 和 (e(s))，每步计算 ($\delta=r+\gamma V(s')-V(s)$)，令 ($e(s)\leftarrow e(s)+1$)，对所有状态执行 ($V(s)\leftarrow V(s)+\alpha\delta e(s)$)，再执行 ($e(s)\leftarrow\gamma\lambda e(s)$)。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf "Chapter7.ppt"))

---

# 4. 伪代码形式

```text
Input: policy π, step size α, discount γ, trace parameter λ

Initialize V(s) arbitrarily for all s

For each episode:
    Initialize e(s) = 0 for all s
    Initialize S

    Repeat until S is terminal:

        Choose A ~ π(. | S)
        Take A, observe R, S'

        if S' is terminal:
            δ = R - V(S)
        else:
            δ = R + γ V(S') - V(S)

        e(S) = e(S) + 1

        For all states s:
            V(s) = V(s) + α δ e(s)
            e(s) = γ λ e(s)

        S = S'
```

---

# 5. 更新顺序的两种等价写法

$TD(\lambda)$的 trace 更新有两种常见写法。

## 写法 A：先增量，再整体衰减

这对应上面的伪代码：


$$
e(S_t)\leftarrow e(S_t)+1,  
$$

$$
V(s)\leftarrow V(s)+\alpha\delta_t e(s),  
$$

$$
e(s)\leftarrow \gamma\lambda e(s).  
$$


在这种实现中，episode 开始时 (e=0)，每一步更新结束后，trace 已经被衰减，留给下一步使用。

---

## 写法 B：先衰减，再增加当前状态

另一种数学写法是：


$$
e_t(s)
=
\gamma\lambda e_{t-1}(s)  
+  
\mathbb 1\{S_t=s\},  
$$


然后：


$$
V_{t+1}(s)
=
V_t(s)  
+  
\alpha\delta_t e_t(s).  
$$


对应伪代码为：

```text
For all states s:
    e(s) = γ λ e(s)

e(S) = e(S) + 1

For all states s:
    V(s) = V(s) + α δ e(s)
```

两种写法本质等价，只是变量 (e) 在代码中表示的是“已经衰减后的 trace”还是“当前更新使用的 trace”。严谨推导中通常使用：


$$
\boxed{  
e_t(s)=\gamma\lambda e_{t-1}(s)+\mathbb 1\{S_t=s\}.  
}  
$$


---

# 6. trace 的显式形式

由递推：

$$
e_t(s)
=
\gamma\lambda e_{t-1}(s)  
+  
\mathbb 1\{S_t=s\},  
$$
可展开为：
$$
\boxed{  
e_t(s)
=
\sum_{k=0}^{t}  
(\gamma\lambda)^{t-k}  
\mathbb 1\{S_k=s\}.  
}  
$$

这说明：

- 如果状态 (s) 在当前时刻 (t) 被访问，则贡献 (1)；
  
- 如果在上一步 (t-1) 被访问，则当前 trace 中贡献 $(\gamma\lambda)$；
  
- 如果在 (t-2) 被访问，则贡献 $(\gamma\lambda)^2$；
  
- 依此类推。
  

所以 eligibility trace 是过去访问事件的指数衰减记忆。Sutton 与 Barto 的讲义将 backward view 直观解释为把当前 TD error “向过去喊出去”，声音强度随时间距离按 (\gamma\lambda) 衰减。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf "Chapter7.ppt"))

---

# 7. 单步更新的完整展开

假设时间 (t) 处，过去访问过状态：


$$
S_{t-2}=x,\qquad S_{t-1}=y,\qquad S_t=z.  
$$


假设这些状态最近只出现过一次，则当前 traces 近似为：


$$
e_t(z)=1,  
$$

$$
e_t(y)=\gamma\lambda,  
$$
$$
e_t(x)=(\gamma\lambda)^2.  
$$


计算 TD error：


$$
\delta_t
=
 R_{t+1}  
+  
\gamma V(S_{t+1})
-
V(S_t).  
$$
更新为：


$$
V(z)\leftarrow V(z)+\alpha\delta_t,  
$$

$$
V(y)\leftarrow V(y)+\alpha\delta_t\gamma\lambda,  
$$

$$
V(x)\leftarrow V(x)+\alpha\delta_t(\gamma\lambda)^2.  
$$

所以当前 TD error 不只影响当前状态 (z)，也影响过去状态 (y,x)，但影响随时间距离指数衰减。

---

# 8. $(\lambda=0)$ 时的更新过程

若：


$$
\lambda=0,  
$$


则：


$$
e_t(s)
=
 \gamma\cdot 0\cdot e_{t-1}(s)  
+  
\mathbb 1\{S_t=s\}
=
\mathbb 1\{S_t=s\}.  
$$


所以只有当前状态 (S_t) 的 trace 为 1，其他状态 trace 为 0。

更新变成：


$$
V(S_t)  
\leftarrow  
V(S_t)+\alpha\delta_t.  
$$


这正是 TD(0)。

也就是说：


$$
\boxed{  
TD(0)  
\text{ 是 $TD(\lambda)$ 在 }\lambda=0\text{ 时的特例。}  
}  
$$


Sutton 与 Barto 的讲义中也明确指出，$(\lambda=0)$ 时得到 TD(0)，$(\lambda=1)$ 时得到接近 Monte Carlo 的形式。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf "Chapter7.ppt"))

---

# 9. $(\lambda=1)$ 时的更新过程

若：


$$
\lambda=1,  
$$


则 trace 衰减为：


$$
e_t(s)=
\gamma e_{t-1}(s)  
+  
\mathbb 1\{S_t=s\}.  
$$


如果 (\gamma) 接近 1，过去状态的 trace 衰减很慢。当前 TD error 会被较强地分配给更早的状态。

在 episodic prediction 中，$\lambda=1$的 forward-view 目标接近完整 Monte Carlo return；但 backward view 仍然可以逐步在线更新，不必等 episode 结束。讲义中也说明 TD(1) 可以增量、在线运行，而不是像普通 Monte Carlo 那样必须等到 episode 结束。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf "Chapter7.ppt"))

---

# 10. 为什么 $TD(\lambda)$ 的更新等价于使用 $\lambda-return$？

Forward view 中，$TD(\lambda)$ 使用：


$$
G_t^\lambda
=
(1-\lambda)  
\sum_{n=1}^{T-t-1}  
\lambda^{n-1}G_{t:t+n}  
+  
\lambda^{T-t-1}G_t.  
$$

对应更新：


$$
V(S_t)  
\leftarrow  
V(S_t)  
+  
\alpha  
\left[  
G_t^\lambda
-
V(S_t)  
\right].  
$$


Backward view 使用：


$$
V(s)  
\leftarrow V(s)+\alpha\delta_t e_t(s).  
$$


两者的桥梁是：


$$
\boxed{  
G_t^\lambda - V(S_t)

=
\sum_{k=t}^{T-1}  
(\gamma\lambda)^{k-t}\delta_k.  
}  
$$


这说明，从 forward view 看，状态 (S_t) 应该接收未来所有 TD errors：


$$
\delta_t,\delta_{t+1},\delta_{t+2},\dots  
$$


且权重分别为：


$$
1,\gamma\lambda,(\gamma\lambda)^2,\dots  
$$


Backward view 中，eligibility trace 正好保存这些权重。因此，当未来 TD error 出现时，不需要回头重新计算 ($G_t^\lambda$)，只需用当前 trace 在线更新。Sutton 与 Barto 的讲义也说明，forward view 是理论视角，backward view 是机制视角；二者在 offline updating 中等价，online updating 在小步长时相近。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf "Chapter7.ppt"))

---

# 11. Accumulating trace 与 replacing trace

上面使用的是 **accumulating trace**：


$$
e_t(s)
=
\gamma\lambda e_{t-1}(s)  
+  
\mathbb 1\{S_t=s\}.  
$$


如果某个状态短时间内反复访问，trace 会不断累加，可能大于 1。

另一种常见形式是 **replacing trace**：


$$
e_t(s)

\begin{cases}  
1, & s=S_t,\  
\gamma\lambda e_{t-1}(s), & s\ne S_t.  
\end{cases}  
$$


区别是：

- accumulating trace：当前状态 trace 加 1；
  
- replacing trace：当前状态 trace 直接设为 1。
  

Replacing trace 可以避免某些循环任务中 trace 过度累积。

---

# 12. 函数逼近版本的 $TD(\lambda)$

如果价值函数不是表格，而是参数化函数：


$$
\hat v(s,w),  
$$

则维护参数向量 ($w$) 和 trace 向量 ($e$)。

TD error：


$$
\delta_t
=
 R_{t+1}  
+  
\gamma \hat v(S_{t+1},w_t)
-
\hat v(S_t,w_t).  
$$

trace 更新：


$$
\boxed{  
e_t
=
\gamma\lambda e_{t-1}  
+  
\nabla_w \hat v(S_t,w_t).  
}  
$$

参数更新：


$$
\boxed{  
w_{t+1}
=
w_t  
+  
\alpha\delta_t e_t.  
}  
$$


如果是线性函数逼近：


$$
\hat v(s,w)=w^\top x(s),  
$$

则：

$$

\nabla_w\hat v(s,w)=x(s),  
$$


所以：


$$
e_t=\gamma\lambda e_{t-1}+x(S_t),  
$$


 
$$
w_{t+1}=w_t+\alpha\delta_t e_t.  
$$


现代 $TD(\lambda)$相关论文也把函数逼近下的 trace 解释为过去访问状态的价值函数梯度的移动平均；该 trace 向量用于用当前 TD error 同时更新多个过去状态相关的参数方向。([arXiv](https://arxiv.org/html/2312.12972v1 "From Past to Future: Rethinking Eligibility Traces"))

---

# 13. 控制版本：$Sarsa(\lambda)$ 的更新过程

$TD(\lambda)$ 是状态价值预测算法。若用于 on-policy 控制，常见算法是 $Sarsa(\lambda)$。

此时学习：


$$
Q(s,a).  
$$


维护状态—动作 trace：

$$
e(s,a).  
$$

每一步：


$$
A_t\sim \pi(\cdot|S_t),  
$$


执行 (A_t)，得到 (R_{t+1},S_{t+1})，再选：


$$
A_{t+1}\sim \pi(\cdot|S_{t+1}).  
$$


TD error：

$$
\delta_t
=
 R_{t+1}  
+  
\gamma Q(S_{t+1},A_{t+1})
-
Q(S_t,A_t).  
$$

当前 state-action trace 增加：


$$
e(S_t,A_t)\leftarrow e(S_t,A_t)+1.  
$$


对所有 $(s,a)$：


$$
Q(s,a)\leftarrow Q(s,a)+\alpha\delta_t e(s,a),  
$$



$$
e(s,a)\leftarrow \gamma\lambda e(s,a).  
$$


Sutton 与 Barto 的讲义中也给出 $Sarsa(\lambda)$：为 state-action pair 保存 eligibility，TD error 使用 $r+\gamma Q(s',a')-Q(s,a)$，然后按 $e(s,a)$ 更新所有 $Q(s,a)$。([Autonomous Learning Laboratory](https://www-anw.cs.umass.edu/~barto/courses/cs687/Chapter%207.pdf "Chapter7.ppt"))

---

# 14. 实际实现中的稀疏 trace 优化

表格 $TD(\lambda)$ 的伪代码写作：


$$
\forall s,\quad V(s)\leftarrow V(s)+\alpha\delta e(s),  
$$



$$
\forall s,\quad e(s)\leftarrow \gamma\lambda e(s).  
$$
]

但如果状态空间很大，遍历所有状态代价很高。实际实现通常只维护 trace 显著非零的状态集合：


$$
{s:e(s)>\epsilon}.  
$$


因为：


$$
e_t(s)  
$$


会以 (\gamma\lambda) 指数衰减，许多很久未访问的状态 trace 接近 0。此时只更新最近访问过、trace 尚未衰减到阈值以下的状态即可近似实现 TD(\lambda)。

---

# 15. TD(\lambda) 更新过程的总括

TD(\lambda) 每一步做三件事：


$$
\boxed{  
1.\ \text{用一步 bootstrap 计算 TD error：}  
\quad  
\delta_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t).  
}  
$$

$$
\boxed{  
2.\ \text{用 eligibility trace 记录过去状态：}  
\quad  
e_t(s)=\gamma\lambda e_{t-1}(s)+\mathbf 1{S_t=s}.  
}  
$$

$$
\boxed{  
3.\ \text{用当前 TD error 更新所有有资格的状态：}  
\quad  
V_{t+1}(s)=V_t(s)+\alpha\delta_t e_t(s).  
}  
$$

因此 $TD(\lambda)$的本质是：

$$
\boxed{  
\text{当前 TD error 通过 eligibility traces 向过去访问过的状态传播。}  
}  
$$



$$
\boxed{  
\lambda\text{ 控制传播距离；}\lambda=0\text{ 得到 TD(0)，}\lambda=1\text{ 接近 Monte Carlo。}  
}
$$