RL 学习笔记（5）：蒙特卡洛方法

本博客基于西安交通大学强化学习课程 PPT 改编，历经 Gemini 以及本人总结以及整理形成。

引言#

蒙特卡洛 (Monte Carlo, MC) 方法 是一大类依赖于重复随机抽样来获取数值近似解的计算技术。在强化学习（RL）领域，蒙特卡洛方法特指一类无模型 (Model-Free) 的学习算法，它们直接从与环境交互得到的完整经验片段 (Complete Episodes) 中学习价值函数和策略，而不需要关于环境动态（如状态转移概率 $\mathcal{P}$ 和奖励函数 $\mathcal{R}$）的先验知识。

核心思想：MC 方法利用大数定律，通过计算许多样本回报的平均值 (Mean Sample Return) 来估计期望回报，也就是状态或动作的价值 (Value)。

基本要求：MC 方法直接适用于分幕式任务 (Episodic Tasks)，因为它们需要等待一个完整的片段结束后才能计算该片段中每个时间步的回报 (Return, $G_t$)。

学习内容：

1. MC 预测 (Prediction)：给定一个策略 $\pi$，估计其价值函数 $v_\pi$ 或 $q_\pi$。
2. MC 控制 (Control)：寻找最优策略 $\pi_*$。

蒙特卡洛预测 (MC Prediction)#

目标：给定策略 $\pi$，从遵循该策略生成的经验片段中估计其状态价值函数 $v_\pi(s)$ 或 动作价值函数 $q_\pi(s, a)$。

基本原理： 价值函数定义为期望回报：$v_\pi(s) = \mathbb{E}_\pi[G_t | S_t=s]$ （状态价值）或 $q_\pi(s, a) = \mathbb{E}_\pi[G_t | S_t=s, A_t=a]$ （动作价值）。 MC 方法通过收集大量样本回报并计算其平均值来近似这个期望。

• 对于 $v_\pi(s)$：收集策略 $\pi$ 下多个片段中，所有访问状态 $s$ 之后直到片段结束的回报 $G_t^{(i)}$，然后求平均。 $$V(s) \approx \frac{\sum_{i} G_t^{(i)} \text{ where } S_t^{(i)} = s}{N(s)}$$ 其中 $N(s)$ 是状态 $s$ 被访问的总次数（根据首次/每次访问定义）。
• 对于 $q_\pi(s, a)$：类似地，收集所有访问状态-动作对 $(s, a)$ 之后的回报 $G_t^{(j)}$，然后求平均。 $$Q(s, a) \approx \frac{\sum_{j} G_t^{(j)} \text{ where } (S_t^{(j)}, A_t^{(j)}) = (s, a)}{N(s, a)}$$

首次访问 (First-Visit) vs 每次访问 (Every-Visit)： 在一个片段中，某个状态 $s$ （或状态-动作对 $(s,a)$）可能被访问多次。

• 首次访问 MC：对于每个片段，只使用该片段中状态 $s$ （或对 $(s,a)$）第一次被访问时之后的回报 $G_t$ 来更新价值估计。
• 每次访问 MC：对于每个片段，使用该片段中状态 $s$ （或对 $(s,a)$）每一次被访问时之后的回报 $G_t$ 来更新价值估计。 理论上，在无限数据下，两者都会收敛到真实的价值函数。首次访问 MC 在理论分析上更常用，且某些情况下方差可能更低。

算法：首次访问 MC 预测 (用于估计 $v_\pi$)

初始化:
  对于所有状态 s ∈ S:
    V(s) ← 任意值 (通常为 0)
    Returns(s) ← 空列表

循环 对每个 episode:
  生成一个 episode 遵循策略 π: S₀, A₀, R₁, S₁, A₁, R₂, ..., S_{T-1}, A_{T-1}, R_T
  G ← 0
  VisitedStates ← 空集合  // 记录本片段已访问的状态 (用于首次访问)

  循环 对于 t = T-1, T-2, ..., 0:
    G ← R_{t+1} + γ * G
    如果 S_t 不在 VisitedStates 中:
      将 G 添加到 Returns(S_t) 列表
      V(S_t) ← Average(Returns(S_t))  // 计算列表的平均值
      将 S_t 添加到 VisitedStates

