Week 4: 蒙特卡洛方法 - 从完整经验中学习

回顾：MDP 与 最优决策

前三周我们建立了强化学习的基础框架：

  • MDP (\(S\), \(A\), \(P\), \(R\), \(\gamma\)): 描述序贯决策问题。
  • 策略 \(\pi\): 智能体的行为方式。
  • 价值函数 (\(V_\pi\), \(Q_\pi\)): 评估策略的好坏。
  • 最优价值函数 (\(V^*\), \(Q^*\)): 描述最优行为能达到的价值上限。
  • Bellman 期望方程: 用于策略评估。
  • Bellman 最优方程: 描述最优价值函数的性质，理论上解出它就能得到最优策略。

问题: Bellman 方程（无论是期望还是最优）都依赖于我们知道环境的模型 (Model)，即状态转移概率 \(P(s' | s, a)\) 和奖励函数 \(R(s, a, s')\)。

现实挑战: 在许多实际商业问题中，我们无法精确知道环境模型 \(P\) 和 \(R\)。

  • 市场如何对价格变动做出反应？(\(P\) 未知)
  • 客户点击广告的具体概率是多少？(\(P\) 未知)
  • 供应链中断的概率和影响？(\(P\), \(R\) 未知)

因此，我们需要无模型 (Model-Free) 的强化学习方法。这类方法不依赖于环境模型，而是直接从智能体与环境交互产生的经验 (Experience) 中学习。

本周我们将学习第一类重要的无模型方法：蒙特卡洛 (Monte Carlo, MC) 方法。

在有模型的情况下，我们可以直接使用 Bellman 期望方程来计算价值函数。以下是一个具体的可计算例子：

