强化学习，第 5 部分：时间差异学习

目录

一、介绍

1.1 关于强化学习

1.2 关于此文章

二、算法思路

2.1 时间序列

2.2 举个例子

三、Constant-α 蒙特卡洛

3.1 一步式 TD

3.2 比较

四、算法变体

4.1 Sarsa

4.2 Q-学习

4.3 预期 SARSA

五、最大化偏差

5.1 最大偏差

5.2 例

六、双重学习

6.1 算法思路

6.2 例

七、结论

一、介绍

1.1 关于强化学习

        R强化学习是机器学习中的一个领域，它引入了智能体在复杂环境中学习最佳策略的概念。代理从其操作中学习，从而根据环境的状态获得奖励。强化学习是一个具有挑战性的话题，与机器学习的其他领域有很大不同。

        强化学习的显着之处在于，可以使用相同的算法来使代理适应完全不同的、未知的和复杂的条件。

笔记。要完全理解本文中包含的概念，强烈建议熟悉前面文章中讨论的动态规划和 Monte Carlo 方法。

• 在第 2 部分中，我们探讨了动态规划 （DP） 方法，其中代理根据以前的计算迭代更新 V-/Q-函数及其策略，并用新的估计值替换它们。
• 在第 3 部分和第 4 部分中，我们介绍了蒙特卡洛 （MC） 方法，其中代理从通过采样事件获得的经验中学习。

我们将在本文中重点介绍的时间差分 （TD） 学习算法结合了这两个应用的原则：

• 与 DP 类似，TD 算法根据先前估计的信息更新估计值。如第 2 部分所示，可以在不更新其他状态值的情况下执行状态更新，这种技术称为引导，这是 DP 的一个关键功能。
• 与 MC 类似，TD 算法不需要环境动态的知识，因为它们也从经验中学习。

时间差分算法结合了动态规划和 Monte Carlo 方法的优点。

本文基于 Richard S. Sutton 和 Andrew G. Barto 撰写的《强化学习》一书的第6 章。我非常感谢为本书的出版做出贡献的作者们的努力。

二、算法思路

2.1 时间序列

        正如我们已经知道的，蒙特卡洛算法通过生成一个事件并观察每个访问的州的奖励来从经验中学习。状态更新仅在剧集结束后执行。

        时间差异算法的运行方式类似，唯一的关键区别是它们不会等到剧集结束才更新状态。相反，每个状态的更新都在访问状态的 n 个时间步长之后执行（n 是算法的参数）。在观察到的这 n 个时间步长中，算法会计算收到的奖励，并使用该信息来更新之前访问的状态。

在 n 个时间步长后执行状态更新的时间差分算法表示为 TD（n）。

最简单的 TD 版本在下一个时间步 （n = 1） 中执行更新，称为一步 TD。

在上一部分的结尾，我们介绍了常α MC 算法。事实证明，一步 TD 的伪代码几乎相同，除了 state update 之外，如下所示：

一步式 TD 学习伪代码。来源：强化学习。引言。第二版 |Richard S. Sutton 和 Andrew G. Barto

由于 TD 方法不会等到剧集结束并使用当前估计进行更新，因此它们被称为使用引导，就像 DP 算法一样。

更新公式中括号中的表达式称为 TD 错误：

TD 错误。来源：强化学习。引言。第二版 |Richard S. Sutton 和 Andrew G. Barto

在此等式中，γ 是折扣因子，其值介于 0 和 1 之间，并定义当前奖励与未来奖励相比的重要性权重。

TD 误差起着重要作用。正如我们稍后将看到的，TD 算法可以根据 TD 误差的形式进行调整。

