时序差异学习与探索的重要性：一份图解指南

比较模型无关和模型基础的强化学习方法在动态网格世界上的效果

最近，强化学习（RL）算法通过解决研究问题，如蛋白质折叠、达到超人水平的无人机竞赛，甚至在您最喜欢的聊天机器人中整合人类反馈，获得了很多关注。

事实上，RL为各种顺序决策问题提供了有用的解决方案。时间差分学习（TD学习）方法是RL算法的一个流行子集。TD学习方法结合了蒙特卡洛和动态规划方法的关键方面，加速学习而不需要对环境动态的完美模型。

在本文中，我们将在一个自定义的网格世界中比较不同类型的TD算法。实验的设计将强调连续探索的重要性以及被测试算法的个体特征：Q学习、Dyna-Q和Dyna-Q+。

本文的概要包括：

• 环境描述
• 时间差分（TD）学习
• 无模型TD方法（Q学习）和模型基础TD方法（Dyna-Q和Dyna-Q+）
• 参数
• 性能比较
• 结论

可以在此处找到完整的代码，以重现结果和图表：https://github.com/RPegoud/Temporal-Difference-learning

环境

本实验中使用的环境是一个具有以下特征的网格世界：

• 网格大小为12×8个单元格。
• 代理开始于网格的左下角，目标是到达位于右上角的宝藏（一个具有奖励1的终止状态）。
• 蓝色传送门相连，通过位于单元格（10, 6）的传送门可以到达单元格（11, 0）。代理在第一次过渡后不能再次使用传送门。
• 紫色传送门仅在100个剧集后出现，但使代理能够更快地到达宝藏。这鼓励不断探索环境。
• 红色传送门是陷阱（具有奖励0的终止状态），并结束剧集。
• 撞到墙壁会导致代理保持在同一状态。

本实验旨在比较Q学习、Dyna-Q和Dyna-Q+代理在一个变化的环境中的行为。在100个剧集之后，最优策略将发生变化，并且成功剧集中的最优步数将从17减少到12。

时间差分学习简介：

时序差分学习是蒙特卡洛（MC）和动态规划（DP）方法的结合：

• 与MC方法类似，TD方法可以从经验中学习，而不需要模型的环境动态。
• 与DP方法类似，TD方法在每一步之后根据其他学到的估计更新估计值，而不需要等待结果（这被称为自举）。

TD方法的一个特点是它们在每个时间步骤都更新其值估计，而MC方法要等到一个情节结束才更新。

事实上，这两种方法有不同的更新目标。MC方法旨在更新回报Gt，这只在一个情节结束时才可用。相反，TD方法的目标是：

其中V是真实值函数Vπ的估计。

因此，TD方法将采样（通过使用真实值的估计）和自举（通过根据进一步的估计更新V）的思想结合起来。

时序差分学习的最简单版本称为TD(0)或一步TD，TD(0)的一个实际实现如下：

当从状态S过渡到新状态S’时，TD(0)算法将计算一个备份值并相应地更新V(S)。这个备份值称为TD误差，即最优值函数 V_star 与我们当前估计值V(S)之间的差异：

总之，TD方法具有以下几个优点：

• 它们不需要对环境动态的模型进行完美建模。
• 它们以在线方式实现，每个时间步骤后更新目标。
• 如果学习率α（学习速率或步长）遵循随机逼近条件，TD(0)对于任何固定策略π都保证收敛（更多详细信息请参见《强化学习导论》[4]第55页“跟踪非平稳问题”）。

实现细节：

以下各节探讨了几种TD算法的主要特点和在网格世界中的性能。

出于简化的目的，所有模型使用相同的参数：

• Epsilon (ε) = 0.1：在ε-贪婪策略中选择随机动作的概率
• Gamma (γ)= 0.9：应用于未来奖励或值估计的折扣因子
• Aplha (α) = 0.25：限制Q值更新的学习率
• Planning steps = 100：对于Dyna-Q和Dyna-Q+，每个直接交互执行的规划步骤数
• Kappa (κ)= 0.001：对于Dyna-Q+，规划步骤期间应用的奖励奖励的权重

