蒙特卡洛方法

蒙特卡洛方法是第一类实用的估计价值函数与寻找最优策略的算法。

基础RL框架复习

Model-free

从蒙特卡洛方法开始，我们便进入到经典强化学习的范畴。我们一般把强化学习分为如下三个时代：

动态规划时代，agent知道所有环境状态
表格法时代，model-free，基于采样
函数逼近和深度强化学习时代（这个时代内部当然还有很多更细节的划分）

其中表格法时代基于采样，不再需要了解全部的环境状态，我们可以通过采样的方式来不断迭代策略。

Model-free 是指智能体在完全不知道环境运作规律的情况下，直接通过“试错”（与环境交互，收集真实的经验轨迹）来评估价值和寻找最优策略。它不去试图搞懂“世界是怎么运转的”，它只关心“在什么情况下做什么动作能拿到最高分”。

策略和价值函数

在本章之前我们已经探讨了多臂老虎机问题、有限MDP和动态规划。我们简单回顾一下其中最为重要的两个概念：策略和价值函数。

策略是智能体从状态（State）到动作（Action） 的映射。它就像是一本“行动指南”，告诉智能体在特定的环境下应该采取什么反应。

策略通常分为两种类型：

确定性策略 (Deterministic Policy): 对于每一个状态，智能体总是选择同一个特定的动作。 $$ \pi(s) = a $$
随机性策略 (Stochastic Policy): 对于每一个状态，策略给出的每个动作被选中的概率。 $$ \pi(a|s) = P(A_t = a | S_t = s) $$

形象比喻： 如果你在玩游戏，策略就是你的“出招表”。看到敌人跳起来（状态），你就按防御键（动作）。

价值函数是对未来奖励的 长期预测 。它不仅仅看当前的即时奖励（Reward），更看重从当前时刻开始，未来能获得的累计奖励总和。

常见的价值函数有两种：

1、状态价值函数 (State-Value Function, $V$)

它表示智能体处在状态 $s$ 时，按照策略 $\pi$ 行动，预期能获得的累积回报。它衡量的是 这个位置好不好 。

\[ V_\pi(s) = \mathbb{E}_\pi [ \sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t = s ] \]

(其中 $\gamma$ 是折扣因子，决定了我们对未来奖励的重视程度)

2、动作价值函数 (Action-Value Function, $Q$)

通常被称为 Q 函数 。它表示在状态 $s$ 下，先执行动作 $a$，之后再按策略 $\pi$ 行动，预期获得的累积回报。它衡量的是 在这个位置做这个动作好不好 。

\[ Q_\pi(s, a) = \mathbb{E}_\pi [ \sum_{k=0}^\infty \gamma^k R_{t+k+1} | S_t = s, A_t = a ] \]

简单来说，策略就是决定怎么做，价值函数就是评价该策略有多好。

广义策略迭代

广义策略迭代 (Generalized Policy Iteration, GPI)不是某一个具体的算法，而是强化学习中寻找最优策略的 通用框架和核心思想 。它描述了两个不断交替、相互竞争又相互合作的过程：

策略评估 (Policy Evaluation)： 根据当前的策略，计算出每个状态的价值（这就是你刚学过的“预测”）。
策略改进 (Policy Improvement)： 根据刚计算出的价值，贪婪地选择能带来最大价值的动作，从而生成一个更好的新策略。

这两个过程交替进行，策略在价值的基础上改进，价值又根据新策略重新评估，直到两者都收敛到最优（最优价值函数 $V^*$ 和最优策略 $\pi^*$）。

假设当前策略为 $\pi$，评估得到动作价值函数 $Q_\pi(s, a)$。

改进策略时，我们直接取最大化 $Q$ 值的动作：