(注意：上述伪代码使用了 Python 风格的 defaultdict 和列表操作)

增量式实现 (Incremental Implementation)： 为了节省内存，避免存储所有回报，可以使用增量式更新（运行平均）： 对于状态 $s$ （或对 $(s,a)$）的第 $N$ 次（首次/每次）访问，得到回报 $G$：

或者使用常数步长 $\alpha \in (0, 1]$，这有助于处理非平稳环境（奖励或动态随时间变化）或作为一种指数加权平均：

蒙特卡洛控制 (MC Control)#

目标：在不知道环境模型的情况下，找到最优策略 $\pi_*$。

基于动作价值 (Action-Value $Q$)： 在无模型情况下，仅仅知道状态价值 $V(s)$ 不足以改进策略，因为我们无法进行一步预测来比较不同动作的优劣（这需要模型 $\mathcal{P}$ 和 $\mathcal{R}$）。因此，MC 控制方法通常直接估计动作价值函数 $Q(s, a)$，然后基于 $Q$ 值来改进策略。

框架：广义策略迭代 (GPI)： MC 控制遵循 GPI 的模式：不断交替执行策略评估和策略改进。

• 评估 (E)：使用 MC 预测方法（如首次访问 MC）估计当前策略 $\pi$ 的动作价值函数 $Q \approx q_\pi$。
• 改进 (I)：基于当前的 $Q$ 值使策略 $\pi$ 变得更贪心。例如，对于每个状态 $s$，将策略更新为选择具有最高估计值的动作：$\pi(s) \leftarrow \arg\max_a Q(s, a)$。

核心挑战：维持探索 (Maintaining Exploration)： 如果策略在改进步骤中变得完全贪心（确定性策略），智能体可能会停止探索某些状态-动作对。如果未被探索的 $(s, a)$ 对恰好是最优策略的一部分，那么算法将永远无法发现真正的最优策略。MC 方法依赖于持续不断地访问所有需要评估其价值的状态-动作对。

解决方案 (A)：试探性出发 (Exploring Starts, ES) - 理论方法

• 假设：每次开始一个新片段时，我们能够以非零概率随机选择任意一个状态-动作对 $(S_0, A_0)$ 作为起点。
• 算法：带 ES 的 MC 控制

初始化:
  对于所有状态 s ∈ S, 所有动作 a ∈ A(s):
    Q(s, a) ← 任意值 (通常为 0)
    Returns(s, a) ← 空列表
  对于所有状态 s ∈ S:
    π(s) ← 任意确定性动作从 A(s) 中选择

循环 无限次:
  选择起始状态 S₀ 和 起始动作 A₀，确保所有 (s, a) 都有非零概率被选为起点 (ES 假设)
  从 (S₀, A₀) 开始, 之后遵循策略 π 生成一个 episode: S₀, A₀, R₁, ..., S_{T-1}, A_{T-1}, R_T
  G ← 0
  VisitedPairs ← 空集合 // 记录首次访问的 (s, a) 对

  循环 对于 t = T-1, T-2, ..., 0:
    G ← R_{t+1} + γ * G
    令 Pair = (S_t, A_t)

    如果 Pair 不在 VisitedPairs 中:
      将 G 添加到 Returns(Pair) 列表
      Q(Pair) ← Average(Returns(Pair))  // (E) 策略评估

      // (I) 策略改进：更新状态 S_t 的策略
      π(S_t) ← argmax_{a' ∈ A(S_t)} Q(S_t, a')

      将 Pair 添加到 VisitedPairs

• 优点：在 ES 假设下，保证收敛到最优策略 $\pi_*$ 和最优动作价值 $q_*$。
• 缺点：ES 假设在许多实际问题中不现实（例如，机器人不能随意瞬移到任意状态并执行任意动作）。

解决方案 (B)：维持策略本身的探索性

