蒙特卡洛方法

一句话总结 · 要点速览

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

术语不熟悉？查看 强化学习术语表。

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

动机：没有模型怎么办

动态规划 需要知道 $p(s^{\prime },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 预测的伪代码：

输入：待评估策略 π
初始化：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}(G_{n+1}-V_n)$$

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

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

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

蒙特卡洛控制

预测之后，下一步是找最优策略（控制问题）。沿用 GPI 框架：评估 + 改进。

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

探索性起点

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

ε-贪心策略

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

$$\pi (a\mid s)=\{\begin{array}{ll}1-\epsilon +{\displaystyle \frac{\epsilon }{|\mathcal{A}|}},& a=\arg \underset{a^{\prime }}{max}Q(s,a^{\prime })\\ {\displaystyle \frac{\epsilon }{|\mathcal{A}|}},& \text{其他}\end{array}$$

可以证明，相对 $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[{\rho }_{t:T-1}{G}_t\mid S_t=s]=v_{\pi }(s)$$

• 普通重要性采样：$V(s)={\displaystyle \frac{\sum _{t\in \mathcal{T}(s)}{\rho }_{t:T-1}{G}_t}{|\mathcal{T}(s)|}}$，无偏但方差可能无界；
• 加权重要性采样：$V(s)={\displaystyle \frac{\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 一致。下面用首次访问、同策略、ε-贪心（$\epsilon =0.1$）的 MC 控制训练 50 万局，然后用贪心策略评估 10 万局。

"""蒙特卡洛控制（首次访问、ε-贪心、同策略）：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 秒）：

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

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

MC 方法的优缺点

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

常见误区

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

小结

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

练习题

1. 把例题改为每次访问 MC，比较最终策略的平均回报。
2. 把 $\epsilon$ 改为 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）学习——不必等回合结束，每一步都能更新。