本文章没有找到对应的语言版本

零、写在前面

之前的动态规划法（DP）假设智能代理能直接使用环境模型：给定状态和行动，就能查询后继状态、奖励或其概率分布。因此它可以枚举所有一步分支，并做 Bellman backup。

本章主动不让学习算法查询 $p(s'\mid s,a)$ 和 $r(s,a,s')$。环境客观上仍可能有这些规律，甚至代码中的环境对象内部也会实现它们；但代理只允许真的执行行动、等待环境给出一段经历。一次经历结束后，代理从中得到一个完整收益 $G_t$；许多次经历的平均，才逐渐逼近价值函数：

$$ \underbrace{ v_\pi(s) =\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a) \left[r(s,a,s')+\gamma v_\pi(s')\right] }_{\text{DP：已知模型，对所有一步分支求期望}} \quad\Longrightarrow\quad \underbrace{ v_\pi(s) \approx \frac{1}{N(s)}\sum_{i=1}^{N(s)}G_t^{(i)} }_{\text{MC：未知模型，对完整经历的回报样本取平均}}. $$

这就是**蒙特卡洛方法（Monte Carlo, MC）**的核心。它不是“猜一个价值”，而是把真实交互中已经发生的完整回报，当作随机变量的样本来做统计估计。

一、蒙特卡洛方法的基础知识

如果知道完整概率分布，可以直接求期望；如果不知道或不想列出完整分布，但可以不断抽样，也可以用平均值逼近期望。

1.1 骰子的点数和：已知分布时怎样算期望

掷两个公平六面骰子，共有 $6\times6=36$ 个等概率的有序结果。点数和为 $2,3,\ldots,12$ 的组合数依次为：

image.png

image.png

若随机变量 $X$ 表示点数和，期望按“数值乘概率，再全部相加”定义：

$$ \mathbb E[X] =\sum_{x=2}^{12}x\,p(x) =7. $$

1.2 分布模型与样本模型

模型 持有的信息 能做什么 两骰子例子
分布模型 每个结果及其概率 直接求 $\sum_x xp(x)$ 明确存储 2–12 及其概率
样本模型 只要能按正确规律产生样本 重复采样、统计样本均值 真的“掷骰子”并观察一次点数和

image.png

写个脚本模拟下，顺手计算均值：

import numpy as np

def sample(dices=2):
    x = 0
    for _ in range(dices):
        x += np.random.choice([1, 2, 3, 4, 5, 6])
    return x

trival = 1000
V = n = 0

for _ in range(trival):
    s = sample()
    n += 1
    # nv = (s1 + s2 + ... + sn) / n = v * (n-1)/n + sn/n
    # v += (s-v)/n
    V += (s - V) / n
    print(V)

最终结果：

6.986999999999994

我们大可以模拟10个骰子的情况，但会有 $6^{10}=60\,466\,176$ 种组合。若目标只是估计均值，能够快速产生一个正确样本，往往比显式建造整个分布实用得多。

二、使用蒙特卡洛方法评估策略

骰子样本的平均能估计骰子均值；同样，从某个状态开始的一条完整 episode 所产生的收益样本，能估计该状态在策略 $\pi$ 下的价值。

2.1 使用蒙特卡洛方法计算价值函数：把“骰子样本”换成“回报样本”

回顾状态价值的定义：

$$ v_\pi(s) =\mathbb E_\pi\left[G_t\mid S_t=s\right]. \tag{L5.3} $$

对于在时刻 $T$ 终止的回合，完整收益为：

$$ G_t =R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-t-1}R_T. \tag{L5.4} $$

如果每次从状态 $s$ 出发、按固定策略 $\pi$ 走到终点，就会得到一组 $G_t^{(1)},G_t^{(2)},\ldots$。MC 策略评估的目标是：

$$ \boxed{ V_n(s) =\frac{1}{n}\sum_{i=1}^{n}G_t^{(i)} \ \longrightarrow\ v_\pi(s) }. \tag{L5.5} $$

即，通过多轮采样，去估计我们的价值函数。

以下图为例，策略和状态迁移都是随机的：

