蒙特卡洛方法 (Monte Carlo Methods)

1. 为什么要引入蒙特卡洛？

在讲 MDP 和贝尔曼方程时，我们假设智能体知道 $P$ (转移概率) 和 $R$ (奖励函数)。

• Model-Based (有模型)：就像拿着地图走迷宫，我们可以直接用数学公式（动态规划 DP）算出最优解。

但在现实中，智能体通常没有地图 (Model-Free)。

• 我们不知道做这个动作会有多大概率摔倒 ($P$ 未知)。
• 我们不知道这一步到底给多少分，除非真的去做了 ($R$ 未知)。

核心观点：
当期望值 (Expectation) 无法直接计算时（因为不知概率分布），我们可以利用 大数定律 (Law of Large Numbers)，通过大量采样 (Sampling) 的平均值来近似期望值。

这就是蒙特卡洛方法的本质。

---

2. 数学原理：从期望到平均

回忆价值函数的定义，它是一个期望：
$$v_{\pi }(s)=\mathbb{E}[G_t|S_t=s]$$

在没有模型的情况下，我们无法计算这个 $\mathbb{E}$。于是我们采用 MC 策略评估：

1. 让智能体从状态 $s$ 出发，按照策略 $\pi$ 玩游戏。
2. 一直玩到游戏结束（Terminal State），记录下一条完整的轨迹 (Trajectory)。
3. 计算这条轨迹的实际回报 $G$。
4. 重复玩 $N$ 次，得到 $G_1,G_2,\dots ,G_N$。
5. 计算平均值：
   $$v_{\pi }(s)\approx \frac{1}{N}\sum _{i=1}^N{G}_i$$

当 $N\to \infty$ 时，平均值收敛于真实价值。

---

3. 核心算法：增量式更新 (Incremental Update)

在写代码时，我们不需要把几百万次 $G$ 都存下来最后求平均，而是用增量公式（这也就是 Q-learning 更新公式的前身）：

$$V(s)\leftarrow V(s)+\alpha [\underset{\text{真实回报}}{\underbrace{G}}-\underset{\text{旧估计}}{\underbrace{V(s)}}]$$

• $G$ (Target)：这是一整局游戏玩完后的实际总分。
• $V(s)$：现在的估计值。
• $G-V(s)$：Error (误差)。

注意与 Q-learning (TD) 的区别：

• MC 必须等一整局结束，算出 $G$，才能更新 $V(s)$。
• TD 只需要走一步，用 $R+\gamma V(s^{\prime })$ 估算 $G$，就能更新。

---

4. MC 的关键特性 (重点)

A. 必须有终点 (Episodic Tasks)

蒙特卡洛方法要求任务必须是分段的 (Episodic)，必须能停下来结算。如果是一个无限运行的任务（比如服务器持续散热），MC 没法用，因为 $G$ 算不出来（无穷加和）。

B. 探索性开始 (Exploring Starts)

如果策略是确定的（比如看到墙一定左转），那么很多状态可能永远访问不到。
为了估计所有状态的价值，MC 要求**“每一条路都有概率被走到”**。

• 工程做法：通常使用 $ϵ$-greedy 策略（有一点概率瞎走）来保证所有状态都被访问。

C. 高方差，无偏差 (High Variance, Zero Bias)

这是赵老师对比 MC 和 TD 时的经典考点：

1. 无偏差 (Unbiased)：

   • MC 的目标值 $G$ 是真实的采样回报。只要次数够多，它一定会收敛到真值。
   • 比喻：你为了算从北京到上海的平均耗时，真的跑了100次，取平均。这个数据是绝对准的。

2. 高方差 (High Variance)：

   • 因为 $G$ 是一条长长的轨迹上所有随机事件的累积 ($S_1,A_1,R_1,S_2,\dots ,S_T$)。任何一步的随机波动都会影响最终的 $G$。
   • 这导致训练时 Loss 曲线波动极大，收敛很慢。
   • 比喻：虽然你真的跑了，但某次堵车、某次下雨、某次爆胎，导致每次的时间差得特别多。

---

5. MC 与 TD 的对比 (一张表看懂)

这是强化学习面试和考试中出现频率最高的内容：

