Chap 12 - 资格迹

Eligibility Traces 是强化学习的基本原理之一。几乎所有 TD 方法都可以和 eligibility traces 结合起来生成更高效通用的方法。

在 TD($\lambda$) 方法中，$\lambda \in [0,1]$，两个极端的例子是 MC ($\lambda =1$) 和 1-step TD ($\lambda =0$)。

与n-step方法相比：

• Eligibility Traces 方法只需存储一个trace vector，而不是 n 个最新的 feature vectors
• 学习过程是连续且均匀的，不会有延迟
• 不需要在 episode 结束时才进行所有运算
• 学习可以立刻影响行为，不需要 n step 后才延迟生效

前面讲过的很多方法根据后面的一些 rewards 来更新，这种形式称为 forward views ，通常 forward views 并不实用，因为 update 依赖于当前未知的量，这一章会介绍一种新方法，采用 eligibility trace 往前看最近经过的 states ，从而得到当前 TD error ，称之为 backward views 。

12.1 The $\lambda$-return

n-step return 的定义如下：

$$G_{t:t+n}\doteq R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^n\hat{v}\left(S_{t+n},{\mathbf{w}}_{t+n-1}\right)$$

现在考虑多个 n-step return 的加权平均，只需权重和为 1，仍能用作 update target，如 $\frac{1}{2}{G}_{t:t+2}+\frac{1}{2}{G}_{t:t+4}$ ，这种更新方式称为 compound update，其 backup 图如下

TD($\lambda$) 也属于这种 averaging n-step update ，他包括了所有的 n-step updates，权重系数分别为 ${\lambda }^{n-1},\lambda \in [0,1]$，$\lambda$-return 定义如下（其中 $1-\lambda$ 确保能归一化）：

$$G_t^{\lambda }\doteq (1-\lambda )\sum _{n=1}^{\infty }{\lambda }^{n-1}{G}_{t:t+n}$$

其 backup 图如下：

将上式提取一部分出来，可写为

$$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 =1$ ，此方法为 MC；当 $\lambda =0$ ，此方法为 1-step TD。

更一般地，将这个 $G_t^{\lambda }$ 作为 update target ，此算法称为『offline $\lambda$-return algorithm』，采用半梯度法更新：

$${\mathbf{w}}_{t+1}\doteq {\mathbf{w}}_t+\alpha \left[G_t^{\lambda }-\hat{v}\left(S_t,{\mathbf{w}}_t\right)\right]\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right)$$

下图通过一个实例比较了算法效果：

目前我们讨论的方法都是『forward views』算法，在每个 state 处都能得到一些未来的信息，如下面示意图所示。

12.2 TD($\lambda$)

本节介绍的 TD($\lambda$) 对上一节的 offline $\lambda$-return 有三点提升：

• 单步更新权重向量，无需等待 episode 结束
• 计算在时间上均匀分布
• 不仅可用于 episode 问题，还适用于连续问题

本节引入 eligibility trace ${\mathbf{z}}_t\in {\mathbb{R}}^d$ ，他与权向量 ${\mathbf{w}}_t$ 维度相同，权向量有长期的记忆性，其存在时间与系统等长，而 eligibility trace 则体现短期记忆，存在于 episode 内的一个子片段中。

eligibility trace 定义如下：

$$\begin{array}{l}{\mathbf{z}}_{-1}\doteq 0\\ {\mathbf{z}}_t\doteq \gamma \lambda {\mathbf{z}}_{t-1}+\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right),0\le t\le T\end{array}$$

eligibility trace 一直在追踪那些对『recent state valuation』有贡献的权重分量，这个 recent 体现在系数 $\gamma \lambda$ 上。

在 1-step TD 中，TD error 为

$${\delta }_t\doteq R_{t+1}+\gamma \hat{v}\left(S_{t+1},{\mathbf{w}}_t\right)-\hat{v}\left(S_t,{\mathbf{w}}_t\right)$$

更新式为

$${\mathbf{w}}_{t+1}\doteq {\mathbf{w}}_t+\alpha {\delta }_t\nabla \hat{v}(S_t,{\mathbf{w}}_t)$$

将梯度增加一些信息

$${\mathbf{w}}_{t+1}\doteq {\mathbf{w}}_t+\alpha {\delta }_t[\nabla \hat{v}(S_t,{\mathbf{w}}_t)+\gamma \lambda {\mathbf{z}}_{t-1}]$$

即可得到 TD($\lambda$) 的更新式

$${\mathbf{w}}_{t+1}\stackrel{\cdot }{=}{\mathbf{w}}_t+\alpha {\delta }_t{\mathbf{z}}_t$$

算法伪代码如下

TD($\lambda$) 是 backward 的，即，每个时刻得到新的 TD error 后，又依据它对之前 states 的 eligibility trace 作一些调整，如下面示意图所示。

算法的实际测试效果如下图所示

当 $\lambda =0$ 时，trace 恰好就是 value function 的梯度，此时正好对应 1-step TD ；当 $\lambda =1$ 时，可以看出每一个 state 都刚好衰减 $\gamma$ 倍，跑完这个 episode ，恰好就是 MC 。可以看出，使用了 eligibility trace 后仍能统一地表示各种算法。

若满足条件