image.png

第一次经历的奖励为 $1,0,2$，因此 $G^{(1)}=3$；第二次经历的奖励为 $0,0,1,1$，因此 $G^{(2)}=2$。两条完整经历之后的估计是：

$$ V_2(s)=\frac{3+2}{2}=2.5. $$

值得注意的是，普通 MC 方法只处理回合制任务。

Q：为什么 普通 MC 只处理回合制任务？

A：

式 (L5.4) 要在终点出现后才知道全部奖励，所以普通 MC 必须等待 episode 结束。连续性任务没有天然终点，不能直接拿到一个完整的 $G_t$ 样本；这正是下一章 TD 方法要解决的问题。

2.2 求所有状态的价值函数：一条轨迹怎样估计多个状态

image.png

上图只能应用于可以从任意状态开始的问题。如，在 游戏或基于模拟器的问题中，智能代理可能会从任意位置开始。但对 于现实生活中的问题，从任意位置开始几乎是不可能的。

如果有3个状态：A、B、C，那么我们可以像之前那样算出每个状态的价值函数。

image.png

但其实不必为每个状态单独重开一个 episode。设一条回合依次经历 $A\to B\to C\to\text{terminal}$，即时奖励依次为 $R_1,R_2,R_3$。那么同一条经历同时给出：

$$ \begin{aligned} G_A&=R_1+\gamma R_2+\gamma^2R_3,\\ G_B&=R_2+\gamma R_3,\\ G_C&=R_3. \end{aligned} \tag{L5.6} $$

因此，一次 episode 不是只有一个训练样本，而是为它经过的每个状态都提供一个“从这里往后的后缀回报”。

通过这样的计算，我们仅从一次实验就获得了 3 个状态的 收益（样本数据）。

2.3 蒙特卡洛方法的高效实现：倒序计算所有后缀回报

因为这是一个dag，我们倒着递推显然效率最高。

$$ \boxed{G_t=R_{t+1}+\gamma G_{t+1}}. \tag{L5.7} $$

因此应从终点往前扫描：

G = 0                         # 终止状态之后没有未来奖励
从最后一次转移倒序到第一次：
    G = reward + gamma * G
    用 G 更新该状态（或状态—行动对）的均值

这一递推的形式看起来像第 3 章的 $G_t=R_{t+1}+\gamma G_{t+1}$，但其实还是不同的。因为这里的右侧 G 已经由同一条、已经结束的轨迹的真实后续奖励完全算出；其中没有拿当前 V[next_state] 或 Q[next_state, ...] 来充当目标。

三、蒙特卡洛方法的实现

我们尝试使用蒙特卡洛方法解决之前的 3x4 网格世界问题。

image.png

3.1 智能代理类的实现：RandomAgent 的固定策略 MC 评估

接下来实现使用蒙特卡洛方法评估策略的智能代理。假设该智能代理 按照随机性策略采取行动。

class RandomAgent:
    def __init__(self):
        self.gamma = 0.9
        self.action_size = 4

        random_actions = {0: 0.25, 1: 0.25, 2: 0.25, 3: 0.25}
        self.pi = defaultdict(lambda: random_actions)
        self.V = defaultdict(lambda: 0)
        self.cnts = defaultdict(lambda: 0)
        self.memory = []

    def get_action(self, state):
        action_probs = self.pi[state]
        actions = list(action_probs.keys())
        probs = list(action_probs.values())
        return np.random.choice(actions, p=probs)

    def add(self, state, action, reward):
        data = (state, action, reward)
        self.memory.append(data)

    def reset(self):
        self.memory.clear()

    def eval(self):
        G = 0
        for data in reversed(self.memory):
            state, action, reward = data
            G = self.gamma * G + reward
            self.cnts[state] += 1
            self.V[state] += (G - self.V[state]) / self.cnts[state]

一次 episode 中得到的时间序列可写为：

$$ S_0,A_0,R_1,S_1,A_1,R_2,\ldots,S_{T-1},A_{T-1},R_T,S_T. $$

代码只保存每次行动对应的三元组：

