强化学习教程（三）：蒙特卡罗算法

hdy

01

引言

强化学习是机器学习中的一个领域，其核心在于智能体（agent）必须在复杂环境中学习最优策略。智能体通过环境状态反馈的奖励信号，从自身行为中进行学习。这一领域极具挑战性，与其他机器学习分支存在显著差异。正因如此，仅当其他方法无法解决问题时，才应考虑采用强化学习技术。

本文将重点探讨蒙特卡洛算法。相较于传统方法，该算法的精妙之处在于无需预先知晓环境动态模型。这一特性具有决定性意义——现实中我们往往无法获知所有状态间的转移概率。

注：为了全面理解本文所涉及的概念，建议熟悉强化学习的基本概念以及本文系列前两篇文章中介绍的策略改进方法。

02

  Model-Free Vs Model-Based

在强化学习中，“模型”（model）指代智能体用于预测环境对动作反馈的任何机制。

强化学习算法可分为两大类：

• 基于模型的方法（Model-based）：利用模型在采取动作前进行规划；
• 无模型方法（Model-free）：不依赖模型，通过直接学习动作与对应回报的关联来优化策略。
  

我们在上一篇文章中研究的算法就是基于模型方法的一个例子，因其依赖状态转移概率估计 p(s’, r | s, a)。

蒙特卡洛 (MC) 方法既不估计也不使用 p(s’, r | s, a)，因此它们属于无模型方法。相反，它们从经验中学习——也就是状态、行动和奖励的序列。
它通过经验（状态、动作、奖励序列）进行学习，基于智能体轨迹数据计算期望值的近似均值，并配合广义策略迭代（GPI）获得最优策略。

本文仅研究episodic tasks。这类任务与MC方法契合度更高——每个episodic的经验数据相互独立，episodic 越多，就可以使用越多信息来更好地近似值函数。

03
  V函数估计

根据定义，状态的V值（v-value）表示智能体从该状态出发能获得的期望回报。利用智能体的经验数据，我们可以对该状态被访问后的所有回报取平均值，该计算所得的平均值即代表该状态的V值。

经验数据越丰富，计算就越精确——因为可以从更多状态的回报中求取平均值，从而提升整体近似效果。

由于智能体在一个episode中可能多次访问同一状态，V函数估计的蒙特卡洛（MC）算法存在两种版本：

• 首次访问MC法（First-visit MC）：仅考虑首次访问某状态时的回报；
• 每次访问MC法（Every-visit MC）：考虑所有访问该状态时的回报。
  
  

首次访问 MC 算法在该领域得到了更广泛的研究。



随着访问次数趋于无穷，根据大数定律，这两种方法都收敛于真实的 V 函数（价值函数）。

• 举例
  
  

我们将以最受欢迎的赌场游戏 21 点为例进行分析。

游戏目标是使手中牌的点数超过庄家，但不能超过21点。规则很简单：玩家先获得两张明牌，庄家则亮出一张明牌。随后玩家必须做出二选一的决策：

• 要牌（Hit）：玩家额外抽取一张牌，该牌点数将累加至玩家总分。若总分超过21点，则玩家直接爆牌输局。玩家可以持续要牌，次数不限。
• 停牌（Stick）：玩家停止要牌，轮到庄家行动。庄家会持续要牌直至其点数达到或超过17点。若庄家爆牌（超过21点），玩家获胜；若庄家点数介于17至21点之间，则比较双方点数，点数更高者获胜。若双方点数相同，则为平局。
  
  

初始手牌点数如下：



A牌（Ace）是一张特殊的游戏牌：若其计入11点后总点数不超过21（此时称为可用A牌），则按11点计算；否则按1点计算。

• 状态定义
  
  

在二十一点游戏中，玩家的决策仅取决于三个关键因素：

• 玩家当前总点数（12至21点之间）；
• 是否持有可转换的A牌（布尔值）；
• 庄家明牌显示的点数（2至11点之间）。
  
  

