摘要：本讲深入探讨强化学习中的无模型学习方法。我们将系统讲解蒙特卡洛方法的两种变体（首次访问与每次访问）、时序差分学习的核心思想，以及SARSA和Q-Learning两种经典算法的原理与实现。通过完整的代码实战，你将学会在未知环境中从零开始学习最优策略，并掌握算法性能对比与超参数调优的方法。

---

环境声明

• Python版本：Python 3.10+
• 核心依赖：NumPy 1.24+, Matplotlib 3.7+, Gymnasium 0.29+
• 开发工具：PyCharm / VS Code / Jupyter Notebook
• 操作系统：Windows / macOS / Linux

pip install numpy matplotlib gymnasium

---

学习目标

完成本讲学习后，你将能够：

1. 理解蒙特卡洛方法的核心思想与两种变体的区别
2. 掌握时序差分学习的基本原理与优势
3. 深入理解SARSA与Q-Learning算法的异同
4. 能够独立实现MC、SARSA、Q-Learning三种算法
5. 学会进行算法性能对比与超参数调优
6. 理解n步TD与资格迹的基本概念

---

1. 无模型学习：在未知世界中探索

1.1 为什么需要无模型学习

在上一讲中，我们学习了马尔可夫决策过程（MDP）的形式化定义，并讨论了基于动态规划的求解方法。然而，动态规划方法有一个关键前提：必须知道环境的完整模型，即状态转移概率P(s’|s,a)和奖励函数R(s,a)。

在现实世界中，这个前提往往难以满足：

• 复杂系统：机器人控制、自动驾驶等系统的动力学方程过于复杂，难以精确建模
• 未知环境：游戏AI面对的新游戏、推荐系统面对的新用户群体
• 随机性：金融市场、用户行为等具有高度不确定性

**无模型学习（Model-Free Learning）**正是解决这类问题的利器。它不依赖环境的先验知识，而是通过与环境的直接交互来学习最优策略。

一句话总结：无模型学习就像一位探险家在未知的大陆上探索——没有地图，没有指南，只能通过亲身经历来绘制地图、积累经验。

1.2 无模型学习的分类

无模型学习方法主要分为两大类：

方法类别	代表算法	核心思想	适用场景
蒙特卡洛方法	MC Prediction, MC Control	基于完整回合的回报进行估计	回合制任务（如围棋、迷宫）
时序差分方法	TD(0), SARSA, Q-Learning	基于单步转移进行自举更新	连续任务或回合制任务

这两类方法各有优劣，我们将在后续章节详细探讨。

---

2. 蒙特卡洛方法：从经验中学习

2.1 蒙特卡洛方法的核心思想

蒙特卡洛（Monte Carlo, MC）方法是一类基于随机采样的统计方法。在强化学习中，MC方法的核心思想是：通过采样多条完整的回合（episode），用经验平均回报来估计价值函数。

具体来说，MC方法遵循以下流程：

1. 采样：让智能体按照某种策略与环境交互，生成完整的回合轨迹
2. 计算回报：对于每个访问过的状态（或状态-动作对），计算从该时刻开始的累积折扣回报
3. 更新估计：用回报的样本均值来更新价值函数的估计

关键特点：MC方法必须等待一个回合结束后才能进行更新，因为它需要知道完整的回报G_t。

2.2 首次访问与每次访问

在MC方法中，同一个状态可能在同一个回合中被多次访问。这就引出了两种变体：

首次访问MC（First-Visit MC）：只考虑每个回合中第一次访问某个状态的回报。

每次访问MC（Every-Visit MC）：考虑每个回合中所有访问某个状态的回报。

数学表达：

对于状态s，首次访问MC的价值估计为：

$$V(s)=\frac{1}{N(s)}\sum _{i=1}^{N(s)}{G}_i^{(first)}(s)$$

其中，$N(s)$是状态s被首次访问的回合数，$G_i^{(first)}(s)$是第i个回合中首次访问s后的回报。

每次访问MC的价值估计为：

$$V(s)=\frac{1}{M(s)}\sum _{j=1}^{M(s)}{G}_j(s)$$

其中，$M(s)$是状态s被访问的总次数（包括同一回合内的多次访问）。

两种方法的比较：

特性	首次访问MC	每次访问MC
收敛性	收敛到真实价值函数	收敛到真实价值函数（有偏但一致）
样本效率	每个回合只用一个样本	每个回合可用多个样本
实现复杂度	需要记录是否已访问	无需记录访问状态
方差	较高	略低

在大多数实际应用中，两种方法的性能差异不大，但首次访问MC的理论分析更为简洁。

