Post

Chap5 MC

Posted
By floyd white
18 min read
Chap5 MC

第5章：蒙特卡洛方法

试探性出发假设

在算法的每次迭代或每个“回合”开始时，主动让智能体（agent）从环境中随机选择一个初始状态和初始动作，而不是固定从一个已知状态出发。这样做的好处是确保算法能充分探索所有可能的状态-动作组合，避免因路径依赖而遗漏潜在更优的策略。

Why 试探性出发假设很难被满足

举个具体例子 🌰

假设用蒙特卡洛方法训练一个外卖配送AI，如果要求“试探性出发”：

  • 理论上需要让AI从所有可能的初始位置（如不同街道、不同天气、不同订单量）开始探索。
  • 但现实中无法主动控制天气或订单分布，某些极端状态（如暴雨+爆单）可能天然出现频率极低，导致AI在这些场景下缺乏训练数据。

替代方案 🔄

正因如此，实际算法中常采用更实用的探索策略，例如：

  • ε-贪婪策略（ε-greedy）：以一定概率随机探索未知动作。
  • 基于模型的探索：利用环境模型预测高价值区域，针对性探索。
  • 重要性采样：通过调整采样权重弥补探索不足。

避免无限多幕样本序列假设

1. 传统策略迭代的问题

传统方法严格分为两阶段：

  1. 策略评估（Policy Evaluation）：必须完整计算当前策略π的Q值函数，直到收敛（比如通过贝尔曼方程迭代到误差足够小）。
  2. 策略改进（Policy Improvement）：基于完全收敛的Q值，贪婪地选择新策略π’（比如选每个状态下的最优动作）。

缺点：如果状态空间大或连续，策略评估可能耗时极长（需要“无限多幕样本”或无限次迭代），导致策略改进被严重延迟。

2. 新方法的改进思路

  1. 评估阶段有限逼近
    • 每次评估只做有限次迭代（比如k=1次贝尔曼更新），让Q值向真实值qm方向移动，但不要求完全收敛。
  2. 提前触发策略改进
    • 基于当前“未收敛但已优化”的Q值，直接改进策略。例如：在Qₜ₊₁基础上，立即选择每个状态下Q值最大的动作，生成新策略π’。
  3. 动态平衡效率与精度
    • 评估和改进交替进行，类似“边学边用”。即使Q值不完美，策略也能逐步优化（类似人类先掌握大致方向再细化细节）。

3. 数学上的合理性

虽然Q值未收敛，但只要每次评估的更新方向正确（如贝尔曼误差单调减小），策略改进仍能保证策略性能不下降（理论上有收敛性保障，参考《强化学习导论》相关证明）。

同/离轨策略的引入

“如何避免很难被满足的试探性出发假设呢?唯一的一般性解决方案就是智能体能
够持续不断地选择所有可能的动作。“

  1. 解释：
    想象你在玩一个迷宫游戏，但有个奇怪的规则——每次游戏开始时，你必须从某个随机起点出发，并且要尝试所有可能的走法（比如先左转、直走、右转）。但问题来了：如果迷宫特别复杂，你永远无法保证每次开局都能覆盖所有可能的起点和初始走法。这就是”试探性出发假设”的困境——现实中很难满足这种苛刻的初始条件。
  2. 为什么要”持续选择所有动作”？
    假设现在取消”必须从各种起点开始”的要求，甚至允许你固定从一个起点出发。但为了找到最佳路线，你在每次移动时故意随机尝试不同的方向（比如大部分时间选当前认为最好的方向，偶尔故意绕路）。这样长期下来，你仍然能探索到所有可能的路径，而无需依赖初始条件的多样性。

”有两种方法可以保证这一点（持续选择所有可能的动作）——同轨策略(on-policy)方法和离轨策略(off-policy)方法。“

