强化学习中的泛化：使用稀疏粗编码的成功示例|哈希|示例|神经网络|算法

Generalization in Reinforcement Learning: Successful Examples Using Sparse Coarse Coding

强化学习中的泛化：使用稀疏粗编码的成功示例

https://cseweb.ucsd.edu/~gary/190-RL/sutton-98.pdf

摘要

在大型问题上，强化学习系统必须使用参数化函数逼近器（如神经网络），以便在相似的情况和动作之间进行泛化。在这些情况下，关于收敛精度的理论结果尚不成熟，且计算结果好坏参半。特别是，Boyan和Moore在去年的会议上报告了一系列负面结果，他们在尝试将动态规划与函数逼近相结合，应用于具有连续状态空间的简单控制问题时遭遇了失败。在本文中，我们针对他们尝试过的所有控制任务，以及一个规模显著更大的任务，展示了正面的结果。最重要的区别在于，我们使用了稀疏粗编码函数逼近器（CMACs），而他们主要使用的是全局函数逼近器；并且我们是在线学习，而他们是离线学习。Boyan、Moore及其他人曾建议，他们遇到的问题可以通过使用实际结果（“rollouts”）来解决，就像经典蒙特卡洛方法那样，或者像TD(λ)算法中λ=1时那样。然而，在我们的实验中，这种方法总是导致性能显著变差。我们得出结论，强化学习可以与函数逼近器稳健地结合工作，并且目前几乎没有理由避免使用一般λ的情况。

1 强化学习与函数逼近

强化学习是一类广泛的最优控制方法，基于从经验、模拟或搜索中估计价值函数（Barto, Bradtke & Singh, 1995; Sutton, 1988; Watkins, 1989）。这些方法中的许多，例如动态规划和时序差分学习，部分地基于其他估计来构建它们的估计。这可能令人担忧，因为在实践中，估计永远不会变得完全精确；在大型问题上，必须使用参数化函数逼近器，如神经网络。因为估计是不完美的，并且因为它们反过来被用作其他估计的目标，所以最终结果可能是非常差的估计，甚至发散，这似乎是可能的。事实上，一些这样的方法已被证明在理论上是不稳定的（Baird, 1995; Gordon, 1995; Tsitsiklis & Van Roy, 1994）以及在实践中（Boyan & Moore, 1995）。另一方面，其他方法已被证明在理论上是稳定的（Sutton, 1988; Dayan, 1992）并且在实践中非常有效（Lin, 1991; Tesauro, 1992; Zhang & Dietterich, 1995; Crites & Barto, 1996）。为了获得良好的性能，方法或任务的关键要求是什么？本文中的实验是缩小这个问题答案范围的一部分。

为了将 sarsa 算法应用于具有连续状态空间的任务，我们将其与一种稀疏的、粗编码的函数逼近器结合，称为 CMAC（Albus, 1980; Miller, Gordon & Kraft, 1990; Watkins, 1989; Lin & Kim, 1991; Dean et al., 1992; Tham, 1994）。CMAC 使用状态空间的多个重叠平铺（tilings）来产生特征表示，用于最终发生所有学习的线性映射。见图 2。整体效果非常像具有固定径向基函数的网络，除了它在计算上特别高效（在其他方面，人们会期望 RBF 网络和类似方法（见 Sutton & Whitehead, 1993）也能同样工作）。重要的是要注意，平铺不需要是简单的网格。例如，为了避免“维数灾难”，一个常见的技巧是在某些平铺中忽略某些维度，即使用超平面切片而不是盒子。第二个主要技巧是“哈希”——将大量瓦片（tiles）一致地随机折叠成一个小得多的集合。通过哈希，内存需求通常减少很大的倍数，而性能损失很小。这是可能的，因为只有在状态空间的一小部分需要高分辨率。哈希使我们从维数灾难中解放出来，其意义在于内存需求不需要在维度数量上呈指数增长，而只需要匹配任务的真实需求。

2 控制问题上的良好收敛

我们将 sarsa 和 CMAC 的组合应用于 Boyan 和 Moore (1995) 研究的三个连续状态控制问题：2D 网格世界（2D gridworld）、水坑世界（puddle world）和山地车（mountain car）。虽然他们使用了任务动态模型，并对一组固定的状态离线应用动态规划回溯（backups），但我们是在线学习的，没有模型，并且对在完整试验中遇到的任何状态进行回溯。与 Boyan 和 Moore 不同，我们在所有任务上都发现了稳健的良好性能。我们在此报告水坑世界和山地车的结果，这是他们考虑的任务中较难的两个。

我们还实验了一个更大且更困难的任务，这是 Boyan 和 Moore 未曾尝试过的。Acrobot（杂技机器人）是一个双连杆欠驱动机器人（图 5），大致类似于在单杠上摆动的体操运动员（Dejong & Spong, 1994; Spong & Vidyasagar, 1989）。第一个关节（对应体操运动员抓在杠上的手）无法施加（力矩）。

目标是将端点（脚）摆动到高于横杆一个连杆长度的位置。如同在山地车任务中一样，有三个动作：正力矩、负力矩和无力矩，并且每一步的奖励是 -1。（见附录。）

3 λ λ 的影响

图7总结了这些数据，以及另外两项针对不同任务的系统研究的数据，从而展示了 λ λ 影响的全貌。在所有情况下，性能都是 λ λ 的倒U形函数，并且当 λ λ 接近1时性能迅速恶化，此时获得最差性能。随着 λ λ 从0增加性能有所提高，这一事实支持使用资格迹（eligibility traces），并反对使用 TD(0) 和单步 Q-learning 等单步方法。随着 λ λ降至1以下性能迅速提高，这一事实反对使用蒙特卡洛或“rollout”方法。尽管这些方法具有理论上的渐近优势，但在实践中它们似乎表现较差。