假设一个简单状态序列 $s_0$ → $s_1$ → $s_2$ → $s_3=\text{Goal}$，$r_1=r_2=0$， $r_3=1$. 终点状态 $V(s_3)=0$，折扣因子 $\gamma$，学习率 $\alpha$.

1）$\text{TD}(0)$

目的：对 $\pi$ 评估.初始化 $V(s)=0,\forall s$. 根据 TD 更新公式

episode 1：

$$\begin{aligned}& V(s_0)=V(s_1)=0,\\& V(s_2)=0+\alpha[1+0\cdot 0]=\alpha.\end{aligned}$$

episode 2:

$$\begin{aligned}& V(s_0)=0,\ V(s_1)=0+\alpha[0+\gamma V(s_2)-0]=\alpha^2\gamma,\\ & V(s_2)=\alpha+\alpha [1-\alpha]=2\alpha-\alpha^2.\end{aligned}$$

episode 3:

$$\begin{aligned}& V(s_0)=0+\alpha[0+\gamma V(s_1)-0]=\alpha^3\gamma^2, \\& V(s_1)=\alpha^2\gamma+\alpha[\gamma(2\alpha-\alpha^2)-\alpha^2\gamma]=3\alpha^2\gamma-2\alpha^3 \gamma, \\& V(s_2)=\ldots. \\\end{aligned}$$

可以看到，每一个 episode 只传播一点.在 episode 1 中，想要更新 $s_0,s_1$ 的价值，只能等下一个 episode. 由于 $\text{TD}(0)$一次更新只看一步，它并不知道后面还有多远，因此 $\text{TD}(0)$的信息传播速度慢.

2）Monte Carlo

Monte Carlo 在一次 episode 结束后，知道整条轨迹的最终回报，其看到了每一步的奖励.针对上述序列问题，已知 $r_1,r_2,r_3$，那么可直接计算得到 $G_0,G_1,G_2$，从而得到各状态的价值，即 Monte Carlo 能更快地传播奖励信息

【注】信息传播速度快 $\neq$ 收敛速度快：$\text{TD}(0)$只利用一步信息，若环境随机，则更新时只受一步随机性的影响；而 Monte Carlo 依赖整条轨迹，任何一步随机变化都会影响，每次更新存在较大方差，使得更新可能一直剧烈震荡.TD 由于单步地逐步学习，后续状态价值会越来越稳定，更新波动会小很多，因而一般情况下收敛更稳定，收敛速度更快.但若为确定性环境，如上述的确定状态序列，明显 Monte Carlo 的收敛速度更快.

偏差： 指代作用权重、资格分配不完整.

假设一个简单状态序列 $s_0$ → $s_1$ → $s_2$ → $s_3=\text{Goal}$，$r_1=r_2=0$， $r_3=1$. 终点状态 $V(s_3)=0$，折扣因子 $\gamma$，学习率 $\alpha$.

• $\text{TD}(0)$

episode 1: $V(s_0)=V(s_1)=0,V(s_2)=\alpha$，即 $s_0,s_1$ 没有奖励，没有贡献，$s_2$ 得到奖励，有贡献. 但这样的表述明显不对：正是由 $s_1\to s_2$，$s_2$ 才能到达 $s_3$，同样地有 $s_0\to s_1$.由此出现了短暂的、不完整的分配.

原因： $\text{TD}(0)$ 只看到了下一步，如对于 $s_0$ 来说不知道再走两步便到达 Goal.

$\text{TD}(0)$：第一次只奖励 $s_2$，第二次奖励 $s_1$，第三次奖励 $s_0$，因此更早的状态需要多次重复经历才能获得更完整公平的信用分配.

• Monte Carlo

整个 episode 结束后，知道最终到达 Goal（$s_3$），且知道每一步奖励，可以直接计算每个状态真正经历得到的回报.

对于 Monte Carlo 来说，其所谓的高效分配，即是对轨迹中的状态，按照之后真正获得的累计回报来分配 直观上，$s_2$ 距 Goal($s_3$)最近，价值最大，$s_1$ 可以到达距离 Goal 更近的 $s_2$，也有价值，而 $s_0$ 虽然距 Goal 远，但最终还是可以到到 Goal，因此也分配一定的价值.