2.3 增量式蒙特卡洛更新

直接存储所有回报再取平均的方式内存开销较大。我们可以使用增量式更新：

$$V(S_t)\leftarrow V(S_t)+\alpha [G_t-V(S_t)]$$

其中，$\alpha$是学习率（或步长）。当$\alpha =\frac{1}{N(S_t)}$时，这等价于样本平均。

使用固定学习率的好处是可以跟踪非平稳环境（环境特性随时间变化），但会引入估计偏差。

2.4 蒙特卡洛控制：策略迭代

MC方法不仅可以用于策略评估（预测问题），还可以用于策略优化（控制问题）。

MC控制的基本框架（广义策略迭代）：

1. 策略评估：使用当前策略采样多个回合，估计动作价值函数Q(s,a)
2. 策略改进：基于Q函数进行贪婪更新，得到新的策略

探索问题：如果总是执行贪婪动作，某些状态-动作对可能永远不会被访问，导致估计不准确。因此需要引入探索机制。

epsilon-贪婪策略：

$$\pi (a|s)=\{\begin{array}{ll}1-ϵ+\frac{ϵ}{|A(s)|}& \text{if }a=\arg {\max }_{a}Q(s,a)\\ \frac{ϵ}{|A(s)|}& \text{otherwise}\end{array}$$

其中，$ϵ$是探索概率。当$ϵ$逐渐衰减到0时，策略收敛到最优策略。

---

3. 时序差分学习：自举的力量

3.1 TD方法的核心思想

时序差分（Temporal Difference, TD）学习是强化学习中最核心的思想之一。它结合了蒙特卡洛方法和动态规划的优点：

• 像MC一样：直接从与环境的交互中学习，无需环境模型
• 像DP一样：利用自举（bootstrapping）进行更新，无需等待回合结束

TD(0)更新公式：

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

其中，$R_{t+1}+\gamma V(S_{t+1})$称为TD目标，${\delta }_t=R_{t+1}+\gamma V(S_{t+1})-V(S_t)$称为TD误差。

直观理解：TD方法用当前的估计来更新当前的估计。它认为"从下一个状态获得的价值"加上"立即奖励"就是对当前价值的更好估计。

3.2 TD与MC的比较

特性	蒙特卡洛	时序差分TD(0)
更新时机	回合结束后	每步之后
自举	否	是
偏差	无偏估计	有偏估计（因自举）
方差	高（回报累积多步随机性）	低（只考虑一步随机性）
适用性	仅回合制任务	回合制和连续任务
收敛速度	较慢	通常较快

TD的优势：

1. 在线学习：无需等待回合结束，可以实时更新
2. 低方差：由于只考虑一步转移，方差比MC小得多
3. 连续任务：可以应用于没有终止状态的连续任务

TD的劣势：

1. 有偏估计：由于使用了自举，估计是有偏的（尤其在早期）
2. 初始值敏感：初始价值估计会影响学习过程

3.3 SARSA算法：同策略TD控制

SARSA是一种同策略（on-policy）TD控制算法。"同策略"意味着用于生成数据的策略与正在学习的策略相同。

SARSA名称来源：更新公式使用了状态-动作-奖励-状态-动作五元组 $(S_t,A_t,R_{t+1},S_{t+1},A_{t+1})$。

SARSA更新公式：

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma Q(S_{t+1},A_{t+1})-Q(S_t,A_t)]$$

SARSA算法流程：

1. 初始化Q表（如全零或随机值）
2. 对于每个回合：
   • 初始化状态S
   • 使用当前策略（如epsilon-贪婪）选择动作A
   • 对于回合的每一步：
     • 执行动作A，观察奖励R和新状态S’
     • 使用当前策略选择新动作A’
     • 更新Q(S, A)
     • S = S’, A = A’
     • 如果S是终止状态，结束回合

SARSA的特点：

• 学习的是实际执行策略的价值
• 对探索比较保守（因为学习的是包含探索的策略）
• 收敛到的是epsilon-贪婪策略下的最优Q函数

3.4 Q-Learning算法：异策略TD控制

Q-Learning是强化学习领域最具影响力的算法之一，由Watkins在1989年提出。它是一种异策略（off-policy）算法。

异策略 vs 同策略：

• 同策略：学习的是正在执行的策略
• 异策略：学习的是另一个策略（通常是贪婪策略），而执行的是探索性策略

Q-Learning更新公式：

$$Q(S_t,A_t)\leftarrow Q(S_t,A_t)+\alpha [R_{t+1}+\gamma \underset{a}{\max }Q(S_{t+1},a)-Q(S_t,A_t)]$$

