Week 5: 时序差分学习 - 从不完整经验中学习

回顾：蒙特卡洛 (MC) 方法

上周我们学习了蒙特卡洛 (MC) 方法用于无模型预测：

  • 核心思想: 通过模拟大量完整回合，用样本回报 \(G_t\) 的平均值来估计 \(V_{\pi}(s)\) 或 \(Q_{\pi}(s, a)\)。
  • 优点: 无模型、简单直观、无偏估计。
  • 缺点:
    • 必须等待回合结束才能学习和更新价值函数。
    • 高方差，导致收敛可能较慢。
    • 基本形式只适用于回合制任务。

这些缺点，特别是必须等待回合结束，限制了 MC 方法在许多需要快速响应或回合非常长的场景中的应用。本周我们将学习一种更灵活、应用更广泛的无模型预测方法：时序差分学习 (Temporal-Difference Learning, TD)。

时序差分 (TD) 学习核心思想

TD 学习结合了 MC 方法和动态规划 (Dynamic Programming, DP) 的思想。

  • 像 MC 一样: TD 直接从与环境交互的经验中学习，不需要环境模型 (\(P\), \(R\))。
  • 像 DP 一样: TD 使用自举 (Bootstrapping) 的思想，即用当前估计的价值来更新之前的估计，而不是等待最终的实际回报。这种思想类似于动态规划中利用已知信息逐步求解未知问题的过程。

关键区别:

  • MC 更新目标: 使用完整的回报 \(G_t\) 来更新 \(V(S_t)\)。
    • \(V(S_t) ← V(S_t) + \alpha [G_t - V(S_t)]\) (\(\alpha\) 是学习率)
  • TD 更新目标: 使用一步之后的奖励 \(R_{t+1}\) 和后继状态的估计价值 \(\gamma V(S_{t+1})\) 来更新 \(V(S_t)\)。
    • \(V(S_t) ← V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]\)
TD 方法与 MC 方法的比较

TD 方法的优点:

  • 实时性: 不需要等待回合结束，可以在每一步之后立即更新，适用于需要快速响应的场景。
  • 低方差: 只依赖单步转移，相比 MC 的完整回合回报，方差更小。
  • 适用性广: 既适用于回合制任务，也适用于连续任务。

TD 方法的缺点:

  • 引入偏差: 由于使用自举，依赖于当前的价值估计，可能导致偏差。
  • 收敛性: 在某些情况下，收敛性可能不如 MC 方法稳定。

MC 方法的优点:

  • 无偏性: 使用实际回报，不依赖估计值，是无偏估计。
  • 简单直观: 直接使用完整回合的回报，概念上更容易理解。

MC 方法的缺点:

  • 高方差: 完整回合的回报可能波动较大，导致高方差。
  • 延迟更新: 必须等待回合结束才能更新，不适合实时应用。
  • 仅限回合制: 基本形式只适用于回合制任务。
TD 方法的有效性及理论证明

TD 方法不仅在实践中表现出色，其有效性也得到了理论证明：

  • 理论保证: Sutton (1988) 在论文《Learning to Predict by the Methods of Temporal Differences》中首次系统性地提出了 TD 学习算法，并证明了其收敛性。
  • 收敛性证明: Tsitsiklis (1994) 在《Asynchronous Stochastic Approximation and Q-Learning》中严格证明了 TD(0) 在马尔可夫决策过程下的收敛性。
  • 性能优势: Singh 和 Dayan (1998) 在《Analytical Mean Squared Error Curves for Temporal Difference Learning》中通过理论分析表明，TD 方法在均方误差方面优于 MC 方法。
  • 实际应用: Tesauro (1995) 在《Temporal Difference Learning and TD-Gammon》中展示了 TD 方法在西洋双陆棋中的卓越表现，达到了人类专家水平。

这些理论研究和实际应用共同证明了 TD 方法的有效性和实用性，使其成为强化学习领域最重要的算法之一。

TD(0) 预测 (最简单的 TD 方法)

TD(0) 是最基础的 TD 预测算法，用于在给定策略 \(\pi\) 的情况下估计 \(V_{\pi}\)。

更新规则: 在时间步 \(t\)，智能体处于状态 \(S_t\)，执行动作 \(A_t\) (根据策略 \(\pi\))，得到奖励 \(R_{t+1}\) 和下一个状态 \(S_{t+1}\)。TD(0) 使用这个单步转移 (transition) \((S_t, A_t, R_{t+1}, S_{t+1})\) 来更新状态 \(S_t\) 的价值估计 \(V(S_t)\)：

\[ V(S_t) ← V(S_t) + \alpha [ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) ] \]