想象一排 21个状态，从左端 -10 走到右端 +10，每步等概率向左或向右，到达两端 episode 终止，奖励只有到达 +10 时 +1，其他 0.

• 如果采用 $\text{TD}(0)$（λ=0），价值信息必须从终点逐步向相邻状态传播.在 100 个 episode 训练后，远离终点的状态价值依然接近 0.
• 如果采用 MC（λ=1），每个 episode 结束后，整条路径上的状态都根据最终奖励更新，信息瞬间传遍，但因每个 episode 路径长度差异大，方差很高，学习曲线震荡剧烈.
• 取一个中间值，如 λ=0.5 或 0.7，能用明显更少的 episode 达到更低的均方根误差.这就是 λ-回报的优势：结合两者优势，加速学习.

假设一个简单状态序列 $s_0$ → $s_1$ → $s_2$ → $s_3=\text{Goal}$ .折扣因子 $\gamma$，迹退化参数 $\lambda$，初始化所有 $V=0$，迹为 $0$.

• 从 $s_0$ 到 $s_1$，迹 $E(s_0)$ =1，其它为 $0$.计算 $\delta_0$ ，此时仅更新 $V(s_0)$.

• 从 $s_1$ 到 $s_2$，$E(s_0)$ 衰减为 $\gamma\lambda$，$E(s_1)=1$，计算 $\delta_1$ ，此时更新 $V$ 会同时影响 $s_0$ 和 $s_1$，但 $s_0$ 的影响权重小于 $s_1$.

• 从 $s_2$ 到 $s_3$，$E(s_0)=(\gamma\lambda)^2$，$E(s_1)=\gamma\lambda$，$E(s_2)=1$.此时到达终点 $s_3$ 获得 $+1$ 奖励，误差 $\delta_2$ 较大.该误差会依据迹的权重同时更新 $s_0,s_1,s_2$，$s_0$ 因衰减系数得到较小的更新，$s_2$ 得到较大的更新.

  另一方面，在 $\text{TD}(0)$ 中，每一步只更新当前状态，到达终点时，得到 $+1$ 奖励与误差 $\delta_2$，但只有 $s_3$ 的前一个状态 $s_2$ 被更新，而要更新 $s_0$ 需要很多次重复经历.资格迹正好弥补了这一缺陷.

在 $\text{TD}(\lambda)$的前向视角中，定义了 $\lambda$ -回报为所有 $n$ 步回报的加权平均

$$G_t^\lambda = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)},$$

其中第 $n$ 步回报的权重为

$$w_n=(1-\lambda)\lambda^{n-1}.$$

可能会问为什么要这样进行权重分配，实际上该权重呈几何级数（衰减）.

• 权重需要构成一个概率分布，即权重之和为 $1$ :

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

• 几何分布的“无记忆性”： 几何分布是唯一具有无记忆性的离散分布.

从直观上理解 $\lambda$ - 回报的构造过程：站在时刻 $t$，有两种选择：

1. 以概率 $(1-\lambda)$ 停下，使用 1 步回报 $G_t^{(1)}$
2. 以概率 $\lambda$ 继续走，在时刻 $t+1$，面临相同的选择 这就产生了一个递归结构

$$G_t^{\lambda}=(1-\lambda)G_t^{(1)}+\lambda[(1-\lambda)G_t^{(2)}+\lambda[(1-\lambda)G_t^{(3)}+\cdots]].$$

最终展开后即得

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

• 从前向视角 $\lambda$-回报到后向视角资格迹

在终止型任务中

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

其中

$$G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + \dots + \gamma^{n-1} R_{t+n} + \gamma^n V(S_{t+n}).$$

TD误差

$$\delta_k=R_{k+1}+\gamma V(S_{k+1})-V(S_k).$$

考虑离线 $\text{TD}(\lambda)$，即整个 episode 期间不改变状态价值，只记录所有 TD 误差和资格迹，等 episode 结束后一次性完成更新，此时在整个 episode 中，有