• 核心思想：不依赖 ES，而是确保用于生成数据的策略本身始终保持一定的探索性。
• 同轨策略 (On-Policy) vs 离轨策略 (Off-Policy)：
  • 同轨策略学习：学习和改进的策略，与用于生成经验数据的策略是同一个。
  • 离轨策略学习：学习和改进的策略（目标策略 $\pi$），与用于生成经验数据的策略（行为策略 $b$）不同。
• $\epsilon$-软性策略 ($\epsilon$-Soft Policies)：为保证持续探索，同轨方法通常采用 $\epsilon$-软性策略，即对于所有状态 $s$ 和动作 $a$，策略选择该动作的概率 $\pi(a|s) \ge \frac{\epsilon}{|\mathcal{A}(s)|} > 0$。这意味着每个动作始终有至少 $\epsilon / |\mathcal{A}(s)|$ 的概率被选中。
• $\epsilon$-贪心策略 ($\epsilon$-Greedy Policies)：是实现 $\epsilon$-软性的一种常用策略。
  • 以 $1-\epsilon$ 的概率选择当前认为最优的动作（即 $\arg\max_a Q(s, a)$）。
  • 以 $\epsilon$ 的概率从所有 $|\mathcal{A}(s)|$ 个可用动作中（包括最优动作）均匀随机选择一个。

算法：同轨首次访问 MC 控制 (使用 $\epsilon$-Greedy)

初始化:
  对于所有状态 s ∈ S, 所有动作 a ∈ A(s):
    Q(s, a) ← 任意值 (通常为 0)
    Returns(s, a) ← 空列表
  初始化策略 π 为关于 Q 的 ε-greedy 策略

循环 无限次:
  (a) 使用当前策略 π 生成一个 episode: S₀, A₀, R₁, ..., S_{T-1}, A_{T-1}, R_T
  G ← 0
  VisitedPairs ← 空集合

  (b) 循环 对于 t = T-1, T-2, ..., 0:
    G ← R_{t+1} + γ * G
    令 Pair = (S_t, A_t)

    如果 Pair 不在 VisitedPairs 中:
      将 G 添加到 Returns(Pair) 列表
      Q(Pair) ← Average(Returns(Pair))  // (E) 策略评估

      // (c) 策略改进: 确保状态 S_t 的策略是关于更新后 Q 的 ε-greedy
      // (隐式或显式更新 π(·|S_t))
      令 A* = argmax_{a' ∈ A(S_t)} Q(S_t, a')
      对于所有动作 a ∈ A(S_t):
        如果 a = A*:
          π(a|S_t) ← 1 - ε + ε / |A(S_t)|
        否则:
          π(a|S_t) ← ε / |A(S_t)|

      将 Pair 添加到 VisitedPairs

• 收敛性：同轨 MC 控制（使用 $\epsilon$-Greedy）会收敛到最优的 $\epsilon$-贪心策略，而不是真正的最优策略 $\pi_*$（因为 $\epsilon > 0$ 导致它永远在探索）。不过，这个策略通常也相当好。可以通过逐渐减小 $\epsilon$ 值（例如 $\epsilon_k = 1/k$）来使其在极限情况下趋近于最优策略 (GLIE - Greedy in the Limit with Infinite Exploration)。
• 策略改进保证：可以证明，对于任意 $\epsilon$-贪心策略 $\pi$，基于其动作价值 $q_\pi$ 进行 $\epsilon$-贪心选择得到的新策略 $\pi'$，仍然满足 $v_{\pi'}(s) \ge v_\pi(s)$ 对所有状态 $s$ 成立。这保证了 GPI 过程的单调性。

离轨策略蒙特卡洛方法 (Off-Policy MC)#

同轨策略 MC 为了保证探索，最终学习到的只是一个 $\epsilon$-软性策略。离轨策略学习 的目标是：使用一个具有探索性的行为策略 $b$ (Behavior Policy) 来生成数据，但学习和评估的是一个不同的、通常是确定性的贪心策略——目标策略 $\pi$ (Target Policy)。

优点：

• 可以学习最优的确定性策略 $\pi_*$（目标策略），同时通过行为策略 $b$ 保证充分的探索。
• 更灵活，允许从历史数据、人类演示或其他智能体的经验中学习。