其中:

  • \(\alpha\) (Alpha): 学习率 (Learning Rate)，是一个小的正数 (e.g., 0.1, 0.01)。它控制了每次更新的步长。
  • \(R_{t+1} + \gamma V(S_{t+1})\): 称为 TD 目标 (TD Target)。这是对状态 \(S_t\) 应该具有的价值的一个估计。它由两部分组成：
    • \(R_{t+1}\): 实际获得的即时奖励。
    • \(\gamma V(S_{t+1})\): 对未来所有奖励的折扣总和的当前估计 (基于后继状态 \(S_{t+1}\) 的当前价值估计 \(V(S_{t+1})\) 进行自举)。
  • \(\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)\): 称为 TD 误差 (TD Error)。它衡量了当前估计 \(V(S_t)\) 与更”准确”的 TD 目标之间的差距。TD 学习的目标就是通过调整 \(V(S_t)\) 来减小这个误差。
TD(0) 的含义

“0” 表示 TD 误差 \(\delta_t\) 只依赖于下一步 (\(t+1\)) 的信息 (\(R_{t+1}\), \(S_{t+1}\))。还有更复杂的 TD(\(\lambda\)) 算法会考虑未来更多步的信息。

自举 (Bootstrapping)

TD 学习的核心特点是自举 (Bootstrapping)。它指的是用当前的估计值来更新估计值。

在 TD(0) 中，我们使用 \(V(S_{t+1})\)（一个估计值）来计算 TD 目标，进而更新 \(V(S_t)\)（另一个估计值）。

  • 优点: 使得 TD 可以在每一步之后立即学习，不需要等待回合结束。
  • 缺点: 引入了偏差 (Bias)。因为 TD 目标 \(R_{t+1} + \gamma V(S_{t+1})\) 本身就依赖于可能不准确的 \(V(S_{t+1})\)。如果 \(V(S_{t+1})\) 的估计不准，那么对 \(V(S_t)\) 的更新也会受到影响。

TD(0) 预测算法伪代码

初始化:
π ← 要评估的策略
V(s) ← 任意状态值函数 (例如，对所有 s ∈ S，V(s)=0)
α ← 学习率 (一个小的正数)