[(S0, A0, R1), (S1, A1, R2), ..., (S(T-1), A(T-1), RT)]

而终止状态 $S_T$ 不在 memory 中。原因不是它没有发生，而是对它不需再估计后续价值。

策略评估在 eval()：

def eval(self):
    G = 0
    for data in reversed(self.memory):
        state, action, reward = data
        G = self.gamma * G + reward
        self.cnts[state] += 1
        self.V[state] += (G - self.V[state]) / self.cnts[state]

3.2 运行蒙特卡洛方法 

env = GridWorld()
agent = RandomAgent()

episodes = 1000
for episode in range(episodes):
    state = env.reset()
    agent.reset()

    while True:
        action = agent.get_action(state)
        next_state, reward, done = env.step(action)

        agent.add(state, action, reward)
        if done:
            agent.eval()
            break

        state = next_state

env.render_v(agent.V)

image.png

对比之前动态规划法的评估结果：

image-20260723154750323

动态规划法的结果是正确的，不过其与使用蒙特卡洛 方法的结果基本相同。

四、使用蒙特卡洛方法的策略控制

策略评估回答“当前策略有多好”；策略控制回答“怎样得到更好的策略”。

4.1 评估和改进：为什么无模型控制要学习 $Q(s,a)$

若已知模型，从状态价值 $V$ 可以用下面的式子比较行动：

$$ \mu(s) =\arg\max_a\sum_{s'}p(s'\mid s,a) \left[r(s,a,s')+\gamma V(s')\right]. \tag{L5.8} $$

但式 (L5.8) 正需要未知的 $p,r$，不能用于本章的无模型设定。解决办法是直接估计行动价值：

$$ q_\pi(s,a) =\mathbb E_\pi\left[G_t\mid S_t=s,A_t=a\right]. \tag{L5.9} $$

对每个状态—行动对收集完整回报样本，就能把状态价值的平均式平移到 $Q$ 上：

$$ \boxed{ Q_n(s,a) =Q_{n-1}(s,a) +\frac{G^{(n)}-Q_{n-1}(s,a)}{n} }. \tag{L5.10} $$

一旦有了 $Q(s,a)$，贪婪改进不需要模型：

$$ \boxed{\mu(s)=\arg\max_a Q(s,a)}. \tag{L5.11} $$

这里 max 返回最大的数值，argmax 返回达到最大值的行动。策略控制需要的是行动，所以讲义式 (L5.11) 是 argmax。

4.2 使用蒙特卡洛方法实现策略控制：完全贪婪为什么不够

一开始所有 $Q(s,a)$ 常被初始化为 0。若每次都选当前最大值，程序会因并列规则偏向少数行动；一旦走出一条路径，就可能再也不收集其他行动的回报。

这会形成一个循环：

没有尝试过的行动 -> 没有 Q 样本 -> Q 仍是初始化值
    -> 不会被选中 -> 永远没有机会证明自己更好

所以策略改进不能只“利用”（exploitation）当前看起来最好的行动，还要保留“探索”（exploration）其他行动的机会。

4.3 ε-greedy（第 1 个修改）

令 $ a^* $ 是一个当前贪婪行动。对有 $|\mathcal A|$ 个行动的环境，然后构建一个 ε-greedy 分布：

image.png

即，将所有行动 的概率设为 ε/4 ，然后为 Q 函数值最大的行动增加 1−ε 的概率

image.png

对应代码为：

def greedy_probs(Q, state, epsilon=0, action_size=4):
    qs = [Q[(state, action)] for action in range(action_size)]
    max_action = np.argmax(qs)

    base_prob = epsilon / action_size
    action_probs = {action: base_prob for action in range(action_size)}
    action_probs[max_action] += (1 - epsilon)
    return action_probs

4.4 修改为固定值 $\alpha$ 的方式（第 2 个修改）

对固定策略做评估时，所有回报都来自同一个概率分布，样本均值会公平地给每条历史样本 $1/n$ 权重。策略控制中却在不断修改策略，回报的产生分布也随之变化。

我们把式 (L5.10) 的样本均值更新替换为：

