蒙特卡洛方法在强化学习中的原理、实现与优化

1. 从“试错”到“估算”：蒙特卡洛方法为什么是强化学习的必经之路

如果你跟着这个系列一路走到第四篇，说明你已经啃完了动态规划那一套东西。动态规划很优雅，但它有个硬伤：你得知道环境的完整模型，也就是状态转移概率和奖励函数都得明明白白摆在你面前。现实里哪有这么好的事？你让一个机械臂去抓东西，它不可能提前知道每一个关节角度变化后物体滑落的精确概率。这时候就需要一种不依赖环境模型的方法——蒙特卡洛。

蒙特卡洛这个词听起来唬人，其实核心思想朴素得很：不知道期望值？那就多采样几次，用样本均值去逼近。你在赌场里扔骰子，想知道掷出六点的概率，扔一万次统计一下就行了。强化学习里的蒙特卡洛方法也是这个逻辑：让智能体跑完一整条轨迹，拿到从某个状态出发的实际回报，然后用这些回报的平均值来估计这个状态的价值。

这个思路的转变非常关键。动态规划是“我全知全能，我直接算”，蒙特卡洛是“我啥也不知道，但我可以试”。从工程实现的角度看，这意味着我们不再需要写那个让人头疼的环境模型类，只需要一个能跟环境交互、能收集轨迹的采样循环。代码结构一下子简单了很多，但随之而来的是新的问题：方差大、需要等回合结束、对连续任务不友好。这些问题怎么解决，就是这一篇要聊透的东西。

我个人的经验是，很多人学强化学习卡在蒙特卡洛这一块，不是因为概念难，而是因为从“表格更新”到“采样估计”这个思维跳跃没完成。动态规划里你更新的是价值表，蒙特卡洛里你更新的是对价值表的估计，而这个估计本身是个随机变量。理解这一点，后面的重要性采样、策略优化才能顺理成章。

2. 蒙特卡洛预测与控制：从“跑完再说”到“边走边学”

2.1 首次访问与每次访问：两种估计策略的取舍

蒙特卡洛预测要解决的问题是：给定一个策略，估计每个状态的价值函数。具体做法是让智能体按照这个策略跑很多个回合，每个回合结束后，对于回合中出现的每个状态，计算它的回报，然后把这些回报平均起来。

这里有个细节需要做选择：同一个回合里，如果一个状态出现了多次，你是只统计第一次出现时的回报，还是每次都统计？这就是首次访问蒙特卡洛和每次访问蒙特卡洛的区别。

首次访问的逻辑更干净：每个回合对每个状态的估计只贡献一个样本，样本之间独立同分布，数学性质好，收敛性有保证。每次访问则利用了更多数据，但样本之间相关性更强。实际写代码的时候，首次访问更容易实现，因为你只需要记录哪些状态已经访问过就行。

def mc_prediction_first_visit(env, policy, episodes, gamma=0.99): V = defaultdict(float) returns = defaultdict(list) for _ in range(episodes): episode = generate_episode(env, policy) states = [step[0] for step in episode] G = 0 visited = set() for t in range(len(episode) - 1, -1, -1): state, action, reward = episode[t] G = gamma * G + reward if state not in visited: returns[state].append(G) V[state] = np.mean(returns[state]) visited.add(state) return V

这段代码里有个容易踩的坑：回报的计算必须从后往前累加。很多人习惯从前往后算，每次重新遍历剩余步骤求和，那样时间复杂度直接变成O(n²)，回合一长就慢得没法看。从后往前累加是O(n)，这是写蒙特卡洛代码的基本功。

注意：visited集合必须在每个回合开始时重置，否则跨回合的去重会导致估计偏差。我见过有人把这个集合定义在循环外面，结果跑了几千个回合发现价值函数几乎没更新，排查了半天才发现是这里的问题。

2.2 探索性初始化：保证每个状态都被“照顾”到