$$\sum _{n=1}^{\infty }{\alpha }_n=\infty \text{ and }\sum _{n=1}^{\infty }{\alpha }_n^2<\infty$$

线性 TD($\lambda$) 可以在 on-policy 下确保收敛，此时有上界

$$\overline{\mathrm{VE}}\left({\mathbf{w}}_{\infty }\right)\le \frac{1-\gamma \lambda }{1-\gamma }\underset{\mathbf{w}}{\min }\overline{\mathrm{VE}}(\mathbf{w})$$

12.3 n-step Truncated $\lambda$-return Methods

前面讲过的 offline $\lambda$-return 是一个重要的概念，但并不实用，因为他需要跑完一整个 episode 才能结束，而在连续型任务中，n 可以无限大，$\lambda$-return 无法计算，因此需要考虑将序列截断，用估计值来替代抛弃掉的较远的 rewards 。

定义 truncated $\lambda$-return 如下：

$$G_{t:h}^{\lambda }\doteq (1-\lambda )\sum _{n=1}^{h-t-1}{\lambda }^{n-1}{G}_{t:t+n}+{\lambda }^{h-t-1}{G}_{t:h}$$

而之前定义的完整的 $\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$$

对比可知，truncated $\lambda$-return 提前结束了模拟（后面未模拟部分用估计值代替），在此算法中，update 只被延迟了 n 步。称该算法为 truncated TD($\lambda$) ，或 TTD($\lambda$) 。

下面是算法的 backup 示意图：

算法的更新式为

$${\mathbf{w}}_{t+n}\doteq {\mathbf{w}}_{t+n-1}+\alpha \left[G_{t:t+n}^{\lambda }-\hat{v}\left(S_t,{\mathbf{w}}_{t+n-1}\right)\right]\nabla \hat{v}\left(S_t,{\mathbf{w}}_{t+n-1}\right)$$

其中

$$\begin{array}{rl}& G_{t:t+k}^{\lambda }=\hat{v}\left(S_t,{\mathbf{w}}_{t-1}\right)+\sum _{i=t}^{t+k-1}(\gamma \lambda {)}^{i-t}{\delta }_i^{\prime }\\ & {\delta }_t^{\prime }\doteq R_{t+1}+\gamma \hat{v}\left(S_{t+1},{\mathbf{w}}_t\right)-\hat{v}\left(S_t,{\mathbf{w}}_{t-1}\right)\end{array}$$

12.4 Redoing Updates: The Online $\lambda$-return Algorithm

实用 truncated TD 涉及到对 n 的平衡，n 越大越接近 offline $\lambda$-return ，越小则更新速度越快。此平衡是可以达到的，方法是每次获得新数据后，重新从头开始执行所有更新：

$$\begin{array}{cl}h=1:& {\mathbf{w}}_1^1\doteq {\mathbf{w}}_0^1+\alpha \left[G_{0:1}^{\lambda }-\hat{v}\left(S_0,{\mathbf{w}}_0^1\right)\right]\nabla \hat{v}\left(S_0,{\mathbf{w}}_0^1\right)\\ & \\ h=2:& {\mathbf{w}}_1^2\doteq {\mathbf{w}}_0^2+\alpha \left[G_{0:2}^{\lambda }-\hat{v}\left(S_0,{\mathbf{w}}_0^2\right)\right]\nabla \hat{v}\left(S_0,{\mathbf{w}}_0^2\right)\\ & {\mathbf{w}}_2^2\doteq {\mathbf{w}}_1^2+\alpha \left[G_{1:2}^{\lambda }-\hat{v}\left(S_1,{\mathbf{w}}_1^2\right)\right]\nabla \hat{v}\left(S_1,{\mathbf{w}}_1^2\right)\\ & \\ h=3:& {\mathbf{w}}_1^3\doteq {\mathbf{w}}_0^3+\alpha \left[G_{0:3}^{\lambda }-\hat{v}\left(S_0,{\mathbf{w}}_0^3\right)\right]\nabla \hat{v}\left(S_0,{\mathbf{w}}_0^3\right)\\ & {\mathbf{w}}_2^3\doteq {\mathbf{w}}_1^3+\alpha \left[G_{1:3}^{\lambda }-\hat{v}\left(S_1,{\mathbf{w}}_1^3\right)\right]\nabla \hat{v}\left(S_1,{\mathbf{w}}_1^3\right)\\ & {\mathbf{w}}_3^3\doteq {\mathbf{w}}_2^3+\alpha \left[G_{2:3}^{\lambda }-\hat{v}\left(S_2,{\mathbf{w}}_2^3\right)\right]\nabla \hat{v}\left(S_2,{\mathbf{w}}_2^3\right)\end{array}$$

其中 ${\mathbf{w}}_0^h$ 都继承自上一个 episode（因此所有的 ${\mathbf{w}}_0^h$ 也都为同一值），${\mathbf{w}}_h^h$ 则为每一步的更新结果。

更一般的表示为：

$${\mathbf{w}}_{t+1}^h\doteq {\mathbf{w}}_t^h+\alpha \left[G_{t:h}^{\lambda }-\hat{v}\left(S_t,{\mathbf{w}}_t^h\right)\right]\nabla \hat{v}\left(S_t,{\mathbf{w}}_t^h\right)$$

此算法称为『online $\lambda$-return algorithm』，是完全在线算法，每个时间点 t 均使用已有数据产生一个新权重向量 ${\mathbf{w}}_t$ 。