与SARSA的关键区别：Q-Learning使用max操作来选择下一个状态的最优动作，而不是实际执行的下一个动作。

Q-Learning算法流程：

1. 初始化Q表
2. 对于每个回合：
   • 初始化状态S
   • 对于回合的每一步：
     • 使用epsilon-贪婪策略选择动作A
     • 执行动作A，观察奖励R和新状态S’
     • 更新Q(S, A)使用max操作
     • S = S’
     • 如果S是终止状态，结束回合

Q-Learning的优势：

• 直接学习最优策略的价值
• 对探索更加激进（因为学习的是最优动作价值，不管实际执行什么）
• 理论上可以收敛到最优Q函数

3.5 SARSA与Q-Learning的对比

特性	SARSA	Q-Learning
策略类型	同策略	异策略
学习目标	实际执行策略的价值	最优策略的价值
更新方式	使用实际执行的下一个动作	使用最大Q值的动作
探索性	较保守	较激进
风险	较低（避免危险动作）	较高（可能尝试危险动作）
收敛目标	epsilon-贪婪最优	贪婪最优

选择建议：

• 如果环境安全，探索成本低，选择Q-Learning
• 如果环境有风险，需要避免危险动作，选择SARSA

---

4. n步TD与资格迹

4.1 n步TD：MC与TD的折中

MC方法使用完整回合的回报，方差大但无偏；TD(0)只使用一步，方差小但有偏。n步TD是两者的折中。

n步回报定义：

$$G_{t:t+n}=R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^{n-1}{R}_{t+n}+{\gamma }^{n}V(S_{t+n})$$

n步TD更新：

$$V(S_t)\leftarrow V(S_t)+\alpha [G_{t:t+n}-V(S_t)]$$

特殊情况：

• 当n=1时，退化为TD(0)
• 当n趋向无穷大（或回合结束）时，退化为MC

n步SARSA：类似地，可以定义n步SARSA用于控制问题。

4.2 资格迹：高效的多步学习

n步TD的一个问题是计算开销大，需要存储n步的转移。资格迹（Eligibility Traces）提供了一种高效的实现方式。

核心思想：为每个状态（或状态-动作对）维护一个"资格"值，表示该状态对当前TD误差的贡献程度。

TD(lambda)算法：

1. 初始化资格迹E(s)=0
2. 对于每个回合的每一步：
   • 计算TD误差：$\delta =R+\gamma V(S^{\prime })-V(S)$
   • 更新资格迹：$E(S)=E(S)+1$（累积迹）或$E(S)=1$（替代迹）
   • 对所有状态s：$V(s)=V(s)+\alpha \delta E(s)$
   • 衰减资格迹：$E(s)=\gamma \lambda E(s)$

其中，$\lambda \in [0,1]$是迹衰减参数。当$\lambda =0$时，退化为TD(0)；当$\lambda =1$时，近似MC方法。

资格迹的优势：

• 只需单步计算，但等效于多步更新
• 可以在线更新，无需等待多步
• 对近期访问的状态给予更高的更新权重

---

5. 算法实现

5.1 环境设置：悬崖行走

我们将使用Gymnasium中的"CliffWalking-v0"环境来测试三种算法。这是一个经典的网格世界问题：

• 4x12的网格
• 智能体从起点(3,0)出发，目标是(3,11)
• 底部一行是悬崖，掉下去奖励-100，回到起点
• 每步奖励-1
• 动作：上、下、左、右

import numpy as np
import matplotlib.pyplot as plt
from collections import defaultdict
import gymnasium as gym
from typing import Dict, Tuple, List, Callable

# 设置随机种子以保证可复现
np.random.seed(42)

# 创建环境
env = gym.make('CliffWalking-v0')
print(f"状态空间大小: {env.observation_space.n}")
print(f"动作空间大小: {env.action_space.n}")

5.2 蒙特卡洛控制实现