蒙特卡洛控制面临一个鸡生蛋的问题：要评估一个策略，需要采样；要采样，得保证每个状态都能被访问到；但如果策略是确定性的，某些状态可能永远访问不到，那它们的价值就永远估不准。

最直接的解决方案叫探索性初始化：每个回合开始时，随机选择一个状态-动作对作为起点，并且保证每个状态-动作对都有非零概率被选为起点。这样理论上只要回合数足够多，所有状态-动作对都会被访问到。

这个方案在表格型问题里能用，但到了实际场景就很别扭。你训练一个机器人走路，总不能每次都把它瞬移到随机位置开始吧？所以后来有了更实用的方案：用ε-贪心策略，让智能体在大多数时候选当前认为最好的动作，但偶尔随机探索一下。这个思路在后面的时序差分方法里会成为主流，蒙特卡洛这里先埋个伏笔。

2.3 增量式更新：不用存所有回报也能算均值

前面代码里用了一个列表把所有回报存下来，最后求平均。这样做在回合数不多的时候没问题，但如果跑几十万回合，内存就吃不消了。而且每次求平均都要遍历整个列表，效率也低。

增量式更新的思路很简单：维护一个计数N和一个当前均值V，每来一个新回报G，就更新：

V ← V + (1/N) * (G - V)

这个公式的直觉是：新均值等于旧均值加上一个修正项，修正项是预测误差乘以学习率。当N很大的时候，学习率变小，新样本对均值的影响减弱，这符合我们对“大量样本平均”的预期。

def mc_prediction_incremental(env, policy, episodes, gamma=0.99): V = defaultdict(float) N = defaultdict(int) for _ in range(episodes): episode = generate_episode(env, policy) G = 0 visited = set() for t in range(len(episode) - 1, -1, -1): state, action, reward = episode[t] G = gamma * G + reward if state not in visited: N[state] += 1 V[state] += (G - V[state]) / N[state] visited.add(state) return V

这个写法不仅省内存，而且天然支持在线更新。你甚至可以把N换成一个固定的学习率α，变成非平稳环境下的跟踪版本。这个改动看似小，但它是从蒙特卡洛到时序差分的关键桥梁。

3. 重要性采样：当策略“换了个脑子”怎么继续用旧数据

3.1 为什么需要重要性采样

蒙特卡洛控制有个绕不开的矛盾：你要评估和改进的是目标策略π，但采样用的行为策略μ可能跟π不一样。比如你在训练一个机器人，行为策略是带探索的ε-贪心，目标策略是纯贪心。你收集到的轨迹是按ε-贪心分布的，但你想估计的是纯贪心策略的价值。这两个分布不一样，直接平均就错了。

重要性采样就是解决这个问题的数学工具。它的核心公式是：

E_π[X] = E_μ[ (π(a|s) / μ(a|s)) * X ]

这个比值π/μ叫做重要性采样比。直觉上，如果某个动作在目标策略下比行为策略下更常出现，那这个样本就应该被放大；反之则缩小。这样加权平均之后，得到的就是目标策略下的期望。

3.2 普通重要性采样与加权重要性采样

普通重要性采样直接用比值乘以回报，然后求平均。这个估计是无偏的，但方差可能非常大。原因在于比值可能很大，尤其是当μ(a|s)很小的时候，一个样本就能把均值拉飞。

加权重要性采样用比值之和做归一化：

V(s) = Σ(ρ_t * G_t) / Σρ_t

这个估计是有偏的，但方差小很多。实际用的时候，加权版本通常更受欢迎，因为它在偏差和方差之间取得了更好的平衡。

def off_policy_mc(env, target_policy, behavior_policy, episodes, gamma=0.99): V = defaultdict(float) C = defaultdict(float) for _ in range(episodes): episode = generate_episode(env, behavior_policy) G = 0 W = 1 for t in range(len(episode) - 1, -1, -1): state, action, reward = episode[t] G = gamma * G + reward C[state] += W V[state] += (W / C[state]) * (G - V[state]) W *= target_policy(state, action) / behavior_policy(state, action) if W == 0: break return V

