当前位置：首页 > news >正文

时间差分学习：结合动态规划和蒙特卡洛方法进行强化学习

news 2026/5/12 22:21:02

原文：towardsdatascience.com/temporal-difference-learning-combining-dynamic-programming-and-monte-carlo-methods-for-e0c2f0829a51

我们继续深入探讨 Sutton 的书籍《强化学习：入门》[1]，并在本文中介绍时间差分（TD）学习，这是该书的第六章。

TD 学习可以看作是动态规划（DP）和蒙特卡洛（MC）方法的结合，这些方法我们在前两篇文章中已经介绍过，并在强化学习（RL）领域标记了一个重要的里程碑——结合上述方法的优势：TD 学习不需要模型，仅从经验中学习，类似于 MC，但也“自举”——使用先前建立的估计，类似于 DP。

https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/eb52f35560f6ca7920f5aa29ea850512.png

由Brooke Campbell在Unsplash上的照片

在这里，我们将从理论角度介绍这一系列方法，同时展示相关的实际算法，例如 Q 学习——附带 Python 代码。像往常一样，所有代码都可以在GitHub上找到。

我们从介绍和动机开始，然后从预测问题开始——类似于之前的文章。然后，我们深入理论，讨论 TD 学习找到的解决方案。随后，我们转向控制问题，并展示了一系列基本算法：Sarsa、Q 学习、期望 Sarsa 和双 Q 学习。我们以一些实用技巧结束本文。

时间差分学习简介

如前所述，TD 方法可以看作是 DP 和 MC 的结合。让我们快速回顾一下：DP 方法需要一个模型，并迭代地试图改进其对价值函数的估计。为此，他们将 Bellman 方程转化为一个更新规则，并计算：

<…/Images/8b029d64664ae42498d64f5c0eec4d14.png>

来自[1]的图片

也就是说，他们使用先前估计的价值函数作为更新估计的起点——对所有动作及其相应的回报以及先前价值估计进行平均——他们进行“自举”。

相反，MC 方法可以仅从经验中学习，这是一个惊人的认识。为了做到这一点，它们会播放完整的剧集，然后通过“简单地”平均观察到的回报来估计一个价值函数：

图片来自[1]

TD 方法似乎结合了两个世界的优点：它们自举，即可以完全增量实现——但不需要环境模型，也可以仅从经验中学习。一个简单的更新规则可以是：

<…/Images/7c754ef40919009eef8fde5bd03eaf5e.png>

图片来自[1]

为了做到这一点，我们可以采样遵循某些策略的剧集，并在每次观察到的回报后，将我们的价值估计更新为先前估计和我们现在认为更准确的价值的加权总和：观察到的奖励加上下一个状态的估计价值。

从现在开始，我们将多次遇到右边的这个量，它是TD 误差：

<…/Images/315bae78e659fba9255e8d9264bfe88c.png>

图片来自[1]

TD 预测

让我们将这些组合成一个初步的预测算法，称为TD(0)：

图片来自[1]

这应该正式化我们在上一段中介绍的内容：目标是估计策略π的价值函数。为此，我们生成遵循此策略的剧集，并使用上面介绍的计算公式更新价值估计——直到我们对估计的准确性满意（例如，直到收敛）。

上述方法被称为 TD(0)——或一步 TD——因为我们只进行了一步的环境操作，并立即更新我们的价值估计。在本书的后面，Sutton 介绍了n 步 TD和TD(λ)，它们无缝地统一了 DP 和 MC 方法。

为了总结本节，让我们重申 TD 方法的优势。首先，假设可以访问环境的（完整）模型，这是 DP 所要求的，这是一个强烈的假设。因此，仅从经验中学习是很好的。然而，像 MC 那样等待完整剧集完成，对算法来说是一个沉重的负担。想想一些长游戏，比如围棋——完成每一场比赛的结束几乎是不可能的——这解释了自举的优势。

TD(0)的收敛性

