# 蒙特卡洛方法

> 来源：https://dqn.cn/basics/monte-carlo ｜ 作者：DQN.CN 编辑部 ｜ 发布：2026-10-29 ｜ 更新：2026-10-30 ｜ 许可：CC BY-NC-SA 4.0（文字）/ MIT（代码）

> **要点速览**
>
> - 蒙特卡洛方法不需要环境模型，而是用完整回合的实际回报的平均值来估计价值函数。
> - MC 预测对每个状态的回报 G_t 求平均；MC 控制在估计 Q 值的同时用 ε-贪心等策略逐步改进。
> - 异策略 MC 用行为策略采样数据、通过重要性采样来评估或改进另一个目标策略。
> - MC 估计无偏但方差大，并且必须等回合结束才能更新，只适用于回合制任务。

蒙特卡洛（Monte Carlo，MC）方法**不需要环境模型**，而是通过采样完整回合、用实际得到的回报的平均值来估计价值函数。它是第一类真正“从经验中学习”的方法：估计是无偏的，但方差较大，并且只适用于回合制任务（必须等回合结束才能算出回报）。本节介绍 MC 预测、MC 控制，以及重要性采样在异策略学习中的作用，并在 21 点（Blackjack）上学出一个接近最优的策略。

## 动机：没有模型怎么办

[动态规划](https://dqn.cn/basics/dynamic-programming) 需要知道 $p(s', r \mid s, a)$。但很多问题中我们只能“玩”环境、观察结果，例如 21 点：给定当前点数，精确写出下一张牌带来的所有转移概率很繁琐，但模拟一局牌非常容易。

回忆价值函数的定义 $v_\pi(s) = \mathbb{E}_\pi[G_t \mid S_t = s]$。既然是期望，最直接的估计方式就是**采样求平均**：多次从 $s$ 出发按 $\pi$ 行动，记录每次得到的回报，取平均。由大数定律，样本均值收敛到期望。

## 蒙特卡洛预测

### 首次访问 MC 与每次访问 MC

一个回合中同一个状态可能被访问多次：

- **首次访问 MC**（first-visit）：每个回合只用状态 $s$ **第一次**出现之后的回报；
- **每次访问 MC**（every-visit）：$s$ 每次出现都用对应的回报。

两者都收敛到 $v_\pi(s)$。首次访问 MC 的各个样本相互独立，分析更简单；每次访问 MC 更容易推广到函数近似。

首次访问 MC 预测的伪代码：

```text
输入：待评估策略 π
初始化：V(s) 任意，Returns(s) ← 空列表
重复（对每个回合）：
    按 π 生成回合 S0, A0, R1, ..., S_{T-1}, A_{T-1}, R_T
    G ← 0
    对 t = T-1, T-2, ..., 0：
        G ← γG + R_{t+1}
        若 S_t 没有出现在 S0..S_{t-1} 中：
            把 G 加入 Returns(S_t)
            V(S_t) ← mean(Returns(S_t))
```

从后往前遍历可以用 $G \leftarrow \gamma G + R_{t+1}$ 递推地算出每一步的回报。

### 增量式均值更新

不必保存所有回报。设 $V_n$ 是前 $n$ 个回报的均值，则

$$
V_{n+1} = V_n + \frac{1}{n+1}\left(G_{n+1} - V_n\right)
$$

更一般地，用常数步长 $\alpha$ 代替 $\frac{1}{n}$：

$$
V(S_t) \leftarrow V(S_t) + \alpha\left[G_t - V(S_t)\right]
$$

这就是**常数步长 MC**。它给近期样本更大的权重，适合非平稳问题（策略在不断变化时就是非平稳的）。这个“新估计 = 旧估计 + 步长 × (目标 − 旧估计)”的形式会贯穿后面所有算法。

## 蒙特卡洛控制

预测之后，下一步是找最优策略（控制问题）。沿用 [GPI](https://dqn.cn/basics/dynamic-programming) 框架：评估 + 改进。

没有模型时，只知道 $v_\pi$ 无法做策略改进（需要一步前瞻，要用到模型），所以 MC 控制估计的是**动作价值** $q_\pi(s, a)$，改进时直接 $\pi(s) = \arg\max_a Q(s, a)$。

### 探索性起点

问题：如果策略是确定性的，很多 $(s, a)$ 永远不会被访问，它们的 $Q$ 无法估计。一种解决办法是**探索性起点**（exploring starts）：每个回合从随机的 $(s, a)$ 开始，保证所有状态—动作对都有机会被访问。但在真实环境中往往无法任意指定起点。

### ε-贪心策略

更实用的做法是使用**软策略**，例如 ε-贪心：

$$
\pi(a \mid s) =
\begin{cases}
1 - \varepsilon + \dfrac{\varepsilon}{|\mathcal{A}|}, & a = \arg\max_{a'} Q(s, a') \\[2mm]
\dfrac{\varepsilon}{|\mathcal{A}|}, & \text{其他}
\end{cases}
$$

可以证明，相对 $q_\pi$ 的 ε-贪心策略不差于原 ε-软策略（ε-软策略类中的策略改进定理）。因此“MC 评估 + ε-贪心改进”会收敛到**最优的 ε-软策略**。若让 ε 逐渐衰减到 0（GLIE 条件：无限探索、极限贪心），则收敛到真正的最优策略。

## 异策略蒙特卡洛

### 行为策略与目标策略

ε-贪心策略始终带有探索，学到的是“带探索的最优”。如果想在探索的同时学习**纯贪心**策略的价值，就需要区分两个策略：

- **目标策略** $\pi$：我们想评估和改进的策略（例如贪心策略）；
- **行为策略** $b$：实际用来与环境交互、产生数据的策略（例如 ε-贪心或随机策略）。

用 $b$ 的数据学习 $\pi$，称为**异策略**（off-policy）学习；$b = \pi$ 时称为**同策略**（on-policy）学习。

### 重要性采样

两个策略下轨迹出现的概率不同，需要用**重要性采样比**修正。从时刻 $t$ 到回合结束的比值为：

$$
\rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k \mid S_k)}{b(A_k \mid S_k)}
$$