2.2 举个例子

        乍一看，似乎不清楚仅使用来自当前转换奖励以及当前和下一个状态的状态值的信息如何确实有利于最佳策略搜索。如果我们看一个例子，会更容易理解。

        让我们想象一下著名的“美洲杯”足球锦标赛的简化版本，该赛事定期在南美洲举行。在我们的版本中，在每届美洲杯锦标赛中，我们球队都以相同的顺序面对 6 个对手。通过系统不是真实的，我们将省略复杂的细节，以便更好地理解示例。

        我们想创建一种算法，可以预测我们球队在一系列比赛后的总净胜球。下表显示了球队在最近一届美洲杯中获得的成绩。

        我们球队在美洲杯锦标赛中的比赛结果。最后一列是每场比赛后计算的累积净胜球。

        为了更好地深入研究数据，让我们可视化结果。初始算法估计值由下图中的黄线显示。获得的累积净胜球（表格最后一列）以黑色表示。

基于获得的结果的初始算法估计值（黄线）和累积目标差值（黑线）

粗略地说，我们的目标是根据最近的比赛结果，以更好地适应变化的方式更新黄线。为此，我们将比较常数α蒙特卡洛算法和一步 TD 算法如何应对这项任务。

三、Constant-α 蒙特卡洛

        蒙特卡洛方法计算剧集的累积奖励 G，在我们的例子中是所有比赛后的总净胜球 （+3）。然后，每个状态都会根据总剧集的奖励与当前状态的值之间的差额按比例更新。

        例如，让我们以第三场对阵秘鲁的比赛后的状态为例（我们将使用 α = 0.5 的学习率)

• 初始状态的值为 v = 1.2（对应于智利的黄点）。
• 累积奖励为 G = 3（黑色虚线）。
• 然后将两个值 G–v = 1.8 之间的差乘以 α = 0.5，得到更新步长等于 Δ = 0.9（红色箭头对应于智利）。
• 新值的状态等于 v = v + Δ = 1.2 + 0.9 = 2.1（对应于智利的红点）。

恒定α Monte Carlo 更新。红色透明箭头显示更新的方向。红色不透明箭头显示算法所做的更改 （α = 0.5）。

3.1 一步式 TD

对于示例演示，我们将采用第四场对阵智利的比赛后的总净胜球。

• 初始状态的值为 v[t] = 1.5（对应于智利的黄点）。
• 下一个州的值为 v[t+1]= 2.1（对应于厄瓜多尔的黄点）。
• 连续状态值之间的差异为 v[t+1]–v[t] = 0.6（对应于智利的黄色箭头）。
• 由于我们队以 5 ： 0 的比分战胜了厄瓜多尔，那么从状态 t 到 t + 1 的过渡奖励是 R = 5（对应于厄瓜多尔的黑色箭头）。
• TD 误差衡量获得的奖励与 state 值的差异相比大了多少。在我们的例子中，TD 误差 = R –（v[t+1]–v[t]） = 5–0.6 = 4.4（红色透明箭头对应于智利）。
• TD 误差乘以学习率 a = 0.5，得到更新步骤 β = 2.2（红色箭头对应于智利）。
• 新状态的值为 v[t] = v[t] + β = 1.5 + 2.2 = 3.7（对应于智利的红点）。

一步 TD 更新。红色透明箭头显示对阵智利的第 4 场比赛后的更新方向。红色不透明箭头显示算法所做的更改 （α = 0.5）。

3.2 比较

        收敛

        我们可以清楚地看到，蒙特卡洛算法将初始估计推向了剧集的回归。同时，one-step TD 使用引导并更新有关下一个状态的值及其即时奖励的每个估计值，这通常可以更快地适应任何变化。

例如，让我们获取第一个匹配之后的状态。我们知道，在第二场比赛中，我们队以 0 比 3 输给了阿根廷。但是，这两种算法对这种情况的反应完全不同：

• 尽管结果是负面的，但蒙特卡洛只考虑了所有比赛后的总净胜球，并将当前状态的值推高，这是不合逻辑的。
• 另一方面，一步 TD 考虑了获得的结果并立即向下更新状态的值。