他在每个时间点 h 都能充分利用上 h 时间之前的所有信息，可以看出现在这种算法对数据的利用率更高，更新效果更好，缺点则为每次均需从头计算，复杂度高。

下面是实际的性能比较：

12.5 True Online TD($\lambda$)

online $\lambda$-return 效果很好，但计算复杂度太高，需要考虑利用 eligibility trace 将算法变换为 backward view 算法，这便是本节要讲的『true online TD($\lambda$)』。

之前的 online $\lambda$-return 方法产生的权重序列如下：

$$\begin{array}{cccccc}{\mathbf{w}}_0^0& & & & & \\ {\mathbf{w}}_0^1& {\mathbf{w}}_1^1& & & & \\ {\mathbf{w}}_0^2& {\mathbf{w}}_1^2& {\mathbf{w}}_2^2& & & \\ {\mathbf{w}}_0^3& {\mathbf{w}}_1^3& {\mathbf{w}}_2^3& {\mathbf{w}}_3^3& & \\ ⋮& ⋮& ⋮& ⋮& \ddots & \\ {\mathbf{w}}_0^T& {\mathbf{w}}_1^T& {\mathbf{w}}_2^T& {\mathbf{w}}_3^T& \cdots & {\mathbf{w}}_T^T\end{array}$$

事实上，我们需要的只是每行最后一个权重 ${\mathbf{w}}_t^t$ ，得到 ${\mathbf{w}}_t={\mathbf{w}}_t^t$ 。

对于 linear case，true online TD($\lambda$) 定义如下：

$$\begin{array}{l}{\mathbf{w}}_{t+1}\doteq {\mathbf{w}}_t+\alpha {\delta }_t{\mathbf{z}}_t+\alpha \left({\mathbf{w}}_t^{\top }{\mathbf{x}}_t-{\mathbf{w}}_{t-1}^{\top }{\mathbf{x}}_t\right)\left({\mathbf{z}}_t-{\mathbf{x}}_t\right)\\ {\mathbf{z}}_t\doteq \gamma \lambda {\mathbf{z}}_{t-1}+\left(1-\alpha \gamma \lambda {\mathbf{z}}_{t-1}^{\top }{\mathbf{x}}_t\right){\mathbf{x}}_t\end{array}$$

此算法可以产生和 online $\lambda$-return 算法一样的结果，空间要求和 TD($\lambda$) 相同，计算量稍微增加了 50%，但仍为 $O(d)$ 复杂度。

这一节 true online TD($\lambda$) 使用的 eligibility trace 称为『dutch trace』，之前的 TD($\lambda$) 中则称为『accumulating trace』。

12.6 Dutch Traces in Monte Carlo Learning

尽管 eligibility trace 于 TD 方法结合紧密，但他们本质上并无联系，事实上，eligibility trace 起源于 MC learning ，下面用一个例子简单介绍一下。

线性情况下，梯度 MC 法的更新式如下：

$${\mathbf{w}}_{t+1}\doteq {\mathbf{w}}_t+\alpha \left[G-{\mathbf{w}}_t^{\top }{\mathbf{x}}_t\right]{\mathbf{x}}_t$$

为了简化问题，这里的 return $G$ 只是 episode 结束后得到的单个 reward（因此没有下标），并且没有做 discounting 。想要做的优化就是，在 episode 每一步都进行一些计算，但仍只在 episode 结束后才进行更新，所以复杂度仍为 $O(d)$。算法如下：

$$\begin{array}{rl}{\mathbf{w}}_T& ={\mathbf{w}}_{T-1}+\alpha \left(G-{\mathbf{w}}_{T-1}^{\top }{\mathbf{x}}_{T-1}\right){\mathbf{x}}_{T-1}\\ & ={\mathbf{w}}_{T-1}+\alpha {\mathbf{x}}_{T-1}\left(-{\mathbf{x}}_{T-1}^{\top }{\mathbf{w}}_{T-1}\right)+\alpha G{\mathbf{x}}_{T-1}\\ & =\left(\mathbf{I}-\alpha {\mathbf{x}}_{T-1}{\mathbf{x}}_{T-1}^{\top }\right){\mathbf{w}}_{T-1}+\alpha G{\mathbf{x}}_{T-1}\\ & ={\mathbf{F}}_{T-1}{\mathbf{w}}_{T-1}+\alpha G{\mathbf{x}}_{T-1}\end{array}$$

这里引入 ${\mathbf{F}}_t\doteq \mathbf{I}-\alpha {\mathbf{x}}_t{\mathbf{x}}_t^{\top }$ 称为 遗忘矩阵（or 衰退矩阵），接上式，下面进行递归

