Eligibility Traces是强化学习的一个基本技术。在 TD(\lambda) 算法中，\lambda 指的是Eligibility Traces的使用。几乎所有的时间差分方法，例如 Q-learning 或 Sarsa，都可以与Eligibility Traces相结合，以获得可以更有效的更通用的方法。
TD(\lambda)是引入Eligibility Traces的重要方法，因此我们先介绍这个方法以及理解这个方法的两种视角，然后引入Eligibility Traces方法，最后将Eligibility Traces方法应用于状态值函数和动作值函数的迭代更新以及策略优化的实施。
TD(\lambda)
n-step TD prediction
TD(\lambda) 基于 n-step 的时间差分方法，因此我们先来介绍n-step时间差分。
回忆时间差分和MonteCarlo的区别，在之前所分享的时间差分方法中，值函数的更新是在每个step之后进行的，而MonteCarlo方法中值函数的更新是在每个episode之后进行的。那么介于两者之间的方法就是n-step时间差分了。
我们需要定义n-step的回报，MonteCarlo方法所使用的回报为
G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots \gamma^{T-t-1}R_T,而 TD(0) 使用的回报为
R_{t+1} + \gamma V_t(S_{t+1}),其中，V_t 是 t 时刻对值函数 v_\pi 的估计，V_t(S_{t+1}) 可以被认为是对 R_{t+2} + \gamma R_{t+3} + \cdots \gamma^{T-t-2}R_T 的估计，同理，使用 V_t(S_{t+2}) 作为对 R_{t+3} + \cdots \gamma^{T-t-3}R_T 的估计就得到了 2-step 时间差分方法，以此类推，n-step时间差分所使用的回报就是
R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^nV_t(S_{t+n}).这里定义一个新的计算符号
G_t^{t+n}(c) = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n c,进而将增量项表示为
\Delta_t(S_t) = \alpha[G_t^{t+n}(V_t(S_{t+n}))-V_t(S_t)],对于没有被访问过的状态 s\neq S_t，记 \Delta_t(s) = 0，那么在 on-line 策略下值函数的更新就可以表示为
V_{t+1}(s) = V_t(s) + \Delta_t(s).类似地，对于 off-line 策略（只在episode结束的时候更新值函数，因此需要将值函数的增量项在一旁存储起来最后进行更新，故而叫做 offline），使用如下的迭代策略
V_{t+1}(s) = V_t(s), \forall t < T,\\
V_T(s) = V_{T-1}(s) + \sum_{t=0}^{T-1}\Delta_t(s).Forward view of TD(\lambda)
所谓的 TD(\lambda) 事实上就是在因子 \lambda 的控制下对不同的 n-step的一种组合使用，比如在 t 时刻，我们同时使用 2-step和 3-step的平均对当前的值函数进行更新，也就是使用 \frac{1}{2}G_t^{t+2}(V_t(S_{t+2})) + \frac{1}{2}G_t^{t+4}(V_t(S_{t+4})) 作为回报。这里的加权平均需要和前面的 \sum_{t=0}^{T-1}\Delta_t(s) 区分开，区别点就是起始时刻 t 不同，这里所说的是一种新的方法。
当有多个 n-step的时候，我们使用因子 \lambda 对不同的项进行加权，如下定义
L_t = (1-\lambda) \sum_{n=1}^\infty\lambda^{n-1}G_t^{t+n}(V_t(S_{t+n})).易知，每个 G_t^\sim的权重的和恒为1。对于那些 t+n>T 的 n 而言，直接使用 G_t 代表 G_t^{t+n}，于是
L_t = (1-\lambda) \sum_{n=1}^{T-t-1}\lambda^{n-1}G_t^{t+n}(V_t(S_{t+n})) + \lambda^{T-t-1}G_t. \lambda 控制了每个回报项的权重，所有的权重和为1，并且距离当前时刻 t 约遥远的回报项所占的权重越小，现在重新将 \Delta_t(S_t) 定义为
\alpha[L_t - V_t(S_t)]\\
\Delta_t(S_t) = 0, \forall s \neq S_t,其余的对值函数的更新就和前一小节是一样的了。
Backward view of TD(\lambda)
在反向视角下需要引入一个新的内存变量 E_t(s)，也就是 Eligibility\ Trace，因为它反映了每个状态最近被访问的情况，在每个step，如果一个状态没有被访问，那么它的trace进行如下的更新
E_t(s) = \gamma \lambda E_{t-1}(s),其中，\gamma 是回报折扣率，\lambda 是权重控制因子。注意这里的 E_t(s) 不是期望，而是 Eligibility\ Trace，是一个用于控制值函数增量的因子。因此一种简单的办法就是：如果一个状态被访问了，就是用加1进行更新
E_t(s) = \gamma \lambda E_{t-1}(s) + 1.状态值函数的时间差分误差定义为
\delta_t = R_{t+1} + \gamma V_t(S_{t+1}) - V_t(S_t),状态值函数的增量定义为
\Delta_t(V_t(s)) = \alpha\delta_tE_t(s). 事实上，\delta_t 控制了更新的方向，Eligibility\ Trace 控制了更新的尺度，状态最近被访问的越多，对于当前的更新尺度就越大，反则越小。
可以证明 TD(\lambda) 的前向视角和反向视角是等价的方法，感兴趣的话可以参考书中第七章第四小节内容。而且显而易见，反向视角下值函数的更新更加高效和便于计算。
策略优化
还是老规矩，上面讲完了值函数估计，下面就该进行策略优化了，还是先给出动作值函数的迭代方法，然后给出策略优化的伪代码。注意下面的更新都会基于反向视角进行计算，因为这样更加高效。
这里每个状态-动作对都有一个Eligibility\ Trace，记作 E_t(s,a)，没有被访问的状态-动作对的更新为
E_t(s,a) = \lambda\gamma E_{t-1}(s,a),为了进行更好的统一描述，我们定义一个标记变量 I_{aA}，如果 A=a 那么 I_{aA} = 1，否则为 。Eligibility\ Trace 的更新现在可以统一表示为
E_t(s,a) = \lambda\gamma E_{t-1}(s,a) + I_{sS_t}I_{aA_t}.这种更新方法被称作 accumulating，当然还有 dutch 和 replacing 两种方法，如下：
E_t(s,a) = (1-\alpha)\lambda\gamma E_{t-1}(s,a) + I_{sS_t}I_{aA_t}\ \ (dutch)\\
E_t(s,a) = (1 - I_{sS_t}I_{aA_t})\lambda\gamma E_{t-1}(s,a) + I_{sS_t}I_{aA_t}\ \ (replacing).和状态值函数一样，现在可以定义动作值函数的增量并进行更新了
Q_{t+1}(s,a) = Q_t(s,a) + \alpha\delta_tE_t(s,a), \forall s,a,其中，\delta_t = R_{t+1}+\gamma Q_t(S_{t+1},A_{t+1}) - Q_t(S_t,A_t).
伪代码如下
当然也可以采用off-policy的方法，也就是之前说过的Q-learning方法，只需要将 \delta_t 替换为
R_{t+1}+\gamma \max_{a'}Q_t(S_{t+1},a') - Q_t(S_t,A_t).总结
以上就是关于 Eligibility\ Traces 的部分，下次是强化学习中的Tabular方法，敬请期待~