class MonteCarloAgent:
    """蒙特卡洛控制智能体（使用epsilon-贪婪策略）"""
    
    def __init__(self, n_states: int, n_actions: int, 
                 epsilon: float = 0.1, gamma: float = 1.0):
        self.n_states = n_states
        self.n_actions = n_actions
        self.epsilon = epsilon
        self.gamma = gamma
        
        # 初始化Q表
        self.Q = np.zeros((n_states, n_actions))
        
        # 用于存储每个状态-动作对的访问次数
        self.visit_count = defaultdict(int)
        
    def get_action(self, state: int, training: bool = True) -> int:
        """epsilon-贪婪策略选择动作"""
        if training and np.random.random() < self.epsilon:
            return np.random.randint(self.n_actions)
        else:
            # 贪婪选择
            return np.argmax(self.Q[state])
    
    def update(self, episode: List[Tuple[int, int, float]]):
        """
        使用一个回合的经验更新Q值
        episode: [(state, action, reward), ...]
        """
        G = 0
        visited = set()
        
        # 从后向前遍历，计算回报
        for t in range(len(episode) - 1, -1, -1):
            state, action, reward = episode[t]
            G = self.gamma * G + reward
            
            # 首次访问MC
            if (state, action) not in visited:
                visited.add((state, action))
                
                # 增量式更新
                self.visit_count[(state, action)] += 1
                alpha = 1.0 / self.visit_count[(state, action)]
                self.Q[state, action] += alpha * (G - self.Q[state, action])


def train_mc(env, n_episodes: int = 500, epsilon: float = 0.1, 
             gamma: float = 1.0) -> Tuple[MonteCarloAgent, List[float]]:
    """训练蒙特卡洛智能体"""
    agent = MonteCarloAgent(
        env.observation_space.n,
        env.action_space.n,
        epsilon=epsilon,
        gamma=gamma
    )
    
    rewards_history = []
    
    for episode in range(n_episodes):
        state, _ = env.reset(seed=episode)
        episode_data = []
        total_reward = 0
        done = False
        
        # 生成一个回合
        while not done:
            action = agent.get_action(state, training=True)
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated
            
            episode_data.append((state, action, reward))
            total_reward += reward
            state = next_state
        
        # 更新Q值
        agent.update(episode_data)
        rewards_history.append(total_reward)
    
    return agent, rewards_history

5.3 SARSA算法实现

class SARSAAgent:
    """SARSA智能体（同策略TD控制）"""
    
    def __init__(self, n_states: int, n_actions: int,
                 alpha: float = 0.1, epsilon: float = 0.1, 
                 gamma: float = 1.0):
        self.n_states = n_states
        self.n_actions = n_actions
        self.alpha = alpha
        self.epsilon = epsilon
        self.gamma = gamma
        
        # 初始化Q表
        self.Q = np.zeros((n_states, n_actions))
    
    def get_action(self, state: int, training: bool = True) -> int:
        """epsilon-贪婪策略选择动作"""
        if training and np.random.random() < self.epsilon:
            return np.random.randint(self.n_actions)
        else:
            return np.argmax(self.Q[state])
    
    def update(self, state: int, action: int, reward: float,
               next_state: int, next_action: int, done: bool):
        """SARSA更新"""
        if done:
            target = reward
        else:
            target = reward + self.gamma * self.Q[next_state, next_action]
        
        td_error = target - self.Q[state, action]
        self.Q[state, action] += self.alpha * td_error


def train_sarsa(env, n_episodes: int = 500, alpha: float = 0.1,
                epsilon: float = 0.1, gamma: float = 1.0) -> Tuple[SARSAAgent, List[float]]:
    """训练SARSA智能体"""
    agent = SARSAAgent(
        env.observation_space.n,
        env.action_space.n,
        alpha=alpha,
        epsilon=epsilon,
        gamma=gamma
    )
    
    rewards_history = []
    
    for episode in range(n_episodes):
        state, _ = env.reset(seed=episode)
        action = agent.get_action(state, training=True)
        total_reward = 0
        done = False
        
        while not done:
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated
            
            next_action = agent.get_action(next_state, training=True)
            agent.update(state, action, reward, next_state, next_action, done)
            
            total_reward += reward
            state = next_state
            action = next_action
        
        rewards_history.append(total_reward)
    
    return agent, rewards_history

5.4 Q-Learning算法实现

class QLearningAgent:
    """Q-Learning智能体（异策略TD控制）"""
    
    def __init__(self, n_states: int, n_actions: int,
                 alpha: float = 0.1, epsilon: float = 0.1,
                 gamma: float = 1.0):
        self.n_states = n_states
        self.n_actions = n_actions
        self.alpha = alpha
        self.epsilon = epsilon
        self.gamma = gamma
        
        # 初始化Q表
        self.Q = np.zeros((n_states, n_actions))
    
    def get_action(self, state: int, training: bool = True) -> int:
        """epsilon-贪婪策略选择动作"""
        if training and np.random.random() < self.epsilon:
            return np.random.randint(self.n_actions)
        else:
            return np.argmax(self.Q[state])
    
    def update(self, state: int, action: int, reward: float,
               next_state: int, done: bool):
        """Q-Learning更新（使用max操作）"""
        if done:
            target = reward
        else:
            target = reward + self.gamma * np.max(self.Q[next_state])
        
        td_error = target - self.Q[state, action]
        self.Q[state, action] += self.alpha * td_error