注意环境转移概率在分子分母中相互抵消，所以**不需要知道模型**。于是

$$
\mathbb{E}_b\left[\rho_{t:T-1} G_t \mid S_t = s\right] = v_\pi(s)
$$

- **普通重要性采样**：$V(s) = \dfrac{\sum_{t \in \mathcal{T}(s)} \rho_{t:T-1} G_t}{|\mathcal{T}(s)|}$，无偏但方差可能无界；
- **加权重要性采样**：$V(s) = \dfrac{\sum_{t \in \mathcal{T}(s)} \rho_{t:T-1} G_t}{\sum_{t \in \mathcal{T}(s)} \rho_{t:T-1}}$，有偏（偏差随样本增加趋于 0），但方差小得多，实践中更常用。

覆盖性要求：凡是 $\pi(a \mid s) > 0$ 的动作，必须有 $b(a \mid s) > 0$。

## 代码：21 点（Blackjack）上的 MC 控制

Gymnasium 的 `Blackjack-v1` 中，状态是三元组（玩家点数、庄家明牌、玩家是否有可用的 A），动作为 0 停牌、1 要牌，赢 +1、平 0、输 −1，$\gamma = 1$。`sab=True` 使规则与 Sutton & Barto 书中例 5.1 一致。下面用首次访问、同策略、ε-贪心（$\varepsilon = 0.1$）的 MC 控制训练 50 万局，然后用贪心策略评估 10 万局。

```python
"""蒙特卡洛控制（首次访问、ε-贪心、同策略）：Blackjack-v1。"""
from collections import defaultdict

import gymnasium as gym
import numpy as np

env = gym.make("Blackjack-v1", sab=True)   # sab=True：与 Sutton & Barto 书中规则一致
nA = env.action_space.n                     # 0 = 停牌(stick)，1 = 要牌(hit)
Q = defaultdict(lambda: np.zeros(nA))
N = defaultdict(lambda: np.zeros(nA))       # 访问次数，用于增量式平均
gamma, epsilon = 1.0, 0.1
rng = np.random.default_rng(0)

def act(state, eps):
    if rng.random() < eps:
        return int(rng.integers(nA))
    return int(np.argmax(Q[state]))

for ep in range(500_000):
    # 1) 用当前 ε-贪心策略生成一个完整回合
    episode = []
    s, _ = env.reset(seed=ep)
    done = False
    while not done:
        a = act(s, epsilon)
        s2, r, term, trunc, _ = env.step(a)
        episode.append((s, a, r))
        s, done = s2, term or trunc

    # 2) 从后往前计算回报，首次访问时更新 Q
    G = 0.0
    first_visit = {}
    for t, (s, a, _) in enumerate(episode):
        first_visit.setdefault((s, a), t)
    for t in reversed(range(len(episode))):
        s, a, r = episode[t]
        G = gamma * G + r
        if first_visit[(s, a)] == t:
            N[s][a] += 1
            Q[s][a] += (G - Q[s][a]) / N[s][a]     # 增量式均值

def evaluate(policy_fn, episodes=100_000):
    total = 0.0
    for ep in range(episodes):
        s, _ = env.reset(seed=10_000_000 + ep)
        done = False
        while not done:
            s, r, term, trunc, _ = env.step(policy_fn(s))
            done = term or trunc
        total += r
    return total / episodes

greedy = lambda s: int(np.argmax(Q[s]))
naive = lambda s: 0 if s[0] >= 20 else 1     # 书中的“点数≥20 才停牌”策略
print(f"学到的贪心策略平均回报: {evaluate(greedy):+.4f}")
print(f"“≥20 停牌”策略平均回报: {evaluate(naive):+.4f}")
```
实际运行输出（耗时约 40 秒）：