$$\begin{array}{l}={\mathbf{F}}_{T-1}\left({\mathbf{F}}_{T-2}{\mathbf{w}}_{T-2}+\alpha G{\mathbf{x}}_{T-2}\right)+\alpha G{\mathbf{x}}_{T-1}\\ ={\mathbf{F}}_{T-1}{\mathbf{F}}_{T-2}{\mathbf{w}}_{T-2}+\alpha G\left({\mathbf{F}}_{T-1}{\mathbf{x}}_{T-2}+{\mathbf{x}}_{T-1}\right)\\ ={\mathbf{F}}_{T-1}{\mathbf{F}}_{T-2}\left({\mathbf{F}}_{T-3}{\mathbf{w}}_{T-3}+\alpha G{\mathbf{x}}_{T-3}\right)+\alpha G\left({\mathbf{F}}_{T-1}{\mathbf{x}}_{T-2}+{\mathbf{x}}_{T-1}\right)\\ ={\mathbf{F}}_{T-1}{\mathbf{F}}_{T-2}{\mathbf{F}}_{T-3}{\mathbf{W}}_{T-3}+\alpha G\left({\mathbf{F}}_{T-1}{\mathbf{F}}_{T-2}{\mathbf{x}}_{T-3}+{\mathbf{F}}_{T-1}{\mathbf{x}}_{T-2}+{\mathbf{x}}_{T-1}\right)\\ ⋮\\ =\underset{{\mathbf{a}}_{T-1}}{\underbrace{{\mathbf{F}}_{T-1}{\mathbf{F}}_{T-2}\cdots {\mathbf{F}}_0{\mathbf{w}}_0}}+\alpha G\underset{{\mathbf{z}}_{T-1}}{\underbrace{\sum _{k=0}^{T-1}{\mathbf{F}}_{T-1}{\mathbf{F}}_{T-2}\cdots {\mathbf{F}}_{k+1}{\mathbf{x}}_k}}\\ ={\mathbf{a}}_{T-1}+\alpha G{\mathbf{z}}_{T-1}\end{array}$$

其中 ${\mathbf{a}}_{T-1},{\mathbf{z}}_{T-1}$ 是 T-1 时刻的两个辅助记忆向量，即使不知道 G ，也能在每步先做一些这样的计算，用以存储一些信息。

事实上，${\mathbf{z}}_t$ 是一个 dutch-style eligibility trace，初始值为 ${\mathbf{z}}_0={\mathbf{x}}_0$ ，他的更新式为：

$$\begin{array}{rl}{\mathbf{z}}_t& \doteq \sum _{k=0}^t{\mathbf{F}}_t{\mathbf{F}}_{t-1}\cdots {\mathbf{F}}_{k+1}{\mathbf{x}}_k,1\le t<T\\ & =\sum _{k=0}^{t-1}{\mathbf{F}}_t{\mathbf{F}}_{t-1}\cdots {\mathbf{F}}_{k+1}{\mathbf{x}}_k+{\mathbf{x}}_t\\ & ={\mathbf{F}}_t\sum _{k=0}^{t-1}{\mathbf{F}}_{t-1}{\mathbf{F}}_{t-2}\cdots {\mathbf{F}}_{k+1}{\mathbf{x}}_k+{\mathbf{x}}_t\\ & ={\mathbf{F}}_t{\mathbf{z}}_{t-1}+{\mathbf{x}}_t\\ & =\left(\mathbf{I}-\alpha {\mathbf{x}}_t{\mathbf{x}}_t^{\top }\right){\mathbf{z}}_{t-1}+{\mathbf{x}}_t\\ & ={\mathbf{z}}_{t-1}-\alpha {\mathbf{x}}_t{\mathbf{x}}_t^{\top }{\mathbf{z}}_{t-1}+{\mathbf{x}}_t\\ & ={\mathbf{z}}_{t-1}-\alpha \left({\mathbf{z}}_{t-1}^{\top }{\mathbf{x}}_t\right){\mathbf{x}}_t+{\mathbf{x}}_t\\ & ={\mathbf{z}}_{t-1}+\left(1-\alpha {\mathbf{z}}_{t-1}^{\top }{\mathbf{x}}_t\right){\mathbf{x}}_t\end{array}$$

辅助向量 ${\mathbf{a}}_t$ 初始值为 ${\mathbf{a}}_0={\mathbf{w}}_0$ ，更新式为

$${\mathbf{a}}_t\doteq {\mathbf{F}}_t{\mathbf{F}}_{t-1}\cdots {\mathbf{F}}_0{\mathbf{w}}_0={\mathbf{F}}_t{\mathbf{a}}_{t-1}={\mathbf{a}}_{t-1}-\alpha {\mathbf{x}}_t{\mathbf{x}}_t^{\top }{\mathbf{a}}_{t-1}$$

在 t < T 时，每步更新辅助向量 ${\mathbf{a}}_t,{\mathbf{z}}_t$ ，当 T 时刻获得 G 后再最终计算出 ${\mathbf{w}}_T$。得到的结果和 MC 相同，但计算更简单。

本例说明了 eligibility trace 并不局限于 TD 方法，只要想做长期预测，都可以采用 eligibility trace 。

12.7 Sarsa($\lambda$)

这一节把 eligibility trace 从 state-value 扩展到 action-value，只需简单地将 $\hat{v}(s,\mathbf{w})$ 变为 $\hat{q}(s,a,\mathbf{w})$ 。

action-value 形式的 n-step return 为：

$$G_{t:t+n}\doteq R_{t+1}+\cdots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^n\hat{q}\left(S_{t+n},A_{t+n},{\mathbf{w}}_{t+n-1}\right)$$

利用这个 return ，可以根据前面公式构造 action-value 形式的 truncated $\lambda$-return $G_t^{\lambda }$ ，进而得到 action-value 形式的 offline $\lambda$-return 算法：

