蒙特卡洛方法

蒙特卡洛方法

本节摘要:动态规划需要一个模型。蒙特卡洛(Monte Carlo, MC)什么都不需要,只要回合。跑策略、看回报、求平均——RL 里最朴素的想法,却是下游一切的钥匙。本节讲透 MC 的核心:V^π(s) ≈ (1/N) Σ G(s);首次访问 vs 每次访问的区别;增量均值 V_new = V_old + α(target - V_old) 这一行代码如何把 MC 推向 TD、再推向所有现代 RL;以及探索为什么突然成了问题——确定性策略会让大片状态永远没价值。你会在 4×4 GridWorld 上跑 MC 控制,用 50000 回合逼近 DP 的金标准,并理解为什么二十一点、扑克这种天然终止的游戏至今仍是 MC 的主场。

对应原课程:Phase 9 · Lesson 03 · monte-carlo-methods(原英文 phases/09-reinforcement-learning/03-monte-carlo-methods/docs/en.md)。

学习目标

阅读完本节,你应当能够:

1. 写出蒙特卡洛的核心估计器 V^π(s) ≈ (1/N) Σ G^{(i)}(s),并说明它只需采样能力。
2. 区分首次访问(First-Visit)与每次访问(Every-Visit)MC,说明各自的无偏性与样本效率。
3. 用增量均值公式把 MC 改造成常数步长 α 的非平稳估计器——这是通往 TD 的跳板。
4. 说明探索为何在 MC 里成了问题,并能列出三种解法(探索性起点、ε-贪心、离策略重要性采样)。
5. 实现MC 控制(评估 → 改进 → 评估),并与 DP 金标准对比验证。

一、问题与直觉