因此，将状态集合S定义为包含这三个变量的所有可能元组组合是合理的。为简化模型，我们不考虑玩家点数低于12点的简单状态——因为在此情况下选择要牌始终是最优策略。最终我们得到的状态空间大小为10（玩家点数）×2（有无A牌）×10（庄家明牌点数）=200种可能状态。相较于大多数强化学习问题，这个状态规模非常小，对于蒙特卡洛算法而言，计算价值函数应该相对容易。

在二十一点场景中，首次访问型MC（first-visit MC）与每次访问型MC（every-visit MC）完全等效，因为每个游戏状态在一局游戏中最多只会被访问一次。

• 价值函数
  
  

下图展示了蒙特卡洛算法经过500万次迭代后，在"仅当玩家达到20点时才停牌"的策略下估算得到的价值函数。

通过分析我们可以得出以下重要发现：

• 保守策略（20点停牌）总体表现欠佳。只有当玩家手牌为20或21点时才具有优势。举例说明：若玩家持有18点选择要牌，抽到4点及以上牌就会爆牌（超过21点）导致失败。
  
  

• 虽然两种热力图的色彩结构相似，但持有可转换A牌能为玩家提供"二次机会"：当点数超过21时，可将A牌由11点转为1点避免爆牌。因此，含A牌状态的价值函数估值普遍更高。
• 含A牌状态的价值函数估算精度较低，这是因为在实际游戏中出现A牌组合的概率较小。解决方案可通过增加模拟对局次数来提高数据准确性。
  
  

虽然理论上可以采用动态规划算法估算状态价值，但其实现难度显著更大。例如计算13点状态的价值函数时，需要获取14-21点所有状态的转移概率——由于游戏组合过于复杂，通过概率公式精确计算这些转移概率极具挑战性。

04

Q函数估计