def train_qlearning(env, n_episodes: int = 500, alpha: float = 0.1,
                    epsilon: float = 0.1, gamma: float = 1.0) -> Tuple[QLearningAgent, List[float]]:
    """训练Q-Learning智能体"""
    agent = QLearningAgent(
        env.observation_space.n,
        env.action_space.n,
        alpha=alpha,
        epsilon=epsilon,
        gamma=gamma
    )
    
    rewards_history = []
    
    for episode in range(n_episodes):
        state, _ = env.reset(seed=episode)
        total_reward = 0
        done = False
        
        while not done:
            action = agent.get_action(state, training=True)
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated
            
            agent.update(state, action, reward, next_state, done)
            
            total_reward += reward
            state = next_state
        
        rewards_history.append(total_reward)
    
    return agent, rewards_history

5.5 性能对比与可视化

def moving_average(data: List[float], window: int = 100) -> np.ndarray:
    """计算移动平均"""
    return np.convolve(data, np.ones(window)/window, mode='valid')


def evaluate_policy(env, agent, n_episodes: int = 100) -> float:
    """评估策略（不使用探索）"""
    total_rewards = 0
    for episode in range(n_episodes):
        state, _ = env.reset(seed=episode + 10000)
        done = False
        
        while not done:
            action = agent.get_action(state, training=False)
            state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated
            total_rewards += reward
    
    return total_rewards / n_episodes


def plot_learning_curves(results: Dict[str, List[float]], window: int = 100):
    """绘制学习曲线对比"""
    plt.figure(figsize=(12, 5))
    
    # 原始奖励
    plt.subplot(1, 2, 1)
    for name, rewards in results.items():
        plt.plot(rewards, alpha=0.3, label=f'{name} (raw)')
        if len(rewards) >= window:
            smoothed = moving_average(rewards, window)
            plt.plot(range(window-1, len(rewards)), smoothed, 
                    linewidth=2, label=f'{name} (smoothed)')
    
    plt.xlabel('Episode')
    plt.ylabel('Total Reward')
    plt.title('Learning Curves Comparison')
    plt.legend()
    plt.grid(True, alpha=0.3)
    
    # 移动平均对比
    plt.subplot(1, 2, 2)
    for name, rewards in results.items():
        if len(rewards) >= window:
            smoothed = moving_average(rewards, window)
            plt.plot(range(window-1, len(rewards)), smoothed, 
                    linewidth=2, label=name)
    
    plt.xlabel('Episode')
    plt.ylabel('Average Reward')
    plt.title(f'Moving Average (window={window})')
    plt.legend()
    plt.grid(True, alpha=0.3)
    
    plt.tight_layout()
    plt.savefig('learning_curves_comparison.png', dpi=150, bbox_inches='tight')
    plt.show()


def visualize_policy(env, agent, title: str):
    """可视化学习到的策略"""
    #  CliffWalking是4x12的网格
    grid_height = 4
    grid_width = 12
    
    policy = np.zeros((grid_height, grid_width), dtype=int)
    
    for state in range(env.observation_space.n):
        row = state // grid_width
        col = state % grid_width
        action = agent.get_action(state, training=False)
        policy[row, col] = action
    
    # 动作映射: 0=上, 1=右, 2=下, 3=左
    action_arrows = {0: '↑', 1: '→', 2: '↓', 3: '←'}
    
    fig, ax = plt.subplots(figsize=(12, 4))
    
    for row in range(grid_height):
        for col in range(grid_width):
            action = policy[row, col]
            ax.text(col, grid_height - 1 - row, action_arrows[action],
                   ha='center', va='center', fontsize=16)
    
    ax.set_xlim(-0.5, grid_width - 0.5)
    ax.set_ylim(-0.5, grid_height - 0.5)
    ax.set_xticks(range(grid_width))
    ax.set_yticks(range(grid_height))
    ax.set_yticklabels(range(grid_height - 1, -1, -1))
    ax.grid(True, alpha=0.3)
    ax.set_title(title)
    
    plt.savefig(f'{title.replace(" ", "_")}.png', dpi=150, bbox_inches='tight')
    plt.show()


