时序差分学习

21.2.3 时序差分学习

（几乎）同时具备这两种方法的优点是可能的。也就是说，可以近似前面所示的约束方程，而不必对所有可能的状态求解它们。关键在于使用观察到的转移来调整观察到的状态的值，使它们与约束方程相一致。例如，考虑第21.2节中第2次试验中从状态(1, 3)到(2, 3)的转移。假定作为第1次试验的结果，效用估计为Uπ(1,3)=0.84和Uπ(2,3)=0.92。现在，如果此转移总是出现，我们期望其效用服从

Uπ(1,3)=−0.04+Uπ(2,3)

所以Uπ(1, 3) 是0.88。这样，其当前估计值0.84就有些偏低了，应该提高。一般来说，当发生从状态s到s'的转移时，我们将对Uπ(s)应用如下更新：

这里α 是学习速度参数。因为此更新规则使用的是相继状态之间的效用差分，它也经常被称为时序差分或TD公式。

所有时序差分方法的基本思想是，首先定义当效用估计正确时局部成立的条件，然后，写出更新公式使估计值向理想的“均衡”方程靠近。在被动学习的情况下，公式（21.2）给出了其均衡方程。现在，公式（21.3）确实使得智能体达到公式（21.2）所给出的均衡，不过其中涉及到一些微妙之处。首先，注意更新只涉及观察到的后继状态 s'，而实际的均衡条件则涉及到所有可能的下一个状态。人们也许会认为当一个非常罕见的转移发生时，这会导致Uπ(s)发生不正确的巨大变化，但事实上，由于罕见转移鲜有发生，Uπ(s)的平均值仍将收敛到正确的值。此外，如果我们把α 由一个固定的参数变为一个随某个状态被访问次数的增加而递减的函数，那么U(s)本身将会收敛到正确的值[29]。这样我们得到了图21.4所示的智能体程序。图21.5描绘了被动时序差分（TD）智能体在4 × 3世界里的性能表现。它的学习速度不如ADP智能体快，并且表现出更高的易变性，但是它更简单，每次观察所需的计算量也要少得多。注意，TD 不需要一个模型来执行其更新。环境以观察到的转移的形式提供了相邻状态之间的联系。

图21.4 一个使用时序差分方法学习效用估计的被动强化学习智能体

ADP方法和TD方法实际上是密切相关的。二者都试图对效用估计进行局部调整，以便使每一个状态都与其后继状态相“一致”。一个区别在于TD调整一个状态使其与已观察到的后继状态相一致（公式（21.3）），而ADP则调整该状态使其与所有可能出现的后继状态相一致，根据概率进行加权（公式（21.2））。由于转移集合中的每个后继状态的频率与其概率近似成正比，所以当TD调整的影响在大量的转移上计算平均的时候，上述差别便消失了。一个更重要的差别是，TD 对每个观察到的转移都只进行单一的调整，而ADP为了重建效用估计U和环境模型T之间的一致性会按所需进行尽可能多地调整。虽然观察到的转移只造成T的局部变化，其影响却可能需要在整个U中传递。因此，TD可以被视为对ADP的一个粗略而有效的一阶近似。

图21.5 4×3世界中的TD学习曲线。（a）挑选出来的状态子集的效用估计，作为试验次数的函数。（b）对U(1,1)进行估计的均方根误差，20次运行的平均值，每次进行500次试验。图中只显示了前100次试验以便与图21.3相比较

从TD的观点来看，ADP所做的每一个调整都可以被视为通过模拟当前环境模型而生成的一个“伪经验（pseudo-experience）”的结果。已知当前环境模型，就可能扩展TD方法，以利用该模型产生一些伪经验——TD智能体能想象出的可能发生的转移。对于每个观察到的转移，TD智能体可以生成大量的虚构转移。这样，对作为结果的效用估计就会越来越近似接近于 ADP 的效用估计——当然，这是以增加计算时间为代价的。

用一种类似的方式，我们可以通过直接对算法的价值迭代或策略迭代过程进行近似，生成 ADP的更为有效的版本。回忆前面提到的，当状态数量巨大时，完全价值迭代将是不可操作的。然而，许多调整步骤是极其微小的。快速生成相当好的答案的一条可能途径是限制在每次观察到的转移之后所做调整的数量。也可以用启发式对可能的调整排序，以便只执行那些最显著的。区分优先次序的筛选启发式优先调整那些其可能后继状态在自身的效用估计中刚刚完成较大调整的状态。使用这样的启发式，就训练序列的数量而言，近似ADP算法通常几乎能学习得如同完全ADP一样快，但是从计算的角度看则其效率可以提高几个数量级。（参见习题21.3。）这使得它们能够处理那些对完全ADP来说太大的状态空间。近似ADP算法还有另外一个优势：在对一个新环境进行学习的早期阶段，环境模型T往往与正确的模型相差很远，所以无法计算出一个确切的效用函数与之相匹配。近似算法可以使用最小的调整规模，随着环境模型的不断精确而下降。这消除了在学习早期由于模型的巨大变化而可能发生的非常长时间的价值迭代。