5. Monte Carlo Estimation

发布于 2026 年 8 月 17 日

动态规划假设环境模型 $p(s',r\mid s,a)$ 已知，因此可以直接计算期望。Monte Carlo（MC）方法走另一条路：不显式建立环境模型，而是通过真实采样得到的回报来估计期望。

1. Model-based 与 Model-free

RL 中的 model（环境模型） 指：给定当前状态 $s$ 和动作 $a$ 后，环境会以多大概率转移到下一状态 $s'$，并产生奖励 $r$。完整的模型可以写成：

$$p(s',r\mid s,a).$$

它包含两类环境信息：

• 状态转移规律 $p(s'\mid s,a)$：执行 $a$ 后到达各个 $s'$ 的概率；
• 奖励规律：奖励的条件分布，或只使用它的期望 $r(s,a)=\mathbb E[R_{t+1}\mid S_t=s,A_t=a]$。

方法	环境模型的情况	如何学习/决策
Model-based	$p(s',r\mid s,a)$ 已知，或者根据样本显式估计出一个模型	利用模型预测后继状态和奖励，再通过规划、Bellman 更新或搜索选择动作
Model-free	不知道，也不显式学习或使用 $p(s',r\mid s,a)$	直接从交互样本 $(s,a,r,s')$ 学习 $V(s)$、$Q(s,a)$ 或策略 $\pi(a\mid s)$

因此，两者的关键区别不是“是否知道策略或价值函数”，而是是否拥有并使用环境的转移与奖励模型。在策略评估问题中，策略 $\pi$ 可以是已知的，但 $V^\pi$ 或 $Q^\pi$ 仍是待求量；这并不决定方法属于哪一类。

例如，棋类游戏的规则已知，可以根据当前局面推演下一局面，这属于 Model-based。如果智能体不知道转移概率和奖励规则，只能反复与环境交互，再从实际观察到的回报直接估计价值，就是 Model-free。Monte Carlo 属于后者。

一个离散随机变量的期望可以直接由分布计算：

$$\mathbb E[X]=\sum_x x p(x).$$

如果分布未知，也可以用 $N$ 个独立同分布样本的均值估计：

$$\bar X_N=\frac1N\sum_{i=1}^N X_i.$$

根据大数定律：

$$\bar X_N\xrightarrow[N\to\infty]{P}\mathbb E[X].$$

同时，在样本相互独立且方差有限时：

$$\mathbb E[\bar X_N]=\mathbb E[X], \qquad \operatorname{Var}(\bar X_N)=\frac{\operatorname{Var}(X)}{N}.$$

展开：样本均值的期望和方差推导

设 $X_1,X_2,\ldots,X_N$ 独立同分布，且：

$$\mathbb E[X_i]=\mu, \qquad \operatorname{Var}(X_i)=\sigma^2<\infty.$$

样本均值为：

$$\bar X_N=\frac{1}{N}\sum_{i=1}^{N}X_i.$$

根据期望的线性性：

$$\begin{aligned} \mathbb E[\bar X_N] &=\mathbb E\left[\frac{1}{N}\sum_{i=1}^{N}X_i\right]\\ &=\frac{1}{N}\sum_{i=1}^{N}\mathbb E[X_i]\\ &=\frac{1}{N}\cdot N\mu =\mu. \end{aligned}$$

由于各个样本相互独立，协方差项为 $0$，所以和的方差等于各项方差之和：

$$\begin{aligned} \operatorname{Var}(\bar X_N) &=\operatorname{Var}\left(\frac{1}{N}\sum_{i=1}^{N}X_i\right)\\ &=\frac{1}{N^2}\sum_{i=1}^{N}\operatorname{Var}(X_i)\\ &=\frac{1}{N^2}\cdot N\sigma^2 =\frac{\sigma^2}{N}. \end{aligned}$$

因此，$\bar X_N$ 的期望始终等于真实期望 $\mu$，而方差会随着样本数 $N$ 增加而减小。

因此样本越多，均值估计越稳定。这就是 MC 方法的统计基础。

2. 两种动作价值表达式

模型已知时，动作价值可以写成一步展开：

$$q_\pi(s,a) =\sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v_\pi(s').$$

模型未知时，无法直接计算这些概率，但动作价值本身仍然是条件期望：

$$\boxed{ q_\pi(s,a)=\mathbb E_\pi[G_t\mid S_t=s,A_t=a] }.$$

其中 episode 的折扣回报为：

$$G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots =\sum_{k=0}^{T-t-1}\gamma^kR_{t+k+1}.$$

MC 的思路就是多次访问 $(s,a)$，记录每次访问之后的 $G_t$，再取样本均值。

3. MC 策略评估

在策略 $\pi$ 下生成多个完整 episode。对每个 $(s,a)$ 保存：

• Returns(s, a)：观察到的回报集合；
• $Q(s,a)$：这些回报的均值。

批量形式为：

$$Q(s,a)=\frac{1}{N(s,a)} \sum_{i=1}^{N(s,a)}G_i(s,a).$$

实践中无需保存全部历史回报，可以增量更新：

$$\boxed{ Q_{n+1}(s,a) =Q_n(s,a)+\frac{1}{n+1} \left[G_n-Q_n(s,a)\right] }.$$

若环境非平稳，也可以使用固定步长：

$$Q(s,a)\leftarrow Q(s,a)+\alpha[G_t-Q(s,a)].$$

4. First-visit 与 Every-visit

一个 episode 中，同一个状态或状态—动作对可能出现多次。

4.1 First-visit MC

每个 episode 只使用 $(s,a)$ 第一次出现后的回报：

$$G_t\quad\text{where }t=\min\{k:(S_k,A_k)=(s,a)\}.$$

4.2 Every-visit MC

使用该 episode 中 $(s,a)$ 每一次出现后的回报。

两者在适当条件下都能收敛。区别在于一个 episode 为同一 $(s,a)$ 提供一个样本还是多个相关样本。

5. 倒序计算回报

完整收集一条长度为 $T$ 的轨迹：

$$S_0,A_0,R_1,S_1,A_1,R_2,\ldots,S_T.$$

从末尾倒序扫描，可以递推计算所有回报：

$$\boxed{G\leftarrow\gamma G+R_{t+1}}.$$

对于 first-visit MC，只有当 $(S_t,A_t)$ 在当前 episode 更早的位置没有出现时才更新：

$$\begin{aligned} &\textbf{对每个 episode：}\\ &\quad \tau\sim\pi: S_0,A_0,R_1,\ldots,S_{T-1},A_{T-1},R_T,S_T,\\ &\quad G\leftarrow 0,\\ &\quad \textbf{for }t=T-1,T-2,\ldots,0:\\ &\qquad G\leftarrow R_{t+1}+\gamma G,\\ &\qquad \textbf{if }(S_t,A_t)\notin \{(S_0,A_0),\ldots,(S_{t-1},A_{t-1})\}:\\ &\qquad\quad N(S_t,A_t)\leftarrow N(S_t,A_t)+1,\\ &\qquad\quad Q(S_t,A_t)\leftarrow Q(S_t,A_t) +\frac{G-Q(S_t,A_t)}{N(S_t,A_t)}. \end{aligned}$$

6. 从评估到控制

只估计 $v_\pi(s)$ 不足以在无模型环境中改进策略。Bellman 贪心更新需要比较不同动作，但状态价值的一步展开依赖未知模型：

$$v(s)=\max_a\left[ \sum_r p(r\mid s,a)r +\gamma\sum_{s'}p(s'\mid s,a)v(s') \right].$$

因此 model-free 控制直接估计动作价值 $q(s,a)$。得到 $Q$ 后即可贪心改进：

$$a^*(s)\in\arg\max_a Q(s,a).$$

纯贪心策略为：

$$\pi(a\mid s)= \begin{cases} 1,&a=a^*(s),\\ 0,&a\neq a^*(s). \end{cases}$$

7. 探索问题与 Exploring Starts

如果一开始就始终选择当前贪心动作，某些 $(s,a)$ 可能永远不会被访问，估计也就无法纠正。

MC Exploring Starts 假设每个 episode 的初始 $(S_0,A_0)$ 都有非零概率被选中。这样所有状态—动作对最终都有机会获得样本。其控制过程是广义策略迭代：

1. 随机选择起始 $(S_0,A_0)$；
2. 按当前策略生成完整 episode；
3. 用回报更新 $Q(S_t,A_t)$；
4. 令策略对新的 $Q$ 贪心；
5. 重复以上过程。

Exploring Starts 在理论上直观，但现实系统通常无法任意指定初始状态。因此更常用软策略保证持续探索。

8. $\varepsilon$-greedy 策略

设动作数为 $|\mathcal A(s)|$，当前贪心动作为 $a^*(s)$。$\varepsilon$-greedy 策略定义为：

$$\pi(a\mid s)= \begin{cases} 1-\varepsilon+\dfrac{\varepsilon}{|\mathcal A(s)|}, &a=a^*(s),\\[6pt] \dfrac{\varepsilon}{|\mathcal A(s)|}, &a\neq a^*(s). \end{cases}$$

它以大概率利用当前最优动作，同时让每个动作保持非零的探索概率。

一个 on-policy MC 控制算法如下：

$$\begin{aligned} &Q(s,a)\leftarrow\text{任意初值}, \qquad N(s,a)\leftarrow 0,\\ &\pi\leftarrow\text{任意 }\varepsilon\text{-soft 策略},\\[4pt] &\textbf{对每个 episode：}\\ &\quad \tau\sim\pi: S_0,A_0,R_1,\ldots,S_{T-1},A_{T-1},R_T,S_T,\\ &\quad G\leftarrow 0,\\ &\quad \textbf{for }t=T-1,T-2,\ldots,0:\\ &\qquad G\leftarrow R_{t+1}+\gamma G,\\ &\qquad \textbf{if }(S_t,A_t)\text{ 是 first visit}:\\ &\qquad\quad N(S_t,A_t)\leftarrow N(S_t,A_t)+1,\\ &\qquad\quad Q(S_t,A_t)\leftarrow Q(S_t,A_t) +\frac{G-Q(S_t,A_t)}{N(S_t,A_t)},\\ &\qquad\quad a^*(S_t)\in\arg\max_a Q(S_t,a),\\ &\qquad\quad \pi(\cdot\mid S_t) \leftarrow\varepsilon\text{-greedy}\bigl(a^*(S_t)\bigr). \end{aligned}$$

9. MC 的特点与限制

MC 方法具有以下特点：

• 无模型：只需要环境交互产生的轨迹；
• 非自举：目标 $G_t$ 不依赖当前的 $V$ 或 $Q$ 估计；
• 无偏但方差较高：完整回报包含很多随机奖励与转移；
• 通常是离线更新：必须等 episode 结束后才能得到完整 $G_t$；
• 主要适合 episodic tasks：持续任务没有自然终点时需要截断或换用其他方法。

MC 用真实完整回报回答“这次最终得到了多少”。下一篇的 TD 方法会把真实的一步奖励与当前估计拼接起来，在 episode 尚未结束时就更新价值。