对每个回合循环:
初始化 S (回合的第一个状态)
对回合的每一步循环:
    A ← 根据策略 π 为 S 选择的动作
    执行动作 A，观察 R, S' (下一个状态)
    # 核心更新步骤
    V(S) ← V(S) + α * [R + γ * V(S') - V(S)]
    S ← S' # 转移到下一个状态
    如果 S 是终止状态，跳出内层循环 (回合结束)

解释:

  1. 初始化 \(V(s)\) 和学习率 \(\alpha\)。
  2. 对于每个回合：
  3. 获取起始状态 \(S\)。
  4. 对于回合中的每一步：
  5. 根据策略 \(\pi\) 选择动作 \(A\)。
  6. 执行动作 \(A\)，观察到奖励 \(R\) 和下一个状态 \(S'\)。
  7. 计算 TD 误差: \(\delta = R + \gamma * V(S') - V(S)\) (如果 \(S'\) 是终止状态，则 \(V(S')=0\))。
  8. 更新当前状态的价值: \(V(S) ← V(S) + \alpha * \delta\)。
  9. 将当前状态更新为下一个状态：\(S ← S'\)。
  10. 如果 \(S'\) 是终止状态，则结束当前回合。

Blackjack环境下的TD(0)预测实现

为了更好地理解TD(0)算法的实际应用，我们以Blackjack环境为例，实现TD(0)预测算法，与前面学习的MC方法形成对比。

import gymnasium as gym
import numpy as np
from collections import defaultdict
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

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

# 定义要评估的策略 π（与MC方法中相同）
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

# 初始化
V = defaultdict(float)  # 状态值函数 V(s)，用 defaultdict 初始化为 0
alpha = 0.1  # 学习率
gamma = 1.0  # 折扣因子，Blackjack 环境通常使用 γ=1

num_episodes = 500000  # 模拟的回合数

# TD(0) 预测主循环
for i in range(num_episodes):
    if (i + 1) % 50000 == 0:
        print(f"Episode {i+1}/{num_episodes}")
    
    # 初始化回合
    observation, info = env.reset()
    terminated = False
    truncated = False
    
    # 对回合的每一步循环
    while not (terminated or truncated):
        action = simple_policy(observation)  # 根据策略选择动作
        
        # 记录当前状态，以便后续更新
        current_state = observation
        
        # 执行动作，获取奖励和下一个状态
        next_observation, reward, terminated, truncated, info = env.step(action)
        
        # 如果游戏结束，下一个状态的价值为0
        next_state_value = 0 if terminated else V[next_observation]
        
        # 计算 TD 误差
        td_error = reward + gamma * next_state_value - V[current_state]
        
        # 更新当前状态的价值
        V[current_state] = V[current_state] + alpha * td_error
        
        # 移动到下一个状态
        observation = next_observation

# 可视化价值函数
def plot_blackjack_value_function(V, title="Value Function"):
    # 确定价值函数的范围
    player_range = range(12, 22)  # 玩家点数范围
    dealer_range = range(1, 11)   # 庄家明牌范围
    
    X, Y = np.meshgrid(dealer_range, player_range)
    
    # 分别绘制有可用 Ace 和无可用 Ace 的情况
    Z_no_ace = np.zeros((len(player_range), len(dealer_range)))
    Z_ace = np.zeros((len(player_range), len(dealer_range)))
    
    for i, player in enumerate(player_range):
        for j, dealer in enumerate(dealer_range):
            Z_no_ace[i, j] = V[(player, dealer, False)]
            Z_ace[i, j] = V[(player, dealer, True)]
    
    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('庄家明牌')
    ax1.set_ylabel('玩家点数')
    ax1.set_zlabel('价值')
    ax1.set_title(f"{title} (无可用 Ace)")
    
    ax2 = fig.add_subplot(122, projection='3d')
    ax2.plot_surface(X, Y, Z_ace, cmap='viridis')
    ax2.set_xlabel('庄家明牌')
    ax2.set_ylabel('玩家点数')
    ax2.set_zlabel('价值')
    ax2.set_title(f"{title} (有可用 Ace)")
    
    plt.tight_layout()
    plt.show()

# 可视化TD(0)估计的价值函数
plot_blackjack_value_function(V, title="TD(0) 估计的价值函数 (简单策略)")

env.close()

这个TD(0)实现的核心区别在于，它在每一步之后立即更新状态价值，而不是像MC方法那样等待整个回合结束。

在Blackjack这样的环境中，TD(0)通常会比MC方法更快地收敛，特别是在训练的早期阶段。这是因为TD(0)的更新目标具有更低的方差（只依赖于一步奖励而非整个回合的累积奖励）。

通过运行上述代码并与MC方法进行对比，你可以观察到：

  1. TD(0)在较少的回合数下就能获得较好的价值估计
  2. TD(0)生成的价值函数可能与MC方法略有不同，特别是在状态访问频率较低的区域
  3. TD(0)算法更适合在线学习，无需存储整个回合的历史

这个例子展示了TD方法的核心优势：能够从部分经验中学习，而不必等待完整回合结束。这一特性使TD方法在很多实际应用中比MC方法更为实用。

TD(0) vs. Monte Carlo (MC)

TD(0) 和 MC 都是用于策略评估的无模型方法，但它们有显著的区别：

特性 Monte Carlo (MC) Temporal-Difference (TD(0))
更新时机 回合结束后 每一步之后 (Online)
更新目标 完整回报 \(G_t\) TD 目标: \(R_{t+1} + \gamma V(S_{t+1})\)
是否自举 否 (No Bootstrapping) 是 (Bootstrapping)
偏差 (Bias) 无偏 (Unbiased) 有偏 (Biased, 依赖于 \(V(S_{t+1})\))
方差 (Variance) 高方差 (High Variance) 低方差 (Low Variance)
对初始值敏感度 低 高
适用任务 回合制 (Episodic) 回合制 & 持续性 (Continuing)
计算效率 可能较低 (需存储整个回合) 通常较高 (只需存储上一步信息)
收敛性 (Markov) 收敛到 \(V_{\pi}\) 收敛到 \(V_{\pi}\) (通常更快)
收敛性 (Non-Markov) 仍可应用，可能收敛到近似解 理论保证减弱，可能不收敛或收敛到错误值
偏差-方差权衡 (Bias-Variance Tradeoff)
  • MC: 使用的是实际的、完整的样本回报 \(G_t\)，所以对 \(V_{\pi}(s)\) 的估计是无偏的。但 \(G_t\) 受到整个回合随机性的影响，方差很大。
  • TD(0): 使用的是 TD 目标 \(R_{t+1} + \gamma V(S_{t+1})\)，它本身依赖于估计值 \(V(S_{t+1})\)，因此是有偏的。但 TD 目标只涉及一步随机性 (\(R_{t+1}\), \(S_{t+1}\))，方差比 \(G_t\) 小得多。

在实践中，TD 方法通常因为其较低的方差和在线学习能力而收敛更快，尤其是在状态空间较大的情况下。然而，TD 的偏差意味着它对初始值更敏感，并且在非马尔可夫环境中可能表现不佳。

何时选择？
  • 如果环境模型已知 -> 动态规划 (DP)
  • 如果环境模型未知，且任务是回合制的，可以轻松模拟大量完整回合 -> MC 或 TD (TD 通常更快)
  • 如果环境模型未知，且任务是持续性的，或者回合非常长 -> TD

Lab 3: TD(0) 预测实践

目标

  1. 在一个简单的环境中（如 Gridworld）实现或运行 TD(0) 预测算法。
  2. 对比 TD(0) 和 MC 方法在相同任务上的收敛速度和最终价值估计结果。

环境：Gridworld

Gridworld 是一个非常适合演示 TD 和 MC 区别的环境。我们可以定义一个简单的网格，包含起始点、目标点（正奖励）、陷阱点（负奖励）和普通格子（小负奖励，鼓励尽快结束）。

由于 Gymnasium 没有内置的标准 Gridworld，你需要：

  • 选项 A: 自己实现一个简单的 Gridworld 环境类，遵循 Gymnasium 的 API (类似上周 Lab 的 SimpleInventoryEnv)。
  • 选项 B: 在网上搜索并使用一个现成的 Python Gridworld 实现 (确保它提供 step 和 reset 等基本接口)。

Gridworld 示例定义:

  • 4x4 网格。
  • 状态: 格子坐标 (row, col)。
  • 动作: 上(0), 下(1), 左(2), 右(3)。
  • 起始点: (0, 0)。
  • 目标点: (3, 3)，奖励 +1，回合结束。
  • 陷阱点: (1, 1), (2, 3)，奖励 -1，回合结束。
  • 普通格子: 移动一步奖励 -0.1。
  • 撞墙: 状态不变，奖励 -0.1。
  • 策略 \(\pi\): 随机策略 (等概率选择上/下/左/右)。

任务

  1. 实现/获取 Gridworld 环境: 确保你有一个可以运行的 Gridworld 环境。
  2. 实现 TD(0) 预测:
    • 初始化 \(V(s) = 0, \forall s \in S\)。
    • 选择一个学习率 \(\alpha\) (e.g., 0.1)。
    • 选择一个折扣因子 \(\gamma\) (e.g., 0.9 or 1.0)。
    • 运行 TD(0) 算法（使用随机策略 \(\pi\)）足够多的回合 (e.g., 1000, 5000, 10000)。
    • 记录或可视化 \(V(s)\) 随着回合数的变化过程。
  3. 实现 MC 预测 (首次访问或每次访问):
    • 使用相同的 Gridworld 环境和随机策略 \(\pi\)。
    • 运行 MC 预测算法相同的回合数。
    • 记录或可视化 \(V(s)\) 随着回合数的变化过程。
  4. 对比分析:
    • 收敛速度: 比较 TD(0) 和 MC 的价值函数 \(V(s)\) 达到稳定状态所需的回合数。哪个更快？
    • 最终结果: 比较两种方法最终估计出的 \(V(s)\) 是否相似？如果有差异，可能是什么原因？
    • 方差: (可选) 如果记录了每次更新的值，可以观察 TD 误差和 MC 回报 \(G_t\) 的波动情况。TD 误差的波动是否通常小于 \(G_t\) 的波动？
    • 实验参数: 尝试改变学习率 \(\alpha\) 和回合数，观察对 TD(0) 收敛速度和结果的影响。

可视化

对于 Gridworld，价值函数 \(V(s)\) 可以方便地用热力图 (Heatmap) 可视化：创建一个与网格大小相同的矩阵，每个单元格的值对应 \(V(row, col)\)。

# 假设 V 是一个字典，key 是 (row, col) 元组，value 是价值
# grid_height, grid_width 是网格尺寸
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns # 用于更好的热力图

# 假设 grid_height 和 grid_width 已定义
value_grid = np.zeros((grid_height, grid_width))
# 假设 V 是包含 (row, col): value 的字典
for (r, c), value in V.items():
     if 0 <= r < grid_height and 0 <= c < grid_width: # Add boundary check
        value_grid[r, c] = value

plt.figure(figsize=(6, 6))
sns.heatmap(value_grid, annot=True, fmt=".2f", cmap="viridis", cbar=False)
plt.title("Value Function Heatmap (TD or MC)")
plt.show()

提交要求

  • 提交你的 Gridworld 环境代码（如果是自己实现的）或说明使用的来源。
  • 提交 TD(0) 和 MC 预测算法的实现代码。
  • 提交最终的价值函数可视化结果（热力图）。
  • 提交一份简短的对比分析报告，讨论收敛速度、最终结果和观察到的现象。

下周预告: 从预测到控制 - 学习如何找到最优策略。介绍第一个控制算法：同策略 TD 控制 - SARSA。