此示例表明，从长远来看，一步 TD 执行更多的自适应更新，从而获得比 Monte Carlo 更好的收敛率。

该理论保证在 TD 方法中收敛到正确的值函数。

        更新

• Monte Carlo 要求结束剧集以最终进行状态更新。
• 一步 TD 允许在收到操作的奖励后立即更新状态。

        在许多情况下，这种更新方面是 TD 方法的一个显著优势，因为在实践中，剧集可能很长。在这种情况下，在 Monte Carlo 方法中，整个学习过程会延迟到一个情节结束。这就是 TD 算法学习得更快的原因。

四、算法变体

        在介绍了 TD 学习的基础知识之后，我们现在可以继续进行具体的算法实现。在以下部分中，我们将重点介绍三种最流行的 TD 变体：

• 萨尔萨
• Q-学习
• 预期 SARSA

4.1 Sarsa

        正如我们在第 3 部分的蒙特卡洛方法简介中学到的那样，要找到最佳策略，我们需要估计状态-动作函数 Q，而不是值函数 V。为了有效地实现这一点，我们通过将状态-动作对视为状态本身来调整问题表述。Sarsa 是一种基于此原理的算法。

为了执行状态更新，Sarsa 使用与上面定义的一步 TD 相同的公式，但这次它将变量替换为 Q-function 值：

Sarsa 更新规则。来源：强化学习。引言。第二版 |Richard S. Sutton 和 Andrew G. Barto

Sarsa 名称由其更新规则派生，该规则按顺序使用 5 个变量：（S[t]， A[t]， R[t + 1]， S[t + 1]， A[t + 1]）。

Sarsa 控制的工作原理类似于 Monte Carlo 控制，使用 ε 软或 ε 贪婪策略贪婪地更新 Q 函数的当前策略。

Sarsa 伪代码。来源：强化学习。引言。第二版 |Richard S. Sutton 和 Andrew G. Barto

Sarsa，因为它根据代理程序遵循的当前策略更新 Q 值。

4.2 Q-学习

        Q-learning 是强化学习中最流行的算法之一。它与 Sarsa 几乎相同，只是更新规则的微小变化：

Q-learning 更新规则。来源：强化学习。引言。第二版 |Richard S. Sutton 和 Andrew G. Barto

        唯一的区别是，我们根据导致该状态的最佳操作，将下一个 Q 值替换为下一个状态的最大 Q 值。在实践中，这种替换使得 Q-learning 在大多数问题中比 Sarsa 性能更高。

        同时，如果我们仔细观察公式，我们会注意到整个表达式都是从 Bellman 最优方程推导出来的。从这个角度来看，贝尔曼方程保证了 Q 值的迭代更新导致它们收敛到最优 Q 值。

Q-learning 是一种非策略算法：它根据可以做出的最佳决策来更新 Q 值，而无需考虑代理使用的行为策略。

4.3 预期 SARSA

预期 Sarsa 是一种源自 Q-learning 的算法。它不是使用最大 Q 值，而是根据在当前策略下执行每项操作的概率来计算下一个操作状态值的预期 Q 值。

预期的 Sarsa 更新规则。来源：强化学习。引言。第二版 |Richard S. Sutton 和 Andrew G. Barto

与普通 Sarsa 相比，预期 Sarsa 需要更多的计算，但作为回报，它在每个更新步骤中都会考虑更多信息。因此，预期 Sarsa 在选择下一个动作时减轻了过渡随机性的影响，尤其是在学习的初始阶段。因此，与普通 Sarsa 相比，预期 Sarsa 在更广泛的学习步长α具有更高的稳定性。

预期 Sarsa 是一种符合政策的方法，但可以通过简单地分别采用单独的行为和目标策略来生成和学习来适应非政策变体。

一步 TD 算法的比较。

五、最大化偏差