# 主实验代码
if __name__ == "__main__":
    # 训练参数
    N_EPISODES = 500
    ALPHA = 0.1
    EPSILON = 0.1
    GAMMA = 1.0
    
    print("开始训练蒙特卡洛智能体...")
    mc_agent, mc_rewards = train_mc(env, N_EPISODES, EPSILON, GAMMA)
    
    print("开始训练SARSA智能体...")
    sarsa_agent, sarsa_rewards = train_sarsa(env, N_EPISODES, ALPHA, EPSILON, GAMMA)
    
    print("开始训练Q-Learning智能体...")
    ql_agent, ql_rewards = train_qlearning(env, N_EPISODES, ALPHA, EPSILON, GAMMA)
    
    # 绘制学习曲线
    results = {
        'Monte Carlo': mc_rewards,
        'SARSA': sarsa_rewards,
        'Q-Learning': ql_rewards
    }
    plot_learning_curves(results)
    
    # 评估最终策略
    print("\n最终策略评估（100回合平均奖励）：")
    print(f"Monte Carlo: {evaluate_policy(env, mc_agent):.2f}")
    print(f"SARSA: {evaluate_policy(env, sarsa_agent):.2f}")
    print(f"Q-Learning: {evaluate_policy(env, ql_agent):.2f}")
    
    # 可视化策略
    visualize_policy(env, mc_agent, "Monte Carlo Policy")
    visualize_policy(env, sarsa_agent, "SARSA Policy")
    visualize_policy(env, ql_agent, "Q-Learning Policy")

---

6. 超参数影响分析

6.1 学习率alpha的影响

学习率alpha控制每次更新的步长。在TD方法中，alpha的选择对性能有显著影响：

def analyze_alpha_impact(env, n_episodes=500, alphas=[0.01, 0.05, 0.1, 0.3, 0.5]):
    """分析学习率对Q-Learning的影响"""
    plt.figure(figsize=(12, 5))
    
    for alpha in alphas:
        agent, rewards = train_qlearning(env, n_episodes, alpha=alpha)
        smoothed = moving_average(rewards, window=50)
        plt.plot(range(49, len(rewards)), smoothed, 
                linewidth=2, label=f'alpha={alpha}')
    
    plt.xlabel('Episode')
    plt.ylabel('Average Reward')
    plt.title('Impact of Learning Rate (alpha) on Q-Learning')
    plt.legend()
    plt.grid(True, alpha=0.3)
    plt.savefig('alpha_impact.png', dpi=150, bbox_inches='tight')
    plt.show()


analyze_alpha_impact(env)

分析结论：

• alpha过小（如0.01）：学习速度慢，收敛慢
• alpha适中（如0.1）：平衡了学习速度和稳定性
• alpha过大（如0.5）：震荡剧烈，可能无法收敛

6.2 探索率epsilon的影响

epsilon控制探索与利用的权衡：

def analyze_epsilon_impact(env, n_episodes=500, epsilons=[0.01, 0.1, 0.3, 0.5]):
    """分析探索率对SARSA的影响"""
    plt.figure(figsize=(12, 5))
    
    for epsilon in epsilons:
        agent, rewards = train_sarsa(env, n_episodes, epsilon=epsilon)
        smoothed = moving_average(rewards, window=50)
        plt.plot(range(49, len(rewards)), smoothed,
                linewidth=2, label=f'epsilon={epsilon}')
    
    plt.xlabel('Episode')
    plt.ylabel('Average Reward')
    plt.title('Impact of Exploration Rate (epsilon) on SARSA')
    plt.legend()
    plt.grid(True, alpha=0.3)
    plt.savefig('epsilon_impact.png', dpi=150, bbox_inches='tight')
    plt.show()


analyze_epsilon_impact(env)

分析结论：

• epsilon过小（如0.01）：探索不足，容易陷入局部最优
• epsilon适中（如0.1）：平衡探索与利用
• epsilon过大（如0.5）：过度探索，学习到的策略不是最优

6.3 epsilon衰减策略

固定epsilon的问题在于：早期需要更多探索，后期需要更多利用。可以使用衰减策略：

class DecayEpsilonAgent(QLearningAgent):
    """带epsilon衰减的Q-Learning智能体"""
    
    def __init__(self, n_states, n_actions, alpha=0.1, 
                 epsilon_start=1.0, epsilon_end=0.01, 
                 epsilon_decay=0.995, gamma=1.0):
        super().__init__(n_states, n_actions, alpha, epsilon_start, gamma)
        self.epsilon_start = epsilon_start
        self.epsilon_end = epsilon_end
        self.epsilon_decay = epsilon_decay
        self.episode_count = 0
    
    def get_action(self, state, training=True):
        if training:
            self.epsilon = max(self.epsilon_end, 
                              self.epsilon_start * (self.epsilon_decay ** self.episode_count))
        return super().get_action(state, training)
    
    def end_episode(self):
        self.episode_count += 1