现在我们更详细地分析一下 TD——特别是回答以下问题：它是否收敛？如果是，收敛到哪个解？第一个问题我们不会在这里详细回答，而是直接给出答案：是的——TD 方法收敛，并且它们收敛到一个令人满意的解。我们将现在描述这个解。令人惊讶的是，找到的解与例如 MC 方法找到的解不同。

对于这一点，假设我们有一些固定的数据集，我们从这些数据集中采样——然后我们迭代地将这些数据批量输入到我们的算法中，直到收敛——我们称这种设置为“批量设置”（对于非批量的 TD(0)，解决方案并不完全相同——但我们优化的是相同的方向）。

我们将使用[1]中给出的例子来推导这一点。假设，你观察到了以下来自某个（未知）MDP 的场景：

<…/Images/a33d8cfb01261cbdf3693f90f852680f.png>

图像来自[1]

这些序列被写成状态-奖励对，即第一个场景从状态 A 开始，经过奖励为 0 的转换到 B，然后以奖励为 0 结束。使用 MC 方法后，A 的状态估计会是什么？我们只观察到 A 一次，奖励为 0——因此，值估计将是 0。

然而，你也会得出这个结论吗？也许不会。你可能已经在你的脑海中构建了以下图表，想象中的 MDP：

<…/Images/9b4e4e9d7a8b38d3ba08f52bc85506eb.png>

图像来自[1]

从我们看到的数据来看，A 总是先于 B。而且，由于 B 的估计值为 3/4（6/8），不考虑折现，我们也应该估计 A 的值为 3/4。这正是 TD(0)所做的事情。

原因是 MC 找到的解决方案是在训练集上最小化（平方）误差的解决方案——并且对于 A 预测 0 是给定这个指标和数据我们能做的最好的。另一方面，TD 学习找到最可能生成这些数据的马尔可夫过程参数的最大似然估计——那就是上面的图表。这也可能解释了为什么 TD(0)（通常）收敛得更快，并且能找到更好的解决方案。

TD 控制

在阅读了 TD 学习的基础知识以及一些理论性质（预测问题）之后，让我们转向控制问题，即实际上使用这些方法找到策略。在本节中，我们将介绍四种方法，其中包括著名的 Q 学习算法。

在我们开始之前，有一些一般性的评论——这些评论在我们对 MC 方法的讨论中是共通的，并且在之前的文章上一篇文章中更详细地介绍过：

对于以下算法，我们不是估计值函数，而是转向估计状态-动作对的价值，这些定义了动作值函数。
对于涉及采样的方法，至关重要的是，所有状态-动作对都要持续访问。为此，我们可以例如使用ε-greedy 策略来处理策略方法，或者使用行为策略持续探索的离策略方法。

Sarsa

我们首先考虑的是 Sarsa，这是在这个领域相对著名且基础的一个算法。与 MC 方法类似，我们玩完整的场景——但现在我们在每个时间步更新值估计（TD 学习），而不是只在每个场景后更新。

如前所述，我们并不处理值函数，而是处理动作值函数。因此，上述更新规则可以转化为：

<…/Images/1f8ddce9ce73f196a625dad93c6ed92b.png>

图像来自[1]

这个算法的名字来源于描述两个连续时间步的 quintuple：

<…/Images/a5654e9b0c8c1a0d0bccf9f2dd1f017e.png>

图片来自[1]

所有这些值都在更新步骤中使用。

让我们看看伪代码：

<…/Images/4b2737232ddb77dbd6ba5c90b97ed00e.png>

图片来自[1]

在上述介绍之后，它应该读起来很自然，并且也可以直接翻译成 Python 代码：

importrandomfromgym_utilsimportget_observation_action_spaceimportnumpyasnpfromenvimportParametrizedEnv ALPHA=0.1NUM_STEPS=1000defget_eps_greedy_action(q_values:np.ndarray,eps:float=0.05)->np.integer:ifrandom.uniform(0,1)<epsornp.all(q_values==q_values[0]):returnnp.random.choice([aforainrange(len(q_values))])else:returnnp.argmax(q_values)defsarsa(env:ParametrizedEnv)->np.ndarray:observation_space,action_space=get_observation_action_space(env)Q=np.zeros((observation_space.n,action_space.n))for_inrange(NUM_STEPS):observation,_=env.env.reset()terminated=truncated=Falseaction=get_eps_greedy_action(Q[observation])whilenotterminatedandnottruncated:observation_new,reward,terminated,truncated,_=env.env.step(action)action_new=get_eps_greedy_action(Q[observation_new])q_next=Q[observation_new,action_new]ifnotterminatedelse0Q[observation,action]=Q[observation,action]+ALPHA*(reward+env.gamma*q_next-Q[observation,action])observation=observation_new action=action_newreturnnp.array([np.argmax(Q[s])forsinrange(observation_space.n)])