\[ \pi'(s) = \arg\max_a Q_\pi(s, a) \]

因为 $\pi'$ 在每个状态都选择了当前看起来最好的动作，所以 $\pi'$ 总是比 $\pi$ 好（或相等）。

预测和控制

在强化学习里，“预测（Prediction）” 这个词其实翻译得有点迷惑，将其理解为评估（Evaluation）或者“算命”反倒更贴切一点。简单来说：

预测就是给定策略下，算出每个状态对应的价值
控制就是要根据算出来的价值，修改策略，从而找到最优策略

预测（Prediction）的任务是：给定一个具体的策略 $\pi$，计算出在这个策略下的 价值函数 （$V_\pi$ 或 $Q_\pi$）。

核心目标： 计算值（Value Estimation）。
回答的问题： “如果我按照现在的策略走下去，在某个状态下平均能拿多少分？”
输入： 环境 $M$ + 策略 $\pi$。
输出： 价值函数 $V_\pi$。
举例：天气预报中，预测明天80%的下雨概率。

控制（Control）的任务是：不限制策略，目标是找到一个最优策略 $\pi^*$，使得获取的累积奖励最大化。

核心目标： 优化策略（Policy Optimization）。
回答的问题： “我应该采取什么样的行动，才能拿到最高的分数？”
输入： 环境 $M$。
输出： 最优策略 $\pi^*$ 和最优价值函数 $V^*$。
举例：自动驾驶系统中，预测前方有障碍物后，立刻决定刹车。

在预测阶段，你可能只关心某个状态值多少分（$V$）。但在控制（寻优）阶段，知道一个状态值多少分是不够的，因为你不知道该做哪个动作才能拿到高分。

核心逻辑： 在没有环境模型（Model-Free）的情况下，你必须估算状态-动作对的价值 $Q(s, a)$。
学习点： 理解为什么在无模型强化学习中，$Q$ 函数比 $V$ 函数更实用。

On-policy vs Off-policy

在做“控制”时，我们需要让智能体与环境交互来收集数据（玩游戏）。这就引出了一个矛盾：为了找到最优策略，我们应该总是选择当前价值最高的动作（ 利用/Exploitation ）；但如果不去尝试没走过的路，我们可能永远不知道那条路更好（ 探索/Exploration ）。如何生成交互数据，就分成了 On-policy 和 Off-policy。

On-policy 的核心是：你用来与环境交互、收集数据的策略（行为策略 Behavior Policy），和你正在评估、优化的策略（目标策略 Target Policy），是同一个策略。

为了保证既能优化又能探索，On-policy 算法通常采用 $\epsilon$-greedy 策略。即有 $1-\epsilon$ 的概率选择当前最优动作，有 $\epsilon$ 的概率随机选择动作。

数学体现： 更新 $Q$ 值时，使用的是智能体实际采取的动作 $A_{t+1}$ 来更新当前的 $Q(S_t, A_t)$。
举例说明：“从自己的错误中学习”。 你在学习打篮球（目标策略），你亲自上场打比赛（行为策略也是你自己）。你投丢了球，你吸取教训，调整自己的投篮姿势。你自己既是数据的产生者，也是策略的优化者。

Off-policy 的核心是：收集数据的策略（行为策略 $b$）和正在优化的策略（目标策略 $\pi$）是分离的。

目标策略 $\pi$：这是我们想要学习的最优策略，通常是完全贪婪的（只选最好的，不探索）。
行为策略 $b$：这是用来和环境交互产生数据的策略，它必须具有高度的探索性（比如完全随机），以确保所有状态都能被访问到。

举例说明：

“站在巨人的肩膀上”或“旁观者清”。 你想学习下围棋（优化目标策略 $\pi$），但你不是自己下，而是去观看围棋大师的对弈录像（数据由大师的行为策略 $b$ 产生），或者看两个新手瞎下。你通过观察别人的操作和结果，在自己脑海中总结出一套最优的下棋策略。

探索vs利用

这是控制任务的核心挑战。如果你发现动作 A 能得 10 分，你可能就永远只选 A，从而错过了能得 100 分的动作 B。

解决方案 A：探索性初始化 (Exploring Starts, ES)
- 强制让每一幕从随机的状态和动作开始。
- 学习点： 理解它的数学完美性，以及在现实中“瞬移”到随机状态的局限性。
解决方案 B：$\epsilon$-贪婪策略 ($\epsilon$-Greedy)
- 不再要求随机起点，而是在选择动作时，有 $\epsilon$ 的概率去乱走（探索），$1-\epsilon$ 的概率走最好的路。
- 学习点： 掌握如何用这种简单的概率分配平衡搜索空间。

蒙特卡洛预测

底层原理

蒙特卡洛并不是一种具体的算法，而是一类依靠重复随机采样来解决数学问题的方法。比如说，假设你想知道一个不规则湖泊的面积，但没有公式。你可以对着包含湖泊的正方形区域随机“撒豆子”，只要豆子撒的足够多，那么落在水里的豆子比例 $\times$ 正方形总面积，就是湖泊的近似面积。

为什么“撒豆子”是靠谱的？这全靠大数定律。在随机试验中，当试验次数 $$ 趋向于无穷大时，样本的算术平均值

会收敛于该随机变量的理论期望值 $\mu$：

\[ \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^{n} X_i = \mathbb{E}[X] \]

因此，蒙特卡洛方法才能用采样来代替计算，用频率来近似概率。

在强化学习中，我们想要知道状态 $s$ 的价值 $V(s)$，而 $V(s)$ 的定义就是从状态 $s$ 开始所能获得的期望回报。既然无法直接计算这个期望，我们就根据大数定律，多跑几次，算平均回报。

在强化学习中，预测（Prediction） 的目标是：给定一个策略 $\pi$，估算在这个策略下每个状态的价值 $V_\pi(s)$。

核心运作流程：

完整采样： 智能体必须根据策略 $\pi$ 完整地跑完一幕（Episode），直到抵达终止状态。
记录回报： 计算这一幕中每个状态 $s_t$ 之后获得的所有奖励总和（折扣回报 $G_t$）。
取平均值： 随着玩的游戏次数增多，把每个状态收到的 $G_t$ 全都存起来算平均数。

注意： 蒙特卡洛方法是 Model-Free（无模型） 的。它不需要知道环境的转移概率 $P$，只需要通过“亲身体验”来学习。

First-visit型

首次访问型MC预测是蒙特卡洛预测中最经典的一个变体。它处理的是一个细节问题：如果智能体在同一幕里多次经过同一个状态怎么办？

比方说，你在走迷宫，路过“客厅”状态，绕了一圈又回到了“客厅”，最后走出迷宫。根据First-visit的规则，在这一episode中，我们只计算第一次进入“客厅”后所获得的回报 $G$。之后在同一episode中再次进入“客厅”时的回报会被忽略。

这是因为每一幕产生的“第一次访问”回报都是对 $V_\pi(s)$ 的一个独立同分布采样；它在统计学上更容易证明能收敛到真实的期望值（偏差低）。

# 首次访问型蒙特卡洛预测 (First-visit MC Prediction)
# 目标：估算在策略 pi 下的状态价值函数 V(s)

初始化:
    对于所有状态 s:
        V(s) = 0               # 初始价值
        Returns(s) = []        # 存放状态 s 在各幕中得到的“总回报”的列表
        gamma = 0.9            # 折扣因子 (根据实际情况设定)

无限循环 (每一幕/Episode):
    1. 根据策略 pi 运行一幕，记录下数据：
       状态序列: S0, S1, S2, ..., ST
       奖励序列: R1, R2, ..., RT

    2. G = 0                   # 初始化总回报 (Return)

    3. 从后往前遍历这一幕的每一步 (t = T-1, T-2, ..., 0):
       G = gamma * G + R_{t+1} # 计算从时间 t 开始的折扣总回报

       # 【关键：首次访问判断】
       如果 状态 St 在之前的步骤 (S0, S1, ..., S_{t-1}) 中没有出现过:
           将 G 添加到 Returns(St) 列表中
           V(St) = average(Returns(St))  # 更新价值：取该状态所有回报的平均值

.

我们来看一个例子：

蒙特卡洛控制

基于重要度采样的Off-policy

在 Off-policy 中，我们用策略 $b$ 收集了数据（例如，回报 $G$），但我们想评估的是策略 $\pi$。由于这两个策略选择同一个动作的概率不同，我们 不能直接把策略 $b$ 跑出来的平均得分，算作策略 $\pi$ 的得分 。这时候就需要“重要度采样”来修正偏差。

重要度采样是一种统计学方法，用于在已知一个分布的数据时，估计另一个分布下的期望值。在强化学习中，它通过计算两个策略产生同一个轨迹的概率比值（重要度比率 Importance Sampling Ratio），来给回报 $G$ 加权。

设目标策略选择动作的概率为 $\pi(a|s)$，行为策略为 $b(a|s)$。在时刻 $t$ 到 $T-1$ 的轨迹重要度比率为：

\[ \rho_{t:T-1} = \prod_{k=t}^{T-1} \frac{\pi(A_k|S_k)}{b(A_k|S_k)} \]

然后，我们用这个比率去乘以实际得到的回报 $G_t$。如果目标策略下发生这个轨迹的概率比行为策略大，$\rho > 1$，这个回报的权重就被放大；反之则缩小。

估计的价值为：

\[ V(s) = \frac{\sum \rho_{t:T-1} G_t}{\text{样本数}} \]

比方说，你想估算“职业篮球运动员（策略 $\pi$）的平均身高”，但你手头只有“普通大学生（策略 $b$）的身高数据”。你不能直接求大学生的平均身高。此时你需要使用重要度采样：当你从大学生中抽到一个身高 2 米的人时，你给他的数据赋予 极高的权重 （因为这在职业球员中很常见，$\pi$ 大 $b$ 小，比值大于 1）；抽到一个身高 1.7 米的人时，你赋予 极低的权重 （因为这在职业球员中罕见）。通过这种加权，你就可以用大学生的数据，准确估算出篮球运动员的平均身高。

蒙特卡洛ES

蒙特卡洛 ES 实际上是把“预测”和“改进”揉在了一起，遵循的是 广义策略迭代 (GPI) 的逻辑：

MC Prediction做的是给定策略情况下，估算V或者Q；而MC Control做的是不固定策略，目的在于学到最优策略。

在Model-Free + Control的场景下，我们几乎总是直接学 $Q(s, a)$，并且一旦有了Q，策略就能直接变成贪婪：

\[ \pi(s) = \arg\max_{a} Q(s, a) \]

如果我们每个episode都从固定的起点开始，且策略越来越贪婪，那agent可能永远到不了某些状态动作组合，从而导致有些$(s,a)$无法被采样；这将导致Q永远不准，策略极有可能卡在局部最优。

我们用ES来解决这个问题。ES就是Exploring Starts，其要求是每一幕（episode）的起始 状态 S0 和起始 动作 A0 必须能以非零概率被选到。也就是说，任何$(s,a)$都有机会成为“开局第一步”。这保证所有 $(s,a)$都会被不断探索，从而 Q 的估计有机会收敛到真实值，策略才能真正走向最优。

MC-ES在每一个episode做两件事：

（1）策略评估：用“First-visit MC”估计$Q(s,a)$。在一条episode轨迹里，如果同一个$(s,a)$出现多次，只取第一次出现后的回报G：

\[ Q(s, a) \leftarrow \text{average of returns following first visit of } (s, a) \]

（2）策略改进：episode结束后立刻让$\pi$变贪婪：

\[ \pi(s) \leftarrow \arg\max_{a} Q(s, a) \]

伪代码如下：

初始化：
    对所有 s,a:
        Q(s,a) = 0
        Returns(s,a) = []
    对所有 s:
        π(s) = 随机（或任意初始化）

重复每一幕 Episode：
    1) ES 随机开局：
        随机选 S0
        随机选 A0
    2) 用 “A0 + 后续按 π” 跑完整幕，记录轨迹：
        (S0,A0,R1), (S1,A1,R2), ..., (ST-1,AT-1,RT)
    3) 从后往前算回报 G，并做 First-visit (s,a) 更新：
        G=0
        for t=T-1..0:
            G = γG + R_{t+1}
            如果 (St,At) 没在 (S0,A0)...(S_{t-1},A_{t-1}) 出现过:
                Returns(St,At).append(G)
                Q(St,At)=average(Returns(St,At))
    4) 策略改进（贪婪）：
        对 episode 中出现过的每个状态 s:
            π(s)=argmax_a Q(s,a)