每个算法的性能首先展示了对400个情节的单次运行（部分：Q-learning，Dyna-Q和Dyna-Q+），然后在“概述和算法比较”部分中对250个情节的100次运行进行了平均。

Q-learning

我们首先要实现的算法是著名的Q-learning算法（Watkins, 1989）：

Q-learning是一种离策略算法，因为其目标是直接逼近最优值函数，而不是逼近智能体遵循的策略π的值函数。

在实践中，Q-learning仍然依赖于一个策略，通常称为“行为策略”，用于选择要访问和更新的状态-动作对。然而，Q-learning是离策略的，因为它基于未来回报的最佳估计值来更新其Q值，而不管所选动作是否遵循当前策略π。

与前面的时序差分学习伪代码相比，有三个主要的不同之处：

• 我们需要为所有的状态和动作初始化Q函数，并且Q(terminal)应该为0
• 动作是根据Q值选择的策略选择的（例如，相对于Q值的ε-贪婪策略）
• 更新的目标是动作值函数Q，而不是状态值函数V

现在我们有了第一个算法用于测试，我们可以开始训练阶段了。我们的智能体将使用ε-贪婪策略在网格世界中导航，这个策略是根据Q值选择具有最高Q值的动作的概率为(1 – ε)，并以概率ε选择一个随机动作。每次执行动作后，智能体将会更新它的Q值估计。

我们可以使用热力图来可视化网格世界的每个单元格的估计最大动作值 Q(S, a) 的演化。在这里，智能体进行了400个回合。由于每个回合只有一次更新，Q值的演化速度相对较慢，一大部分状态保持未映射：

完成了400个回合后，对每个单元格的总访问次数进行分析，可以给出智能体平均路径的相当准确的估计。如下图右侧所示，智能体似乎已经收敛到了一个次优路径，避开了单元格(4,4)并始终沿着下边墙行动。

由于这种次优策略，智能体每个回合的步数最少为21步，如“总访问次数”图所示。步数的变化可以归因于ε-贪婪策略，该策略引入了10%的随机动作的可能性。根据这个策略，沿着下边墙走是一种不错的策略，可以减少随机动作带来的潜在干扰。

总之，正如之前提到的，Q-learning代理器收敛到了一个次优策略。此外，环境的一部分仍然未被Q函数探索，这阻止了代理器在第100个episode之后紫色传送门出现时找到新的最优路径。

这些性能限制可以归因于相对较低的训练步数（400），限制了与环境的交互和ε-greedy策略引发的探索。

规划是模型为基的强化学习方法的一个重要组成部分，特别有助于提高样本效率和动作值的估计。Dyna-Q和Dyna-Q+是结合了规划步骤的TD算法的良好示例。

Dyna-Q

Dyna-Q算法（动态Q-learning）是模型为基强化学习和TD学习的结合。

模型为基强化学习算法依赖于环境模型来通过规划作为其主要的值估计更新方式。相反，无模型算法依赖于直接学习。

“环境模型是代理器用来预测环境对其行为的响应的任何东西” — 强化学习导论。

在本文的范围内，模型可以被看作是转移动态p(s’, r|s, a)的近似。这里，p返回给定当前状态-动作对的单个下一个状态和奖励对。

在p是随机的环境中，我们区分分布模型和采样模型，前者返回下一个状态和动作的分布，而后者返回从估计分布中采样得到的单个对。

模型在模拟episode中特别有用，因此通过规划步骤替换与真实环境的交互来训练代理器。

实施Dyna-Q算法的代理器属于规划代理器类，即将直接强化学习和模型学习相结合的代理器。它们使用与环境的直接交互来更新其值函数（如Q-learning中的那样），并且还使用模型学习环境的模型。在每次直接交互之后，它们还可以执行规划步骤，使用模拟交互来更新其值函数。

一个快速的国际象棋示例

想象一下进行一场精彩的国际象棋比赛。在每一步棋之后，对手的反应可以让你评估你的走法的质量。这类似于接收到正面或负面的奖励，使你能够“更新”你的策略。如果你的走法导致失误，你可能不会再做同样的走法，前提是棋盘的配置相同。到目前为止，这与直接强化学习相似。