我们只需要讨论几件事情（有些我们将在文章末尾的“高级”部分更详细地讨论）：

与关于 MC 方法的帖子类似，我们初始化 Q 表为零，然后在get_eps_greedy_action中随机打破平局。Sutton 这样做是随机的，但要求终端状态 Q 设置为 0。此外，在更新步骤中，我们将终端状态的 Q 值设置为 0。

并且与之前的帖子类似，我们可以在那里定义的框架中运行这个算法：

python grid_world.py--method=sarsa

这将生成一个网格世界环境，并使用 Sarsa 找到通过它的方法。

Q-Learning

接下来我们来看 Q-learning，这真正可以被认为是 RL 领域的一个突破。它是一个离策略算法，简化了分析和收敛证明，并且也导致了将 RL 算法应用于具有深度神经网络的“现实世界”问题的突破性成果[2]。

让我们看看更新规则：

<…/Images/a18da2f8df1753479e860f66fce34dc9.png>

图片来自[1]

当将此与 Sarsa 进行比较时，我们发现现在我们不再采取实际执行的转换，而是使用后续状态的最大的 Q 值。也就是说：我们使用不同的策略来更新我们的估计（一个采取最大动作的贪婪策略）而不是生成剧集（这是我们默认的ε-贪婪策略），这解释了为什么 Q-learning 被认为是离策略的，并回答了 Sutton 书中练习 6.11 的问题。

关于伪代码，与 Sarsa 没有太大区别：

<…/Images/09b54e9ebd301724daddd4695918d7f8.png>

图片来自[1]

对于 Python 实现也是一样：

defq(env):observation_space,action_space=get_observation_action_space(env)Q=np.zeros((observation_space.n,action_space.n))for_inrange(NUM_STEPS):observation,_=env.env.reset()terminated=truncated=Falsewhilenotterminatedandnottruncated:action=get_eps_greedy_action(Q[observation])observation_new,reward,terminated,truncated,_=env.env.step(action)Q[observation,action]=Q[observation,action]+ALPHA*(reward+env.gamma*np.max(Q[observation_new])-Q[observation,action])observation=observation_newreturnnp.array([np.argmax(Q[s])forsinrange(env.env.observation_space.n)])

在继续之前，让我们花一点时间比较 Sarsa 和 Q-learning，并按照 Sutton 提出的有趣例子来做。目标是找到以下网格世界环境中的路径（与我们的玩具问题非常相似）：

<…/Images/ce6049ec503cdbbb07ad8c9875e31f84.png>

图片来自[1]

我们必须尽可能快地从（S）开始到（G）目标，同时不跌落悬崖。Q-learning 在更新时使用最大操作，因此学习的 Q 函数更喜欢直接、最优的路径。然而，我们的动作选择是ε-贪婪，这意味着如果选择了这样的随机动作，我们可能会跌落悬崖。相比之下，Sarsa 由于使用自己的策略来更新价值估计，隐式地考虑了这种动作选择。确实，Sarsa 收集到的奖励高于 Q-learning 收集到的奖励：

<…/Images/019c17eef7eab05e083deaf3275d648d.png>

图片来自[1]

但是需要注意的是，总的来说，Q-learning 的使用范围更广，而且 Sarsa 不太可能成功部署到硬真实世界问题中——离线学习的承诺和优势似乎太好了。

接下来，我们将考虑两个更高级的算法，这些算法基于之前介绍过的算法。

预期 Sarsa