$$ \boxed{ Q(s,a)\leftarrow Q(s,a)+\alpha\left[G-Q(s,a)\right] }. \tag{L5.13} $$

其中 $0<\alpha\le1$ 为固定步长。展开多次更新可看出较新的样本权重更大：

$$ Q_n =(1-\alpha)^nQ_0 +\sum_{i=1}^{n}\alpha(1-\alpha)^{n-i}G^{(i)}. \tag{L5.14} $$

修改前和修改后的 方式的区别：

image.png

4.5 [修改版] 使用蒙特卡洛方法实现策略迭代法 

def greedy_probs(Q, state, epsilon=0, action_size=4):
    qs = [Q[(state, action)] for action in range(action_size)]
    max_action = np.argmax(qs)

    base_prob = epsilon / action_size
    action_probs = {action: base_prob for action in range(action_size)}  #{0: ε/4, 1: ε/4, 2: ε/4, 3: ε/4}
    action_probs[max_action] += (1 - epsilon)
    return action_probs


class McAgent:
    def __init__(self):
        self.gamma = 0.9
        self.epsilon = 0.1
        self.alpha = 0.1
        self.action_size = 4

        random_actions = {0: 0.25, 1: 0.25, 2: 0.25, 3: 0.25}
        self.pi = defaultdict(lambda: random_actions)
        self.Q = defaultdict(lambda: 0)
        self.memory = []

    def get_action(self, state):
        action_probs = self.pi[state]
        actions = list(action_probs.keys())
        probs = list(action_probs.values())
        return np.random.choice(actions, p=probs)

    def add(self, state, action, reward):
        data = (state, action, reward)
        self.memory.append(data)

    def reset(self):
        self.memory.clear()

    def update(self):
        G = 0
        for data in reversed(self.memory):
            state, action, reward = data
            G = self.gamma * G + reward
            key = (state, action)
            self.Q[key] += (G - self.Q[key]) * self.alpha
            self.pi[state] = greedy_probs(self.Q, state, self.epsilon)

跑一下：

env = GridWorld()
agent = McAgent()

episodes = 10000
for episode in range(episodes):
    state = env.reset()
    agent.reset()

    while True:
        action = agent.get_action(state)
        next_state, reward, done = env.step(action)

        agent.add(state, action, reward)
        if done:
            agent.update()
            break

        state = next_state

env.render_q(agent.Q)

结果：

image.png

image.png

从 Q 函数中得到的贪婪策略产生的结果接近于最优策略。 其实智能代理也是通过 ε-greedy 在每个方格中采取随机行动的，但由于大多数行动是贪婪的，因此这种策略也基本能得到好的结果。以上就是对蒙特卡洛策略控制的实现。

五、异策略型和重要性采样

5.1 同策略型与异策略型

类型 目标策略 行为策略 本章代码
同策略型（on-policy） $\pi$ $b=\pi$ mc_control.py 的 self.pi 既取行动又被更新
异策略型（off-policy） $\pi$ $b\ne\pi$ mc_control_offpolicy.py 用 self.b 取行动，用 self.pi 做目标

**目标策略（target policy）**是我们要评估、改进或最终部署的策略；

**行为策略（behaviour policy）**是实际与环境交互、产生 $(s,a,r)$ 样本的策略。

异策略的动机很直观：

行为策略 b：保持 ε-greedy，负责探索并收集覆盖较广的数据
目标策略 π：可以完全贪婪，负责表示“目前真正想利用的策略”

但从 $b$ 得到的样本本来反映的是 $b$ 的期望，不是 $\pi$ 的期望。要拿它估计 $\pi$，必须进行概率校正。

5.2 重要性采样：用 $b$ 的样本算 $\pi$ 的期望

对离散随机变量 $X$，目标是：

$$ \mathbb E_\pi[X] =\sum_x x\pi(x). $$

只要行为分布在目标分布可能出现的地方不为 0，即

$$ b(x)>0\quad\text{whenever}\quad\pi(x)>0, \tag{L5.15} $$

就可插入 $b(x)/b(x)=1$：

