AI 原生开放教材

外观

AI 工程从零到一（中文）源码研读·中文原文 ↗原件 ↓仓库 ↗

蒙特卡洛方法 —— 从完整 episode 中学习 ​

动态规划需要模型。蒙特卡洛什么都不需要，只要 episode。跑策略，看回报，求平均。这是 RL 里最简单的想法——也是解锁后续一切的那个。

类型： Build 语言： Python 前置要求： Phase 9 · 01（MDP）、Phase 9 · 02（动态规划） 预计时间： ~75 分钟

问题背景 ​

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

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

从 DP 到 MC 的转变在哲学上很重要：我们从已知模型 + 精确回溯走到了采样 rollout + 平均回报。方差猛增，但适用范围爆炸式扩大。这一课之后的每个 RL 算法——TD、Q-learning、REINFORCE、PPO、GRPO——本质上都是一个蒙特卡洛估计器，有时上面叠了一层自举。

核心概念 ​

Monte Carlo: rollout, compute returns, average; first-visit vs every-visit

核心想法，一行说清： V^π(s) = E_π[G_t | s_t = s] ≈ (1/N) Σ_i G^\{(i)\}(s)，其中 G^\{(i)\}(s) 是策略 π 下访问 s 之后观测到的回报。

首次访问 vs 每次访问 MC。 给定一个多次访问状态 s 的 episode，首次访问 MC 只统计第一次访问之后的回报；每次访问 MC 统计所有访问。两者在极限下都是无偏的。首次访问更好分析（iid 样本）。每次访问每个 episode 用了更多数据，实践中通常收敛更快。

增量均值。 不存所有回报，而是更新滑动平均：

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. 探索性起点。 让每个 episode 从一个随机的 (s, a) 对开始。保证覆盖；实践中不现实（你没法把机器人"重置"到一个任意状态）。
  2. ε-greedy。 对当前 Q 贪心地行动，但以概率 ε 挑一个随机动作。渐进地让所有状态-动作对都被采样到。
  3. 离策略 MC。 在行为策略 μ 下收集数据，通过重要性采样学习目标策略 π。方差很高，但它是通往 DQN 这类回放缓冲方法的桥梁。

蒙特卡洛控制。 评估 → 改进 → 评估，跟策略迭代一样，只是评估是基于采样的：

  1. 跑 π，拿到一个 episode。
  2. 用观测到的回报更新 Q(s, a)。
  3. 让 π 对 Q 做 ε-greedy。
  4. 重复。

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

figure
epsilon-greedy

动手构建 ​

第 1 步：rollout → (s, a, r) 列表 ​

python
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 环境一样的接口，只是精简了。

第 2 步：计算回报（反向扫描） ​

python
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\} 避免了重复求和。

第 3 步：首次访问 MC 评估 ​

python
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

干活的就三行：首次访问时把状态标记为已见，递增计数，更新滑动均值。

第 4 步：ε-greedy MC 控制（同策略） ​

python
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

第 5 步：和 DP 黄金标准对比 ​

当 episode → ∞ 时，你对 V^π 的 MC 估计应该和第 02 课的 DP 结果一致。实践中：在 4×4 GridWorld 上跑 50000 个 episode，你就能落在 DP 答案 ~0.1 以内。

注意事项 ​

  • 无限 episode。 MC 要求 episode 能终止。如果你的策略可能永远循环，就给 max_steps 封顶，并把封顶当成隐式失败。GridWorld 配随机策略经常超时——这很正常，只要确保你计数正确。
  • 方差。 MC 用完整回报。在长 episode 上方差巨大——末尾一个倒霉奖励就能让 V(s_0) 偏移同样的量。TD 方法（第 04 课）靠自举削掉这部分。
  • 状态覆盖。 对一个全新的、有并列的 Q 做贪心 MC，永远只会试一个动作。你必须探索（ε-greedy、探索性起点、UCB）。
  • 非平稳策略。 如果 π 在变（如 MC 控制中），旧回报来自一个不同的策略。常数-α MC 能处理这个；样本平均 MC 不行。
  • 离策略重要性采样。 权重 π(a|s)/μ(a|s) 沿一条轨迹连乘。方差随视野爆炸。用逐决策加权 IS 封顶，或者改用 TD。

实际使用 ​

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

用途为什么用 MC
短视野游戏（21 点、扑克）episode 自然终止；回报干净。
对一个已记录策略做离线评估对存下来的轨迹求折扣回报的平均。
蒙特卡洛树搜索（AlphaZero）从树叶出发的 MC rollout 指导选择。
LLM RL 评估对给定策略，计算采样补全的平均奖励。
PPO 里的基线估计优势目标 A_t = G_t - V(s_t) 用了一个 MC G_t。
教 RL唯一真正能跑通的最简单算法——剥掉自举来看清核心。

现代深度 RL 算法（PPO、SAC）通过 n-步回报或 GAE，在纯 MC（完整回报）和纯 TD（单步自举）之间做插值。两个端点都是同一个估计器的实例。

拿去用 ​

存为 outputs/skill-mc-evaluator.md：

markdown
---
name: mc-evaluator
description: Evaluate a policy via Monte Carlo rollouts and produce a convergence report with DP-comparison if available.
version: 1.0.0
phase: 9
lesson: 3
tags: [rl, monte-carlo, evaluation]
---

Given an environment (episodic, with reset+step API) and a policy, output:

1. Method. First-visit vs every-visit MC. Reason.
2. Episode budget. Target number, variance diagnostic, expected standard error.
3. Exploration plan. ε schedule (if needed) or exploring starts.
4. Gold-standard comparison. DP-optimal V* if tabular; otherwise a bound from a Q-learning / PPO baseline.
5. Termination check. Max-step cap, timeouts, handling of non-terminating trajectories.

Refuse to run MC on non-episodic tasks without a finite horizon cap. Refuse to report V^π estimates from fewer than 100 episodes per state for tabular tasks. Flag any policy with zero-variance actions as an exploration risk.

练习 ​

  1. 简单。 在 4×4 GridWorld 上实现对均匀随机策略的首次访问 MC 评估。跑 10000 个 episode。把 V(0,0) 随 episode 数的变化画出来，和 DP 答案对照。
  2. 中等。 实现 ε-greedy MC 控制，ε ∈ \{0.01, 0.1, 0.3\}。对比 20000 个 episode 后的平均回报。曲线长什么样？偏差-方差权衡落在哪里？
  3. 困难。 实现带重要性采样的离策略 MC：在均匀随机策略 μ 下收集数据，为确定性最优策略 π 估计 V^π。对比朴素 IS、逐决策 IS、加权 IS。哪个方差最低？

关键术语 ​

术语大家嘴上怎么说它实际是什么
蒙特卡洛"随机采样"通过对分布的 iid 样本求平均来估计期望。
回报 G_t"未来奖励"从第 t 步到 episode 结束的折扣奖励和：Σ_\{k≥0\} γ^k r_\{t+k+1\}。
首次访问 MC"每个状态只数一次"一个 episode 里只有首次访问对价值估计有贡献。
每次访问 MC"用上所有访问"每次访问都有贡献；略有偏差但样本效率更高。
ε-greedy"探索噪声"以概率 1-ε 选贪心动作；以概率 ε 选随机动作。
重要性采样"修正从错误分布采样的偏差"用 `π(a
同策略"从我自己的数据里学"目标策略 = 行为策略。原版 MC、PPO、SARSA。
离策略"从别人的数据里学"目标策略 ≠ 行为策略。重要性采样 MC、Q-learning、DQN。

延伸阅读 ​