$${\mathbf{w}}_{t+1}\doteq {\mathbf{w}}_t+\alpha \left[G_t^{\lambda }-\hat{q}\left(S_t,A_t,{\mathbf{w}}_t\right)\right]\nabla \hat{q}\left(S_t,A_t,{\mathbf{w}}_t\right)$$

算法示意图如下：

Sarsa($\lambda$) 和 TD($\lambda$) 相似，更新式为

$$\begin{array}{l}{\mathbf{w}}_{t+1}\stackrel{\cdot }{=}{\mathbf{w}}_t+\alpha {\delta }_t{\mathbf{z}}_t\\ {\delta }_t\doteq R_{t+1}+\gamma \hat{q}\left(S_{t+1},A_{t+1},{\mathbf{w}}_t\right)-\hat{q}\left(S_t,A_t,{\mathbf{w}}_t\right)\\ {\mathbf{z}}_{-1}\doteq 0\\ {\mathbf{z}}_t\doteq \gamma \lambda {\mathbf{z}}_{t-1}+\nabla \hat{q}\left(S_t,A_t,{\mathbf{w}}_t\right)\end{array}$$

算法伪码如下：

该算法与传统的 n-step sarsa 效果对比如下：

上面是 offline $\lambda$-return 算法，下面介绍 action-value 的 online $\lambda$-return 算法。

本节算法之间的比较：

12.8 Variable $\lambda$ and $\gamma$

为了更泛化地表示每一步中 bootstrapping 和 discounting 的程度，需要更通用的 $\lambda ,\gamma$ ，现定义函数 $\lambda :\mathcal{S}\times \mathcal{A}\to [0,1]$ 和 $\gamma :\mathcal{S}\to [0,1]$ ，从而得到 ${\lambda }_t\doteq \lambda \left(S_t,A_t\right),{\gamma }_t\doteq \gamma \left(S_t\right)$ 。

函数 $\gamma$ 称为『termination function』，现在重新定义 return ：

$$\begin{array}{rl}{G}_t& \doteq R_{t+1}+{\gamma }_{t+1}{G}_{t+1}\\ & =R_{t+1}+{\gamma }_{t+1}{R}_{t+2}+{\gamma }_{t+1}{\gamma }_{t+2}{R}_{t+3}+{\gamma }_{t+1}{\gamma }_{t+2}{\gamma }_{t+3}{R}_{t+4}+\cdots \\ & =\sum _{k=t}^{\infty }\left(\prod _{i=t+1}^k{\gamma }_i\right)R_{k+1}\end{array}$$

为保证结果有限，需要 ${\prod }_{k=t}^{\infty }{\gamma }_k=0$ 。

这种形式的好处是，episodic 任务无需再指定开始状态和结束状态，只需使 $\gamma (s)=0$ 即可，因此便能统一 episodic 和 discounted-continuing 。

上面说了对 discounting 的泛化，下面再介绍对 bootstrapping 的泛化。

若考虑对 state-value 做 bootstrap ，则泛化参数记为 ${\lambda }_s$ ，同理若对 action-value 做 bootstrap ，则泛化参数记为 ${\lambda }_a$（$\lambda$ 控制了 bootstrap 的程度，当为 1 时完全不做 bootstrap ，当为 0 时则完全是在 bootstrap ）。于是可以得到新的递归形式的 state-based $\lambda$-return ：

$$G_t^{\lambda s}\doteq R_{t+1}+{\gamma }_{t+1}\left(\left(1-{\lambda }_{t+1}\right)\hat{v}\left(S_{t+1},{\mathbf{w}}_t\right)+{\lambda }_{t+1}{G}_{t+1}^{\lambda s}\right)$$

或是 action-based $\lambda$-return ：

$$G_t^{\lambda a}\doteq R_{t+1}+{\gamma }_{t+1}\left(\left(1-{\lambda }_{t+1}\right)\hat{q}\left(S_{t+1},A_{t+1},{\mathbf{w}}_t\right)+{\lambda }_{t+1}{G}_{t+1}^{\lambda a}\right)$$

或者 Expected Sarsa 形式：

$$\begin{array}{rl}& G_t^{\lambda a}\doteq R_{t+1}+{\gamma }_{t+1}\left(\left(1-{\lambda }_{t+1}\right){\overline{V}}_t\left(S_{t+1}\right)+{\lambda }_{t+1}{G}_{t+1}^{\lambda a}\right)\\ & {\overline{V}}_t(s)\doteq \sum _a\pi (a|s)\hat{q}\left(s,a,{\mathbf{w}}_t\right)\end{array}$$

12.9 Off-policy Traces with Control Variates

本节主要将 importance sampling 整合进算法。这里采用第 7 章的 per-decision 方法，定义如下的 $\lambda$-return ：

$$G_t^{\lambda s}\doteq {\rho }_t\left(R_{t+1}+{\gamma }_{t+1}\left(\left(1-{\lambda }_{t+1}\right)\hat{v}\left(S_{t+1},{\mathbf{w}}_t\right)+{\lambda }_{t+1}{G}_{t+1}^{\lambda s}\right)\right)+\left(1-{\rho }_t\right)\hat{v}\left(S_t,{\mathbf{w}}_t\right)$$

他的 truncated 形式可由 state-based TD error 逼近得到：