5.1 最大偏差

        在本文之前，我们一直在讨论一组算法，所有这些算法都在贪婪策略更新期间使用 maximization 运算符。但是，在实践中，所有值的 max 运算符会导致值的高估。在学习过程开始时，当 Q 值随机初始化时，此问题尤其会出现。因此，计算这些初始噪声值的最大值通常会导致向上偏差。

        例如，假设状态 S 中每个操作的真实 Q 值等于 Q（S， a） = 0。由于随机初始化，一些初始估计值将低于 0，而另一部分将高于 0。

• true 值的最大值为 0。
• 随机估计的最大值为正值（称为最大化偏差）。

与真实值相比，噪声估计的最大值往往向上偏斜。

5.2 例

        让我们考虑 Sutton 和 Barto 书中的一个例子，其中最大化偏差成为一个问题。我们正在处理下图所示的环境，其中 C 是初始状态，A 和 D 是终端状态。

        环境图。C 是初始代理的状态，A 和 D 是最终状态。图片由作者改编。来源：强化学习。引言。第二版 |Richard S. Sutton 和 Andrew G. Barto

        从 C 到 B 或 D 的转换奖励为 0。但是，从 B 转换为 A 会导致从均值为 -0.1 且方差为 1 的正态分布中采样的奖励。换句话说，此奖励平均为负值，但偶尔也可能为正值。

        基本上，在这种环境中，代理面临一个二元选择：是从 C 向左移动还是向右移动。在这两种情况下，预期回报都很明确：左侧轨迹导致预期回报 G = -0.1，而右侧路径产生 G = 0。显然，最佳策略包括始终向右走。

        另一方面，如果我们未能解决最大化偏差，那么代理很可能在学习过程中优先考虑左方向。为什么？根据正态分布计算的最大值将导致状态 B 中的 Q 值出现正更新。因此，当代理从 C 开始时，它会贪婪地选择移动到 B 而不是 D，后者的 Q 值保持为 0。

        为了更深入地了解为什么会发生这种情况，让我们使用以下参数进行几次计算：

• 学习率 α = 0.1
• 贴现率 γ = 0.9
• 所有初始 Q 值都设置为 0。

迭代 1

        在第一次迭代中，转到 B 和 D 的 Q 值都等于 0。让我们通过任意选择 B 来打破平局。然后，更新状态 （C， ←） 的 Q 值。为简单起见，我们假设定义分布的最大值是有限值 3。实际上，该值大于我们分布的 99% 百分位数：

状态 （C， ← 的 Q 值计算)

然后，代理移动到 A，采样奖励 R = -0.3。

状态 （B， ← 的 Q 值计算)

迭代 2

        代理到达最终状态 A 并开始新的剧集。从 C 开始，代理面临是转到 B 还是 D 的选择。在我们的条件下，使用 ε 贪婪策略，代理几乎会选择转到 B：

第一次迭代后，代理会贪婪地选择再次前往左侧

然后对状态 （C， ←） 执行类似的更新。因此，它的 Q 值只会变得更大：

状态 （C， ← 的 Q 值计算)

        尽管采样负奖励 R = -0.4 并进一步向下更新 B，但它并没有改变情况，因为最大值始终保持在 3。

状态 （B， ← 的 Q 值计算)

        第二次迭代终止，它只使代理的左侧方向比右侧方向更优先。因此，代理将继续从 C 向左移动，认为这是最佳选择，而实际上并非如此。

        基于贪婪的选择，代理将进一步优先考虑向左移动，即使预期回报低于向右移动。

六、双重学习

6.1 算法思路

        消除最大化偏差的最优雅的解决方案之一是使用双重学习算法，该算法对称地使用两个 Q 函数估计。

假设我们需要确定最大化操作及其相应的 Q 值来执行更新。双重学习方法的运作方式如下：

• 使用第一个函数 Q₁ 求最大化操作 a⁎ = argmaxₐQ₁（a）。
• 使用第二个函数 Q₂ 来估计所选操作 a⁎ 的值。

