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

本内容暂时为 PPT 转述，后续会进行修编

蒙特卡洛 (Monte Carlo, MC) 方法#

MC 背景知识 (Background)#

• 蒙特卡洛方法：是一类基于重复随机抽样 (Repeated Random Sampling) 来获得数值结果的计算算法。
• MC 在强化学习中的应用：
  • 核心思想：通过从与环境交互产生的完整经验片段 (Complete Episodes) 中学习价值函数和策略。
  • 无模型 (Model-Free)：不依赖于已知的 MDP 转移概率 $\mathcal{P}$ 和奖励函数 $\mathcal{R}$。
  • 基本原则：用平均样本回报 (Mean Sample Return) 来估计期望回报（即价值函数）。

MC 预测 (Monte Carlo Prediction)#

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

• 基本原理：
  • 回顾：价值函数是期望回报 $v_\pi(s) = \mathbb{E}_\pi[G_t | S_t=s]$。
  • MC 方法用样本均值来近似期望值。通过策略 $\pi$ 生成许多完整的片段 (episodes)。对于某个状态 $s$，收集所有在这些片段中访问 $s$ 之后获得的回报 $G_t^{(i)}$。
  • 价值估计： $$V(s) \approx \frac{1}{N} \sum_{i=1}^N G_t^{(i)} \quad (\text{其中 } S_t^{(i)} = s)$$
• 重要前提：分幕式任务 (Episodic Tasks)：MC 方法需要完整的片段来计算回报 $G_t$，因此它直接适用于有明确终止状态的分幕式任务。
• 首次访问 vs 每次访问：当估计 $v_\pi(s)$ 时，一个片段中状态 $s$ 可能被访问多次。
  • 首次访问 MC (First-Visit MC)：对于每个片段，只使用状态 $s$ 在该片段中第一次被访问时之后的回报 $G_t$ 来更新 $V(s)$ 的估计。
  • 每次访问 MC (Every-Visit MC)：对于每个片段，使用状态 $s$ 在该片段中每一次被访问时之后的回报 $G_t$ 来更新 $V(s)$ 的估计。
  • 收敛性：理论上，随着访问次数趋于无穷，两种方法都会收敛到真实的 $v_\pi(s)$。
• 首次访问 MC 预测算法 (Estimating $v_\pi$)：

  初始化 V(s) = 0, Returns(s) = 空列表, 对所有 s
  循环 (对每个 episode):
      使用策略 π 生成一个 episode: S₀, A₀, R₁, ..., S_{T-1}, A_{T-1}, R_T
      G = 0  // 初始化回报
      visited_states_in_episode = set() // 用于首次访问
      从 t = T-1 到 0: // 从后往前计算回报
          G = R_{t+1} + γ * G
          如果 S_t 不在 visited_states_in_episode 中: // 检查是否首次访问
              将 G 添加到 Returns(S_t)
              V(S_t) = average(Returns(S_t)) // 更新价值估计
              将 S_t 加入 visited_states_in_episode

  plaintext
• 增量式实现 (Incremental Implementation)：为了避免存储所有回报，可以使用增量式更新：
  • 对于状态 $s$ 的第 $N(s)$ 次（首次）访问，得到回报 $G_t$： $$N(s) \leftarrow N(s) + 1$$ $$$$
  • 或者使用常数步长 $\alpha$（适用于非平稳环境或作为一种平滑手段）： $$V(s) \leftarrow V(s) + \alpha (G_t - V(s))$$

MC 控制 (Monte Carlo Control)#

MC 控制的目标是：使用 MC 方法学习最优策略 $\pi_*$。

• 基于动作价值 (Action-Value Based)：
  • 在无模型设置下，仅有 $v_\pi(s)$ 不足以进行策略改进（因为需要模型 $\mathcal{P}, \mathcal{R}$ 来计算 $q_\pi(s, a)$）。
  • 因此，MC 控制通常直接估计动作价值函数 $q_\pi(s, a)$。
  • 估计方法与 $v_\pi(s)$ 类似：$Q(s, a) \approx \text{average}(G_t \text{ for all visits to } (s, a))$，同样有首次访问和每次访问两种方式。
• 广义策略迭代 (GPI) 框架：MC 控制遵循 GPI 的模式，交替进行策略评估和策略改进。
  • 评估：使用 MC 方法估计当前策略 $\pi$ 的动作价值 $Q \approx q_\pi$。
  • 改进 (I)：根据当前的动作价值估计 $Q$，更新策略 $\pi$，使其变得更贪心（例如，$\pi(s) \leftarrow \arg\max_a Q(s, a)$）。