$$\begin{array}{rl}& {\delta }_t^s\doteq R_{t+1}+{\gamma }_{t+1}\hat{v}\left(S_{t+1},{\mathbf{w}}_t\right)-\hat{v}\left(S_t,{\mathbf{w}}_t\right)\\ & G_t^{\lambda s}\approx \hat{v}\left(S_t,{\mathbf{w}}_t\right)+{\rho }_t\sum _{k=t}^{\infty }{\delta }_k^s\prod _{i=t+1}^k{\gamma }_i{\lambda }_i{\rho }_i\end{array}$$

通过上面形式的 $\lambda$-return ，可以方便地进行 forward-view 更新

$$\begin{array}{rl}{\mathbf{w}}_{t+1}& ={\mathbf{w}}_t+\alpha \left(G_t^{\lambda s}-\hat{v}\left(S_t,{\mathbf{w}}_t\right)\right)\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right)\\ & \approx {\mathbf{w}}_t+\alpha {\rho }_t\left(\sum _{k=t}^{\infty }{\delta }_k^s\prod _{i=t+1}^k{\gamma }_i{\lambda }_i{\rho }_i\right)\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right)\end{array}$$

下面探究 forward view 和 backward view 的近似关系。对整个 forward view 过程进行求和，得到：

$$\begin{array}{rl}\sum _{t=1}^{\infty }\left({\mathbf{w}}_{t+1}-{\mathbf{w}}_t\right)& \approx \sum _{t=1}^{\infty }\sum _{k=t}^{\infty }\alpha {\rho }_t{\delta }_k^s\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right)\prod _{i=t+1}^k{\gamma }_i{\lambda }_i{\rho }_i\\ & =\sum _{k=1}^{\infty }\sum _{t=1}^k\alpha {\rho }_t\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right){\delta }_k^s\prod _{i=t+1}^k{\gamma }_i{\lambda }_i{\rho }_i\\ & =\sum _{k=1}^{\infty }\alpha {\delta }_k^s\sum _{t=1}^k{\rho }_t\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right)\prod _{i=t+1}^k{\gamma }_i{\lambda }_i{\rho }_i\end{array}$$

其中第二个等号用到了一个求和规则：

$$\sum _{t=x}^y\sum _{k=t}^y=\sum _{k=x}^y\sum _{t=x}^k$$

若上式的第二个求和项可写作 eligibility trace 并用于更新，则更新式变为 backward view TD update 。即，若表达式为 k 时刻的 trace，那他可由 k-1 时刻的值更新而得：

$$\begin{array}{rl}{\mathbf{z}}_k& =\sum _{t=1}^k{\rho }_t\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right)\prod _{i=t+1}^k{\gamma }_i{\lambda }_i{\rho }_i\\ & =\sum _{t=1}^{k-1}{\rho }_t\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right)\prod _{i=t+1}^k{\gamma }_i{\lambda }_i{\rho }_i+{\rho }_k\nabla \hat{v}\left(S_k,{\mathbf{w}}_k\right)\\ & ={\gamma }_k{\lambda }_k{\rho }_k\underset{{\mathbf{z}}_{k-1}}{\underbrace{\sum _{t=1}^{k-1}{\rho }_t\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right)\prod _{i=t+1}^{k-1}{\gamma }_i{\lambda }_i{\rho }_i}}+{\rho }_k\nabla \hat{v}(S_k,{\mathbf{w}}_k)\\ & ={\rho }_k\left({\gamma }_k{\lambda }_k{\mathbf{z}}_{k-1}+\nabla \hat{v}\left(S_k,{\mathbf{w}}_k\right)\right)\end{array}$$

整理即得

$${\mathbf{z}}_t\doteq {\rho }_t\left({\gamma }_t{\lambda }_t{\mathbf{z}}_{t-1}+\nabla \hat{v}\left(S_t,{\mathbf{w}}_t\right)\right)$$

这个 eligibility trace 结合 半梯度 TD($\lambda$) 更新即为一般的 TD($\lambda$) 算法（${\rho }_t=1$ 时对应 on-policy）。在 off-policy 情况下，算法性能还不错，但是作为一个半梯度算法，稳定性欠佳（后面几节会考虑扩展此算法来保证稳定性）。

对于 action-value 情况的算法，其实和 state-value 情况类似，现构造一个 action-based $\lambda$-return ：

$$\begin{array}{rl}{G}_t^{\lambda a}& \doteq R_{t+1}+{\gamma }_{t+1}(\left(1-{\lambda }_{t+1}\right){\overline{V}}_t\left(S_{t+1}\right)+\\ & {\lambda }_{t+1}\left[{\rho }_{t+1}{G}_{t+1}^{\lambda a}+{\overline{V}}_t\left(S_{t+1}\right)-{\rho }_{t+1}\hat{q}\left(S_{t+1},A_{t+1},{\mathbf{w}}_t\right)\right])\\ & =R_{t+1}+{\gamma }_{t+1}\left({\overline{V}}_t\left(S_{t+1}\right)+{\lambda }_{t+1}{\rho }_{t+1}\left[G_{t+1}^{\lambda a}-\hat{q}\left(S_{t+1},A_{t+1},{\mathbf{w}}_t\right)\right]\right)\end{array}$$

其中

$${\overline{V}}_t(s)\doteq \sum _a\pi (a|s)\hat{q}\left(s,a,{\mathbf{w}}_t\right)$$

