《强化学习的数学原理》【学习笔记05】蒙特卡罗方法：从经验中学习

《强化学习的数学原理》赵世钰 著 · 第 5 章

第 4 章的算法需要知道环境的转移概率 $p$ 和奖励 $r$（model-based）。现实中我们往往不知道——只能通过实际交互获得样本。蒙特卡罗方法就是"纯靠经验"学习的方法。

一、期望值估计：蒙特卡罗的核心思想

基本思想

要估计随机变量 $X$ 的期望 $\mathbb{E}[X]$，采样 $N$ 个样本 $x_1, x_2, \ldots, x_N$，用样本均值估计：

$$\mathbb{E}[X] \approx \frac{1}{N} \sum_{i=1}^{N} x_i$$

由大数定律，当 $N \to \infty$ 时，样本均值收敛到真实期望。

与第 4 章的本质区别：第 4 章用 $p(s'|s,a)$ 计算期望，本章用采样估计期望。不需要知道 $p$ 的具体值，只需要能从环境中获得样本。

二、MC Basic：最简单的蒙特卡罗算法

从策略迭代到无模型

回顾策略迭代的两个步骤：

1. 策略评估：算 $v_\pi(s) = \mathbb{E}[G_t | S_t = s]$
2. 策略改进：$\pi'(s) = \arg\max_a q_\pi(s, a)$

无模型版本的关键改动：

• 策略评估：不用 $p$ 计算，而是从状态 $s$ 出发跑很多回合，用平均回报估计 $v_\pi(s)$
• 策略改进：需要 $q_\pi(s, a)$ 而不是 $v_\pi(s)$，因为不知道 $p$ 就不能从 $v$ 算 $q$

MC Basic 算法

初始化: 任意策略 π, q(s,a) = 0
重复:
    # 策略评估
    对每个 (s, a) 对:
        从 s 出发，强制执行 a，之后遵循 π，跑 N 个回合
        q(s,a) = N 个回合的回报均值
    
    # 策略改进
    π(s) = argmax_a q(s, a)
    
直到: π 不再变化

问题：MC Basic 需要对每个 $(s, a)$ 对都跑 $N$ 个回合，效率极低。但它是最容易理解的蒙特卡罗算法，后续算法都是对它的优化。

三、MC Exploring Starts：更高效地利用样本

问题

MC Basic 中，每个 $(s, a)$ 对独立采样，不同 $(s, a)$ 的回合不共享数据。

改进：利用回合内所有状态

一条回合轨迹 $S_0, A_0, R_1, S_1, A_1, \ldots, S_T$ 中，每个被访问到的 $(S_t, A_t)$ 都可以贡献一个回报样本：

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

这叫 every-visit 估计。或者只用首次访问（first-visit），避免同一回合中同一状态被重复使用。

Exploring Starts 条件

为了保证所有 $(s, a)$ 对都能被采样到，需要 exploring starts：每个回合的初始状态-动作随机选择，覆盖所有可能。

为什么需要 Exploring Starts？ 如果某个 $(s, a)$ 从未被访问，我们就不知道它的 $q$ 值，策略改进就可能出错。这是"探索"问题的雏形。

四、MC ε-Greedy：更实用的探索策略

ε-Greedy 策略

$$\pi(a|s) = \begin{cases} 1 - \epsilon + \frac{\epsilon}{|\mathcal{A}|}, & a = \arg\max_{a'} q(s, a') \\ \frac{\epsilon}{|\mathcal{A}|}, & \text{otherwise} \end{cases}$$

以 $1 - \epsilon$ 的概率选最优动作，以 $\epsilon$ 的概率随机探索。

为什么不用纯贪心？

纯贪心策略（$\epsilon = 0$）有一个致命问题：如果初始策略不好，某些动作永远不被尝试，就永远无法发现它们可能是最优的。

ε-Greedy 保证了每个动作都有非零概率被选中，从而保证了持续探索。

MC ε-Greedy 算法

初始化: q(s,a) = 0, π = ε-greedy(q)
重复:
    # 生成回合（遵循 ε-greedy 策略，自然探索）
    跑一个回合: S₀,A₀,R₁,...,S_T
    对回合中每个 (S_t, A_t):
        G_t = Σ γᵏ Rₜₖ₊₁
        q(S_t, A_t) ← q(S_t, A_t) + α(G_t - q(S_t, A_t))
    
    # 更新策略
    π ← ε-greedy(q)

五、探索与利用的权衡

核心矛盾

• 利用（Exploitation）：选择当前已知最好的动作 → 短期回报高
• 探索（Exploration）：尝试未知动作 → 可能发现更好的策略

这是强化学习的永恒主题。

ε 的选择

理论保证：MC ε-Greedy 在 ε 从 1 逐渐衰减到 0（但不能太快）时，收敛到最优策略。但衰减速度的选择是个艺术——太快则探索不足，太慢则浪费样本。

六、蒙特卡罗方法的特点

优点

• 无需模型：不需要知道 $p$ 和 $r$
• 无偏估计：每个回报样本是真实回报的无偏估计
• 概念简单：就是"跑回合，取平均"

缺点

• 必须有回合：只能用于有终止状态的任务
• 方差大：回报是整条轨迹的累加，方差可能很大
• 数据效率低：每条轨迹只用一次，不同 $(s,a)$ 之间不共享信息

与第 7 章的联系：蒙特卡罗方法用完整回合的回报来更新，而时序差分（TD）方法用一步的奖励来更新——后者方差更小但有偏。这是第 7 章的核心主题。

七、总结