• 维持探索的挑战 (Maintaining Exploration)：
  • 如果策略在改进步骤中变得确定性贪心，可能会导致某些状态-动作对 $(s, a)$ 再也不会被访问。
  • 如果这些未被访问的 $(s, a)$ 恰好是最优策略的一部分，那么算法将无法发现最优策略。
  • MC 评估依赖于持续访问所有需要评估其价值的状态-动作对。
• 解决方案 1：试探性出发 (Exploring Starts, ES)：
  • 假设：每次开始一个新片段时，我们能够随机选择一个任意的状态-动作对 $(S_0, A_0)$ 作为起点，并且保证所有 $(s, a)$ 对都有非零概率被选为起点。
  • MC ES 算法：

    初始化 Q(s, a) 和 π(s) 任意, Returns(s, a) = 空列表
    循环 无限次:
        随机选择一个起始 S₀ 和 A₀ (满足 ES 条件)
        从 (S₀, A₀) 开始, 之后遵循策略 π 生成一个 episode
        G = 0
        对 episode 中的每一步 t = T-1 到 0:
            G = R_{t+1} + γ * G
            如果 (S_t, A_t) 是首次出现在 S₀, A₀, S₁, A₁, ... S_{t-1}, A_{t-1} 中:
                将 G 添加到 Returns(S_t, A_t)
                Q(S_t, A_t) = average(Returns(S_t, A_t))
                // 策略改进：更新该状态的策略为贪心策略
                π(S_t) = argmax[a'] Q(S_t, a')

    plaintext
  • 优点：在 ES 假设下，保证收敛到最优策略 $\pi_*$ 和最优动作价值 $q_*$。
  • 缺点：ES 假设在现实中通常难以满足。
• 解决方案 2：同轨策略 (On-Policy) MC 控制 (无 ES 假设)：
  • 核心思想：不依赖 ES，而是通过确保策略本身永远保持探索性来解决探索问题。
  • 同轨 (On-Policy)：用于生成数据的策略与正在学习和改进的策略是同一个。
  • 离轨 (Off-Policy)：用于生成数据的策略（行为策略 $\mu$）与正在学习和改进的策略（目标策略 $\pi$）不同。
  • $\epsilon$-软性策略 ($\epsilon$-Soft Policies)：为了保证持续探索，采用 $\epsilon$-软性策略，即对于所有状态 $s$ 和动作 $a$，都有 $\pi(a|s) \ge \frac{\epsilon}{|\mathcal{A}(s)|} > 0$。这意味着每个动作始终有被选中的最小概率。
  • $\epsilon$-贪心策略 ($\epsilon$-Greedy Policies)：是实现 $\epsilon$-软性的一种常用方法。
    • 以 $1-\epsilon$ 的概率选择当前认为最优的动作（根据 $Q(s,a)$）。
    • 以 $\epsilon$ 的概率从所有动作中随机选择一个。
  • 同轨首次访问 MC 控制算法 (On-Policy First-Visit MC Control)：

    初始化 Q(s, a) 任意, Returns(s, a) = 空列表
    初始化 π 为任意的 ε-soft 策略
    循环 无限次:
        (a) 使用当前策略 π 生成一个 episode
        (b) 对 episode 中每个出现的 (s, a) 对:
            G = episode 中首次访问 (s, a) 后的回报
            将 G 添加到 Returns(s, a)
            Q(s, a) = average(Returns(s, a))  // 策略评估
        (c) 对 episode 中每个出现的 s:
            A* = argmax[a'] Q(s, a') // 找到当前最优动作
            // 策略改进：更新策略 π(·|s) 使其对 Q(s,·) 是 ε-greedy
            对所有 a ∈ A(s):
                如果 a == A*:
                    π(a|s) = 1 - ε + ε / |A(s)|
                否则:
                    π(a|s) = ε / |A(s)|

    plaintext
  • 收敛性：该算法不会收敛到真正的最优策略 $\pi_*$（因为 $\epsilon>0$），但会收敛到一个接近最优的 $\epsilon$-贪心策略。可以通过逐渐减小 $\epsilon$ 来趋近最优。
  • 策略改进保证：定理证明，对于一个 $\epsilon$-贪心策略 $\pi$，基于其动作价值 $q_\pi$ 再进行 $\epsilon$-贪心选择得到的新策略 $\pi'$，仍然满足 $v_{\pi'} \ge v_\pi$。这保证了 GPI 过程的单调性。

