原文towardsdatascience.com/reinforcement-learning-part-5-temporal-difference-learning-cacf7854fe0chttps://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/d06ac84afe0e1e525667e94eace4989f.png简介强化学习是机器学习的一个领域它引入了智能体在复杂环境中学习最优策略的概念。智能体根据环境的状态从其行为中学习这些行为导致奖励。强化学习是一个具有挑战性的主题与机器学习的其他领域有显著差异。强化学习的显著之处在于相同的算法可以用来使智能体适应完全不同、未知和复杂的环境。注意. 要完全理解本文中包含的概念强烈建议熟悉之前文章中讨论的动态规划和蒙特卡洛方法。强化学习第二部分策略评估和改进强化学习第三部分蒙特卡洛方法关于本文在第二部分中我们探讨了**动态规划DP**方法其中智能体基于之前的计算迭代更新 V- / Q 函数及其策略用新的估计值替换它们。在第三部分和第四部分中我们介绍了蒙特卡洛MC方法其中智能体通过采样回合获得的经验进行学习。时间差分TD学习算法我们将在这篇文章中重点关注结合了这两种方法的原理与 DP 类似TD 算法根据先前估计的信息更新估计值。正如第二部分所看到的可以在不更新其他状态值的情况下执行状态更新这种技术称为自举这是 DP 的一个关键特征。与 MC 类似TD 算法不需要了解环境的动态因为它们也通过经验进行学习。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/c6ad2514ea3bd2e69c5908353a454862.png时间差分算法结合了动态规划和蒙特卡洛方法的优势。本文基于由理查德·S·萨顿和安德鲁·G·巴特罗撰写的书籍强化学习的第六章。我非常感谢作者们的努力他们为这本书的出版做出了贡献。理念如我们所知蒙特卡洛算法通过生成一个场景并观察每个访问状态下的奖励来从经验中学习。状态更新仅在场景结束后进行。时间差分算法操作类似唯一的关键区别是它们不需要等到场景结束时才更新状态。相反每个状态的更新都是在状态被访问后的n个时间步之后进行的n是算法的参数。在这观察的n个时间步中算法计算收到的奖励并使用该信息来更新之前访问过的状态。执行 n 个时间步后的状态更新的时间差分算法表示为 TD(n)。最简单的 TD 版本在下一个时间步进行更新n 1称为一步 TD。在上一部分的结尾我们介绍了常量α蒙特卡洛算法。结果发现一步 TD 的伪代码几乎完全相同除了状态更新如下所示https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/8804c6fcf2c4add53842434cffec4e3f.png一步 TD 学习伪代码。来源强化学习。入门。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗由于 TD 方法不需要等到场景结束而是使用当前估计进行更新因此它们被称为使用自举就像 DP 算法一样。更新公式中的括号内的表达式称为TD 误差https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/423c0f7f727b7cf3abda84c35f791bdd.pngTD 误差。来源强化学习。入门。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗在这个公式中γ是折现因子其取值在 0 和 1 之间并定义了当前奖励相对于未来奖励的重要性权重。TD 误差起着重要作用。正如我们稍后将会看到的TD 算法可以根据 TD 误差的形式进行适应。示例初看起来使用仅来自当前转换奖励以及当前和下一个状态值的州值的信息如何真正有益于最优策略搜索可能不清楚。如果我们看一下一个例子可能会更容易理解。让我们想象一个简化的版本即著名的“南美杯”足球锦标赛它定期在南美洲举行。在我们的版本中在每一届南美杯锦标赛中我们的球队以相同的顺序面对 6 个对手。虽然这个系统并非真实但我们将省略复杂的细节以便更好地理解这个例子。我们希望创建一个算法该算法可以预测一系列比赛后我们球队的总进球差。下表显示了球队在最近一届南美杯中获得的结果。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/830faee904c2db0fc207fcb1941db635.png南美杯锦标赛中我们球队的比赛结果。最后一列是每场比赛后计算的累积进球差。为了更好地深入数据让我们可视化结果。下面的图表中显示了初始算法估计黄色线。获得的累积进球差最后表列用黑色描绘。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/1e8fe2fb42f5e347aef2f5eb066dcca7.png基于获得结果的初始算法估计黄色线和累积进球差黑色线大致来说我们的目标是更新黄色线以便更好地适应基于最近比赛结果的变化。为此我们将比较恒定-α蒙特卡洛和一步 TD 算法如何处理这项任务。恒定-α蒙特卡洛蒙特卡洛方法计算整个事件的累积奖励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(红色点对应智利)。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/910eeaef7839c24ea88c288934f97b3e.png恒定-α蒙特卡洛更新。红色透明箭头显示更新的方向。红色不透明箭头显示算法α 0.5所做的更改。一步 TD对于示例演示我们将取与智利的第四场比赛后的总进球差。初始状态的价值是v[t] 1.5(黄色点对应智利)。下一个状态的价值是v[t1] 2.1(对应厄瓜多尔的黄色点)。连续状态值之间的差异是v[t1]–v[t] 0.6(对应智利的黄色箭头)。由于我们的队伍以 5 : 0 战胜了厄瓜多尔因此从状态t到t 1的过渡奖励是R 5(对应厄瓜多尔的黑色箭头)。TD 误差衡量的是获得的奖励与状态值差异相比有多大。在我们的例子中TD 误差 R –(v[t1]–v[t]) 5–0.6 4.4(对应智利的红色透明箭头)。TD 误差乘以学习率a 0.5导致更新步骤β 2.2(对应智利的红色箭头)。新状态的价值是v[t] v[t] β 1.5 2.2 3.7(对应智利的红色点)。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/1b6336430b6ab0dbf9d350652bedca6b.png一步 TD 更新。红色透明箭头显示了在第四场对阵智利的比赛后的更新方向。红色不透明箭头显示了算法α 0.5所做的更改。比较收敛性我们可以清楚地看到蒙特卡洛算法将初始估计推向剧集的回报。同时一步 TD 使用自举并更新每个估计值以反映下一个状态的价值及其即时奖励这通常使其更快地适应任何变化。例如让我们看看第一场比赛后的状态。我们知道在第二场比赛中我们的队伍以 0 : 3 输给了阿根廷。然而两种算法对此场景的反应完全不同尽管结果负面蒙特卡洛方法只考虑所有比赛后的整体得分差并将当前状态的价值向上推这并不合理。一步 TD另一方面考虑了获得的结果并立即更新状态的价值。这个例子表明从长远来看一步 TD 执行更适应的更新比蒙特卡洛方法具有更好的收敛速度。理论保证了 TD 方法收敛到正确的值函数。更新蒙特卡洛方法需要将剧集结束才能最终进行状态更新。一步 TD 允许在接收到动作奖励后立即更新状态。在许多情况下这种更新方面是 TD 方法的一个显著优势因为在实践中剧集可以非常长。在这种情况下在蒙特卡洛方法中整个学习过程被延迟到剧集的结束。这就是为什么TD 算法学习更快。算法变体在掌握 TD 学习的基础知识之后我们现在可以继续具体算法的实现。在接下来的章节中我们将重点关注三种最流行的 TD 变体SarsaQ-learning预期 SarsaSarsa正如我们在第三部分中关于蒙特卡洛方法的介绍中学到的为了找到一个最优策略我们需要估计状态动作函数 Q 而不是值函数 V。为了有效地完成这项任务我们通过将状态动作对视为状态本身来调整问题表述。Sarsa是一种基于此原理的算法。为了执行状态更新Sarsa 使用与上面定义的单一步 TD 相同的公式但这次它用 Q 函数值替换了变量https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/41e2efb26df08e42a24673077362e287.pngSarsa 更新规则。来源强化学习。引言。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗Sarsa 的名字来源于其更新规则该规则按以下顺序使用 5 个变量(S[t]A[t]R[t 1]S[t 1]A[t 1])。Sarsa 控制操作类似于蒙特卡洛控制使用ε-软或ε-贪婪策略贪婪地根据 Q 函数更新当前策略。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/a7b7b4b71787f4bfe2c135c180b95b59.pngSarsa 伪代码。来源强化学习。引言。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗Sarsa 是一种在策略方法因为它根据智能体遵循的当前策略来更新 Q 值。Q-learningQ-learning是强化学习中应用最广泛的算法之一。它几乎与 Sarsa 相同只是在更新规则上略有不同https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/bfb1048da980f99a2cbaf6ab6e6fd791.pngQ-learning 更新规则。来源强化学习。引言。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗唯一的区别是我们将下一个 Q 值替换为基于导致该状态的优化动作的最大 Q 值。在实践中这种替换使得 Q-learning 在大多数问题中比 Sarsa 更高效。同时如果我们仔细观察公式我们可以注意到整个表达式是从 Bellman 最优方程推导出来的。从这个角度来看Bellman 方程保证了 Q 值的迭代更新将收敛到最优 Q 值。Q-learning是一种离策略算法它根据在不考虑智能体使用的策略行为的情况下可以做出的最佳可能决策来更新 Q 值。预期 SarsaExpected Sarsa 是从 Q-learning 派生出的算法。它不是使用最大 Q 值而是根据当前策略下采取每个动作的概率来计算下一个动作-状态值的期望 Q 值。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/1af64d6a7c4ca34617582d4eacfca72f.pngExpected Sarsa 更新规则。来源强化学习。入门。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗与普通的 Sarsa 相比Expected Sarsa 需要更多的计算但作为回报它在每次更新步骤中考虑了更多信息。因此Expected Sarsa 在选择下一个动作时减轻了过渡随机性的影响尤其是在学习的初始阶段。因此Expected Sarsa 在比普通 Sarsa 更广泛的学习步长α范围内提供了更大的稳定性。Expected Sarsa 是一种 on-policy 方法但可以通过分别使用用于数据生成和学习的独立行为策略和目标策略来适应 off-policy 变体。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/d5e5925f33a13d6c406d72537b910d0e.png一步 TD 算法的比较。最大化偏差到目前为止我们一直在讨论一系列算法这些算法在贪婪策略更新期间都使用了最大化操作符。然而在实践中对所有值的 max 操作符会导致值的过度估计。这个问题尤其在学习过程的开始时出现当时 Q 值是随机初始化的。因此对这些初始噪声值的最大值计算往往会导致向上偏差。例如想象一个状态 S其中每个动作的真实 Q 值都等于Q(S, a) 0。由于随机初始化一些初始估计将低于零而另一部分将高于 0。真实值的最大值是 0。随机估计的最大值是一个正值称为最大化偏差。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/2e0645c6c90c0dde4b0360b002618f68.png在有噪声的估计中最大值往往比真实值偏高。示例让我们考虑一个来自萨顿和巴特罗书籍的例子其中最大化偏差成为一个问题。我们处理的是下面图中所示的环境其中C是初始状态A和D是终端状态。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/608d9047bba9fcb868b34ccf66075cff.png环境图。C 是初始代理的状态A 和 D 是终端状态。图片由作者改编。来源强化学习。入门。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗从C转移到B或D的过渡奖励为 0。然而从B转移到A将导致一个从均值为 -0.1方差为 1 的正态分布中采样的奖励。换句话说这个奖励的平均值是负的但偶尔可以是正的。基本上在这个环境中代理面临一个二元选择是否从C向左或向右移动。在两种情况下期望回报都很清楚左侧轨迹导致期望回报G -0.1而右侧路径产生G 0。显然最佳策略是始终向右侧移动。另一方面如果我们未能解决最大化偏差那么代理在学习过程中很可能优先考虑左侧方向。为什么从正态分布中计算出的最大值将导致状态B的 Q 值更新为正值。因此当代理从C开始时它将贪婪地选择移动到B而不是到 Q 值保持为 0 的D。为了更深入地理解为什么会发生这种情况让我们使用以下参数进行几个计算学习率α 0.1折扣率 _γ **** 0._9所有初始 Q 值都设置为 0。迭代 1在第一次迭代中前往B和D的 Q 值都等于 0。让我们通过任意选择B来打破这个平局。然后状态(C, ←)的 Q 值被更新。为了简单起见让我们假设定义的分布中的最大值是一个有限的值 3。实际上这个值大于我们分布的 99% 分位数https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4568f0bb5960ac272028237105f3e528.png状态 (C,←) 的 Q 值计算代理随后移动到A并采样到奖励R -0.3。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/c297a5f8a488514b237f90ccd25cf1b8.png状态 (B,←) 的 Q 值计算迭代 2代理达到终端状态A一个新的剧集开始。从C开始代理面临是否前往B或D的选择。在我们的条件下使用 ε-贪婪策略代理几乎会选择前往Bhttps://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/63870fe7d7218d13242628240639fe39.png在第一次迭代之后代理将贪婪地选择再次向左侧移动然后在状态(C, ←)上执行类似的更新。因此其 Q 值只会越来越大https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/eb57031bb59c48b33bcc88610ddc221d.png状态 (C,←) 的 Q 值计算尽管采样了负奖励R -0.4并进一步更新B但这并没有改变情况因为最大值始终保持在 3。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/f69ed48f74fd601f3f24a4f53233cb2f.png状态B←的 Q 值计算第二次迭代结束它只使代理对左方向的优先级高于右方向。因此代理将继续从C向左移动认为这是最佳选择而实际上并非如此。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/6c22ea9dd53f3a6ed6c4954b8773f4f1.png基于贪婪选择即使与向右走相比预期回报较低代理将进一步优先考虑向左走。双重学习消除最大化偏差的最优雅解决方案之一是使用双重学习算法该算法对称地使用两个 Q 函数估计。假设我们需要确定最大化动作及其相应的 Q 值以执行更新。双重学习方法的操作如下使用第一个函数 Q₁来找到最大化动作 a*⁎* argmaxₐQ₁(a)。使用第二个函数 Q₂来估计所选动作 a*⁎*的值。两个函数 Q₁和 Q₂也可以按相反的顺序使用。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/b04fdc171ffceb51a888b214cce9672f.png双重 Q 学习伪代码。来源强化学习导论。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗在双重学习中每次迭代只更新一个估计 Q而不是两个。虽然第一个 Q 函数选择最佳动作但第二个 Q 函数提供其无偏估计。示例我们将探讨双重学习如何应用于 Q 学习的示例。迭代 1为了说明双重学习的工作原理让我们考虑一个代理在每个迭代中可以在四个方向中移动一步的迷宫。我们的目标是使用双重 Q 学习算法更新 Q 函数。我们将使用学习率α 0.1和折扣率γ**** _ 0._9。对于第一次迭代代理从单元格S A2开始并遵循当前策略向右移动一步到S’ B2获得奖励R 2。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/52d253f5a0af93f7a1acdef5cd04c67e.png迷宫示例。代理从 A2 移动到 B2。我们假设我们必须使用上面显示的伪代码中的第二个更新方程。让我们重写它https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/de0f92e904bc4b3a0013e46a24b4b442.pngQ₂函数更新方程由于我们的智能体移动到状态S’ B2我们需要使用其 Q 值。让我们看看包括B2的当前状态-动作对的 Q 表https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/875f8aa8f59aa143868c0439380af0fb.png包含 B2 的状态 Q 表我们需要找到一个动作使得S’ B2最大化 Q₁并最终使用相应的 Q₂ 值来执行相同的动作。通过采取 ← 动作达到最大的 Q₁ 值q 1.2红色圆圈。对应于动作 ← 的 Q₂ 值为q 0.7黄色圆圈。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/91aba6bc0912e00017de5577fd931de6.png寻找无偏 Q₂ 值让我们将更新方程重写为更简单的形式https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/2901eaa1308dd1ea900d392c0b7a0861.png当前 Q₂ 状态-动作值的更新方程假设初始估计Q₂(A2, →) 0.5我们可以插入值并执行更新https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/2e4308f152814fdaddfc510fb58b6d3b.pngQ₂ 值计算迭代 2智能体现在位于B2并需要选择下一个动作。由于我们处理两个 Q 函数我们必须找到它们的和https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/8965ab811ad8c410be450bebdf47e5d5.png选择 Q₁ 和 Q₂ 之和的最大值根据我们的策略类型我们必须从分布中采样下一个动作。例如如果我们使用ε贪婪策略其中ε 0.08那么动作分布将具有以下形式https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/04881d0886e396377d6a1b0839b1f862.png动作分布 (ε 0.08)我们将假设以 94% 的概率我们采样了 ↑ 动作。这意味着智能体将移动到S’ B3单元格。它收到的奖励是R -3。对于这次迭代我们假设我们已经采样了 Q 函数的第一个更新方程。让我们将其分解https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/0e14169344dfc73370e7ef7934ed9fb9.pngQ₁ 函数的更新方程我们需要知道所有对应于B3的动作的 Q 值。这里它们是https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/6b974d19c310304923d210fe1f69f945.png包含 B3 的状态 Q 表由于这次我们使用第一个更新方程我们取最大的 Q₂ 值红色圆圈和相应的 Q₁ 值黄色圆圈。然后我们可以将方程重写为简化的形式https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/57c6d3c56d9c53d5abfee6b077d537f8.png当前 Q₁ 状态-动作值的更新方程在进行所有值替换后我们可以计算最终结果https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/66dd48ad28e0dfad59e16ea0056b6066.pngQ₁ 值计算我们已经看到了双 Q 学习的例子它减轻了 Q 学习算法中的最大化偏差。这种双学习方法也可以扩展到 Sarsa 和 Expected Sarsa 算法。而不是在每个迭代中选择使用哪个更新方程双学习可以适应性地在两个方程之间迭代交替。结论尽管它们很简单但时序差分方法现在是强化学习中应用最广泛的技术之一。同样有趣的是它们也广泛应用于其他预测问题如时间序列分析、股票预测或天气预报。到目前为止我们只讨论了 TD 学习的一个特例即当n 1时。正如我们将在下一篇文章中看到的在某些情况下将n设置为更高的值可能是有益的。强化学习第六部分n 步自助我们尚未涉及这一点但结果表明TD 算法的控制可以通过演员-评论家方法实现这些方法将在本系列文章的后续部分讨论。目前我们只是重新使用了动态规划算法中引入的 GPI广义策略迭代的想法。资源强化学习。简介。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗所有图像除非另有说明均为作者所有。