挑战与核心技术：重要性采样 (Importance Sampling, IS) 由于数据来自 $b$ 而非 $\pi$，直接用 $b$ 产生的回报来评估 $\pi$ 是有偏的。我们需要一种方法来修正这种分布不匹配，这就是重要性采样的作用。

• 覆盖性假设 (Coverage Assumption)：为了能够评估 $\pi$，行为策略 $b$ 必须覆盖 $\pi$ 可能采取的所有动作。即：如果 $\pi(a|s) > 0$，那么必须有 $b(a|s) > 0$。

• 重要性采样比率 (Importance Sampling Ratio)：对于一个从时间 $t$ 开始到片段结束 (时间 $T-1$) 的轨迹片段 $S_t, A_t, S_{t+1}, A_{t+1}, \dots, S_{T-1}, A_{T-1}, S_T$，其在目标策略 $\pi$ 和行为策略 $b$ 下发生的相对概率由 IS 比率给出：

  $$\rho_{t:T-1} \doteq \frac{\prod_{k=t}^{T-1} \pi(A_k|S_k) p(S_{k+1}|S_k, A_k)}{\prod_{k=t}^{T-1} b(A_k|S_k) p(S_{k+1}|S_k, A_k)} = \prod_{k=t}^{T-1} \frac{\pi(A_k|S_k)}{b(A_k|S_k)}$$

  (环境动态 $p(S_{k+1}|S_k, A_k)$ 相同，被约掉了)。

• 离轨 MC 预测：

  • 要估计 $v_\pi(s)$（或 $q_\pi(s,a)$），我们可以使用行为策略 $b$ 生成的回报 $G_t$，并用 IS 比率 $\rho_{t:T-1}$ 对其加权：$G_t^{\pi/b} = \rho_{t:T-1} G_t$。
  • 理论上 $\mathbb{E}_b[G_t^{\pi/b} | S_t=s] = v_\pi(s)$。
  • 普通重要性采样 (Ordinary IS, OIS)：简单地对加权回报求平均 $V(s) = \frac{\sum \rho G}{\text{count}}$。这是无偏估计，但方差可能极大，尤其当 $\rho$ 值波动很大时。
  • 加权重要性采样 (Weighted IS, WIS)：$V(s) = \frac{\sum \rho G}{\sum \rho}$。这是一个有偏估计（偏差随样本增多趋于 0），但通常方差小得多，实践中更常用。
  • 增量式 WIS 更新 (用于 Q 值)：维护累积权重 $C(s, a)$ 和价值估计 $Q(s, a)$。当获得状态-动作对 $(s, a)$ 的第 $n$ 个回报 $G_n$ 和对应的权重 $W_n = \rho_{t:T(n)-1}$ 时： $$C_n \leftarrow C_{n-1} + W_n \quad (\text{初始 } C_0 = 0)$$ $$Q_n(s, a) \leftarrow Q_{n-1}(s, a) + \frac{W_n}{C_n} [G_n - Q_{n-1}(s, a)]$$

• 算法：离轨 MC 预测 (WIS 估计 $q_\pi$)

输入: 目标策略 π
初始化:
  对于所有状态 s ∈ S, 所有动作 a ∈ A(s):
    Q(s, a) ← 任意值 (通常为 0)
    C(s, a) ← 0  // 累积权重

循环 无限次 (对每个 episode):
  选择行为策略 b (确保覆盖 π, 例如关于当前 Q 的 ε-greedy 策略)
  使用 b 生成 episode: S₀, A₀, R₁, ..., S_{T-1}, A_{T-1}, R_T
  G ← 0
  W ← 1  // 重要性采样比率的累乘

  循环 对于 t = T-1, T-2, ..., 0:
    G ← R_{t+1} + γ * G
    令 Pair = (S_t, A_t)

    C(Pair) ← C(Pair) + W
    如果 C(Pair) = 0:
      跳转到循环的下一次迭代 (t-1) // 避免除零
    Q(Pair) ← Q(Pair) + (W / C(Pair)) * [G - Q(Pair)] // WIS 更新

    // 更新下次回溯的 IS 权重
    W ← W * (π(A_t | S_t) / b(A_t | S_t))

    如果 W = 0:
      终止内层循环 (对于 t 的循环) // 后续轨迹与 π 无关