$$ \begin{aligned} \mathbb E_\pi[X] &=\sum_xx\frac{\pi(x)}{b(x)}b(x)\\ &=\mathbb E_b\left[\rho(X)X\right], \qquad \rho(x)=\frac{\pi(x)}{b(x)}. \end{aligned} \tag{L5.16} $$

于是，用 $b$ 抽取的 $x^{(1)},\ldots,x^{(n)}$ 可组成普通重要性采样估计：

$$ \hat{\mathbb E}_\pi[X] =\frac{1}{n}\sum_{i=1}^{n}\rho\left(x^{(i)}\right)x^{(i)}. \tag{L5.17} $$

b(x)>0 这个覆盖条件不可省略：若目标策略想选择的行动在行为策略下概率为 0，既没有样本可看，$\pi/b$ 也会除以 0。异策略强化学习中常让 $b$ 保持 $\varepsilon$-greedy，正是为了避免此问题。

分别用 MC 方法 和 IS方法来测试一下，对于同一个样例，二者计算结果如何：

import numpy as np

x = np.array([1, 2, 3])
pi = np.array([0.1, 0.1, 0.8])

# =========== Expectation ==================
e = np.sum(x * pi)
print('E_pi[x]', e)

# =========== Monte Carlo ==================
n = 100
samples = []
for _ in range(n):
    s = np.random.choice(x, p=pi)
    samples.append(s)
print('MC: {:.2f} (var: {:.2f})'.format(np.mean(samples), np.var(samples)))

# =========== Importance Sampling ===========
b = np.array([1/3, 1/3, 1/3])
samples = []
for _ in range(n):
    idx = np.arange(len(b))  # [0, 1, 2]
    i = np.random.choice(idx, p=b)
    s = x[i]
    rho = pi[i] / b[i]
    samples.append(rho * s)
print('IS: {:.2f} (var: {:.2f})'.format(np.mean(samples), np.var(samples)))

结果：

E_pi[x] 2.7
MC: 2.70 (var: 0.41)
IS: 2.41 (var: 9.38)

我们发现 IS 的方差太大了。

5.3 如何减小方差：重要性采样不代表省样本

简单解释一下为啥 IS 结果的方差会大：

image.png

在目标分布中，3 出现概率要大一点，但是我们抽样的分布b中 3的概率要低一点，为了修正，这里 ρ 会偏大，使得 3 拉到了 7.2 这个更大的值，所以方差会变大。

一个想法是让 b 更接近 $\pi$：

//...

# =========== Importance Sampling ===========
# b = np.array([1/3, 1/3, 1/3])
b = np.array([0.2, 0.2, 0.6]) 
samples = []
for _ in range(n):
    idx = np.arange(len(b))  # [0, 1, 2]
    i = np.random.choice(idx, p=b)
    s = x[i]
    rho = pi[i] / b[i]
    samples.append(rho * s)
print('IS: {:.2f} (var: {:.2f})'.format(np.mean(samples), np.var(samples)))

输出：

E_pi[x] 2.7
MC: 2.63 (var: 0.47)
IS: 2.46 (var: 2.72)

这个问题的处理有很多策略，这里就不过多讨论了。

六、小结

本章完成了从“已知模型的规划”到“真实经验的学习”的第一步。

本章问题 本章答案
没有 $p,r$，怎样估计价值？ 收集完整 episode 的真实回报，取样本平均
怎样高效计算一条轨迹所有状态的回报？ 从终点反向递推 $G_t=R_{t+1}+\gamma G_{t+1}$
无模型时怎样改进策略？ 估计 $Q(s,a)$，再对 $Q$ 做贪婪或 $\varepsilon$-greedy 改进
为什么不完全贪婪？ 否则未尝试行动没有样本，无法探索
为什么固定 $\alpha$ 有意义？ 控制中策略变化，使回报分布对学习者而言非稳态
怎样用别的策略的数据学习目标策略？ 通过 $\rho=\pi/b$ 的重要性采样校正分布

但MC方法只适用于回合制问题，对于连续型问题怎么办呢？后面的TD方法会给出答案。

说些什么吧！

giscus