维度	蒙特卡洛 (MC)	时序差分 (TD / Q-Learning)
更新时机	回合结束才能更新 (Wait until end)	每走一步就能更新 (Step-by-step)
目标值 (Target)	$G_t$ (真实回报)	$R+\gamma V(s^{\prime })$ (估算值 / Bootstrapping)
适用范围	仅限有终点的任务	连续任务或有终点任务皆可
偏差 (Bias)	无偏差 (Unbiased)	有偏差 (Biased, 因为用了估计值 $V(s^{\prime })$)
方差 (Variance)	高 (High, 容易震荡)	低 (Low, 比较稳定)
对模型需求	Model-Free	Model-Free

---

6. 总结

在赵世钰老师的框架里，蒙特卡洛 (MC) 的地位如下：

1. 它是 Model-Free 的起源：证明了不需要 $P$ 和 $R$，光靠“玩游戏”就能算价值。
2. 它是 TD (Q-Learning) 的基础：TD 其实就是把 MC 中的真实回报 $G_t$，换成了“走一步看一步”的估计值 $R+\gamma V(s^{\prime })$。

一句话概括 MC：
“不管过程多复杂，我就看结果。玩一局算一局，用平均分代表价值。”

Q-learning

1. 核心思想：从数学到直观

直观理解：
“通过不断的试错（Trial and Error），建立一张记录了在任何情况下‘怎么做最好’的备忘录（Q-Table）。”

赵老师的数学视角：
Q-Learning 的本质是在不知道环境模型（即不知道转移概率 $P$ 和奖励函数 $R$）的情况下，利用蒙特卡洛采样（Sample）来求解贝尔曼最优方程 (Bellman Optimality Equation)。
$$Q(s,a)=\mathbb{E}[R+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })]$$
因为我们算不出期望 $\mathbb{E}$（没模型），所以我们用**“采样值”来近似代替“期望值”，这就是随机逼近**的思想。

---

2. 核心机制：TD Learning (时序差分)

为什么叫 TD？

• Temporal (时序)：我们利用 $t+1$ 时刻的估计值去更新 $t$ 时刻的估计值。
• Difference (差分)：即 TD Error，代表“现实”与“预期”的差距。

核心机制：Bootstrapping (自举)

赵老师强调，Bootstrapping 是指利用一个估计值来更新另一个估计值。

• 在 Q-Learning 中，我们用 $R+\gamma \max Q(s^{\prime },a^{\prime })$（这是对 $G_t$ 的估计）来更新 $Q(s,a)$。
• 这意味着我们不需要等到游戏结束（像 MC 方法那样），只要走一步就能更新，这极大提高了效率。

---

3. 核心公式与数学拆解

$$Q(s,a)\leftarrow \underset{\text{旧估计}}{\underbrace{Q(s,a)}}+\alpha \cdot \underset{\text{TD Error (误差)}}{\underbrace{[\underset{\text{TD Target (采样得到的现实)}}{\underbrace{R+\gamma \underset{a^{\prime }}{\max }Q(s^{\prime },a^{\prime })}}-\underset{\text{旧估计}}{\underbrace{Q(s,a)}}]}}$$

逐项拆解

1. $Q(s,a)$ (Current Estimate)：
   我们试图求解的未知变量。