(一）同轨策略解决这个困境的逻辑

让智能体在“学习策略”中主动加入随机性，边走边探索，而不是依赖起点覆盖所有可能。就像走迷宫时，自己主动尝试不同的方向，而不是被固定在某个起点。

  1. 策略自带“好奇心”

    比如用 ε-greedy 策略：90%的时间按当前最佳路线走，10%的时间随机乱走

  2. 边试错边改进

    每次随机走一步后，根据结果（比如是否更快拿到零食）更新策略：“这个方向也能走通！”

  3. 永不停止探索

    即使策略已经很好（比如找到一条较快路径），仍然保留小概率随机动作（例如ε=10%），防止陷入局部最优。

（二）离轨策略解决这个困境的逻辑

核心：看别人犯错，自己学聪明

想象一个实习生在公司学习：

  1. 行为策略（μ）：普通员工用各种方法工作（有的高效，有的瞎忙），甚至故意试错。
  2. 目标策略（π）：实习生观察所有人的结果，只记住最优操作（比如“老张的方法最快完成报表”）。
  3. 间接学习：实习生无需亲自尝试所有错误方法，但通过观察他人失败，直接优化自己的策略。

为什么能避免试探性出发假设？

  • 行为策略（比如完全随机动作）主动覆盖所有可能性，而目标策略专注提取最优路径。
  • 类似“站在巨人肩膀上”——无需自己从头试错，利用广泛探索的数据直接优化。

优点：

这样分离的好处在于，当行动策略能对所有可能的动作继续进行采样时，目标策略可以是确定的(例如贪心)。

普通重要度采样的缺陷

使用简单平均公式(5.5)得到的结果在期望上总是$v_{\pi}(s)$(是无偏的),但是其值
可能变得很极端。假设比例系数是10,这意味着，被观测到的决策序列轨迹遵循目标策
略的可能性是遵循行动策略的10倍。在这种情况下，普通重要度采样的估计值会是观测
到的回报值的10倍。也就是说，尽管该幕数据序列的轨迹应该可以非常有效地反映目标
策略，但其估计值却会离观测到的回报值很远。

核心概念：重要度采样比率（Importance Sampling Ratio）

假设我们有两个策略：

  • 目标策略π：我们要评估的理想策略（比如考试时的标准答题步骤）
  • 行为策略μ：实际探索时使用的策略（比如平时做练习题时的随意尝试）

重要性采样比率 = π选择某路径的概率 / μ选择同路径的概率

例子场景

假设在某个选择题中：

  • 目标策略π有90%概率选正确答案（A）
  • 行为策略μ只有9%概率选A（其他91%概率随机选错）

某次观测到学生通过μ策略偶然选了A并答对（回报值=1）

此时：
比率ρ = π的概率(90%) / μ的概率(9%) = 10

普通重要度采样公式的作用

普通重要度采样会将观测到的回报值乘以比率：
修正后的估计值 = 1（实际回报） × 10（比率） = 10

虽然这个学生实际只得到1分，但算法认为：”如果按照目标策略π操作，这类情况出现的概率是实际观测时的10倍”，因此需要将单个样本的权重放大10倍来修正偏差。

为什么出现极端值？

  1. 数学特性：当π和μ的概率差异较大时，比率ρ会剧烈放大或缩小观测值
  2. 无偏性的代价：虽然这种修正能保证估计的期望值正确（无偏性），但单个样本可能严重偏离真实分布
  3. 现实类比：就像用1次偶然蒙对的答案，反推”如果每次都按正确方法做”的预期得分是10分，显然夸大了单次偶然事件的影响,

实际效果

这种方法虽然理论正确，但会导致：

  • 对偶然成功的情况过度乐观（如10倍高估）
  • 对常见失败的情况过度悲观（如0值低估）
  • 最终估计结果的方差极大，不利于稳定学习

这就是为什么后续会提出加权重要度采样（Weighted Importance Sampling）来通过分母标准化缓解该问题。

例5.5 无穷方差

在这个例子中，普通重要度采样（Ordinary Importance Sampling，OIS）始终无法收敛到1，而加权重要度采样（Weighted Importance Sampling，WIS）可以收敛到1，这主要归因于普通重要度采样的方差无界，导致估计不稳定。我们可以从数学角度来分析其中的原因。

1. 普通重要度采样的不稳定性

普通重要度采样（OIS）直接使用：

$V(s)\approx \frac{1}{N} \sum_{i=1}^{N} \rho^{(i)} G^{(i)}$

问题在于，如果重要度采样比的方差是无界的，估计的方差也会无界，导致采样效率极差。

在这个 MDP 例子中：

  • 目标策略 只会选择向左，即

    $π(A=left∣S)=1$

  • 行为策略 是均匀随机的，即 。

    $b(A = \text{left} \mid S) = \frac{1}{2}$

因此，重要度采样比为：

$ρ= \prod_{t=0}^{T-1} \frac{\pi(A_t \mid S_t)}{b(A_t \mid S_t)}$

对每条轨迹：

  • 如果行为策略随机选择向左，则 ，即随着步数增长， 呈指数级增长。

    $ρ = \left(\frac{1}{1/2}\right)^T = 2^T$

  • 如果行为策略选择向右，则该轨迹不会被目标策略采样，因此其权重为零，不影响计算。

这意味着：

  1. 轨迹权重 ρ 的方差是指数增长的，导致估计方差无界，从而起伏不定、难以收敛。
  2. 故而在有限采样时，向左的轨迹的权重极大，而向右轨迹的权重接近 0，导致估计极不稳定。

最终导致普通重要度采样无法收敛到正确的期望值。

2. 加权重要度采样的收敛性

加权重要度采样（WIS）使用归一化的权重来计算：

$V(s) \approx \frac{\sum_{i=1}^{N} \rho^{(i)} G^{(i)}}{\sum_{i=1}^{N} \rho^{(i)}}$

其中分母用于归一化权重，保证总权重为 1：

$W = \sum_{i=1}^{N} \rho^{(i)}$

这样做的好处是：

  1. 由于 $\rho^{(i)}$ 归一化了，即使某些轨迹的 ρ 极大，也不会影响整体估计值的稳定性。
  2. 归一化的加权平均减少了高方差的重要度采样比的影响，使得估计不会被极端权重所主导。

从数学上来看，WIS 的估计量满足：

$E[V_{WIS}(s)] = V(s)$

但方差是有界的，不会像 OIS 那样发散。

因此，WIS 可以收敛到 1，而 OIS 无法稳定收敛。

3. 加权重要度采样的”归一化权重“是什么意思？

1） 归一化权重是指将一组原始权重进行归一化处理，把每个权重都除以总权重，使它们的总和等于 1。这样做的目的是防止某些样本的权重过大，从而影响整体估计的稳定性。

2）假设你有一组采样轨迹，它们的原始权重是：[10,200,5,50,35]，总权重 W 为：10+200+5+50+35=300。归一化后，每个权重变为：

$\left[ \frac{10}{300}, \frac{200}{300}, \frac{5}{300}, \frac{50}{300}, \frac{35}{300} \right] = [0.033, 0.667, 0.017, 0.167, 0.117]$

这样，即使某个轨迹的原始权重非常大（如 200），它的影响仍然被控制在 66.7% 左右，而不会完全主导结果。

Reinforcement_learning
rl
This post is licensed under CC BY 4.0 by the author.