这段代码里有个提前终止的优化：如果W变成0，说明目标策略根本不会选这个动作，后面的计算就没意义了，直接跳出循环。这个细节能省不少计算。

3.3 重要性采样的方差问题与实操建议

重要性采样的方差问题在实际项目中非常突出。我做过一个实验，同样的环境，普通重要性采样的价值估计波动范围是加权版本的十几倍。如果你的行为策略和目标策略差异很大，比如行为策略有大量随机探索，目标策略几乎是确定性的，那比值会出现极端值，估计结果基本没法用。

几个实操建议：

• 尽量让行为策略和目标策略接近。如果目标策略是ε-贪心，行为策略也用ε-贪心，只是ε值不同，这样比值不会太离谱。
• 用加权重要性采样而不是普通版本，牺牲一点偏差换方差的大幅降低。
• 对重要性采样比做裁剪，比如限制在[0.1, 10]之间，虽然引入偏差但能防止估计爆炸。
• 如果可能，用后面的时序差分方法替代蒙特卡洛，TD对重要性采样的依赖小得多。

提示：重要性采样在离线强化学习里是个核心话题。你手头有一批旧策略收集的数据，想训练一个新策略，重要性采样比就是连接新旧策略的桥梁。但纯蒙特卡洛的重要性采样在长回合任务里几乎不可用，方差会大到让你怀疑人生。这也是为什么后来的方法都在往TD和Actor-Critic方向走。

4. 策略优化入门：从“评估”到“改进”的闭环

4.1 策略改进定理与贪心策略

蒙特卡洛控制的最终目标是找到最优策略。有了价值函数之后，怎么改进策略？答案藏在策略改进定理里：给定一个策略π的价值函数V_π，如果我们在每个状态都选择那个能最大化“即时奖励+折扣后后续价值”的动作，得到的新策略π'一定不比π差。

用公式说就是：

π'(s) = argmax_a Σ_{s',r} p(s',r|s,a) [r + γV_π(s')]

在蒙特卡洛的设定下，我们没有环境模型，所以用动作价值Q(s,a)来代替。Q(s,a)是在状态s下选动作a，之后按照策略π继续走的期望回报。有了Q，贪心策略就是每个状态选Q最大的动作。

4.2 从Q表到策略：蒙特卡洛控制的完整流程

把预测和控制串起来，蒙特卡洛控制的流程是这样的：

1. 初始化Q表和策略π（通常是ε-贪心）
2. 用π生成一个回合
3. 从后往前计算每个状态-动作对的回报
4. 用增量式更新Q值
5. 根据新的Q值更新策略
6. 重复2-5直到收敛

def mc_control(env, episodes, gamma=0.99, epsilon=0.1): Q = defaultdict(lambda: defaultdict(float)) N = defaultdict(lambda: defaultdict(int)) def policy(state): if np.random.random() < epsilon: return np.random.choice(env.action_space) return max(Q[state], key=Q[state].get) for _ in range(episodes): episode = generate_episode(env, policy) G = 0 visited = set() for t in range(len(episode) - 1, -1, -1): state, action, reward = episode[t] G = gamma * G + reward if (state, action) not in visited: N[state][action] += 1 Q[state][action] += (G - Q[state][action]) / N[state][action] visited.add((state, action)) return Q, policy

这个实现里，策略是动态计算的，每次调用policy函数时根据当前Q值决定动作。这样做的好处是不用显式维护一个策略表，代码简洁。但要注意，如果Q表很大，每次调用都遍历所有动作找最大值会比较慢，可以考虑用优先队列或者只维护一个最优动作缓存。

4.3 ε-贪心的衰减策略

ε-贪心里的ε控制探索程度。ε太大，智能体一直在随机试错，学不到精细的策略；ε太小，可能陷入局部最优，有些状态-动作对永远探索不到。