2. $R+\gamma {\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$ (TD Target)：

   • 这是 Q-Learning 最关键的地方。
   • 注意：这里的 ${\max }_{a^{\prime }}$ 体现了 Q-Learning 是在直接估计最优策略的价值。不管你下一步实际怎么走（可能是随机乱走），我在更新时假设你下一步一定会选最好的那个动作。
   • 这就是为什么 Q-Learning 被称为 Off-policy (异策略) 算法：
     • Behavior Policy (行为策略)：你实际怎么走的？（用 $ϵ$-greedy，有随机性）。
     • Target Policy (目标策略)：你学习的是什么？（用 $\max$，也就是 Greedy 策略）。

3. $\alpha$ (Learning Rate)：

   • 数学上对应 Robbins-Monro 算法 中的步长。
   • 为了保证收敛，数学上要求 $\sum \alpha =\infty$ 且 $\sum {\alpha }^2<\infty$（即 $\alpha$ 要随时间慢慢减小到 0）。但在工程实践中，我们通常设为一个小的常数（如 0.1），以便应对非平稳环境。

4. TD Error (${\delta }_t$)：

   • ${\delta }_t=\text{Target}-\text{Current}$
   • 这是驱动更新的动力。当 Error 为 0 时，说明 $Q$ 值已经收敛到贝尔曼最优方程的解。

---

4. Q-Learning 核心逻辑：Off-Policy (异策略)

这是赵老师课程中非常强调的一个概念，必须单独列出。

• 问题：为什么我们可以在探索（乱走）的同时，还能学到最优策略（走直线）？
• 答案：
  • 我们在走路时，用的是 $ϵ$-greedy 策略（为了探索地图，防闭环）。
  • 我们在写书 (更新 Q 表) 时，用的是 $\max$ 算子（完全贪婪，假设下一刻也是最好的）。
  • 结论：Q-Learning 学到的价值函数 $Q(s,a)$ 是属于最优策略 ${\pi }^{\ast }$ 的，而不是属于当前那个乱走的策略的。这叫做 Off-policy。

---

5. 5x5 迷宫代码

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import time

# --- 1. 定义环境 (Environment) ---
class GridWorld:
    def __init__(self, size=5):
        self.size = size
        # 地图定义：0=空地, -1=陷阱, 1=终点
        self.map = np.zeros((size, size))
        self.start = (0, 0)
        self.goal = (4, 4)
        self.traps = [(2, 2), (1, 3)] # 设置两个陷阱
        
        # 标记地图
        for t in self.traps:
            self.map[t] = -1
        self.map[self.goal] = 1
        
    def reset(self):
        self.state = self.start
        return self.state
    
    def step(self, action):
        # 动作: 0=上, 1=下, 2=左, 3=右
        x, y = self.state
        if action == 0: x = max(0, x-1)
        elif action == 1: x = min(self.size-1, x+1)
        elif action == 2: y = max(0, y-1)
        elif action == 3: y = min(self.size-1, y+1)
        
        next_state = (x, y)
        self.state = next_state
        
        # 奖励机制
        if next_state == self.goal:
            return next_state, 100, True # 到达终点，奖励100，游戏结束
        elif next_state in self.traps:
            return next_state, -100, True # 掉进陷阱，扣100，游戏结束
        else:
            return next_state, -1, False # 普通一步，扣1分（为了督促它快走）

# --- 2. 定义智能体 (Agent) ---
class QLearningAgent:
    def __init__(self, state_size, action_size, learning_rate=0.1, gamma=0.9, epsilon=0.1):
        self.q_table = np.zeros((state_size, state_size, action_size)) # 5x5x4的表格
        self.lr = learning_rate
        self.gamma = gamma
        self.epsilon = epsilon
        self.actions = [0, 1, 2, 3] # 上下左右

    def choose_action(self, state):
        # Epsilon-Greedy 策略
        if np.random.uniform(0, 1) < self.epsilon:
            return np.random.choice(self.actions) # 探索：随机选
        else:
            x, y = state
            return np.argmax(self.q_table[x, y, :]) # 利用：选Q值最大的

    def learn(self, state, action, reward, next_state):
        x, y = state
        nx, ny = next_state
        
        # --- 核心公式 ---
        # 预测值 (Old Q)
        predict = self.q_table[x, y, action]
        # 目标值 (Target) = 奖励 + 折扣 * 下一步最大的Q
        target = reward + self.gamma * np.max(self.q_table[nx, ny, :])
        
        # 更新 Q 表
        self.q_table[x, y, action] += self.lr * (target - predict)

# --- 3. 主程序：训练与绘图 ---
env = GridWorld()
agent = QLearningAgent(state_size=5, action_size=4, epsilon=0.2)

episodes = 200 # 训练玩200局
rewards_history = []

print("开始训练...")
for episode in range(episodes):
    state = env.reset()
    total_reward = 0
    done = False
    
    while not done:
        action = agent.choose_action(state)
        next_state, reward, done = env.step(action)
        agent.learn(state, action, reward, next_state)
        state = next_state
        total_reward += reward
        
    rewards_history.append(total_reward)

print("训练结束！准备绘图...")

# --- 4. 可视化部分 ---
plt.figure(figsize=(15, 5))

# 图1：学习曲线
plt.subplot(1, 3, 1)
plt.plot(rewards_history)
plt.title('Reward per Episode')
plt.xlabel('Episode')
plt.ylabel('Total Reward')
plt.grid(True)

# 图2：最终 Q 值热力图 (每个格子的最大价值)
# 我们把每个格子在4个动作中最大的那个Q值取出来，画成热力图
q_max_map = np.max(agent.q_table, axis=2)
plt.subplot(1, 3, 2)
sns.heatmap(q_max_map, annot=True, fmt=".1f", cmap="YlGnBu")
plt.title('Max Q-Value Map (Heatmap)')
# 标注起点、终点、陷阱
plt.text(0.5, 0.5, 'Start', ha='center', va='center', color='red', fontweight='bold')
plt.text(4.5, 4.5, 'Goal', ha='center', va='center', color='red', fontweight='bold')
plt.text(2.5, 2.5, 'Trap', ha='center', va='center', color='black', fontweight='bold')
plt.text(3.5, 1.5, 'Trap', ha='center', va='center', color='black', fontweight='bold')

# 图3：最佳路径策略图
plt.subplot(1, 3, 3)
action_map = np.argmax(agent.q_table, axis=2)
arrow_map = {0: '↑', 1: '↓', 2: '←', 3: '→'}

# 创建一个空的网格图
plt.xlim(0, 5)
plt.ylim(5, 0) # 翻转Y轴让(0,0)在左上角
plt.grid(True)
plt.title('Best Policy (Arrows)')

for x in range(5):
    for y in range(5):
        # 如果是陷阱或终点，不画箭头
        if (x, y) == env.goal:
            plt.text(y+0.5, x+0.5, 'GOAL', ha='center', va='center', color='green', fontweight='bold')
            continue
        if (x, y) in env.traps:
            plt.text(y+0.5, x+0.5, 'X', ha='center', va='center', color='red', fontweight='bold')
            continue
            
        # 画出最佳动作的箭头
        best_action = action_map[x, y]
        plt.text(y+0.5, x+0.5, arrow_map[best_action], ha='center', va='center', fontsize=20)

plt.tight_layout()
plt.show()

---

6. 超参数调节 (结合收敛性分析)

1. $\alpha$ (Learning Rate)

• 数学含义：步长。
• 赵老师提示：
  • 如果 $\alpha$ 是常数（如 0.1），Q 值最终不会停在一个点，而是在真实值附近震荡。
  • 如果想让它完美收敛，$\alpha$ 需要随时间衰减（比如 $\alpha =1/t$），但在实际做迷宫这种简单问题时，常数 0.1 足够了。

2. $\gamma$ (Discount Factor)

• 数学含义：定义了问题的视界（Horizon）。
• 赵老师提示：
  • $\gamma$ 实际上改变了贝尔曼算子的压缩系数 (Contraction Factor)。
  • $\gamma$ 越小，算子压缩得越快，收敛速度越快，但目光越短浅。
  • $\gamma$ 接近 1，收敛变慢，但能考虑更长远的利益。

3. $ϵ$ (Exploration Rate)

• 数学含义：平衡 Exploration (探索) 与 Exploitation (利用)。
• 重要策略：Epsilon Decay (衰减)。
  • 开始时 $ϵ=1$：全盲探索，收集数据。
  • 结束时 $ϵ\approx 0$：基于收集到的数据，逐渐收敛到贪婪策略。
  • 如果不衰减，智能体永远无法稳定执行最优策略（总有几率乱走）。

---

7. 总结：Q-Learning 的三个标签

按照赵老师的分类体系，Q-Learning 是：

1. Model-Free (无模型)：不需要知道 $P$ 和 $R$，靠采样学习。
2. Value-Based (基于价值)：先学 Q 值，再根据 Q 值选动作（$\arg \max Q$）。
3. Off-Policy (异策略)：一边探索（行为策略是随机的），一边学习最优解（目标策略是贪婪的）。这是它最强大的地方。