def compare_epsilon_strategies(env, n_episodes=500):
    """对比固定epsilon与衰减epsilon"""
    # 固定epsilon
    fixed_agent, fixed_rewards = train_qlearning(env, n_episodes, epsilon=0.1)
    
    # 衰减epsilon
    decay_agent = DecayEpsilonAgent(
        env.observation_space.n,
        env.action_space.n,
        epsilon_start=1.0,
        epsilon_end=0.01,
        epsilon_decay=0.99
    )
    decay_rewards = []
    
    for episode in range(n_episodes):
        state, _ = env.reset(seed=episode)
        total_reward = 0
        done = False
        
        while not done:
            action = decay_agent.get_action(state, training=True)
            next_state, reward, terminated, truncated, _ = env.step(action)
            done = terminated or truncated
            decay_agent.update(state, action, reward, next_state, done)
            total_reward += reward
            state = next_state
        
        decay_agent.end_episode()
        decay_rewards.append(total_reward)
    
    # 绘制对比
    plt.figure(figsize=(10, 5))
    plt.plot(moving_average(fixed_rewards, 50), label='Fixed epsilon=0.1')
    plt.plot(moving_average(decay_rewards, 50), label='Decaying epsilon')
    plt.xlabel('Episode')
    plt.ylabel('Average Reward')
    plt.title('Fixed vs Decaying Epsilon Strategy')
    plt.legend()
    plt.grid(True, alpha=0.3)
    plt.savefig('epsilon_decay_comparison.png', dpi=150, bbox_inches='tight')
    plt.show()


compare_epsilon_strategies(env)

---

7. 避坑小贴士

在学习和实现无模型强化学习算法时，以下是新手容易犯的错误及解决方案：

7.1 Q表初始化问题

常见错误：将Q表初始化为全零，导致在epsilon-贪婪策略下，多个动作具有相同的Q值，选择动作时总是选择索引最小的动作。

解决方案：

• 使用小的随机值初始化Q表
• 或者使用乐观初始化（初始化为较大值），鼓励早期探索

# 乐观初始化示例
self.Q = np.ones((n_states, n_actions)) * 10.0

7.2 学习率设置不当

常见错误：学习率过大导致震荡，过小导致收敛极慢。

解决方案：

• 从0.1开始尝试
• 使用自适应学习率（如Adam优化器，但在简单Q学习中较少使用）
• 随着训练进行逐渐降低学习率

7.3 折扣因子gamma的误解

常见错误：在回合制任务中设置gamma=1，导致回报无界；或在需要长期规划的任务中设置gamma过小。

解决方案：

• 对于有限回合任务，gamma=1通常可行
• 对于无限回合或长期任务，gamma=0.9或0.99更合适
• 注意gamma接近1时，回报的方差会增大

7.4 探索与利用的失衡

常见错误：epsilon设置过大或过小，或者一直使用固定epsilon。

解决方案：

• 使用epsilon衰减策略
• 考虑使用更高级的策略如Softmax或UCB
• 监控训练过程中的探索率，确保有足够的探索

7.5 状态表示问题

常见错误：在部分可观测环境中假设完全可观测，导致状态表示不完整。

解决方案：

• 确认环境是否满足马尔可夫性质
• 对于部分可观测环境，考虑使用RNN或历史状态堆叠
• 使用函数逼近（如神经网络）处理连续或高维状态空间

---

8. 延伸阅读与总结

8.1 本讲要点总结

1. 蒙特卡洛方法：基于完整回合的回报进行估计，无偏但方差大，仅适用于回合制任务。

2. 时序差分学习：结合自举思想，可以在线学习，方差小但有偏。

3. SARSA：同策略TD控制，学习实际执行策略的价值，较为保守。

4. Q-Learning：异策略TD控制，学习最优策略的价值，较为激进。

5. n步TD与资格迹：在MC和TD(0)之间进行权衡，提供了更灵活的更新方式。

8.2 理论深入：收敛性与致命三元组

8.2.1 Q-Learning收敛性定理

定理（Watkins & Dayan, 1992）：在满足以下条件时，Q-Learning以概率1收敛到最优Q函数Q*：

条件1：充分探索
每个状态-动作对(s,a)被无限次访问：
∑t=1∞1{St=s,At=a}=∞,∀s,a\sum_{t=1}^{\infty} \mathbf{1}\{S_t=s, A_t=a\} = \infty, \quad \forall s,at=1∑∞​1{St​=s,At​=a}=∞,∀s,a

