7.1-状态值估计:时序差分算法
本节将介绍最基础的TD算法，它可以估计一个给定策略的状态值。后面的章节会进一步推广这个TD算法从而得到更复杂的算法，因此本节的内容非常重要。 例如，本章介绍的所有算法都属于时序差分（TD）学习的范畴。然而，本节所述的时序差分学习特指一种用于估计状态值的经典算法。
Note
本节核心在于用TD算法求解一个给定的策略\(\pi\)的状态值，之所以要求解状态值，是因为求解出来状态值后就相当于policy evaluation，之后和policy improvement结合，就可以寻找最优策略。
7.1.1 算法描述¶
Note
TD算法基于数据而非模型，这些数据都是由一个给定的策略\(\pi\)产生的，TD算法就是要利用这些数据估计\(\pi\)所对应的状态值。
给定策略\(\pi\)，我们的目标是估计所有状态\(s \in \mathcal{S}\)对应的状态值 \(v_\pi(s)\)。假设我们拥有一些由\(\pi\)生成的经验样本\((s_0, r_1, s_1, \ldots, s_t, r_{t+1}, s_{t+1}, \ldots)\)(也可写为\(\{(s_t,r_{t+1},s_{t+1})\}_t\))，其中\(t=0,1,2,\ldots\)表示采样时刻。以下时序差分(TD)算法可利用这些样本来估计状态值：
其中\(t =0,1,2, \ldots\)。此处\(v_t(s_t)\)表示时刻\(t\)时\(v_\pi(s_t)\)的估计值；\(\alpha_t(s_t)\)为状态\(s_t\)在时刻\(t\)的学习率。
在时刻\(t\)时，只有当时正在被访问的状态\(s_t\)的估计值会被更新(如式\((7.1)\)所示);未访问状态的估计值保持不变(如式\((7.2)\)所示)。通常情况下，式\((7.2)\)会被省略，但是我们应该知道该式子的存在。该式可以帮助我们更好地理解TD算法，如果没有这个式子，TD算法在数学上也是不完整的。
Note
回想一下，TD算法在数学上的作用是什么?答案就是它求解给定策略\(\pi\)的贝尔曼方程，但是之前的课程我们学了解析解和数值解，这里的TD算法与他的区别是什么呢？答案是显而易见的，之前的方法是基于模型的方法，而TD算法并不依赖于模型。
许多读者在第一次看到\((7.1)\)中的TD算法时会问为什么它要设计成这个样子?实际上，该算法是一个用于求解贝尔曼方程的随机近似算法。要理解这一点，我们首先回顾状态值的定义：
式子\((7.3)\)可被重写为
这是因为\(\mathbb{E}[G_{t+1}|S_t = s] = \sum_a \pi(a|s) \sum_{s'} p(s'|s, a)v_\pi(s') = \mathbb{E}[v_\pi(S_{t+1})|S_t = s]\)。式\((7.4)\)是贝尔曼方程的另一种表达，它有时被称为贝尔曼期望方程(Bellman expecta-tion equation)。如果我们应用第6章介绍的罗宾斯-门罗算法来求解式\((7.4)\),相应的算法就是TD算法。感兴趣的读者可以参见Box 7.1。
Note
建议读者读一下Box7.1，否则对于这个算法很可能云里雾里。
7.1.2 性质分析¶
下面讨论TD算法(7.1)的一些重要性质。 首先，我们先介绍TD算法中每一项的含义。具体如下所示：
在这里
被称为TD目标值(TD target)，而
7.1.2 性质分析¶
称为TD误差(TD error)。可以看出，新估计值\(v_{t+1}(s_t)\)是当前估计值\(v_t(s_t)\)与时序差分误差\(\delta_t\)的组合。
-
为什么\(\bar{v}_t\)被叫做TD目标值
是因为该算法在数学上就是让\(v(s_t)\)的值更加接近\(\bar{v}_t\)，即\(\bar{v}_t\)是\(v(s_t)\)的目标值。为了理解这一点，我们在(7.6)两边同时减去可得
\[\begin{gathered}v_{t+1}(s_{t})-\bar{v}_{t}=\left[v_{t}(s_{t})-\bar{v}_{t}\right]-\alpha_{t}(s_{t})\left[v_{t}(s_{t})-\bar{v}_{t}\right]\\=[1-\alpha_{t}(s_{t})]\left[v_{t}(s_{t})-\bar{v}_{t}\right].\end{gathered}\]上述等式两边取绝对值可得
\[|v_{t+1}(s_t) − \bar{v}_t| = |1 − \alpha_t(s_t)||v_t(s_t) − \bar{v}_t|.\]由于\(\alpha_t(s_t)\)是一个小的正数，因此有\(0 <1 - \alpha_t(s_t) <1\)。因此由上式可以推得
\[|v_{t+1}(s_t) − \bar{v}_t| < |v_t(s_t) − \bar{v}_t|.\]上述不等式清晰地表明了新的值\(v_{t+1}(s_t)\)比旧的值\(v_t(s_t)\)更接近 \(\bar{v}_t\)。因此，这个算法在数学上使\(v_t(s_t)\)接近 \(\bar{v}_t\)。这就是为什么\(\bar{v}_t\)被称为TD目标。
-
如何理解TD误差？ TD误差之所以被称为时序差分的原因是\(\delta_t = v_t(s_t) - (r_{t+1} + \gamma v_t(s_{t+1}))\)反映了时刻\(t\)与\(t+1\)之间的差异。TD误差被称为误差不仅仅因为它反映了两个时刻之间的差异，更重要的是反映了估计值\(v_t\)与真实状态值\(v_\pi\)之间的差异。如果估计值是准确的，那么TD误差在期望意义上应该等于0。为了理解这一点，当\(v_t = v_\pi\)时，TD误差的期望值为
\[\begin{aligned}\mathbb{E}[\delta_{t}|S_{t}=s_{t}]&=\mathbb{E}\left[v_{\pi}(S_{t})-(R_{t+1}+\gamma v_{\pi}(S_{t+1}))|S_{t}=s_{t}\right]\\&=v_{\pi}(s_{t})-\mathbb{E}\left[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_{t}=s_{t}\right]\\&=0.\quad\mathrm{(due~to~(7.3))}\end{aligned}\]从另一个角度来说，TD误差可被理解为新息(innovation)，即代表从经验样本 \((s_t, r_{t+1}, s_{t+1})\)中获得的新的信息。这个新的信息可以用来纠正当前估计值，从而使其更准确。新息在很多估计方法例如卡尔曼滤波[33,34]中都是非常关键的量。
第二，\((7.1)\)中的TD算法只能估计某一给定策略的状态值。而不能直接用于寻找最优策略。不过该TD算法对于理解本章其他算法非常重要。例如，我们将在第\(7.2\)节推广\((7.1)\)从而得到能估计行动值的TD算法，进而结合策略改进步骤来得到最优策略。
第三，虽然时序差分(TD)学习和蒙特卡洛(MC)学习均属于无模型方法，它们有什么不同的？答案总结于表\(7.1\)。虽然有些概念在后面章节才会介绍，但是并不影响目前的理解。
| TD学习 | MC学习 |
|---|---|
| 增量: 它可以在得到一个经验样本后立即更新状态/行动值。 | 非增量: MC学习是非增量的。它必须等到一个回合(episode)结束之后，才能用所有经验样本更新估计值，这是因为它必须计算从某一个状态到回合最后的折扣回报。 |
| 持续任务: 由于TD学习是增量的，它可以处理回合制和持续性任务。持续任务可能没有终止状态。 | 回合任务: 由于MC学习是非增量的，它只能处理回合任务，即回合在有限步后终止。 |
| 自举: TD学习采用自举法(bootstrapping)，因为状态/行动值的更新依赖于先前估计值。因此，TD学习需要初始值。 | 非自举: MC学习不是自举的，因为它可以直接估计状态值/行动值，而无需初始值。 |
| 低估计方差: TD算法的估计方差低于MC，因为它涉及较少的随机变量。例如，估计一个动作值 \( q_\pi(s_t, a_t) \)，Sarsa 仅需要三个随机变量的样本：\( R_{t+1} \), \( S_{t+1} \), \( A_{t+1} \)。 | 高估计方差: MC的估计方差较高，因为涉及更多的随机变量。例如，为了估计一个行动值 \( q_\pi(s_t, a_t) \)，我们需要样本 \( R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \)。假设每个回合的长度为 \( L \)，并且每个状态的动作数量相同，记作 ( |
| > 表7.1: TD学习与MC学习的比较。 |
7.1.3 收敛性分析¶
下面给出\((7.1)\)中TD算法的收敛性分析。
Info
定理7.1（时序差分学习的收敛性）。给定一个策略\(\pi\)，基于式\((7.1)\)中的TD算法，如果对所有\(s \in \mathcal{S}\)都有\(\sum_t \alpha_t(s) = \infty\)和\(\sum_t \alpha_t^2(s) < \infty\)，则\(v_t(s)\)几乎必然收敛到 \(v_\pi(s)\)（当 \(t \to \infty\)时）。
在给出该定理的证明之前，我们先讨论其中关于\(\alpha_t\)的条件。第一，条件\(\sum_t \alpha_t(s) = \infty\)和\(\sum_t \alpha^2_t(s) < \infty\)应该对所有\(s \in S\)都成立。值得注意的是，在\(t\)时刻，如果状态\(s\)被访问，则\(\alpha_t(s) >0\);否则，\(\alpha_t(s) =0\)。因此，条件\(\sum_t \alpha_t(s) = \infty\)在理论上要求状态\(s\)被访问无限次(实际中访问足够多次即可)。所以该条件实际上是要求有足够多的经验数据。第二，学习率\(\alpha_t\)在实际中常常被选择为一个小的正数。此时，条件\(\sum_t \alpha_t(s) = \infty\)仍然成立，但是条件\(\sum_t \alpha^2_t(s) < \infty\)不再成立。这样选择a₄的原因是它能够很好地利用后面(t比较大时)得到的数据。否则，如果\(\alpha_t\)逐渐收敛到\(0\),那么当\(t\)较大时得到的数据对估计的影响已经微乎其微了。当\(\alpha_t\)恒等于一个正数时，算法仍然可以在某种意义上收敛，详情参见文献[24,第1.5节]。实际中，我们之所以希望t比较大时数据仍然有效，其本质原因是这样可以应对时变系统(例如策略或环境缓慢变化)。