离轨策略 MC 控制 (Off-Policy MC Control)#

同轨策略 (On-Policy) MC 控制为了保证探索，最终学习到的是一个 $\epsilon$-软性策略，而非真正最优的确定性贪心策略。离轨策略学习的目标就是解决这个问题：使用一个探索性的行为策略 $\mu$ (或记作 $b$) 来生成数据，但同时学习和评估一个不同的（通常是确定性贪心的）目标策略 $\pi$。

• 基本思想：

  • 目标策略 (Target Policy) $\pi$：我们想要学习并评估的策略（通常是当前最优的贪心策略）。
  • 行为策略 (Behavior Policy) $b$：用于实际选择动作、与环境交互并生成经验片段的策略（必须具有探索性，例如 $\epsilon$-greedy）。
  • 优点：可以学习最优确定性策略，同时保证探索。更通用，允许从历史数据或其他智能体的经验中学习。
  • 挑战：行为策略 $b$ 产生的数据分布与目标策略 $\pi$ 下的分布不同，需要进行校正。
  • 覆盖性假设 (Coverage Assumption)：需要保证行为策略 $b$ 探索的动作包含了目标策略 $\pi$ 可能选择的动作，即如果 $\pi(a|s) > 0$，则必须有 $b(a|s) > 0$。

• 重要性采样 (Importance Sampling, IS)：

  • IS 是一种通用的统计技术，用于根据从一个分布 $q(x)$ 得到的样本来估计另一个分布 $p(x)$ 下的期望值。
  • 原理： $$\mathbb{E}_{x\sim p}[f(x)] = \int p(x)f(x)dx = \int q(x) \frac{p(x)}{q(x)} f(x)dx = \mathbb{E}_{x\sim q}\left[\frac{p(x)}{q(x)}f(x)\right]$$
  • 重要性采样比率 (Importance Sampling Ratio)：$\beta(x) = \frac{p(x)}{q(x)}$。通过用这个比率对从 $q(x)$ 抽取的样本 $f(x)$ 进行加权，可以得到 $p(x)$ 下期望的无偏估计。

• 用于离轨 MC 预测的重要性采样 (IS for Off-Policy MC Prediction)：

  • 目标：使用行为策略 $b$ 生成的片段回报 $G_t$ 来估计目标策略 $\pi$ 的价值 $v_\pi(s)$ 或 $q_\pi(s, a)$。
  • 轨迹概率：从时间 $t$ 到 $T-1$ 的状态-动作序列在给定策略下的发生概率正portional于 $\prod_{k=t}^{T-1} \text{policy}(A_k|S_k)$。
  • 重要性采样比率 $\rho_{t:T-1}$：对于从 $t$ 时刻开始到片段结束的回报 $G_t$，其对应的 IS 比率是该段轨迹在目标策略 $\pi$ 和行为策略 $b$ 下发生概率的比值： $$\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)$ 相同且抵消)。这要求 $b(A_k|S_k) > 0$。
  • 加权回报 (Weighted Return)：$G_t^{\pi/b} = \rho_{t:T-1} G_t$。理论上 $\mathbb{E}_b[G_t^{\pi/b} | S_t=s] = v_\pi(s)$。
  • MC 更新：$V(S_t) \leftarrow V(S_t) + \alpha (G_t^{\pi/b} - V(S_t))$。
  • 高方差问题：IS 估计，特别是比率 $\rho$ 可能很大的时候，方差会非常高，导致学习不稳定且收敛缓慢。
  • 普通 vs. 加权重要性采样 (Ordinary vs. Weighted IS)：
    • 设 $\mathcal{T}(s)$ 是状态 $s$ 被访问的所有时间步集合。
    • 普通重要性采样 (OIS)：$V(s) = \frac{\sum_{t\in\mathcal{T}(s)} \rho_{t:T(t)-1} G_t}{|\mathcal{T}(s)|}$。无偏，但方差大。
    • 加权重要性采样 (WIS)：$V(s) = \frac{\sum_{t\in\mathcal{T}(s)} \rho_{t:T(t)-1} G_t}{\sum_{t\in\mathcal{T}(s)} \rho_{t:T(t)-1}}$。有偏（但在极限情况下一致），通常方差小得多，实践中更常用。