$$V_0(s)=V_1(s)=\cdots=V_T(s).$$

最后统一更新

$$V(s)\leftarrow V(s)+\Delta(s),$$

则有式(1)

$$\begin{aligned}\sum_{k=t}^{T-1}(\lambda\gamma)^{k-t}\delta_k = & \delta_t+\lambda\gamma\delta_{t+1}+(\lambda\gamma)^2\delta_{t+2}+\cdots+(\lambda\gamma)^{T-t-1}\delta_{T-1} \\ = & R_{t+1} +\gamma V(S_{t+1})-V(S_t) + \\ & \lambda\gamma( R_{t+2} + \gamma V(S_{t+2})- V(S_{t+1})) + \\ & (\lambda\gamma)^2 (R_{t+3}+\gamma V(S_{t+3})-V(S_{t+2})) + \\ & \cdots + \\ & (\lambda\gamma)^{T-t-1}(R_T+\gamma V(S_T)-V(S_{T-1})) \\ = & R_{t+1}+\lambda\gamma R_{t+2}+(\lambda\gamma)^2 R_{t+3}+\cdots \\ & -V(S_t) + \\ & (1-\lambda)\gamma V(S_{t+1}) + \\ & (1-\lambda)\lambda\gamma^2 V(S_{t+2}) + \\ & (1-\lambda)\lambda^2\gamma^3 V(S_{t+3}) + \\ & \cdots + \\ & (1-\lambda)\lambda^{T-t-2}\gamma^{T-t-1}V(S_{T-1}) + \\ & \lambda^{T-t-1}\gamma^{T-t}V(S_T). \end{aligned}$$

终止状态 $V(S_T)=0$.

另一方面，

$$\begin{aligned} G_t^{(1)} & =R_{t+1}+\gamma V(S_{t+1}) \\G_t^{(2)} & =R_{t+1}+\gamma R_{t+2}+\gamma^2 V(S_{t+2}) \\G_t^{(3)} & =R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+\gamma^3 V(S_{t+3}) \\& \cdots \\G_t^{(T-t-1)} & =R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-t-2}R_{T-1}+\gamma^{T-t-1}V(S_{T-1})\\G_t & =R_{t+1}+\gamma R_{t+2}+\cdots+ \gamma^{T-t-2}R_{T-1}+\gamma^{T-t-1}R_{T}.\end{aligned}$$

有式(2)

$$\begin{aligned} G_t^{\lambda}= & (1-\lambda)\sum_{n=1}^{T-t-1} \lambda^{n-1}G_t^{(n)}+\lambda^{T-t-1}G_t \\ = & (1-\lambda)(1+\lambda+\cdots+\lambda^{T-t-2})R_{t+1}+\lambda^{T-t-1}R_{t+1} + \\ & (1-\lambda)(\lambda+\lambda^2+\cdots+ \lambda^{T-t-2})\gamma R_{t+2} +\lambda^{T-t-1}R_{t+2} + \\ & \cdots + \\ & (1-\lambda)\gamma V(S_{t+1})+ \\ & (1-\lambda)\lambda\gamma^2 V(S_{t+2}) + \\ & \cdots + \\ & (1-\lambda)\lambda^{T-t-2}\gamma^{T-t-1} V(S_{T-1}) \\ = & R_{t+1}+\lambda\gamma R_{t+2}+(\lambda\gamma)^2 R_{t+3}+\cdots \\ & (1-\lambda)\gamma V(S_{t+1})+ \\ & (1-\lambda)\lambda\gamma^2 V(S_{t+2}) + \\ & \cdots + \\ & (1-\lambda)\lambda^{T-t-2}\gamma^{T-t-1} V(S_{T-1}). \end{aligned}$$

比较 $(1)$ 和 $(2)$ 得到

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

这意味着对 $V(S_t)$ 的更新可以表示为所有TD误差的加权和：

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

