原文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]图片来自[1]TD 方法似乎结合了两个世界的优点它们自举即可以完全增量实现——但不需要环境模型也可以仅从经验中学习。一个简单的更新规则可以是…/Images/7c754ef40919009eef8fde5bd03eaf5e.png图片来自[1]为了做到这一点我们可以采样遵循某些策略的剧集并在每次观察到的回报后将我们的价值估计更新为先前估计和我们现在认为更准确的价值的加权总和观察到的奖励加上下一个状态的估计价值。从现在开始我们将多次遇到右边的这个量它是TD 误差…/Images/315bae78e659fba9255e8d9264bfe88c.png图片来自[1]TD 预测让我们将这些组合成一个初步的预测算法称为TD(0)图片来自[1]图片来自[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/46/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 ALPHA0.1NUM_STEPS1000defget_eps_greedy_action(q_values:np.ndarray,eps:float0.05)-np.integer:ifrandom.uniform(0,1)epsornp.all(q_valuesq_values[0]):returnnp.random.choice([aforainrange(len(q_values))])else:returnnp.argmax(q_values)defsarsa(env:ParametrizedEnv)-np.ndarray:observation_space,action_spaceget_observation_action_space(env)Qnp.zeros((observation_space.n,action_space.n))for_inrange(NUM_STEPS):observation,_env.env.reset()terminatedtruncatedFalseactionget_eps_greedy_action(Q[observation])whilenotterminatedandnottruncated:observation_new,reward,terminated,truncated,_env.env.step(action)action_newget_eps_greedy_action(Q[observation_new])q_nextQ[observation_new,action_new]ifnotterminatedelse0Q[observation,action]Q[observation,action]ALPHA*(rewardenv.gamma*q_next-Q[observation,action])observationobservation_new actionaction_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--methodsarsa这将生成一个网格世界环境并使用 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_spaceget_observation_action_space(env)Qnp.zeros((observation_space.n,action_space.n))for_inrange(NUM_STEPS):observation,_env.env.reset()terminatedtruncatedFalsewhilenotterminatedandnottruncated:actionget_eps_greedy_action(Q[observation])observation_new,reward,terminated,truncated,_env.env.step(action)Q[observation,action]Q[observation,action]ALPHA*(rewardenv.gamma*np.max(Q[observation_new])-Q[observation,action])observationobservation_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_{t1}和动作A_{t1}就像它们在剧集中所观察到的我们改变A_{t1}并按照当前策略下结果的可能性来权衡结果使用 softmax 而不是 argmax。Sutton 没有列出任何伪代码所以我们直接进入 Python 版本defexpected_sarsa(env:ParametrizedEnv)-np.ndarray:observation_space,action_spaceget_observation_action_space(env)Qnp.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()terminatedtruncatedFalseactionget_eps_greedy_action(Q[observation])whilenotterminatedandnottruncated:observation_new,reward,terminated,truncated,_env.env.step(action)action_newget_eps_greedy_action(Q[observation_new])updated_q_valueQ[observation,action]ALPHA*(reward-Q[observation,action])forainrange(action_space.n):updated_q_valueALPHA*_get_action_prob(Q)*Q[observation_new,a]Q[observation,action]updated_q_value observationobservation_new actionaction_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.pngImage from [1]让我们比较一下标准的 Q-learning…/Images/a18da2f8df1753479e860f66fce34dc9.pngImage from [1]正如我们所看到的我们引入了一个第二个 Q 值估计器并使用它的估计 Q 值作为更新目标而价值最大化的行动则来自第一个 Q 值估计器。我们如何训练这个嗯在每一步我们只是简单地抛硬币并根据结果更新Q_1或Q_2。对于部署我们然后可以使用Q_1或Q_2或者两者的组合。Sutton 列出了以下伪代码…/Images/d2f178a7cc142fd546294153313831ea.pngImage from [1]在 Python 中这看起来如下——不应该有任何惊喜defdouble_q(env):observation_space,action_spaceget_observation_action_space(env)Q_1np.zeros((observation_space.n,action_space.n))Q_2np.zeros((observation_space.n,action_space.n))for_inrange(NUM_STEPS):observation,_env.env.reset()terminatedtruncatedFalsewhilenotterminatedandnottruncated:actionget_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*(rewardenv.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*(rewardenv.gamma*Q_1[observation_new,np.argmax(Q_2[observation_new])]-Q_2[observation,action])observationobservation_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 时引入了它容易出错希望因此提高性能。最终错误在其他地方对于这个简单的环境来说这并不需要——因此我在后续的算法中省略了它。结论在这篇帖子中我们介绍了时间差分TD学习它可以被视为动态规划DP和蒙特卡洛方法MC的结合——结合两者的优点TD 方法不需要模型但仍然能够在不需要等待完整剧集完成的情况下进行自举。我们从理论介绍和预测问题开始展示了 TD 学习学习底层 MDP 并最小化由此产生的误差相对于 MC 方法找到的解决方案在给定的 rollouts 数据集上最小化经验误差的收敛性。然后我们深入探讨了控制问题并介绍了四种算法Sarsa、Q-learning、预期 Sarsa 和双 Q-learning。Q-learning 可能是 RL 历史上最具影响力的算法之一而双 Q-learning 则在此基础上避免了常见的最大化偏差。对于所有方法我们都展示了伪代码以及完整的 Python 代码所有这些都可以在GitHub上找到。感谢阅读如果您喜欢这篇帖子我将非常感激一些点赞和关注本系列的其他文章第一部分强化学习简介及解决多臂老虎机问题第二部分介绍马尔可夫决策过程、设置 Gymnasium 环境和通过动态规划方法解决它们第三部分解决强化学习问题的蒙特卡洛方法参考文献[1]incompleteideas.net/book/RLbook2020.pdf[2]arxiv.org/abs/1312.5602