现在让我们加入规划。想象一下，在每一步棋之后，当对手在思考时，你会在脑海中回顾你的每一步走法，重新评估它们的质量。你可能会发现一开始忽视的弱点，或者发现特定的走法比你想象的更好。这些思考也可以让你更新你的策略。这正是规划所涉及的，即在不与真实环境交互而是与环境模型交互的情况下更新值函数。

因此，与Q-learning相比，Dyna-Q包含一些额外的步骤：

在每次直接更新Q值之后，模型存储已观察到的状态-动作对以及奖励和下一个状态。这一步骤称为模型训练。

• 在模型训练之后，Dyna-Q执行n个规划步骤：
• 从模型缓冲区中选择一个随机状态-动作对（即，此状态-动作对在直接交互中观察到）
• 模型生成模拟奖励和下一个状态
• 使用模拟观察（s, a, r, s’）更新值函数

我们现在使用Dyna-Q算法进行学习过程的复制，使用n=100。这意味着在每次与环境直接交互之后，我们使用模型进行100个规划步骤（即更新）。

下面的热力图显示了Dyna-Q模型的快速收敛。实际上，该算法只需大约10个回合就能找到最优路径。这是因为每一步都会导致Q值的101次更新（而不是Q-learning的1次）。

规划步骤的另一个好处是更好地估计网格中的动作值。由于间接更新会针对存储在模型中的随机转换，远离目标的状态也会得到更新。

相比之下，Q-learning中的动作值会从目标慢慢传播，导致对网格的不完整映射。

使用Dyna-Q，我们找到了一个最优路径，在17步内解决了网格世界，如下图中的红色条表示。尽管为了探索而偶尔干扰了ε-贪心动作，但定期达到了最佳性能。

最后，虽然Dyna-Q可能因为其规划的引入而比Q-learning更具说服力，但是必须记住规划在计算成本和实际探索之间存在权衡。

Dyna-Q+

到目前为止，测试的两种算法都没有找到在第100步之后出现的最优路径（紫色传送门）。事实上，这两种算法迅速收敛到一个在训练阶段末尾保持不变的最优解。这强调了在整个训练过程中需要持续探索的必要性。

Dyna-Q+与Dyna-Q在很大程度上相似，但对算法进行了小改动。Dyna-Q+不断跟踪自真实与环境的交互中尝试每个状态-动作对的时间步长。

具体而言，考虑一个在τ个时间步内未尝试的产生奖励r的转换。Dyna-Q+会将规划执行，假设此转换的奖励为r + κ √τ，其中κ足够小（实验中为0.001）。

这种奖励设计的变化鼓励代理不断探索环境。它假设状态-动作对越长时间未尝试，这对的动态可能已经改变或者模型不正确的可能性就越大。

如下热力图所示，与之前的算法相比，Dyna-Q+在更新方面更加活跃。在第100个回合之前，智能体探索整个网格并找到了蓝色传送门和第一条最优路径。

其余网格的动作值在一段时间内减小，然后再慢慢增加，因为左上角的状态-动作对没有被探索过一段时间。

当第100个回合出现紫色传送门时，智能体找到了新的捷径，整个区域的值也提高了。在完成400个回合之前，智能体将持续更新每个状态-动作对的动作值，同时偶尔探索网格。

由于对模型奖励添加了奖励，我们最终获得了Q函数的完整映射（每个状态或单元都有一个动作值）。

结合持续的探索，智能体能够在新的最佳路径（即最优策略）出现时找到它，同时保留之前的解决方案。

然而，在Dyna-Q+中，探索和利用的权衡确实是有代价的。当状态-动作对没有被足够长的时间访问时，探索奖励会鼓励智能体重新访问这些状态，这可能会暂时降低其即时性能。这种探索行为优先更新模型以改进长期的决策。