预期 Sarsa 基本上是在 Sarsa 的基础上增加了一个期望值。让我们回顾一下 Sarsa 的更新规则：

<…/Images/1f8ddce9ce73f196a625dad93c6ed92b.png>

图片来自[1]

现在，我们将步骤+1 的 Q 值重写以考虑当前策略，并形成对该期望的估计：

<…/Images/0630cd7dc282e5d61ead838266a268c9.png>

图片来自[1]

也就是说，我们不是简单地取状态S_{t+1}和动作A_{t+1}，就像它们在剧集中所观察到的，我们改变A_{t+1}，并按照当前策略下结果的可能性来权衡结果（使用 softmax 而不是 argmax）。

Sutton 没有列出任何伪代码，所以我们直接进入 Python 版本：

defexpected_sarsa(env:ParametrizedEnv)->np.ndarray:observation_space,action_space=get_observation_action_space(env)Q=np.zeros((observation_space.n,action_space.n))def_get_action_prob(Q:np.ndarray)->float:return(Q[observation_new,a]/sum(Q[observation_new,:])ifsum(Q[observation_new,:])else1)for_inrange(NUM_STEPS):observation,_=env.env.reset()terminated=truncated=Falseaction=get_eps_greedy_action(Q[observation])whilenotterminatedandnottruncated:observation_new,reward,terminated,truncated,_=env.env.step(action)action_new=get_eps_greedy_action(Q[observation_new])updated_q_value=Q[observation,action]+ALPHA*(reward-Q[observation,action])forainrange(action_space.n):updated_q_value+=ALPHA*_get_action_prob(Q)*Q[observation_new,a]Q[observation,action]=updated_q_value observation=observation_new action=action_newreturnnp.array([np.argmax(Q[s])forsinrange(observation_space.n)])

预期 Sarsa 消除了 Sarsa 中来自第二个时间步动作选择的方差，并且实际上在给定的相同经验下通常比 Sarsa 表现更好。但说实话，我不确定（预期）Sarsa 的使用范围和知名度有多广，因为 Q-learning 更受欢迎和普及——如上所述。

双重 Q-Learning

但现在我们来到了另一个基本算法/RL 中的基本概念：双重 Q-learning，它解决了最大化偏差的问题。

许多强化学习算法使用某种最大化方法——例如，在之前介绍的 Q-learning 的更新步骤中，我们使用 Q 值的最大运算——并且特别地，使用期望值的最大值作为最大值的估计——这可能导致显著的正面偏差。

Sutton 给出了一些很好的直觉和例子来说明为什么是这样：想象有几个动作，它们的真实值q(s, a)都是 0——但我们的期望Q(s, a)是从具有均值 0 的分布中取出的，表现出正负值。因此，估计的最大值总是大于 0。让我们用一个实际例子来演示这一点。考虑以下 MDP：

<…/Images/8ed47de4045a5833dfab2294a62f12d8.png>

图片来自[1]

我们总是从状态 A 开始，可以选择向右移动获得奖励 0 到终端状态，或者向左移动到 B。从 B 我们可以继续向左移动到另一个终端状态，但可以通过选择几个动作之一来实现。它们对应的奖励是具有负均值和方差 1 的正态分布——即：我们将遇到最大化偏差问题。实际上，我们可以通过将 Q-learning 部署到这个问题来观察到这一点：

<…/Images/7a3ded481faa39d8e010e940337cf96b.png>

图片来自[1]

最好的行动总是向右走，因为平均来看，这能得到最少的负面奖励。然而，正如我们从图中可以看到的，只要价值估计还没有很好地收敛，Q-learning 往往会因为最大化偏差而向左走。

图表实际上还显示了一个第二种算法，双重 Q-learning——我们将在本节中介绍的这个算法——正如我们所看到的，这个算法的表现显著更好。

所以让我们来解决这个问题——特别是介绍上述双重 Q-learning 算法。问题源于我们使用相同的估计器来估计我们感兴趣的度量（价值函数），以及选择这个度量的最大值。如果我们能够划分我们的数据集，学习两个估计器——并从其中一个获得价值估计，而使用另一个进行最大操作——相关性就会降低，问题就会得到缓解。这就是“双重学习”的概念，这正是双重 Q-learning 所做的事情。