在后向视角中，每产生一个 $\delta_k$，立即乘系数 $(\lambda\gamma)^{k-t}$ 传播给以前访问的状态，所有 TD 误差传播完成后，状态 $S_t$ 得到的累计更新就是$\alpha(G_t^{\lambda}-V(S_t))$.因此前向视角与后向视角两者在本质是统一的.

考虑轨迹

$$s_0 \xrightarrow{a_0} R_1,s_1 \xrightarrow{a_1}R_2, s_2 \xrightarrow{a_2}R_3, s_3.$$

在常规 Q-Learning 的 1 步回报中，更新状态行为对 $(s_0,a_0)$ 的 $Q$ 值，所使用的是 $\max_{a'}Q(s_1,a')$，而不是实际执行的 $a_1$.并且由于只看到下一步，即使真实轨迹没有采取 greedy，我们仍然会认为从 $s_1$ 开始以后是 greedy 策略生成的轨迹，即无论 $a_1$ 是贪婪行为还是探索行为，不影响 $Q(s_0,a_0)$ 的更新；

若考虑多步回报，如 3 步回报，且 $a_1$ 为贪婪行为，$a_2$ 为探索行为，则 TD 目标 $Q^{(3)}$为

$$Q^{(3)}=R_{1}+\gamma R_{2}+\gamma^2 R_{3}+\gamma^3 \max_a Q(s_{3},a).$$

从 $a_2$ 开始，后面的轨迹不是 greedy 策略产生的，对应经验奖励 $R_3\ldots$ 不能再代表 $Q^*$，因此不能使用 3 步回报作为 TD 目标，进而更新 $Q(s_0,a_0)$ ^eg3

状态序列

$$s_t \xrightarrow[\text{greedy}]{a_t} s_{t+1} \xrightarrow[\text{greedy}]{a_{t+1}} s_{t+2} \xrightarrow[\text{explore}]{a_{t+2}} s_{t+3}.$$

在 $(s_t,a_t)$ 处，$E(s_t,a_t)=1$，$a_t$ 是贪婪行为，则资格迹继续衰减并累计

$$\begin{aligned} & E(s_t,a_t)=\gamma\lambda, \\ &E(s_{t+1},a_{t+1})=1. \end{aligned}$$

再执行下一步 $(s_{t+2},a_{t+2})$ ，此时得到

$$\begin{aligned} & E(s_t,a_t)=(\gamma\lambda)^2, \\ & E(s_{t+1},a_{t+1})=\gamma\lambda, \\ & E(s_{t+2},a_{t+2})=1. \end{aligned}$$

在探索动作发生之前，各状态行为对的资格迹均保留，且当前 TD 误差能够传播给之前访问过的状态动作对.

而在 $a_{t+2}$ 不是贪婪动作，表明此后轨迹偏离目标策略，后续经验不能用于估计greedy策略的价值，因此，在计算完当前一步更新后，资格迹立即清理：

$$E(s,a)=0,\ \forall s,a$$

原来的资格迹 $E(s_t,a_t),E(s_{t+1},a_{t+1}),E(s_{t+2},a_{t+2})$ 均变为 $0$.

若不清零，则随后计算得到的 TD 误差 $\delta_{t+3}$ 仍会更新 $(s_t,a_t)$, $(s_{t+1},a_{t+1})$ 和 $(s_{t+2},a_{t+2})$ 对应值，即探索行为后的经验影响了原本目标贪婪策略，因此此时需将资格迹截断清零.

经典的悬崖行走网格中，智能体从起点到终点，途中某些格是悬崖，掉下去会获得 -100 奖励并回到起点.用 Sarsa(0) 学习，智能体学到的安全路径会远离悬崖（因为探索时有概率掉下悬崖，一步更新过于谨慎）.若使用 $\text{Sarsa}(\lambda)$ 并取较大的 λ，掉下悬崖的大负奖励会被迹传播到更早的状态-动作对，那些导致接近悬崖路径的动作会受到更强的惩罚，智能体可能更快地学会避开危险区域.同时，正奖励的传播也更快，使得成功路径的 Q 值提升更迅速.实验通常显示，在 λ≈0.7～0.9 时学习速度明显快于 λ=0.