。

\[ \text{MC ES} = \underbrace{\text{MC Prediction}}_\text{预测 (估算 Q)} + \underbrace{\text{Policy Improvement}}_\text{改进 (贪婪策略)} + \underbrace{\text{Exploring Starts}}_\text{探索机制} \]

其中：

预测部分： 它使用你之前看到的 First-visit MC 逻辑来估算状态-动作对的价值 $Q(s, a)$。
改进部分： 每一幕结束后，它会立刻更新策略，让策略在每个状态下都选择 $Q$ 值最大的那个动作（Greedy）。
ES 部分： 为了防止智能体“固步自封”（只跑已经发现的好路），它强制要求 每一幕的起始点（状态和动作）是随机选择的 。

。

On-policy First-Visit MC Control

在programming/grid_world.py的实验中，我们发现：

由于policy中只存储当下最好的那一个动作，因此如果我们不使用ES，并且agent严格按照policy走，那么它就会变得极度目光短浅且固执
即便随机初始化，依然有很大可能陷入死局，所以我们要规定最大步数限制

由于上述诸多问题，在实际工程中，我们几乎肯定是使用e-greedy，而非ES。智能体老老实实地每次都从起点出发。只不过每走到一个格子，它不再严格听从Q表中的最高分建议，而是：

它有 $1 - \epsilon$ (比如 90%) 的概率，做一个听话的乖孩子，选 $Q$ 值最大的动作（贪婪）。
它有 $\epsilon$ (比如 10%) 的概率，突然“叛逆”，闭着眼睛在所有动作里随机瞎选一个（探索）。