更新规则如下：

<…/Images/664bdae0487d13320ff41da0a34f0878.png>

Image from [1]

让我们比较一下标准的 Q-learning：

<…/Images/a18da2f8df1753479e860f66fce34dc9.png>

Image from [1]

正如我们所看到的，我们引入了一个第二个 Q 值估计器，并使用它的估计 Q 值作为更新目标，而价值最大化的行动则来自第一个 Q 值估计器。

我们如何训练这个？嗯，在每一步我们只是简单地抛硬币，并根据结果更新Q_1或Q_2。对于部署，我们然后可以使用Q_1或Q_2，或者两者的组合。

Sutton 列出了以下伪代码：

<…/Images/d2f178a7cc142fd546294153313831ea.png>

Image from [1]

在 Python 中，这看起来如下——不应该有任何惊喜：

defdouble_q(env):observation_space,action_space=get_observation_action_space(env)Q_1=np.zeros((observation_space.n,action_space.n))Q_2=np.zeros((observation_space.n,action_space.n))for_inrange(NUM_STEPS):observation,_=env.env.reset()terminated=truncated=Falsewhilenotterminatedandnottruncated:action=get_eps_greedy_action(Q_1[observation]+Q_2[observation])observation_new,reward,terminated,truncated,_=env.env.step(action)ifrandom.randint(0,100)<50:Q_1[observation,action]=Q_1[observation,action]+ALPHA*(reward+env.gamma*Q_2[observation_new,np.argmax(Q_1[observation_new])]-Q_1[observation,action])else:Q_2[observation,action]=Q_2[observation,action]+ALPHA*(reward+env.gamma*Q_1[observation_new,np.argmax(Q_2[observation_new])]-Q_2[observation,action])observation=observation_newreturnnp.array([np.argmax(Q_1[s])forsinrange(env.env.observation_space.n)])

讨论和高级技术

让我们以关于实现 RL 算法的一般技巧的讨论来结束这篇文章。在这个帖子系列中，我们主要致力于介绍基本算法，而不是用太多“花哨”的技巧来优化它们的性能——这就是为什么它们在上文中被省略，但在这里进行了讨论。

第一个是 [[ε](https://www.ascii-code.com/character/%CE%B5)](https://www.ascii-code.com/character/%CE%B5)-decay]：在我们的实验中，我们一直在算法运行期间保持ε为常数——而在实践中，人们通常会采用一种随着时间的推移衰减ε的策略。这样，最初我们会进行更多的探索，而后来我们会收敛到最优策略（谁会想要使用一个有 5%概率尝试随机动作的机器人呢？）。

接下来，我想讨论 Q 估计的初始化。Sutton 建议随机实现，但对于终端状态s，将Q(s, :)设为 0。后一部分似乎是一个相当强的假设，考虑到对终端状态的了解——而且说实话，我不确定这是如何实现的。此外，我经常看到初始化为 0 或小值作为推荐——只是为了不过度估计坏状态。这也得到了我在简单环境网格世界上的实验的证实，其中随机初始化不会给出好的结果，或者需要更多的步骤。因此，我选择了零初始化，就像在关于 MC 方法的帖子中已经做的那样。请注意，这需要在动作选择中随机打破平局——当初始所有 Q 估计都是 0 时，argmax 总是会返回相同的（第一个）元素——因此在这种情况下，我们返回一个随机动作。

然而，应该注意的是，RL 在很大程度上可以感觉像是一门没有对错的经验科学——实验通常有很大的变异性，需要找出什么有效，什么无效。

最后，在第一个介绍的算法 Sarsa 中，我提到了在更新步骤中将终端状态的 Q 值设为 0（即与上面讨论的 Sutton 有相似意图，但时间不同——在更新期间）。这也是一种推荐的做法，但在伪代码中并未体现。我在调试 Sarsa 时引入了它（容易出错），希望因此提高性能。最终，错误在其他地方，对于这个简单的环境来说这并不需要——因此我在后续的算法中省略了它。