• WIS 的增量式实现 (Incremental Implementation of WIS)：

  • 维护累积权重 $C(s)$ 和价值估计 $V(s)$。
  • 当获得状态 $s$ 的第 $n$ 个回报 $G_n$ 和对应的权重 $W_n = \rho_{t:T(n)-1}$ 时： $$C_n \leftarrow C_{n-1} + W_n \quad (\text{其中 } C_0 = 0)$$ $$V_n \leftarrow V_{n-1} + \frac{W_n}{C_n} [G_n - V_{n-1}]$$

• 离轨 MC 预测算法 (Off-Policy MC Prediction using WIS)：

  • 估计目标策略 $\pi$ 的 $Q \approx q_\pi$，使用行为策略 $b$ 生成数据。

  输入: 目标策略 π
  初始化: Q(s, a) 任意, C(s, a) = 0, 对所有 s, a
  循环 无限次 (对每个 episode):
      选择行为策略 b (确保覆盖 π)
      使用 b 生成 episode: S₀, A₀, R₁, ..., S_{T-1}, A_{T-1}, R_T
      G = 0
      W = 1
      从 t = T-1 到 0:
          G = R_{t+1} + γ * G
          C(S_t, A_t) = C(S_t, A_t) + W
          // 用 WIS 更新 Q 值
          Q(S_t, A_t) = Q(S_t, A_t) + (W / C(S_t, A_t)) * [G - Q(S_t, A_t)]
          // 更新下次回溯的 IS 权重
          W = W * (π(A_t | S_t) / b(A_t | S_t))
          // 如果 W = 0, 则后续轨迹与 π 无关，可提前终止
          如果 W == 0: 跳出内循环 (break)

  plaintext

• 离轨 MC 控制算法 (Off-Policy MC Control using WIS)：

  • 目标策略 $\pi$：通常是我们想要学习的最优策略，即确定性贪心策略 $\pi(s) = \arg\max_a Q(s, a)$。
  • 行为策略 $b$：必须是探索性的，如 $\epsilon$-greedy。
  • 算法：结合了上面的离轨预测和策略改进。

  初始化: Q(s, a) 任意, C(s, a) = 0, 对所有 s, a
           π(s) = argmax[a'] Q(s, a') 对所有 s // 初始化目标策略
  循环 无限次 (对每个 episode):
      选择行为策略 b (e.g., ε-greedy w.r.t. 当前 Q)
      使用 b 生成 episode: S₀, A₀, R₁, ..., S_{T-1}, A_{T-1}, R_T
      G = 0
      W = 1
      从 t = T-1 到 0:
          G = R_{t+1} + γ * G
          C(S_t, A_t) = C(S_t, A_t) + W
          Q(S_t, A_t) = Q(S_t, A_t) + (W / C(S_t, A_t)) * [G - Q(S_t, A_t)] // (E) Off-policy 评估
          π(S_t) = argmax[a'] Q(S_t, a') // (I) 策略改进
          // 如果行为策略选择的动作 A_t 不是目标策略 π 会选择的动作:
          如果 A_t != π(S_t):
              // 那么这条轨迹后续部分对于 π 的概率为 0，停止处理此 episode
              跳出内循环 (break)
          // 否则，更新 IS 权重 (由于 π 是确定性的，π(A_t|S_t) = 1)
          W = W * (1 / b(A_t | S_t))

  plaintext
  • 关键点：由于目标策略 $\pi$ 是确定性贪心的，一旦行为策略 $b$ 选择了一个非贪心动作 $A_t$，那么从该点往前的轨迹对于评估 $\pi$ 就没有意义了（因为 $\pi(A_t|S_t)=0$），此时重要性采样比率 $W$ 会变为 0，可以提前终止该 episode 的回溯处理。

小结 (Summary)#

• MC 方法是无模型的，直接从完整的经验片段中学习。
• MC 预测通过平均回报来估计 $v_\pi$ 或 $q_\pi$ (首次访问/每次访问)。
• MC 控制使用 GPI 框架，通过估计 $q_\pi$ 并进行策略改进来寻找最优策略。
• 维持探索是 MC 控制的关键挑战，可通过 Exploring Starts (理论上) 或 On-Policy $\epsilon$-soft 方法 (实践中常用) 来解决。
• On-Policy MC 控制学习最优的 $\epsilon$-soft 策略。
• 下一步将学习 Off-Policy 方法和 Temporal-Difference (TD) 学习。