• 离轨 MC 控制 (Off-Policy MC Control)：
  • 结合离轨预测 (WIS) 和策略改进。
  • 目标策略 $\pi$：通常是确定性贪心策略，即 $\pi(s) = \arg\max_a Q(s, a)$。
  • 行为策略 $b$：必须是探索性的，如 $\epsilon$-greedy 策略（基于当前 Q 值）。
  • 算法：

初始化:
  对于所有状态 s ∈ S, 所有动作 a ∈ A(s):
    Q(s, a) ← 任意值 (通常为 0)
    C(s, a) ← 0
  目标策略 π(s) ← argmax_{a' ∈ A(s)} Q(s, a')  // 初始贪心策略

循环 无限次 (对每个 episode):
  选择行为策略 b (例如关于当前 Q 的 ε-greedy 策略)
  使用 b 生成 episode: S₀, A₀, R₁, ..., S_{T-1}, A_{T-1}, R_T
  G ← 0
  W ← 1

  循环 对于 t = T-1, T-2, ..., 0:
    G ← R_{t+1} + γ * G
    令 Pair = (S_t, A_t)

    C(Pair) ← C(Pair) + W
    如果 C(Pair) = 0:
      跳转到循环的下一次迭代 (t-1)
    Q(Pair) ← Q(Pair) + (W / C(Pair)) * [G - Q(Pair)] // (E) Off-policy 评估

    // (I) 策略改进: 更新目标策略 π 使其对 S_t 贪心
    π(S_t) ← argmax_{a' ∈ A(S_t)} Q(S_t, a')

    // 检查行为策略选择的动作是否是目标策略会选择的动作
    如果 A_t ≠ π(S_t):
      终止内层循环 (对于 t 的循环) // 因为 W 之后将变为 0

    // 更新 IS 权重 (假设 π 是确定性的, π(A_t|S_t) = 1)
    如果 b(A_t|S_t) = 0:
       W ← 0 // 覆盖性假设不满足 (理论上不应发生)
    否则:
       W ← W * (1 / b(A_t | S_t))

    如果 W = 0:
      终止内层循环 (对于 t 的循环) // 以防 b(A_t|S_t) = 0

• 关键点：当目标策略 $\pi$ 是确定性贪心时，只要行为策略 $b$ 在某一步 $t$ 选择了一个非贪心动作 $A_t \neq \pi(S_t)$，那么 $\pi(A_t|S_t) = 0$，导致 IS 比率 $\rho_{t:T-1}$ 必然为 0。这意味着从该点往前的回报对于评估 $\pi$ 没有贡献，可以提前停止处理该 episode 的剩余部分。

总结与讨论#

• 蒙特卡洛 (MC) 方法 是一种无模型的 RL 方法，直接从完整经验片段中学习价值函数和策略。
• MC 预测 使用平均样本回报来估计 $v_\pi$ 或 $q_\pi$。
• MC 控制 在 GPI 框架下，通过估计 $q_\pi$ 并进行策略改进来寻找最优策略。动作价值 $Q$ 对于无模型控制至关重要。
• 探索 是 MC 控制的核心挑战。可通过 ES（理论）、同轨 $\epsilon$-软性策略（实用） 或 离轨方法 来解决。
• 同轨 (On-Policy) MC 学习最优的 $\epsilon$-软性策略。
• 离轨 (Off-Policy) MC 使用 重要性采样 (IS)，允许从行为策略 $b$ 生成的数据中学习目标策略 $\pi$（通常是最优贪心策略）。加权重要性采样 (WIS) 在实践中更常用以减小方差。
• MC 的优缺点：
  • 优点：无模型；概念简单；无偏估计（使用完整回报）。
  • 缺点：必须是分幕式任务；效率不高（需要等待片段结束）；方差可能较高（尤其是普通 IS）。
• 展望：MC 方法的局限性（特别是高方差和对完整片段的依赖）引出了下一类重要的无模型学习方法——时序差分 (Temporal-Difference, TD) 学习，它结合了 MC 和动态规划的思想。