该方法非常实用，不需要操纵环境的初始状态，随时随地都在保持探索。不过要注意的是，它的最优解不是“绝对完美”的最优，而是在“带有 10% 犯傻概率”的前提下的最优解。

使用 $\epsilon$-greedy 机制的 MC Control，它的官方学名就叫做 On-policy First-Visit MC Control（同策略蒙特卡洛控制） 。

在强化学习中，智能体其实有两个“脑子”（也就是两个策略）：

行动策略 (Behavior Policy)： 控制它当下真正在迷宫里迈开腿怎么走的策略。
目标策略 (Target Policy)： 它在心里默默计算、想要去评估和优化的最终策略。

之所以叫On-policy，是因为在这套算法里， 行动策略 = 目标策略 = $\epsilon$-greedy 策略 。

智能体在迷宫里闯荡时，用的是包含一点点随机性的 $\epsilon$-greedy 策略去收集经验（保证了充分的探索，不会死循环）。
跑完一幕后，它回过头来评估和更新的，也是这个带有随机性的策略本身。

这就是“知行合一”，自己怎么走的，就怎么学，所以叫 On-policy 。

既然有“同”，自然就有“异”。Off-policy（异策略） 的意思是“精神分裂”：它用一个带有随机性的策略在迷宫里瞎走（为了多踩坑、多收集数据），但是它心里其实在暗暗优化和记录另一套 绝对完美、没有任何随机性的纯贪心策略 。比如大名鼎鼎的 Q-Learning 就是 Off-policy 的代表。我们会在后面的章节中学习Off-policy。