问题描述: 考虑一个简单的库存管理问题，状态空间为 {0,1,2}（库存量），动作空间为 {0,1}（不补货/补货）。已知状态转移概率和奖励函数如下：

  • 状态转移概率 \(P(s'|s,a)\):
    • 当 \(a=0\)（不补货）时：
      • \(P(s'=\max(s-1,0)|s,a=0) = 0.8\)
      • \(P(s'=\max(s-2,0)|s,a=0) = 0.2\)
    • 当 \(a=1\)（补货）时：
      • \(P(s'=\min(s+1,2)|s,a=1) = 0.7\)
      • \(P(s'=\min(s+2,2)|s,a=1) = 0.3\)
  • 奖励函数 \(R(s,a,s')\):
    • 持有成本：\(-0.1 * s'\)
    • 补货成本：\(-0.5 * a\)
    • 销售收益：\(+1.0 * (s - s')\)
    • 总奖励：\(R(s,a,s') = 1.0*(s-s') - 0.1*s' - 0.5*a\)
  • 折扣因子 \(\gamma = 0.9\)

针对库存管理例子的 Bellman 期望方程计算

def inventory_bellman_expectation():
    """
    计算库存管理例子的价值函数
    """
    # 定义状态和动作空间
    states = [0, 1, 2]
    actions = [0, 1]
    
    # 定义状态转移概率
    P = {
        0: {
            0: {0: 1.0, 1: 0.0, 2: 0.0},  # 不补货, s'=0 with prob 1.0, s'=1,2 with prob 0.0
            1: {0: 0.0, 1: 0.7, 2: 0.3}   # 补货, s'=1 with prob 0.7, s'=2 with prob 0.3, s'=0 with prob 0.0
        },
        1: {
            0: {0: 1.0, 1: 0.0, 2: 0.0},  # 不补货, s'=0 with prob 1.0, s'=1,2 with prob 0.0
            1: {0: 0.0, 1: 0.0, 2: 1.0}   # 补货, s'=2 with prob 1.0, s'=0,1 with prob 0.0
        },
        2: {
            0: {0: 0.2, 1: 0.8, 2: 0.0},  # 不补货, s'=0 with prob 0.2, s'=1 with prob 0.8, s'=2 with prob 0.0
            1: {0: 0.0, 1: 0.0, 2: 1.0}   # 补货, s'=2 with prob 1.0, s'=0,1 with prob 0.0
        }
    }
    
    # 定义奖励函数
    def R(s, a, s_prime):
        return 1.0 * (s - s_prime) - 0.1 * s_prime - 0.5 * a
    
    # 定义策略（均匀随机策略）
    policy = {
        0: {0: 0.5, 1: 0.5},
        1: {0: 0.5, 1: 0.5},
        2: {0: 0.5, 1: 0.5}
    }
    
    # 初始化价值函数
    V = {s: 0 for s in states}
    gamma = 0.9
    theta = 1e-6
    
    # 迭代更新价值函数
    while True:
        delta = 0
        for s in states:
            v = V[s]
            # 计算新的价值函数
            V[s] = sum(policy[s][a] * sum(P[s][a][s_prime] * 
                    (R(s, a, s_prime) + gamma * V[s_prime])
                    for s_prime in states) 
                    for a in actions)
            # 更新最大变化量
            delta = max(delta, abs(v - V[s]))
        # 检查是否收敛
        if delta < theta:
            break
            
    return V

# 示例调用
inventory_bellman_expectation()

这个例子展示了在有完整环境模型的情况下，如何具体应用 Bellman 期望方程进行价值函数的计算。

优点: 1. 精确计算: 直接使用 Bellman 期望方程可以得到精确的价值函数值，不需要通过采样来估计。 2. 收敛速度快: 通过迭代更新，通常可以在较少的迭代次数内收敛到真实值。 3. 理论保证: 在满足条件的情况下，可以保证收敛到唯一解。

缺点: 1. 需要完整环境模型: 必须知道状态转移概率 P 和奖励函数 R，这在很多实际问题中难以获得。 2. 计算复杂度高: 对于大规模状态空间，计算所有状态的价值函数会非常耗时。 3. 内存需求大: 需要存储整个状态空间的价值函数，对于高维状态空间可能不现实。 4. 无法处理连续状态空间: 仅适用于离散且有限的状态空间。

无模型预测：蒙特卡洛评估

目标: 在不知道环境模型 \(P\) 和 \(R\) 的情况下，给定一个策略 \(\pi\)，如何估计其价值函数 \(V_\pi(s)\) 或 \(Q_\pi(s, a)\)？

核心思想: 利用大数定律 (Law of Large Numbers)。通过多次模拟（采样），用样本回报的平均值来估计期望回报（即价值函数）。

蒙特卡洛方法的基本流程:

  1. 遵循策略 \(\pi\) 与环境交互，生成大量的完整回合 (Episodes)。
    • 一个回合是从某个起始状态开始，直到达到终止状态为止的一系列 \((S_0, A_0, R_1, S_1, A_1, R_2, ..., S_T)\)。
  2. 对于回合中出现的每个状态 \(s\) (或状态-动作对 \((s, a)\))，计算其在该回合中的实际回报 \(G_t\)。
    • \(G_t = R_{t+1} + γ R_{t+2} + ... + γ^{T-t-1} R_T\)
  3. 将所有回合中状态 \(s\) (或状态-动作对 \((s, a)\)) 的回报收集起来。
  4. 用这些回报的平均值作为 \(V_{\pi}(s)\) (或 \(Q_{\pi}(s, a)\)) 的估计值。

\[ \begin{aligned} V_{\pi}(s) &\approx \text{多次回合中} G_t | S_t = s \text{的平均值} \\ Q_{\pi}(s, a) &\approx \text{多次回合中} G_t | S_t = s, A_t = a \text{的平均值} \end{aligned} \]

首次访问 (First-Visit) MC vs. 每次访问 (Every-Visit) MC

在计算状态 \(s\) (或状态-动作对 \((s, a)\)) 的平均回报时，对于一个回合中 \(s\) (或 \((s, a)\)) 可能出现多次的情况，有两种处理方式：

  • 首次访问 MC (First-Visit MC):
    • 对于每个回合，只计算状态 \(s\) 第一次出现时的回报 \(G_t\)，并将其计入状态 \(s\) 的回报列表。
    • 忽略该回合后续再次访问状态 \(s\) 时的回报。
    • \(V_{\pi}(s) \approx \text{多次回合中} G_t | S_t = s \text{的平均值}\)
  • 每次访问 MC (Every-Visit MC):
    • 对于每个回合，状态 \(s\) 每一次出现时的回报 \(G_t\) 都被计入状态 \(s\) 的回报列表。
    • \(V_{\pi}(s) \approx \text{多次回合中} G_t | S_t = s \text{的平均值}\) （与首次访问MC公式相同，区别在于计算时是否包含重复访问的回报）
选择
  • 两者在理论上都能收敛到真实的 \(V_{\pi}(s)\) (随着回合数趋于无穷)。
  • 首次访问 MC 在理论分析上更常用。
  • 每次访问 MC 更容易实现，并且在某些情况下可能更高效（利用了更多数据点）。
  • 在实践中，两者的差异通常不大。

MC 评估 \(V_{\pi}\) 算法伪代码 (首次访问)

初始化:
$\pi$ ← 要评估的策略
$V(s)$ ← 任意状态价值函数（例如，对所有 $s \in S$，$V(s)=0$）
$Returns(s)$ ← 空列表，对所有 $s \in S$

无限循环（对每个回合）:
使用 $\pi$ 生成一个回合: $S_0, A_0, R_1, S_1, A_1, R_2, ..., S_{T-1}, A_{T-1}, R_T$
$G$ ← 0  # 初始化本回合的回报
Visited_States_In_Episode ← 空集合 # 记录本回合已访问的状态
对回合的每个时间步循环，$t = T-1, T-2, ..., 0$:
    $G$ ← $R_{t+1} + \gamma * G$  # 计算从时间步t开始的回报
    如果 $S_t$ 不在 Visited_States_In_Episode 中:
    将 $G$ 添加到 $Returns(S_t)$
    $V(S_t)$ ← $Returns(S_t)$ 的平均值
    将 $S_t$ 添加到 $Visited_States_In_Episode$

解释:

  1. 初始化 \(V(s)\) 和用于存储回报的列表 \(Returns(s)\)。
  2. 无限循环生成回合。
  3. 对每个生成的回合，从后往前计算每个时间步 \(t\) 的回报 \(G\)。
  4. 对于每个时间步 \(t\) 的状态 \(S_t\)，检查它是否是本回合首次访问。
  5. 如果是首次访问，将计算得到的回报 \(G\) 添加到该状态的回报列表 \(Returns(S_t)\) 中。
  6. 更新 \(V(S_t)\) 为 \(Returns(S_t)\) 中所有回报的平均值。
  7. 标记 \(S_t\) 在本回合已访问。

每次访问 MC 的修改: 只需去掉 Visited_States_In_Episode 的检查和记录即可。

MC 评估 \(Q_{\pi}\) 算法伪代码 (首次访问)

评估 \(Q_{\pi}(s, a)\) 的过程类似，只是我们需要记录和平均状态-动作对 \((s, a)\) 的回报。

初始化:
π ← 要评估的策略
Q(s, a) ← 任意的动作价值函数（例如，对所有 s ∈ S, a ∈ A，Q(s,a)=0）
Returns(s, a) ← 空列表，对所有 s ∈ S, a ∈ A

无限循环（对每个回合）:
使用 π 生成一个回合: S_0, A_0, R_1, S_1, A_1, R_2, ..., S_{T-1}, A_{T-1}, R_T
G ← 0
Visited_StateActions_In_Episode ← 空集合 # 用于首次访问MC
对回合的每个时间步循环，t = T-1, T-2, ..., 0:
    G ← R_{t+1} + γ * G
    StateAction_Pair = (S_t, A_t)
    如果 StateAction_Pair 不在 Visited_StateActions_In_Episode 中: # 用于首次访问MC
    将 G 添加到 Returns(S_t, A_t)
    Q(S_t, A_t) ← Returns(S_t, A_t) 的平均值
    将 StateAction_Pair 添加到 Visited_StateActions_In_Episode # 用于首次访问MC
探索性开端 (Exploring Starts)

为了确保 \(Q(s, a)\) 对所有的状态-动作对都有估计值，我们需要保证在足够多的回合中，所有的 \((s, a)\) 对都被访问到。一种方法是采用探索性开端 (Exploring Starts)：每个回合的起始状态 \(S_0\) 和起始动作 \(A_0\) 是随机选择的，覆盖所有可能的 \((s, a)\) 对。这在模拟中可行，但在真实环境中通常不现实。后续的控制算法会使用其他探索机制（如 \(\epsilon\)-greedy）。

Lab 2: MC 预测实践

目标

  1. 在一个简单的环境中（如 Gridworld 或 Blackjack）实现或运行 MC 预测算法。
  2. 可视化学习到的价值函数。
  3. 理解 MC 方法的优缺点。

环境选择

  • Gridworld (网格世界):
    • 一个经典的 RL 测试平台。智能体在一个二维网格中移动（上、下、左、右）。
    • 某些格子是目标（正奖励），某些是陷阱（负奖励），撞墙保持原地。
    • 状态是离散的（格子坐标），动作是离散的。
    • 通常是回合制任务（到达目标或陷阱结束）。
    • Gymnasium 没有内置的标准 Gridworld，但很容易自己实现或找到第三方实现。
  • Blackjack (二十一点):
    • Gymnasium 内置环境 (gym.make("Blackjack-v1"))。
    • 目标：通过要牌 (hit) 或停牌 (stick) 使得总点数接近 21 点且不超过 21 点，并大于庄家。
    • 状态: (玩家当前总点数, 庄家明牌点数, 玩家是否有可用的 Ace [值为 1 或 11]) (离散)。
    • 动作: 0 (停牌 stick), 1 (要牌 hit) (离散)。
    • 奖励: +1 (赢), -1 (输), 0 (平局)。
    • 回合制任务。

我们将以 Blackjack 为例进行说明，因为它更标准且易于运行。

示例代码框架 (Blackjack - Vπ 评估)

假设我们要评估一个简单的固定策略 π：只要玩家点数小于 20 就一直要牌 (hit)，否则停牌 (stick)。

import gymnasium as gym
import numpy as np
from collections import defaultdict
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D # 用于 3D 绘图

# 创建 Blackjack 环境
env = gym.make("Blackjack-v1", sab=True) # sab=True 表示状态包含玩家是否有可用 Ace

# 1. 定义要评估的策略 π
def simple_policy(observation):
    """
    只要玩家点数小于 20 就一直要牌 (hit)，否则停牌 (stick)。
    observation: (player_sum, dealer_showing, usable_ace)
    """
    player_sum, _, _ = observation
    return 1 if player_sum < 20 else 0 # 1: hit, 0: stick

# 2. 初始化
V = defaultdict(float) # 状态值函数 V(s)，用 defaultdict 初始化为 0
Returns = defaultdict(list) # 存储每个状态的回报列表
N = defaultdict(int) # (可选) 记录每个状态被访问的次数，用于增量更新 V

num_episodes = 500000 # 模拟的回合数

# 3. MC 预测主循环
for i in range(num_episodes):
    if (i + 1) % 50000 == 0:
        print(f"Episode {i+1}/{num_episodes}")

    # 生成一个回合
    episode = []
    observation, info = env.reset()
    terminated = False
    truncated = False
    while not (terminated or truncated):
        action = simple_policy(observation) # 根据策略选择动作
        next_observation, reward, terminated, truncated, info = env.step(action)
        episode.append((observation, action, reward)) # 记录 (状态, 动作, 奖励)
        observation = next_observation

    # 处理回合数据 (首次访问 MC)
    G = 0.0
    visited_states = set()
    # 从后往前遍历回合
    for t in range(len(episode) - 1, -1, -1):
        state, action, reward = episode[t]
        G = reward + 1 * G # Blackjack 环境 gamma 默认为 1

        # 如果是本回合首次访问该状态
        if state not in visited_states:
            Returns[state].append(G)
            # 更新 V(state) 为平均回报
            V[state] = np.mean(Returns[state])
            # --- 或者使用增量更新 (更高效) ---
            # N[state] += 1
            # V[state] = V[state] + (1/N[state]) * (G - V[state])
            # ---------------------------------
            visited_states.add(state)

# 4. 可视化价值函数 (以 V 为例)
# Blackjack 状态: (player_sum, dealer_showing, usable_ace)
# 我们需要将 3D 状态映射到 2D 图上，通常分别绘制 usable_ace=True 和 usable_ace=False 的情况

def plot_blackjack_value_function(V, title="Value Function"):
    min_player_sum = min(k[0] for k in V.keys()) if V else 12 # Handle empty V
    max_player_sum = max(k[0] for k in V.keys()) if V else 21
    min_dealer_show = min(k[1] for k in V.keys()) if V else 1
    max_dealer_show = max(k[1] for k in V.keys()) if V else 10

    player_range = np.arange(min_player_sum, max_player_sum + 1)
    dealer_range = np.arange(min_dealer_show, max_dealer_show + 1)
    X, Y = np.meshgrid(dealer_range, player_range) # 注意顺序

    # 分别绘制有可用 Ace 和无可用 Ace 的情况
    Z_no_ace = np.apply_along_axis(lambda idx: V.get((idx[1], idx[0], False), 0), 2, np.dstack([X, Y]))
    Z_ace = np.apply_along_axis(lambda idx: V.get((idx[1], idx[0], True), 0), 2, np.dstack([X, Y]))

    fig = plt.figure(figsize=(12, 5))

    ax1 = fig.add_subplot(121, projection='3d')
    ax1.plot_surface(X, Y, Z_no_ace, cmap='viridis')
    ax1.set_xlabel('Dealer Showing')
    ax1.set_ylabel('Player Sum')
    ax1.set_zlabel('Value')
    ax1.set_title(f"{title} (No Usable Ace)")
    # Set viewing angle for better visibility if needed
    # ax1.view_init(elev=30, azim=-135)


    ax2 = fig.add_subplot(122, projection='3d')
    ax2.plot_surface(X, Y, Z_ace, cmap='viridis')
    ax2.set_xlabel('Dealer Showing')
    ax2.set_ylabel('Player Sum')
    ax2.set_zlabel('Value')
    ax2.set_title(f"{title} (Usable Ace)")
    # Set viewing angle
    # ax2.view_init(elev=30, azim=-135)


    plt.tight_layout()
    plt.show()

# Check if V is populated before plotting
if V:
    plot_blackjack_value_function(V, title="MC Estimated Value Function (Simple Policy)")
else:
    print("Value function V is empty. No plot generated.")


env.close()

任务与思考

  1. 运行代码: 运行上述 Blackjack MC 预测代码。观察生成的价值函数图像。它是否符合你对这个简单策略的直觉？（例如，点数高时价值是否更高？庄家明牌点数低时价值是否更高？）
  2. 修改策略: 尝试修改 simple_policy，例如改成点数小于 18 就 hit。重新运行 MC 预测，观察价值函数的变化。
  3. (可选) 实现 \(Q_{\pi}\) 评估: 修改代码，计算并可视化 \(Q_{\pi}(s, a)\) 而不是 \(V_{\pi}(s)\)。\(Q\) 函数的可视化稍微复杂，可能需要为每个动作 (hit/stick) 单独绘制价值曲面。
  4. (可选) Gridworld: 如果你找到了或自己实现了 Gridworld 环境，尝试在 Gridworld 中运行 MC 预测。可视化价值函数（可以用热力图表示每个格子的价值）。

MC 方法的优缺点

  • 优点:
    • 无模型: 不需要知道环境的 \(P\) 和 \(R\)。
    • 简单直观: 基于大数定律，易于理解和实现。
    • 无偏估计 (Unbiased): 只要回合能完整生成，MC 估计是 \(V_{\pi}(s)\) 或 \(Q_{\pi}(s, a)\) 的无偏估计。
    • 适用于非马尔可夫环境: 即使环境不完全满足马尔可夫性质，MC 仍然可以应用（尽管理论保证可能减弱）。
  • 缺点:
    • 需要完整回合: 必须等到一个回合结束后才能更新价值函数。对于回合非常长的任务（如某些商业模拟可能持续很久）或者持续性任务，效率低下或无法应用。
    • 高方差 (High Variance): 回报 \(G_t\) 依赖于一个回合中所有的随机转移和奖励，其方差可能很大，导致价值估计收敛慢，需要大量回合才能得到较准确的结果。
    • 学习效率相对较低: 相比于后面要学的 TD 方法，MC 没有利用状态之间的关联信息（Bellman 方程隐含的关系），学习效率可能较低。
    • 只适用于回合制任务 (Episodic Tasks): 基本的 MC 方法不适用于没有明确终点的持续性任务。
关键限制

MC 方法必须等待回合结束才能学习，这在很多实时决策或长周期商业场景中是不可接受的。

下周预告: 时序差分学习 (Temporal-Difference Learning, TD) - 从不完整经验中学习，克服 MC 的部分缺点。