RL笔记（5）：蒙特卡洛

引言（Introduction）#

在上一章 动态规划 中，我们假设环境是已知的（即我们知道状态转移概率 $\mathcal{P}$ 和奖励函数 $\mathcal{R}$）。但在现实中，比如围棋或机器人在火星行走，我们往往无法预知“做了动作后具体会发生什么”。

蒙特卡洛方法 (Monte-Carlo methods, MC) 标志着我们进入了 无模型 (Model-Free) 强化学习的领域。

• 核心思想：不需要知道环境的动力学方程，只需要让智能体在环境中采样（玩游戏）。
• 大数定律：只要玩的次数够多，观测到的平均回报就会趋近于真实的期望回报。

注意：MC 方法仅适用于情节任务 (Episodic Tasks)，即任务必须有终止状态（如一盘棋下完、游戏通关或挂掉）。

---

蒙特卡洛预测 (Monte-Carlo Prediction)#

我们的第一个目标是：给定一个策略 $\pi$，估算它的状态价值函数 $V^\pi(s)$。

回顾 $V$ 的定义：

$$V^\pi(s)=\mathbb{E}_\pi[G_t|S_t=s]$$

在没有模型的情况下，我们无法通过贝尔曼方程的 $\sum P(s'|s)\dots$ 来计算期望。 MC 的做法是：直接用经验平均值来代替期望。

算法流程#

1. 使用策略 $\pi$ 采样 $N$ 条完整的轨迹（Episode）： $s_0 \xrightarrow{a_0} r_0, s_1 \xrightarrow{a_1} r_1, \dots, s_{T-1} \xrightarrow{a_{T-1}} r_{T-1}, s_T$
2. 计算每条轨迹中，状态 $s$ 出现后的累积回报 $G_t$。
3. 取平均值： $V(s) \approx \frac{1}{N(s)} \sum_{i=1}^{N(s)} G_t^{(i)}$

首次访问 vs. 每次访问#

在一条轨迹中，状态 $s$ 可能会出现多次。如何计算回报？

• 首次访问 (First-visit MC)：只计算状态 $s$ 第一次出现时的回报 $G_t$。这是无偏估计。
• 每次访问 (Every-visit MC)：状态 $s$ 每次出现，都计算一次回报 $G_t$ 并纳入平均。这也是无偏估计（但收敛性证明略有不同）。

---

增量式更新 (Incremental Update)#

在实际计算中，我们不需要要把几百万条轨迹的数据都存下来最后求平均，而是可以使用增量更新的方法（类似于第二章多臂老虎机中的更新）。

推导： 假设 $V_{k-1}$ 是前 $k-1$ 次的平均值，$G_k$ 是第 $k$ 次观测到的回报：

$$\begin{align} V_k &= \frac{1}{k} \sum_{i=1}^k G_i \notag \\ &= \frac{1}{k} (G_k + \sum_{i=1}^{k-1} G_i) \notag \\ &= \frac{1}{k} (G_k + (k-1)V_{k-1}) \notag \\ &= V_{k-1} + \frac{1}{k} (G_k - V_{k-1}) \notag \end{align}$$

算法描述： 对于每条采样出的轨迹，对其中的每个状态 $S_t$ 和回报 $G_t$：

1. 计数器加一：$N(S_t) \leftarrow N(S_t) + 1$
2. 更新价值： $$V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)} \underbrace{(G_t - V(S_t))}_{\text{误差 Error}}$$ 或者是使用固定的步长 $\alpha$（适用于非平稳问题）： $$V(S_t) \leftarrow V(S_t) + \alpha (G_t - V(S_t))$$

---

蒙特卡洛控制 (Monte-Carlo Control)#

知道怎么评估价值还不够，我们的最终目标是找到最优策略 $\pi^*$。 这就是 广义策略迭代 (Generalized Policy Iteration, GPI) 的思想：

1. 评估：用 MC 方法估算当前策略的 $Q(s,a)$。
2. 提升：根据估算的 $Q(s,a)$ 改进策略（通常是贪婪策略）。

为什么要用 $Q$ 而不是 $V$？#

在 Model-Free 场景下，如果我们只知道 $V(s)$，却不知道状态转移 $P(s'|s,a)$，我们是无法推断出哪个动作 $a$ 导致了更好的 $s'$。 因此，必须显式地估算 动作价值函数 $Q(s,a)$。

探索的必要性#

如果我们在提升策略时使用完全贪婪策略（greedy）：$\pi(s) = \arg\max_a Q(s,a)$，智能体可能会因为过早收敛而错过最优解（没见过的动作永远不会去尝试）。

解决方案：$\epsilon$-Greedy 策略 保持持续的探索（Exploration）：

• 以 $1-\epsilon$ 的概率选择当前 $Q$ 值最大的动作。
• 以 $\epsilon$ 的概率随机选择动作。

GLIE (Greedy in the Limit with Infinite Exploration)： 如果我们让 $\epsilon$ 随着时间推移逐渐趋近于 0（例如 $\epsilon_k = 1/k$），那么 MC 控制算法最终会收敛到最优策略。

---

总结与对比#

蒙特卡洛方法是强化学习中第一种不需要了解环境模型的算法。

维度	动态规划 (DP)	蒙特卡洛 (MC)
环境模型	需要已知 $P, R$ (Model-Based)	未知，仅需经验 (Model-Free)
更新方式	**自举 (Bootstrapping)**用后继状态的估计值更新当前值	全采样必须等到 Episode 结束拿到真实 $G_t$ 才能更新
适用范围	状态空间较小，已知规则	情节性任务 (Episodic)，未知规则
偏差/方差	有偏差 (Bias)，低方差	无偏差 (Unbiased)，高方差

💡 思考： MC 必须等到游戏结束才能更新，这在像自动驾驶这样没有明确“终点”或者流程极长的任务中非常低效。有没有一种方法，既不需要模型（像 MC），又不需要等到结束就能更新（像 DP）呢？ 这就是下一章 时序差分 (Temporal Difference, TD) 要解决的问题。