常见的做法是让ε随时间衰减。一开始ε=1.0，完全随机探索；然后慢慢降到0.01或0.05，基本利用当前最优策略。衰减的方式可以是指数衰减：

ε_t = ε_min + (ε_max - ε_min) * exp(-t / decay_rate)

也可以是线性衰减，每跑一个回合减一个固定值。我个人的经验是，指数衰减在大多数任务里表现更稳，因为前期探索充分，后期收敛平滑。线性衰减如果步长没调好，可能前期探索不够或者后期还在乱跳。

注意：ε的衰减速度要和任务复杂度匹配。简单任务几百个回合就能收敛，衰减可以快一点；复杂任务可能需要几万甚至几十万回合，衰减太慢会导致收敛慢，衰减太快会导致探索不足。我一般会先跑一个短实验，观察Q值的变化曲线，再决定衰减参数。

5. 实战中的坑与排查技巧

5.1 回报计算错误：最常见的bug来源

蒙特卡洛方法里，回报的计算是最容易出错的地方。我见过太多人把折扣因子用错位置，或者在从后往前累加时忘了乘gamma。这里给一个检查清单：

• 回报的递推公式是G = reward + gamma * G，不是G = gamma * reward + G
• 从后往前遍历时，G的初始值是0
• 如果回合有终止状态，终止状态的回报就是它的即时奖励，不需要再加后续价值
• 折扣因子gamma一般在0.9到0.99之间，太小的gamma会让智能体短视

一个实用的调试技巧：拿一个极简环境（比如只有三四个状态的网格世界），手动计算每个状态的期望回报，然后跟代码跑出来的结果对比。如果对不上，逐行检查回报计算部分。

5.2 探索不足：Q值大面积为零

如果你跑完蒙特卡洛控制，发现Q表里大部分条目还是初始值，说明探索不够。原因可能是ε太小、回合数太少、或者状态空间太大导致每个状态被访问的次数太少。

排查思路：

• 统计每个状态-动作对被访问的次数，看看分布是否均匀
• 如果某些状态-动作对访问次数为零，检查探索性初始化是否覆盖了所有起点
• 如果访问次数差异很大，考虑增大ε或者用基于计数的新颖性奖励

5.3 方差过大：价值估计像过山车

蒙特卡洛的方差问题在长回合任务里特别明显。一个回合可能几百步，回报的随机性累积起来，导致价值估计波动很大。

缓解方案：

• 用加权重要性采样替代普通版本
• 对回报做归一化，比如减去一个基线
• 增加采样回合数，用更多的样本平均来降方差
• 如果任务允许，用n步回报或者TD方法替代纯蒙特卡洛

5.4 常见问题速查表

6. 从蒙特卡洛到时序差分：下一步的方向

蒙特卡洛方法给了我们一套不依赖环境模型的完整工具链：采样、估计、改进。但它有两个天生的局限：必须等回合结束才能更新，以及方差大。这两个问题在长回合或连续任务里会变得非常棘手。

时序差分方法就是冲着这两个问题来的。它不需要等回合结束，每走一步就能更新；它用自举的方式降低方差，用当前的价值估计来更新价值估计。从蒙特卡洛到时序差分，就像从“攒够钱再买房”变成“边攒边贷款”，虽然引入了偏差，但换来了效率和稳定性。

如果你已经把这一篇的代码跑通了，建议你拿同一个环境，把蒙特卡洛和下一章的时序差分做个对比实验。观察收敛速度、价值估计的方差、最终策略的质量。这种对比会让你对两种方法的适用场景有更直观的理解。

我在实际项目里的体会是：蒙特卡洛适合回合短、需要无偏估计的场景，比如某些回合制的游戏AI；时序差分适合回合长、需要在线学习的场景，比如机器人控制。但不管用哪种，探索策略的设计和回报的计算都是最需要花心思的地方。这两个地方做对了，后面的算法改进才有意义。