原文towardsdatascience.com/reinforcement-learning-part-3-monte-carlo-methods-7ce2828a1fdbhttps://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/350815dbc3452a9b348c1b7be5e4b032.png引言强化学习是机器学习的一个领域它引入了代理的概念代理必须在学习复杂环境中的最优策略。代理从其动作中学习这些动作在给定环境的状态下产生奖励。强化学习是一个困难的话题与机器学习的其他领域有显著差异。这就是为什么它只应该在给定问题无法以其他方式解决时使用。在本文中我们将探讨蒙特卡洛算法。与标准方法相比它们的优雅之处在于它们不需要对环境动态有任何了解。这一点至关重要因为在现实生活中我们通常不知道所有可能的状态之间的转移概率。注意。为了完全理解本文中包含的概念强烈建议熟悉强化学习的主要概念以及本系列前两篇文章中介绍的策略改进方法。强化学习第一部分引言和主要概念强化学习第二部分策略评估和改进关于本文在第一部分本文基于理查德·S·萨顿和安德鲁·G·巴特罗所著的著名书籍《强化学习》的第三章我强烈推荐所有对深入研究感兴趣的人阅读。在第二部分中我们了解了 GPI 方法该方法旨在通过在策略评估和策略改进之间交替来寻找最优策略。尽管我们在第二部分中学到了重要的原则但它们仅适用于完全已知动态的完美环境。当转移概率p(s’ r | s, a)未给出这在大多数现实生活中的问题中是情况时寻找最优策略变得更加困难。幸运的是强化学习中存在可以优化策略而不使用关于环境动态知识的技术。Monte Carlo 方法是这类算法的例子。本文基于由理查德·S·萨顿和安德鲁·G·巴特罗撰写的书籍强化学习的第五章。我非常感谢为这本书的出版做出贡献的作者们的努力。注意。本文的源代码可在GitHub上找到。顺便说一下该代码生成的 Plotly 图表在 GitHub 笔记本中无法渲染。如果您想查看图表可以本地运行笔记本或导航到存储库的结果文件夹。ML-medium/monte_carlo/blackjack.ipynb at master · slavastar/ML-medium无模型方法与基于模型的方法在强化学习中术语模型指的是智能体用来预测其动作对环境响应的任何东西。强化学习算法可以分为两类基于模型在采取动作之前使用模型来规划动作的方法。无模型没有模型的方法。算法试图学习将动作与其相应的回报关联起来。我们在上一篇文章中研究的算法是一个基于模型方法的例子因为智能体使用给定的转移概率估计p(s’ r | s, a)。Monte Carlo (MC) 方法既不估计也不使用p(s’ r | s, a)因此它们是无模型的。相反它们从经验——状态、动作和回报的序列中学习。通过使用给定的智能体轨迹它们平均近似期望值并使用 GPI 获得最优策略。在本文中我们将仅关注情景任务。由于经验是独立于每个情景获得的因此在 MC 方法背景下研究它们更容易。可用的情景越多可用于更好地逼近价值函数的信息就越多。V 函数估计根据定义状态 v 值对应于智能体从该状态开始所获得的期望回报。通过智能体的经验信息我们可以对该状态访问后的所有回报进行平均。这样计算出的平均价值将代表该状态的 v 值。了解更多的经验信息非常有用因为我们可以从更多对状态的回报中计算平均值从而提高整体逼近的准确性。基于智能体在情景中可能多次处于相同状态的事实存在两种 MC 算法版本用于 V 函数估计首次访问 MC 方法只考虑首次访问状态时的回报每次访问 MC 方法考虑所有访问状态时的回报。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/691572e4243331c420f03162c579069c.png首次访问 MC 方法伪代码。来源强化学习。引论。第二版 | 理查德·S·萨顿和安德鲁·G·巴特罗首次访问 MC 算法在该领域得到了更多的研究。随着访问次数趋向于无穷大根据大数定律两种方法都会收敛到真实的 V 函数。示例我们将探讨一个流行的赌场游戏——黑桃 A 的例子。规则游戏的目标是获得比经纪人更多的分数而不超过 21 分。规则很简单玩家被发两张牌经纪人公开他的单张牌。然后玩家必须做出以下两个决定之一击牌玩家再抽一张牌这张牌的数值加到玩家的分数上。如果玩家的分数超过 21则玩家输掉游戏。玩家可以继续击牌直到他们愿意为止。停牌玩家不再抽牌并将回合传递给经纪人。经纪人继续抽牌直到他们获得 17 分或更多。如果经纪人的分数超过 21则玩家赢得游戏。如果经纪人的分数在 17 到 21 之间则分数更高的人赢得游戏另一个人输掉。如果分数相同则为平局。以下表格显示了牌的值https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/6cab1951d1e533d293fc7479ecfd1c75.png黑桃 A 牌值。上面一行指的是扑克牌下面一行指的是它们的值。红桃 A 是一张特殊的游戏牌如果加上这张牌后的总分不超过 21在这种情况下这张 A 被称为可用的则 A 计 11 分否则A 计 1 分。状态定义玩家在黑桃 A 中的决定只取决于三个因素玩家的当前分数介于 12 到 21 之间玩家是否有可用的 A二元值经纪人公开的牌的分数介于 2 到 11 之间。正因如此我们逻辑上宣布状态集 S 为包含这三个变量的所有可能元组的组合。为了简单起见我们不会关注玩家分数小于 12 的平凡状态因为在这些情况下玩家总是最优选择击牌。因此我们只有10⋅2⋅10 200种状态。与大多数强化学习问题相比这个状态数量较低。对于蒙特卡洛算法计算价值函数应该相对容易。在 21 点游戏中首次访问 MC 与每次访问 MC 相同因为在每个回合中每个游戏状态只能访问一次。V 函数下面的图表显示了蒙特卡洛算法在 5 ⋅ 10⁶次迭代下根据玩家达到 20 分时坚持的策略估计的 V 函数。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/245a7908959858998cb485ba75c241bb.png根据玩家达到 20 分时坚持的策略的 V 函数。横轴表示玩家的牌面总和纵轴显示庄家的第一张牌。庄家的 A 牌用 1 表示。这里有一些我们可以做出的有趣观察只有在达到 20 分后坚持的策略表现不佳。玩家具有优势的两种情况仅发生在他们的分数为 20 或 21 时。例如如果玩家有 18 分并且再抽一张牌他们很可能超过 21 分通过抽到价值为 4 或更高的牌从而输掉游戏。两个热图的色彩结构非常相似。然而如果玩家的分数超过 21 分一个可用的 A 牌会给玩家一个“第二次机会”。因此具有可使用 A 牌的情况的 v 值高于没有它的情况。具有可使用 A 牌的游戏的 v 值不太精确。这可以通过这些情况在 21 点游戏中出现频率较低来解释。一个可能的解决方案是生成更多的回合。从理论上讲我们可以使用动态规划算法来估计 21 点状态但这会困难得多。例如想象一下玩家有 13 分。为了计算该状态的 v 值我们需要从 14 分到 21 分的所有过渡概率这使用概率公式来估计非常困难因为存在太多的可能的游戏组合。Q 函数估计在基于模型的方法中估计的 V 函数足以找到最优策略在任何状态下我们都可以选择一个动作使得该动作的奖励由*p(s’, r | s, a)*给出和下一个状态回报的总和最大化。在无模型方法即 MC 情况中仅有 V 函数是不够的。我们在这里缺少的是每个状态下选择任何动作的奖励。因此我们不能通过采取某种动作来估计整体回报。同时我们也不能使用贝尔曼方程该方程可以建立 v 值和 q 值之间的关系在这种情况下我们仍然需要p(s’, r | s, a)。一种优雅的技巧是稍微从不同的角度看待这个问题。我们可以考虑所有可能的状态和动作对(s, a) ∈ S x A并将它们视为状态。为了找到这些状态的价值我们可以利用蒙特卡洛方法进行 V 函数估计这个 V 函数的计算将等同于原始问题中的 Q 函数估计。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/df022abe9d2c6f8d322a4bd87a06f152.png蒙特卡洛方法估计 Q 函数的思想包括计算所有访问给定(状态动作)对期间的平均回报。特别是为了应用首次访问蒙特卡洛方法我们可以推导出访问标准如果状态 s 被访问并且在该状态中选择了动作 a则状态-动作对*(s, a)*被访问。优点与我们在上一篇文章中介绍的动态规划方法相比用于估计值函数的蒙特卡洛方法具有显著优势每个状态都是独立估计的并且不依赖于其他状态的价值更新单个状态的算法复杂度取决于剧集数量而不是状态总数。由于我们定义剧集数量以平均最终结果因此即使状态总数很高我们也有更多的灵活性https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/dd97532a3620ef94d2eb797686ce8feb.png使用蒙特卡洛方法而不是动态规划的一个优点是计算值函数的算法复杂度仅取决于剧集数量而不是状态数量。在许多环境设置中理论上估计每个状态和动作的转移概率以获得环境动态几乎是不可能的。同时蒙特卡洛方法不需要这些信息并且可以从易于生成的观察中优雅地学习。示例让我们继续使用之前的二十一点例子但这次是为了 Q 函数估计。Q 函数如我们所知在二十一点中有两种可能的行为击中和坚持。如果我们将它们添加到可能的状态中我们就会得到200⋅2 400*(状态动作)*对。这使得蒙特卡洛算法能够轻松估计给定策略下的任何 Q 函数。下面的图表显示了随机策略的 Q 函数其中p(击中) p(坚持) 0.5。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/28e9e1c2cca638d1cbb17e4bc36126f1.png随机策略的 Q 函数。横轴表示玩家的牌面总和纵轴显示庄家的第一张牌。庄家的 A 表示为 1。与前一种情况一样有和没有可用的 A 的图表在大多数方面相似只是可用的 A 为玩家在每种状态下赢得游戏的几率提供了更高的机会。整体 q 值最低的图表是在没有可用的 A 的情况下击打的动作。导致这一点的两个因素是首先通过击打玩家已经面临爆牌的风险其次根据我们的策略有 50%的几率玩家会再次击打这显著增加了输掉比赛的机会。因此21 点玩家点数的最后一列全部为-1因为玩家在这些情况下通过击打保证会输掉游戏。探索与探索权衡注意。在理解如何评估 Q 函数之后讨论如何找到最佳策略是合乎逻辑的。然而在这样做之前我们需要先了解几个重要概念这些概念将帮助我们构建一个高效的算法。在当前时刻我们在 Q 函数估计的当前方法中面临一个主要问题总对数状态动作数量众多其中许多可能永远不会被访问。如果策略是确定性的那么对于给定状态它可能在后续的学习迭代中始终贪婪地选择一个动作。结果我们将永远无法探索其他可能带来更高回报的*(状态动作)*对。如果代理只能从一个状态采取相同的单一动作则称为确定性策略。这种策略将此动作的概率设为 1并将所有其他动作的概率设为 0。如果这个条件不满足则该策略称为随机策略。描述的问题是探索与利用权衡的经典表述。一方面我们希望利用最佳动作以获得尽可能高的奖励。另一方面我们需要探索所有可能的行为以确定哪些行为会导致更大的奖励。正因如此我们需要努力在利用和探索之间找到正确的平衡。说到蒙特卡洛方法存在几种方法其中一种将在下面描述。示例想象一个代理在下面的迷宫中学习最佳策略。代理的目标是收集最大可能的回报。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/c2c2d5de6e4f4c7a1e18b8c2d03d92f1.png迷宫示例。如果策略是贪婪地更新那么代理很可能不会探索 D2 处的奖励。智能体从A1开始在每次迭代中都可以向任何方向移动。终端状态位于A3并给出奖励R 1。除此之外在D2处有一个大奖励R 10我们显然希望智能体收集它。同时在C1处有一个洞。如果智能体走到那里则游戏结束并给予智能体奖励R -3。走进其他单元格将带来奖励R 0。最优策略将包括在D2收集奖励然后导航到终端状态A3。不幸的是如果探索和利用之间的平衡没有适当调整这种情况并不总是会发生。即如果智能体总是贪婪地选择具有最大回报的动作那么在最初的几次迭代中它可能会发现路径A1-A2-A3是唯一的最优路径而无需探索其他任何选项。在另一种情况下智能体最初可以向右移动但如果它掉入C1那么策略评估将给C1附近的单元格分配负状态或状态-动作值。如果策略是贪婪的或探索率非常小那么智能体将永远不会探索D2的奖励。探索开始探索更多(状态动作)对的最简单方法之一是在每个可能的组合(状态动作)中显式地开始多个游戏以在罕见情况下仍然得到平均值。另一种方法是为每个游戏随机采样起始状态所有状态的概率均不为零。这种方法被称为探索开始。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/2a84bae1892946dca829443f3f292428.png探索开始技术使得状态动作对的分布更加一致并增加了在罕见环境情况下观察回报的机会。尽管探索开始方法很简单但它有一个相当大的缺点智能体与环境交互的实际数据分布可能与用于探索开始的数据分布有很大差异。因此智能体可能会基于不真实的数据分布学习到最优策略。因此在真实环境中学习到的策略将不是最优的。结论在这篇文章中我们讨论了蒙特卡洛方法这在强化学习中非常有用。它们能够在没有任何关于环境动态知识的情况下优化策略这使得它们适用于许多问题与之前部分讨论的政策改进算法相比。尽管如此我们只讨论了 V-函数和 Q-函数估计的方法并没有详细涵盖搜索最优策略的完整蒙特卡洛算法因为我们必须首先解决探索与利用之间的平衡问题。为了做到这一点我们将在下一部分介绍ε-贪婪策略将它们与探索起始方法相结合并对当前算法版本进行一些改进。资源强化学习导论第二版| 理查德·S·萨顿和安德鲁·G·巴特罗所有图片除非另有说明均为作者所有。