同样又基于 action-based TD error 来逼近 $\lambda$-return ：

$$\begin{array}{rl}& G_t^{\lambda a}\approx \hat{q}\left(S_t,A_t,{\mathbf{w}}_t\right)+\sum _{k=t}^{\infty }{\delta }_k^a\prod _{i=t+1}^k{\gamma }_i{\lambda }_i{\rho }_i\\ & {\delta }_t^a=R_{t+1}+{\gamma }_{t+1}{\overline{V}}_t\left(S_{t+1}\right)-\hat{q}\left(S_t,A_t,{\mathbf{w}}_t\right)\end{array}$$

然后做类似变换，得到 eligibility trace for action values：

$${\mathbf{z}}_t\doteq {\gamma }_t{\lambda }_t{\rho }_t{\mathbf{z}}_{t-1}+\nabla \hat{q}\left(S_t,A_t,{\mathbf{w}}_t\right)$$

将其用于半梯度更新可得到更一般的 Sarsa($\lambda$) ，同样可通用于 on-policy 和 off-policy 。

$\lambda =1$ 时，目前这些算法和 MC 联系密切，而 $\lambda <1$ 时，上面所有的 off-policy 算法都将面临 11 章提到过的『致命三因素（the deadly triad）』—— approximation、bootstrapping、off-policy 。

12.10 Watkins’s Q($\lambda$) to Tree-Backup($\lambda$)

近些年提出了很多在 Q-learning 上使用 eligibility trace 的扩展算法，最早的便是 Watkins’s Q($\lambda$) ：若采取 greedy action，则照常对 eligibility trace 进行衰退，否则，就将首个 non-greedy action 之后的 traces 重置为 0 。算法的 backup 示意图如下：

第 7 章介绍过无需 importance sampling 的 n-step tree backup 算法，下面将 eligibility trace 结合于其中，称为 Tree-Backup($\lambda$) 或 TB($\lambda$) 算法，示意图如下：

该算法的 $\lambda$-return 为使用 action values 的递归式：

$$\begin{array}{rl}{G}_t^{\lambda a}& \doteq R_{t+1}+{\gamma }_{t+1}(\left(1-{\lambda }_{t+1}\right){\overline{V}}_t\left(S_{t+1}\right)+\\ & {\lambda }_{t+1}\left[\sum _{a\ne A_{t+1}}\pi (a|S_{t+1})\hat{q}\left(S_{t+1},a,{\mathbf{w}}_t\right)+\pi \left(A_{t+1}|S_{t+1}\right)G_{t+1}^{\lambda a}\right])\\ & =R_{t+1}+{\gamma }_{t+1}\left({\overline{V}}_t\left(S_{t+1}\right)+{\lambda }_{t+1}\pi \left(A_{t+1}|S_{t+1}\right)\left(G_{t+1}^{\lambda a}-\hat{q}\left(S_{t+1},A_{t+1},{\mathbf{w}}_t\right)\right)\right)\end{array}$$

再对 return 做逼近：

$$\begin{array}{rl}& {\delta }_t^a=R_{t+1}+{\gamma }_{t+1}{\overline{V}}_t\left(S_{t+1}\right)-\hat{q}\left(S_t,A_t,{\mathbf{w}}_t\right)\\ & G_t^{\lambda a}\approx \hat{q}\left(S_t,A_t,{\mathbf{w}}_t\right)+\sum _{k=t}^{\infty }{\delta }_k^a\prod _{i=t+1}^k{\gamma }_i{\lambda }_i\pi \left(A_i|S_i\right)\end{array}$$

最后得到 eligibility trace update：

$${\mathbf{z}}_t\doteq {\gamma }_t{\lambda }_t\pi \left(A_t|S_t\right){\mathbf{z}}_{t-1}+\nabla \hat{q}\left(S_t,A_t,{\mathbf{w}}_t\right)$$

再利用更新规则

$${\mathbf{w}}_{t+1}\doteq {\mathbf{w}}_t+\alpha {\delta }_t{\mathbf{z}}_t$$

组成了完整的 TB($\lambda$) 算法。该算法依然不稳定，同样需要结合后面的方法。

12.11 Stable Off-policy Methods with Traces

前面几节中的一些 eligibility trace 方法是可以在 off-policy 中取得稳定解的，这一节介绍四种最为重要的使用了 bootstrapping 和 discounting 的函数，他们的思想都基于 11 章中的 Gradient-TD、Emphatic-TD。下面的算法都假定了线性函数逼近这一前提（至于非线性，理论上也能做相似的处理），符号若无特殊说明，都和前面相同。

(1) GTD($\lambda$) ：TDC 算法的 eligibility trace 形式

目标：学习 $\hat{v}(s,\mathbf{w})\doteq {\mathbf{w}}_t^{\top }\mathbf{x}(s)\approx v_{\pi }(s)$ ，更新式如下：

$$\begin{array}{rl}& {\mathbf{w}}_{t+1}\doteq {\mathbf{w}}_t+\alpha {\delta }_t^s{\mathbf{z}}_t-\alpha {\gamma }_{t+1}\left(1-{\lambda }_{t+1}\right)\left({\mathbf{z}}_t^{\top }{\mathbf{v}}_t\right){\mathbf{x}}_{t+1}\\ & {\mathbf{v}}_{t+1}\doteq {\mathbf{v}}_t+\beta {\delta }_t^s{\mathbf{z}}_t-\beta \left({\mathbf{v}}_t^{\top }{\mathbf{x}}_t\right){\mathbf{x}}_t\end{array}$$