这就解释了为什么Dyna-Q+播放的某些回合可能长达70步，而Q-learning和Dyna-Q分别最多只有35和25步。Dyna-Q+中更长的回合反映了智能体愿意投入额外的步骤进行探索，以收集更多关于环境的信息并改进其模型，即使这会导致短期性能下降。

相比之下，Dyna-Q+定期实现了以前的算法无法达到的最佳性能（在下图中用绿色柱状图表示）。

总结和算法比较

为了比较算法之间的关键差异，我们使用两个指标（请记住，结果取决于相同的输入参数，这是为了简化起见）：

• 每个回合的步数：该指标描述了算法收敛到最优解的速度。它还描述了算法在收敛后的行为，特别是在探索方面。
• 平均累积奖励：导致正奖励的回合的百分比

分析每个回合的步数（见下图），可以揭示基于模型和无模型方法的几个方面：

• 基于模型的效率：基于模型的算法（Dyna-Q和Dyna-Q+）在这个特定的Grid World中更加样本高效（这种特性在强化学习中也更常见）。这是因为它们可以利用对环境的学习模型进行预测，从而更快地收敛到接近最优或最优解。
• Q-learning的收敛性：Q-learning虽然最终会收敛到接近最优解，但需要更多的回合（125个）才能实现。需要强调的是，Q-learning每步只执行1次更新，而Dyna-Q和Dyna-Q+执行多次更新。
• 多次更新：Dyna-Q和Dyna-Q+每步执行101次更新，这有助于它们更快地收敛。然而，这种样本高效性的代价是计算成本（请参见下表中的运行时间部分）。
• 复杂环境：在更复杂或随机的环境中，基于模型的方法的优势可能会减弱。模型可能引入错误或不准确性，这可能导致次优策略。因此，这种比较应该被视为不同方法的优点和缺点的概述，而不是直接的性能比较。

现在我们介绍平均累积奖励（ACR），它表示代理达到目标的百分比（因为达到目标的奖励为1，触发陷阱的奖励为0），ACR可以简单计算如下：

其中N是集数（250），K是独立运行的次数（100），Rn,k是运行k中第n集的累积奖励。

以下是所有算法的性能分析：

• Dyna-Q收敛迅速，达到了最高的总体回报率，ACR为87%。这意味着它能够高效学习并在大部分集数中达到目标。
• Q-learning也达到了类似水平的性能，但需要更多的集数才能收敛，解释了它稍低的ACR，为70%。
• Dyna-Q+在只经过15集后就迅速找到了一个好策略，累积奖励达到了0.8。然而，由于奖励加成引起的变异性和探索性会降低性能，在第100步之前性能有所下降。100步之后，它开始改善，因为它发现了新的最优路径。然而，短期探索会损害其性能，导致ACR为79%，低于Dyna-Q但高于Q-learning。

结论

在本文中，我们介绍了时序差分学习的基本原理，并将Q-learning、Dyna-Q和Dyna-Q+应用于自定义的网格世界。这个网格世界的设计强调了在不断变化的环境中持续探索的重要性，以发现和利用新的最优策略。通过每集步数和累积奖励的评估，这些算法的性能差异展示了它们的优点和缺点。

总结起来，基于模型的方法（Dyna-Q、Dyna-Q+）相比基于模型的方法（Q-learning）在样本效率上具有优势，但计算效率较低。然而，在随机或更复杂的环境中，模型的不准确性可能会影响性能，导致次优策略。

参考文献：

[1] Demis Hassabis, AlphaFold揭示了蛋白质宇宙的结构（2022），DeepMind

[2] Elia Kaufmann, Leonard Bauersfeld, Antonio Loquercio, Matthias Müller, Vladlen Koltun和Davide Scaramuzza，使用深度强化学习进行冠军级无人机竞速（2023），Nature

[3] Nathan Lambert, LouisCastricato, Leandro von Werra, Alex Havrilla，用人类反馈说明强化学习（RLHF），HuggingFace

[4] Sutton, R. S., & Barto, A. G. . 强化学习导论（2018），剑桥（马萨诸塞州）：MIT出版社。

[5] Christopher J. C. H. Watkins & Peter Dayan，Q-learning（1992），机器学习，Springer Link