

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

AI算法之道

2025-05-21

导读：强化学习蒙特卡洛算法讲解

点击蓝字

关注我们

引言

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

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

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

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 越多，就可以使用越多信息来更好地近似值函数。

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点所有状态的转移概率——由于游戏组合过于复杂，通过概率公式精确计算这些转移概率极具挑战性。

Q函数估计‍

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

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

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

解决这个问题的一个巧妙方法是稍微换个角度看待问题。我们可以将所有可能的状态-动作对 ( s , a ) ∈ S × A

具体来说，要应用首次访问蒙特卡洛方法，我们可以定义访问标准：当状态 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——因为在此情况下要牌必然导致爆牌。

‍