函数 Q₁ 和 Q₂ 也可以按相反的顺序使用。

双 Q-learning 伪代码。来源：强化学习。引言。第二版 |Richard S. Sutton 和 Andrew G. Barto

在双重学习中，每次迭代只更新一个估计 Q（而不是两个）。

第一个 Q 函数选择最佳操作，而第二个 Q 函数提供其无偏估计。

6.2 例

我们将看看如何将双重学习应用于 Q-learning 的示例。

迭代 1

为了说明双重学习是如何运作的，让我们考虑一个迷宫，代理在每次迭代期间可以向四个方向中的任何一个方向移动一步。我们的目标是使用双 Q-学习算法更新 Q-函数。我们将使用学习率 α = 0.1 和贴现率 γ = 0.9。

对于第一次迭代，代理从单元格 S = A2 开始，然后按照当前策略，向右移动一步到 S' = B2，奖励为 R = 2。

迷宫示例。代理从 A2 移动到 B2。

我们假设我们必须在上面所示的伪代码中使用第二个 update equation。让我们重写它：

Q₂ 函数更新方程

由于我们的代理移动到状态 S' = B2，因此我们需要使用其 Q 值。让我们看看当前状态-动作对的 Q 表，包括 B2：

状态（包括 B2）的 Q 表

我们需要找到一个 S' = B2 的动作，使 Q₁ 最大化，并最终将相应的 Q₂ 值用于相同的动作。

• 通过执行 ← 操作（q = 1.2，红色圆圈）可以获得最大 Q₁ 值。
• 操作←的相应 Q₂ 值为 q = 0.7（黄色圆圈）。

查找无偏 Q₂ 值

让我们用更简单的形式重写更新方程：

更新当前 Q₂ 状态-操作值的方程

假设初始估计值 Q₂（A2， →） = 0.5，我们可以插入值并执行更新：

Q 值计算

迭代 2

代理现在位于 B2 处，必须选择下一个操作。由于我们正在处理两个 Q-函数，因此我们必须找到它们的和：

选择 Q₁ 和 Q₂ 之和的最大值

根据我们的策略类型，我们必须从分配中对下一个操作进行采样。例如，如果我们使用 ε = 0.08 的 ε贪婪策略，则操作分配将具有以下形式：

操作分布 （ε = 0.08)

我们假设，以 94% 的概率，我们已经对 ↑ 操作进行了采样。这意味着代理将移动到 S' = B3 单元格旁边。它收到的奖励是 R = -3。

对于此迭代，我们假设我们已经对 Q-Function 的第一个更新方程进行了采样。让我们来分析一下：

Q₁ 函数更新方程

我们需要知道与 B3 对应的所有操作的 Q 值。他们是：

状态（包括 B3）的 Q 表

由于这次我们使用第一个更新方程，我们取最大 Q₂ 值（红色圆圈）并使用相应的 Q₁ 值（黄色圆圈）。然后我们可以将方程改写成简化的形式：

更新当前 Q₁ 状态-操作值的方程

在进行所有值替换后，我们可以计算最终结果：

Q₁ 值计算

我们研究了双 Q-learning 的例子，它减轻了 Q-learning 算法中的最大化偏差。这种双重学习方法也可以扩展到 Sarsa 和 Expected Sarsa 算法。

与其在每次迭代中选择使用 p = 0.5 概率的更新方程，不如调整双重学习以在两个方程之间迭代交替。

七、结论

        尽管时间差分方法很简单，但它们是当今强化学习中使用最广泛的技术之一。同样有趣的是，它也被广泛应用于其他预测问题，例如时间序列分析、股票预测或天气预报。

        到目前为止，我们只讨论了 n = 1 时的 TD 学习的一个特定情况。正如我们将在会后文中看到的那样，在某些情况下将 n 设置为更高的值可能是有益的。