```text
学到的贪心策略平均回报: -0.0453
“≥20 停牌”策略平均回报: -0.3493
```

21 点本身对玩家不利（庄家有优势），所以即使最优策略的期望回报也略小于 0。学到的策略平均每局只输约 0.045，远好于“点数 ≥ 20 才停牌”这种简单策略（每局输约 0.35）。

## MC 方法的优缺点

| 优点 | 缺点 |
| --- | --- |
| 不需要环境模型 | 只能用于回合制任务 |
| 估计无偏（不依赖其他状态的估计，即不自举） | 方差大，回合越长越明显 |
| 对马尔可夫性要求较低 | 必须等回合结束才能更新，学习慢 |
| 可以只评估感兴趣的状态 | 异策略版本的重要性采样比连乘后方差很大 |

## 常见误区

- **用 ε-贪心评估学到的策略**：评估时应使用贪心策略，否则测到的是“带探索的”表现。
- **忘记从后往前计算回报**：从前往后需要重复求和，复杂度变为 $O(T^2)$。
- **重要性采样比忘记连乘到回合结束**：$\rho$ 是从当前时刻一直乘到回合结束。
- **以为 MC 不适合大状态空间**：MC 本身与状态数无关，配合函数近似同样可以使用；REINFORCE（[策略梯度](https://dqn.cn/advanced/reinforce)）就使用了 MC 回报。

## 小结

- MC 用采样回报的平均值估计价值，无需模型、无偏、方差大。
- MC 控制估计 $Q(s, a)$，用 ε-贪心保证探索，遵循 GPI 框架。
- 异策略 MC 用重要性采样修正分布差异，加权重要性采样方差更小。
- MC 必须等回合结束；下一节的 TD 学习将解决这个问题。

## 练习题

1. 把例题改为每次访问 MC，比较最终策略的平均回报。
2. 把 $\varepsilon$ 改为 0.3 和 0.01，最终贪心策略的表现如何变化？
3. 打印学到的策略：在“无可用 A”的情况下，玩家点数为多少时选择停牌？与 Sutton & Barto 图 5.2 对比。
4. 证明普通重要性采样估计是无偏的。
5. 用常数步长 $\alpha = 0.01$ 代替样本均值，训练曲线和最终结果有何不同？

## 参考文献

- Sutton, R. S., & Barto, A. G. (2018). *Reinforcement Learning: An Introduction* (2nd ed.), 第 5 章.
- Singh, S. P., & Sutton, R. S. (1996). Reinforcement learning with replacing eligibility traces. *Machine Learning*, 22, 123–158.（首次访问与每次访问 MC 的分析）

## 下一步

继续阅读：[时序差分（TD）学习](https://dqn.cn/basics/td-learning)——不必等回合结束，每一步都能更新。

## 常见问题速查（FAQ）

**问：蒙特卡洛方法和动态规划有什么区别？**

答：DP 需要已知的转移模型并做自举（用估计值更新估计值）；MC 不需要模型，用真实采样的完整回报，不做自举。

**问：首次访问 MC 和每次访问 MC 有什么区别？**

答：首次访问 MC 只使用每个回合中某状态第一次出现之后的回报；每次访问 MC 使用该状态每次出现后的回报。两者在样本足够多时都收敛到真实价值。

**问：重要性采样为什么会导致高方差？**

答：重要性权重是多步概率比的乘积，回合越长、两个策略差异越大，权重的波动就越大，可能出现极端值。加权重要性采样可以显著降低方差。

## 如何引用本文

DQN.CN 编辑部. 蒙特卡洛方法[EB/OL]. DQN.CN, 2026-10-29（更新于 2026-10-30）. https://dqn.cn/basics/monte-carlo.