动态规划很优雅,但它假设你能对每个状态-动作查询 P(s' | s, a)。真实世界几乎不这样工作。机器人无法解析地算出施加关节力矩后摄像头像素的分布。定价算法无法对所有可能的顾客反应做积分。LLM 无法枚举出 token 之后所有可能的续写。

你需要一个只需从环境采样的方法。跑策略,得到一条轨迹 s_0, a_0, r_1, s_1, a_1, r_2, …, s_T,用它来估计价值。这就是蒙特卡洛。

从 DP 到 MC,哲学上很重要的一跃:从「已知模型 + 精确回溯」走向「采样滚动 + 平均回报」。方差飙升,但适用性爆炸。本节之后的每个 RL 算法——TD、Q 学习、REINFORCE、PPO、GRPO——骨子里都是蒙特卡洛估计器,有的在上面叠了自举。

核心公式:一行话讲清

V^π(s) = E_π[G_t | s_t = s] ≈ (1/N) Σ_i G^{(i)}(s),其中 G^{(i)}(s) 是策略 π 下访问到 s 后观测到的回报。

首次访问 vs 每次访问

给定一条多次访问 s 的回合,首次访问 MC 只算第一次访问后的回报;每次访问 MC 算所有访问。两者极限下都无偏。首次访问更易分析(样本独立同分布);每次访问每回合用更多数据,实践中通常收敛更快。

增量均值:通往 TD 的跳板

不存所有回报,直接更新运行平均:

V_n(s) = V_{n-1}(s) + (1/n) [G_n - V_{n-1}(s)]

重排:V_new = V_old + α · (target - V_old),其中 α = 1/n。把 1/n 换成常数步长 α ∈ (0, 1),你就得到一个能跟踪 π 变化的非平稳 MC 估计器。这一步替换,就是从 MC 到 TD 再到所有现代 RL 的全部跳跃。

探索突然成了问题

DP 靠枚举触及每个状态。MC 只能看到策略访问到的状态。如果 π 是确定性的,整片状态空间永远采不到,它们的价值估计永远是零。三道解法,按历史顺序:

1. 探索性起点(Exploring Starts):每回合从随机 (s, a) 对出发。保证覆盖;但不现实(你不能把机器人「重置」到任意状态)。
2. ε-贪心(ε-greedy):对当前 Q 取贪心,但以概率 ε 选随机动作。所有「状态-动作」对渐近地都被采到。
3. 离策略 MC:在行为策略 μ 下收集数据,用重要性采样学习目标策略 π。方差大,但它是通往 DQN 那种经验回放池的桥。

蒙特卡洛控制

评估 → 改进 → 评估,和策略迭代一样,但评估是采样式的:

1. 跑 π,得到一回合。
2. 用观测回报更新 Q(s, a)。
3. 把 π 改成对 Q 的 ε-贪心。
4. 重复。

在温和条件下(每个对被无限次访问、α 满足 Robbins-Monro),以概率 1 收敛到 Q* 与 π*。

💡 MC 的妙处在于「无偏」:每条回报都是真实的 G_t,没有任何自举引入的偏差。代价是方差大——尤其在长回合上,结尾一个不走运的奖励会把 V(s_0) 整体推走。第 04 节的 TD 就是用一点偏差换巨大方差削减。

二、从零实现

Step 1:滚动 → (s, a, r) 列表

def rollout(env, policy, max_steps=200):
    trajectory = []
    s = env.reset()
    for _ in range(max_steps):
        a = policy(s)
        s_next, r, done = env.step(s, a)
        trajectory.append((s, a, r))
        s = s_next
        if done:
            break
    return trajectory
​

没有模型,只有 env.reset() 和 env.step(s, a)。和 gym 环境同接口,只是精简版。

Step 2:计算回报(反向扫一遍)

def returns_from(trajectory, gamma):
    returns = []
    G = 0.0
    for _, _, r in reversed(trajectory):
        G = r + gamma * G
        returns.append(G)
    return list(reversed(returns))
​

一遍过,O(T)。反向递推 G_t = r_{t+1} + γ G_{t+1} 避免重新求和。

Step 3:首次访问 MC 评估

def mc_policy_evaluation(env, policy, episodes, gamma=0.99):
    V = defaultdict(float)
    counts = defaultdict(int)
    for _ in range(episodes):
        trajectory = rollout(env, policy)
        returns = returns_from(trajectory, gamma)
        seen = set()
        for t, ((s, _, _), G) in enumerate(zip(trajectory, returns)):
            if s in seen:
                continue
            seen.add(s)
            counts[s] += 1
            V[s] += (G - V[s]) / counts[s]
    return V
​

三行做核心活:首次访问时标记、计数加一、更新运行均值。

Step 4:ε-贪心 MC 控制(同策略)

def mc_control(env, episodes, gamma=0.99, epsilon=0.1):
    Q = defaultdict(lambda: {a: 0.0 for a in ACTIONS})
    counts = defaultdict(lambda: {a: 0 for a in ACTIONS})

    def policy(s):
        if random() < epsilon:
            return choice(ACTIONS)
        return max(Q[s], key=Q[s].get)

    for _ in range(episodes):
        trajectory = rollout(env, policy)
        returns = returns_from(trajectory, gamma)
        seen = set()
        for (s, a, _), G in zip(trajectory, returns):
            if (s, a) in seen:
                continue
            seen.add((s, a))
            counts[s][a] += 1
            Q[s][a] += (G - Q[s][a]) / counts[s][a]
    return Q, policy
​

Step 5:与 DP 金标准对比

随着回合数 → ∞,你的 MC 估计 V^π 应当与第 02 节 DP 的结果一致。实践上:4×4 GridWorld 上 50000 回合,误差能控制在 ~0.1 以内。

三、框架对比

蒙特卡洛方法在 2026 年的角色:

现代深度 RL(PPO、SAC)在纯 MC(全回报)与纯 TD(单步自举)之间通过 n 步回报或 GAE 做插值。两个端点是同一个估计器的不同实例。

与 Gymnasium / 教学实现的对照

gymnasium 的 Blackjack-v1 是 MC 的经典教学环境:回合短(几手牌就结束)、回报稀疏(只在终局 ±1)、转移虽已知但用 MC 反而更直观——这正是 Sutton & Barto 第 5 章的开篇例子。把它和我们的 rollout + returns_from 套上,就是一个完整可跑的 MC 评估器。

四、可复用产物

本节产出一个可复用 skill(位于原课程 outputs/skill-mc-evaluator.md)。骨架:

---
name: mc-evaluator
description: 通过蒙特卡洛滚动评估策略,并产出带 DP 对比(若可用)的收敛报告。
version: 1.0.0
phase: 9
lesson: 3
tags: [rl, monte-carlo, evaluation]
---

给定一个环境(回合制、有 reset+step API)与一个策略,输出:

1. 方法。首次访问 vs 每次访问 MC。理由。
2. 回合预算。目标数、方差诊断、预期标准误。
3. 探索计划。ε 调度(若需要)或探索性起点。
4. 金标准对比。表格型则给 DP 最优 V*;否则给 Q 学习 / PPO 基线的界。
5. 终止检查。最大步数上限、超时、非终止轨迹的处理。

拒绝在无有限视野上限的非回合任务上跑 MC。
拒绝表格任务上每个状态少于 100 回合就报告 V^π 估计。
标记任何含零方差动作的策略为探索风险。
​

五、练习

1. 基础。 在 4×4 GridWorld 上,实现均匀随机策略的首次访问 MC 评估,跑 10000 回合。把 V(0,0) 作为回合数的函数画出来,叠上 DP 答案。
2. 进阶。 实现 ε-贪心 MC 控制,ε ∈ {0.01, 0.1, 0.3}。比较 20000 回合后的平均回报。曲线长什么样?偏差-方差权衡在哪里?
3. 挑战。 实现离策略 MC(带重要性采样):在均匀随机策略 μ 下收集数据,估计确定性最优策略 π 的 V^π。对比朴素 IS、按决策 IS、加权 IS。哪个方差最低?

六、常见陷阱

• 无限回合。 MC 要求回合终止。如果你的策略可能无限循环,就设 max_steps 上限,并把超时当隐式失败。GridWorld 配随机策略经常超时——正常,只要正确计数。
• 方差。 MC 用全回报。长回合上方差巨大——结尾一个不走运的奖励,会把 V(s_0) 同等幅度地推走。TD 方法(第 04 节)用自举削减它。
• 状态覆盖。 全新 Q 上跑贪心 MC,平局时只会试一个动作。必须探索(ε-贪心、探索性起点、UCB)。
• 非平稳策略。 若 π 在变(如 MC 控制),旧回报来自不同的策略。常数 α MC 能处理;样本均值 MC 不能。
• 离策略重要性采样。 权重 π(a|s)/μ(a|s) 在轨迹上连乘,方差随视野爆炸。用按决策加权 IS 封顶,或转向 TD。

本节要点回顾

1. MC 只需采样:无模型、无自举,从完整回合的平均回报估价值。
2. 首次访问 vs 每次访问:前者样本独立易分析,后者每回合用更多数据、实践中更快。
3. 增量均值 V += α(target - V) 是关键跳板:把 1/n 换成常数 α,就得到非平稳估计器——TD 与现代 RL 的起点。
4. 探索在 MC 里成了问题:DP 靠枚举覆盖,MC 只看策略走过的路;解法是探索性起点、ε-贪心、离策略 IS。
5. MC 控制 = 采样式策略迭代:跑回合 → 更新 Q → ε-贪心改进,温和条件下收敛到 Q*。
6. 方差大是核心痛点:全回报对长回合敏感,这是第 04 节 TD 要解决的。
7. 现代 RL 是 MC 与 TD 的插值:n 步回报、GAE 都在两者之间取折中。

下一节,我们让更新不再等回合结束——时间差分(TD)每走一步就自举更新,Q 学习与 SARSA 都从这里诞生。