条件2：学习率条件
学习率${\alpha }_t(s,a)$满足：
$$\sum _{t=1}^{\infty }{\alpha }_t(s,a)=\infty ,\sum _{t=1}^{\infty }{\alpha }_t^2(s,a)<\infty$$

常用的学习率调度：

• 样本平均：${\alpha }_t(s,a)=\frac{1}{N_t(s,a)}$（满足条件）
• 固定学习率：${\alpha }_t(s,a)=\alpha$（不满足，但实践中常用）
• 多项式衰减：${\alpha }_t(s,a)=\frac{1}{t^{\beta }}$，$\beta \in (0.5,1]$（满足条件）

条件3：有界奖励
$$|R(s,a,s^{\prime })|\le R_{max}<\infty$$

证明思路：

1. 将Q-Learning视为随机逼近算法
2. 证明更新算子是压缩映射
3. 应用随机逼近收敛定理

8.2.2 SARSA收敛性

定理：在相同条件下，SARSA收敛到epsilon-贪婪策略下的最优Q函数。

注意：SARSA收敛的不是全局最优Q*，而是当前探索策略下的最优Q值。这就是为什么SARSA比Q-Learning更保守。

8.2.3 致命三元组（Deadly Triad）

定义：当以下三个条件同时满足时，强化学习算法可能发散：

1. 函数逼近（Function Approximation）：使用神经网络等参数化函数代替Q表
2. 自举（Bootstrapping）：使用当前估计更新当前估计（如TD方法）
3. 异策略学习（Off-policy Learning）：学习的目标策略与执行的行为策略不同

为什么危险？

考虑线性函数逼近下的Q-Learning：

• Q(s,a) ≈ w^T φ(s,a)，其中φ(s,a)是特征向量
• 更新规则：w ← w + α[r + γ max_a’ w^T φ(s’,a’) - w^T φ(s,a)] φ(s,a)

发散示例（Tsitsiklis & Van Roy, 1997）：

即使在一个简单的MDP中，使用线性函数逼近的TD(0)也可能发散。这是因为：

• 自举引入了循环依赖
• 函数逼近引入了近似误差
• 异策略学习改变了数据分布

解决方案：

方法	解决思路	代表算法
梯度TD	使用真实的梯度下降	GTD, GTD2, TDC
经验回放	打破数据相关性	DQN（配合目标网络）
信任区域	限制策略更新幅度	TRPO, PPO
两时间尺度	分离价值函数和策略的更新速度	Actor-Critic

DQN为什么能工作？

DQN通过以下技术缓解了致命三元组：

1. 经验回放：存储和随机采样经验，打破时间相关性
2. 目标网络：使用独立的目标网络计算TD目标，减少自举的不稳定性
3. 大批量训练：使用大批量样本平均掉噪声

但这些只是缓解，并不能完全解决问题。在某些任务上，DQN仍然可能发散。

8.3 延伸阅读

经典论文：

1. Watkins, C. J. C. H. (1989). Learning from Delayed Rewards. PhD Thesis. (Q-Learning原始论文)

2. Watkins, C. J. C. H., & Dayan, P. (1992). Q-learning. Machine Learning, 8(3-4), 279-292. (收敛性证明)

3. Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning. (TD学习奠基论文)

4. Tsitsiklis, J. N., & Van Roy, B. (1997). An analysis of temporal-difference learning with function approximation. IEEE Transactions on Automatic Control. (致命三元组)

5. Rummery, G. A., & Niranjan, M. (1994). On-line Q-learning using connectionist systems. (SARSA相关)

推荐书籍：

• 《Reinforcement Learning: An Introduction》（Sutton & Barto）第5-7章, 第11章
• 《Algorithms for Reinforcement Learning》（Szepesvari）
• 《Neuro-Dynamic Programming》（Bertsekas & Tsitsiklis）

进阶主题：

• 函数逼近（Function Approximation）：使用神经网络代替Q表
• 策略梯度方法（Policy Gradient）：直接优化策略
• Actor-Critic方法：结合价值函数和策略梯度
• 梯度TD方法：GTD, GTD2, TDC

8.3 下一讲预告

第4讲将深入探讨深度Q网络（DQN），我们将学习如何将神经网络与Q-Learning结合，处理高维状态空间（如Atari游戏图像），并介绍经验回放、目标网络等关键技术。

---

如果你觉得本讲内容对你有帮助，欢迎点赞、收藏、评论交流。你的支持是我持续创作的动力！