在基于模型的方法中，仅凭估计的V函数就足以找到最优策略：在任意状态下，我们总能选择一个动作，使得该动作的奖励（由p(s',r|s,a)给出）与下一状态的奖励之和最大化。

而在无模型方法（如蒙特卡洛方法）中，仅拥有V函数是不够的。我们缺少的关键部分是在每个状态下选择任意动作所能获得的奖励，因此无法通过采取特定动作来估计总体回报。同时，我们也不能使用贝尔曼方程来建立V函数和Q函数之间的关系，因

为在这种情况下，我们仍然需要知道 p(s',r|s,a)。

解决这个问题的一个巧妙方法是稍微换个角度看待问题。我们可以将所有可能的状态-动作对 (s,a)∈S×A 视为新的“状态”，并利用蒙特卡洛方法来估计这些“状态”的V函数。计算这个V函数实际上等价于在原问题中估计Q函数。

具体来说，要应用首次访问蒙特卡洛方法，我们可以定义访问标准：当状态 s 被访问且在该状态下选择了动作 a 时，状态-动作对 (s,a) 就被视为被访问过。

• 优点
  
  

与我们在前一篇文章中介绍的动态规划方法相比，蒙特卡洛方法在估计价值函数方面具有显著优势：

• 状态独立性：每个状态的估计是独立的，不依赖于其他状态的值；
• 计算效率：更新单个状态的算法复杂度仅取决于采样回合数，而非总状态数。由于我们可以自由设定用于平均最终结果的回合数，因此即使总状态数很大，我们仍能灵活调整计算量；
• 免模型特性：在多数环境中，理论上几乎无法精确计算每个状态和动作的转移概率以获取环境动态。而蒙特卡洛方法无需此类信息，仅通过易于生成的观测数据即可高效学习。
  

• 示例
  
  

让我们继续以之前的21点游戏为例，这次重点讨论Q函数估计。众所周知，21点游戏中有两个可选动作：要牌（hit）和停牌（stick）。若将动作与状态组合，将得到200×2=400个（状态，动作）对。这使得蒙特卡洛算法能够轻松估计给定策略下的任何Q函数。下图展示了随机策略（要牌与停牌概率均为50%）对应的Q函数热力图：


与先前V函数的情况类似，含可用A（usable ace）与不含可用A的图示结构相似，但前者在所有状态下都赋予玩家更高的胜率优势。所有图示中Q值最低的区域，出现在"无可用A时选择要牌"的情况。这源于两个关键因素：首先，要牌动作本身存在爆牌风险；其次，根据当前策略，玩家有50%概率再次要牌，这将显著提高输牌几率。特别值得注意的是，当玩家当前点数为21时（最右侧一列），所有要牌动作的Q值均为-1——因为在此情况下要牌必然导致爆牌。

05

权衡

在理解如何评估Q函数之后，讨论如何寻找最优策略是顺理成章的。但在那之前，我们需要先了解几个重要概念，这些概念将帮助我们构建高效算法。

当前Q函数估计方法面临一个主要问题：存在大量（状态-动作）组合，其中许多可能永远不会被访问。如果策略是确定性的，那么在给定状态下，算法可能会在后续学习迭代中始终贪婪地选择同一个动作。这样一来，我们就无法探索其他可能带来更高回报的（状态-动作）组合。

确定性策略是指智能体在特定状态下只能采取唯一固定动作的策略。这类策略会将该动作的概率设为1，而其他动作的概率设为0。若不满足此条件，则称为随机性策略。

这个问题是探索与利用权衡的经典案例。一方面，我们希望利用已知最佳动作以获得最高奖励；另一方面，我们需要探索所有可能的动作以确定哪些动作能带来更大回报。

因此，必须在利用与探索之间寻求适当平衡。就蒙特卡洛方法而言，存在多种解决方案，下文将介绍其中一种。

• 示例
  
  

假设一个智能体正在学习下图迷宫中的最优策略，其目标是获取最大累积奖励。



智能体从A1出发，每步可向任意方向移动。终点位于A3，提供奖励R=1。此外，D2处设有高额奖励R=10（这显然是智能体应获取的目标），而C1处存在陷阱——踏入即终止回合并获得R=-3的惩罚，其他单元格的奖励均为R=0。最优策略理应是：先获取D2的高额奖励，再前往A3终点。但若未能妥善调节探索与利用的平衡，实际结果往往难以达成最优。具体而言，若智能体始终贪婪选择当前最高奖励的路径，可能在最初几次迭代后就认定A1-A2-A3是唯一最优路径，从而放弃探索其他可能路径。另一种情况是：智能体初始选择右移时若不幸落入C1陷阱，策略评估将给C1周边单元格赋予负值。当策略过于贪婪或探索率极低时，智能体将永远无法发现D2的高额奖励。

• 探索策略
  
  

探索更多（状态-动作）组合的最简单方法之一，是通过以下两种方式实现：

• 显式启动法：在每个可能的（状态-动作）组合下多次启动训练回合，确保罕见场景也能获得足够的采样数据
• 随机起始法：为每个训练回合随机选择初始状态，且保证所有状态的选择概率均不为零（该方法也被称为"探索性启动"）
  

尽管探索性启动方法简单直接，但存在显著缺陷：智能体与环境交互产生的真实数据分布，可能与探索性启动采用的人为分布存在较大差异。


这将导致两个严重后果：智能体可能基于非真实的数据分布学习策略，以及最终获得的策略在真实环境中并非最优。

06
结论

在本文中，我们介绍了蒙特卡洛方法，这在强化学习中非常有用。它们能够在没有环境动态知识的情况下优化策略，这使得它们比上一部分讨论的策略改进算法更适用于许多问题。

然而，我们这里只谈到了V函数和Q函数的估计方法，并没有详细介绍用于搜索最优策略的完整蒙特卡洛算法，因为首先需要解决平衡探索与利用的权衡问题。为此，我们将在下一部分引入ε-贪婪策略，结合探索性起始方法，并对当前版本的算法进行几项改进。

小小庄稼汉

训练大模型？

天哥GG

强化学习教程（三）：蒙特卡罗算法

高速L

阅读完毕

CalvinKim

跑进来，看看。

szhuang56

来，看看。看不懂