(2) GQ($\lambda$) ：Gradient-TD 算法（action-value）的 eligibility trace 形式

目标：学习 $\hat{q}\left(s,a,{\mathbf{w}}_t\right)\doteq {\mathbf{w}}_t^{\top }\mathbf{x}(s,a)\approx q_{\pi }(s,a)$ ，更新式如下：

$$\begin{array}{rl}& {\mathbf{w}}_{t+1}\doteq {\mathbf{w}}_t+\alpha {\delta }_t^a{\mathbf{z}}_t-\alpha {\gamma }_{t+1}\left(1-{\lambda }_{t+1}\right)\left({\mathbf{z}}_t^{\top }{\mathbf{v}}_t\right){\overline{\mathbf{x}}}_{t+1}\\ & {\overline{\mathbf{x}}}_t\doteq \sum _a\pi (a|S_t)\mathbf{x}\left(S_t,a\right)\\ & {\delta }_t^a\doteq R_{t+1}+{\gamma }_{t+1}{\mathbf{w}}_t^{\top }{\overline{\mathbf{x}}}_{t+1}-{\mathbf{w}}_t^{\top }{\mathbf{x}}_t\end{array}$$

(3) HTD($\lambda$) ：由 GTD($\lambda$) 和 TD($\lambda$) 的结合算法

目标：学习 $\hat{v}(s,\mathbf{w})\doteq {\mathbf{w}}_t^{\top }\mathbf{x}(s)\approx v_{\pi }(s)$ ，更新式如下：

$$\begin{array}{rl}{\mathbf{w}}_{t+1}& \doteq {\mathbf{w}}_t+\alpha {\delta }_t^s{\mathbf{z}}_t+\alpha \left({\left({\mathbf{z}}_t-{\mathbf{z}}_t^b\right)}^{\top }{\mathbf{v}}_t\right)\left({\mathbf{x}}_t-{\gamma }_{t+1}{\mathbf{x}}_{t+1}\right)\\ {\mathbf{v}}_{t+1}& \doteq {\mathbf{v}}_t+\beta {\delta }_t^s{\mathbf{z}}_t-\beta \left({\mathbf{z}}_t^{b^{\top }}{\mathbf{v}}_t\right)\left({\mathbf{x}}_t-{\gamma }_{t+1}{\mathbf{x}}_{t+1}\right),\text{ with }{\mathbf{v}}_0\doteq 0\\ {\mathbf{z}}_t& \doteq {\rho }_t\left({\gamma }_t{\lambda }_t{\mathbf{z}}_{t-1}+{\mathbf{x}}_t\right),\text{ with }{\mathbf{z}}_{-1}\doteq 0\\ {\mathbf{z}}_t^b& \doteq {\gamma }_t{\lambda }_t{\mathbf{z}}_{t-1}^b+{\mathbf{x}}_t,\text{ with }{\mathbf{z}}_{-1}^b\doteq 0\end{array}$$

(4) Emphatic TD($\lambda$) ：Emphatic TD 的 eligibility trace 形式

目标：学习 $\hat{v}(s,\mathbf{w})\doteq {\mathbf{w}}_t^{\top }\mathbf{x}(s)\approx v_{\pi }(s)$ ，此算法在 off-policy 下收敛性很强（代价是高方差、慢速），允许任何程度的 bootstrapping 。更新式如下：

$$\begin{array}{rl}& {\mathbf{w}}_{t+1}\doteq {\mathbf{w}}_t+\alpha {\delta }_t{\mathbf{z}}_t\\ & {\delta }_t\doteq R_{t+1}+{\gamma }_{t+1}{\mathbf{w}}_t^{\top }{\mathbf{x}}_{t+1}-{\mathbf{w}}_t^{\top }{\mathbf{x}}_t\\ & {\mathbf{z}}_t\doteq {\rho }_t\left({\gamma }_t{\lambda }_t{\mathbf{z}}_{t-1}+M_t{\mathbf{x}}_t\right),\text{ with }{\mathbf{z}}_{-1}\doteq 0\\ & M_t\doteq {\lambda }_t{I}_t+\left(1-{\lambda }_t\right)F_t\\ & F_t\doteq {\rho }_{t-1}{\gamma }_t{F}_{t-1}+I_t,\text{ with }{F}_0\doteq i\left(S_0\right)\end{array}$$

其中，

• $M_t\ge 0$ ：emphasis
• $F_t\ge 0$ ：followon trace
• $I_t\ge 0$ ：interest

12.12 Implementation Issues

看起来 eligibility trace 比 one-step 方法更复杂，因为他需要在每个时间点对所有状态做更新。但其实执行起来并不是什么大问题，因为实际中绝大多数 state 的 trace 都为 0，只有少量最近经历过的 state 的trace 大于 0 ，所以也只需做少量更新。

在有函数逼近的情况下，不使用 eligibility trace 的方法的计算优势有所下降，尤其是当使用了神经网络，使用 trace 时的内存和计算力的消耗只是原来的两倍。