表格型方法：Q-learning、Sarsa与蒙特卡洛¶

当环境模型未知时，我们不能用动态规划。本章介绍三种经典的无模型（Model-Free）表格型方法，它们都通过与环境直接交互来学习策略。

一、蒙特卡洛方法（Monte Carlo, MC）¶

1.1 基本思想¶

蒙特卡洛方法的核心很朴素：玩很多局游戏，记录实际拿到的回报，再取平均——平均回报就是价值的估计。

类比理解

你想知道某家餐厅好不好（即"状态价值"），最简单的方法就是去吃很多次，记录每次的体验打分，然后算平均分。吃的次数越多，平均分越接近真实水平。

蒙特卡洛方法要做的就是把策略迭代从model based修改为model free。 20260308123255 回到aciton value最原始的定义，然后用MC方法来求解。 20260308123205

1.2 算法流程¶

MC basic 算法 policy iteration的第一步是先通过贝尔曼方程来求解出state value，再通过state value 得到action value，而MC方法的第一步是直接通过数据得到action value。

20260308161141

MC exploring starts算法（exploring是指需要对每一个（s,a）都有探索，start是指从每个（s,a）开头找episode）一些前置概念：

每个都（s,a）从头来找episode是难以实现的，因此引出MC without exploring starts (MC ε-greedy)

MC ε-greedy

前置概念：
20260308194118

20260308194316 通过设定ε的大小，在利用性和探索性之间做平衡，当ε=1时，探索性很强，=0时，没有探索性。 20260308194533 MC Exploring starts用的是greedy的策略，而现在这个用的是ε-greedy策略，这样就可以避免每个（s,a）都要有一个从头开始的episode，只要episode length足够，可以包含所有的（s,a）。

效果对比： 20260308201356 优点是探索性，缺点是最优性， 20260308201557 ε开始可以设置大一点有探索性，但后面要逐渐减小到0，保证得到最优的策略。

循环 N 个回合（Episode）:
  1. 用当前策略 π 跑完整个回合，记录轨迹：
     S₀, A₀, R₁, S₁, A₁, R₂, ..., Sₜ
  2. 从后向前计算每个时间步的回报 Gₜ = Rₜ₊₁ + γGₜ₊₁
  3. 对每个访问过的 (s, a) 对：
     - 将 Gₜ 加入 (s, a) 的回报列表
     - Q(s, a) ← 该列表的平均值
  4. 根据 Q 值改进策略（如 ε-贪心）

1.3 高效方法¶

高效利用数据：采用first visit method

	首次访问 MC	每次访问 MC
统计方式	只在 $(s,a)$ 第一次出现时记录回报	每次出现都记录
偏差	无偏估计	有偏（但随样本增多趋于无偏）
常用程度	更常用	实践效果也不错

高效更新策略每得到一个episode直接就开始改进策略（思想类似于truncated policy iteration）

1.4 增量更新¶

20260308210715

20260308210821

为了避免存储所有回报，可以用增量平均：

\[ Q(s, a) \leftarrow Q(s, a) + \alpha \left[ G_t - Q(s, a) \right] \]

其中 $\alpha$ 是学习率。这个更新公式的含义是：将估计值向实际回报的方向微调一小步。

MC 的优缺点

优点：
- 不需要知道环境模型（转移概率） - 无偏估计，理论上保证收敛

缺点：
- ==必须等一个回合完全结束==才能更新（不适合很长或没有终止的任务） - 方差较大（一局里随机性很大）

补充：随机近似理论（stochastic apporoximation）¶

20260308214238

RM算法

20260308214358

20260308214648

20260308214941

RM算法需要满足的条件： 20260310095159 1/k就满足这样的条件，所以增量更新那里是对的，同时那里的αk可以取满足条件的值。

SGD（随机梯度下降）

SGD是特殊的RM算法，mean estimation是一个特殊的SGD问题。

20260310101805

20260310101829

20260310125024

20260310125957

20260310130626

20260310151107

二、时序差分学习（Temporal Difference, TD）¶

2.1 核心创新¶

蒙特卡洛需要等到回合结束才更新，TD 的突破在于：每走一步就立刻更新。

TD 的哲学是：不需要等到最终结果，用"当前估计"去修正"之前的估计"。

TD(0) 更新规则：

\[ V(S_t) \leftarrow V(S_t) + \alpha \left[ \underbrace{R_{t+1} + \gamma V(S_{t+1})}_{\text{TD 目标}} - V(S_t) \right] \]

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

TD算法只能用来求解state value，而不能直接求解action value。本质上是求解state value的贝尔曼方程。

20260318185441

20260318185532

20260318185603

20260318185705

MC vs TD 的直觉区别

假设你要估计"从家到公司需要多长时间"：

MC 方法：每天等你到达公司后，记录总耗时，然后更新平均值
TD 方法：你每经过一个路口，就根据"到这个路口花了多久"来立刻更新对剩余路程的估计

2.2 MC vs TD 对比¶

	蒙特卡洛（MC）	时序差分（TD）
更新时机	回合结束后	每一步
使用的目标	实际回报 $G_t$	TD 目标 $R_{t+1} + \gamma V(S_{t+1})$
偏差	无偏	有偏（因为用了估计值 $V(S_{t+1})$）
方差	高（受整个轨迹的随机性影响）	低（只看一步的随机性）
收敛速度	慢	快
是否需要回合结束	✅ 需要	❌ 不需要

三、Sarsa 算法¶

3.1 名字的由来¶

Sarsa 的名字来自于它更新 Q 值时用到的五个元素：

\[ (S_t, \; A_t, \; R_{t+1}, \; S_{t+1}, \; A_{t+1}) \]

3.2 更新规则¶

Sarsa可以直接用来估计action value，Sarsa的本质是求解action value的贝尔曼方程，更新规则如下：

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

注意：$A_{t+1}$ 是智能体实际采取的下一个动作（也按 $\epsilon$-贪心策略选择）。

20260318205829

20260318205945

3.3 算法流程¶

初始化 Q(s, a) 为任意值
循环每个回合:
  初始化状态 S
  用 ε-贪心从 Q 选择动作 A
  循环每一步（直到终止）:
    执行 A，观察 R, S'
    用 ε-贪心从 Q 选择动作 A'        ← 关键：此处选了 A'
    Q(S, A) ← Q(S, A) + α[R + γQ(S', A') - Q(S, A)]
    S ← S', A ← A'

20260318210621

20260318210739

20260318210759

3.4 Sarsa 是"在线策略"（On-Policy）¶

Sarsa 的特点是：行为策略和目标策略是同一个。它用 $\epsilon$-贪心去探索，更新时也使用的是 $\epsilon$-贪心实际选择的下一个动作 $A'$。

什么是 $\\epsilon$-贪心策略？

\[ A_t = \begin{cases} \arg\max_a Q(s, a) & \text{概率 } 1 - \epsilon \\\ \text{随机动作} & \text{概率 } \epsilon \end{cases} \]

以 $1-\epsilon$ 的概率选最优动作（利用），以 $\epsilon$ 的概率随机选（探索）。$\epsilon$ 通常从 1.0 逐渐衰减到 0.01。

四、Q-learning 算法 ⭐¶

4.1 更新规则¶

\[ Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \left[ R_{t+1} + \gamma \max_{a'} Q(S_{t+1}, a') - Q(S_t, A_t) \right] \]

20260319153700

20260319153759

与 Sarsa 的唯一区别：更新时使用的是 $\max_{a'} Q(S_{t+1}, a')$（下一状态的最优动作价值），而不是实际选择的 $Q(S_{t+1}, A_{t+1})$。

Q-learning直接用来估计最优action value。Q-learning的本质是求解action value的最优贝尔曼方程。

4.2 算法流程¶

初始化 Q(s, a) 为任意值
循环每个回合:
  初始化状态 S
  循环每一步（直到终止）:
    用 ε-贪心从 Q 选择动作 A
    执行 A，观察 R, S'
    Q(S, A) ← Q(S, A) + α[R + γ·max_a' Q(S', a') - Q(S, A)]  ← 用 max
    S ← S'

20260319160858

4.3 Q-learning 是"离线策略"（Off-Policy）¶

行为策略（Behavior Policy）：用 $\epsilon$-贪心来探索——实际在环境中做的事
目标策略（Target Policy）：用贪心策略（取 max）——想要学习的最优策略

这两个策略是不同的，所以 Q-learning 是 Off-Policy 的。

Off-Policy 的好处

可以从其他策略收集的经验中学习（如人类演示、随机策略的数据）
可以使用经验回放（这是 DQN 的核心技术之一）
更加灵活和高效

20260319154938

要彻底搞懂“同策略（On-Policy）”和“异策略（Off-Policy）”的区别，我们需要引入强化学习中非常重要的两个概念：“你真正在跑的策略”和“你脑子里正在学的策略”。

在强化学习的训练过程中，智能体其实同时涉及到两种策略： 1. 行为策略（Behavior Policy）：控制智能体在环境里怎么走、怎么选动作、怎么收集经验数据的策略。（为了多看看世界，这个策略通常带有随机性，比如 10% 的时间瞎走）。 2. 目标策略（Target Policy）：智能体在脑子里默默评估、更新，并期望最终学会的那个完美策略。（通常是我们想要的那个不带任何随机性、纯粹追求最高分的策略）。

On-Policy 和 Off-Policy 的根本区别，就在于这“两个策略”是不是同一个。

1. 同策略 (On-Policy)：知行合一¶

核心定义：行为策略和目标策略是同一个策略。 一句话理解：“我正在用什么方式走路，我就老老实实评估这种走路方式能得多少分。”

代表算法：SARSA
具体表现：在 SARSA 中，智能体用带有随机瞎走概率的 $\epsilon$-贪婪策略在迷宫里转悠（收集数据）。当它停下来更新大脑里的 Q 表时，它评估的也是这种“带有瞎走概率”的走法。
优缺点：
- 优点：比较安全、稳健。因为它知道自己偶尔会瞎走作死，所以它在评估一条路好不好时，会把“自己可能失足”的风险算进去，从而选择更远离危险的保守路线（比如远离悬崖）。
- 缺点：学到的最终策略不是绝对最优的，因为它把探索时的随机错误也学进去了。而且它不能利用过去的经验，一旦策略更新了一点点，之前收集的旧数据就作废了，必须重新自己去环境里跑新数据。

2. 异策略 (Off-Policy)：知行不一¶

核心定义：行为策略和目标策略是两个不同的策略。 一句话理解：“虽然我身体正在随便乱走，但我脑子里在偷偷学习一条最完美的路线。”

代表算法：Q-learning
具体表现：在 Q-learning 中，智能体依然用带有随机瞎走概率的 $\epsilon$-贪婪策略在迷宫里转悠（作为行为策略收集数据）。但是，当它停下来更新 Q 表时，它抛弃了刚才的实际决定，直接去寻找理论上最高分的动作（那个 max 操作，作为目标策略）。
优缺点：
- 优点：极其强大！它可以在自己胡乱探索、甚至“看着别人（比如人类专家）瞎玩”的数据中，提炼出一条绝对完美的通关路线。因为它把“收集数据”和“学习最优解”解耦了。这就意味着它可以无限次地反复利用很久以前收集的历史数据（这在深度强化学习中被称为经验回放 Experience Replay）。
- 缺点：比较激进。因为它脑子里的目标策略是完美的，它会天真地认为自己绝不犯错，从而经常贴着悬崖边走。此外，在结合深度神经网络时，Off-Policy 算法由于“左脚踩右脚”的严重自举现象，更容易出现训练不稳定的情况。

总结对比表¶

特性	On-Policy (同策略)	Off-Policy (异策略)
通俗理解	学的是“我现在正在走的这条路”	学的是“抛开我现在的走法，理论上最完美的路”
行为策略与目标策略	相同（都是 $\epsilon$-greedy）	不同（行为是 $\epsilon$-greedy，目标是纯贪婪 max）
代表算法	SARSA	Q-learning
是否能利用旧数据	不能（必须是当前策略现跑出来的新鲜数据）	能（可以学习很久以前的数据，甚至是别人的数据）
学习风格	保守、安全（怕自己随机失误掉下悬崖）	激进、贪婪（贴着悬崖走，认为自己绝不会失误）

这就是强化学习中最核心的分水岭之一。正因为 Off-Policy（如 Q-learning）拥有“可以从任何人的旧经验中学习最完美策略”的能力，它后来才能与神经网络结合，发展出能够看懂游戏画面并超越人类的 DQN 算法。

4.4 Sarsa vs Q-learning 对比¶

	Sarsa	Q-learning
类型	On-Policy	Off-Policy
更新目标	$R + \gamma Q(S', A')$	$R + \gamma \max_{a'} Q(S', a')$
$A'$ 来源	实际执行的下一步动作	取 $\max$ 的虚拟动作
风格	保守（会考虑探索中的"冒险"）	激进（总假设未来走最优）
悬崖行走问题	离悬崖远，更安全的路线	贴着悬崖走，理论最优但容易掉下去

悬崖行走的经典实验

在悬崖行走（Cliff Walking）环境中：

Q-learning 学到了理论最优路线（贴着悬崖走），但在探索阶段经常掉下悬崖，实际累积奖励波动大
Sarsa 学到了更保守的路线（远离悬崖），虽然路径稍长，但探索阶段更安全，实际表现更稳定

这体现了 On-Policy 和 Off-Policy 的本质区别。

五、Q-learning与Sarsa 实战对比分析¶

Q-learning 训练循环¶

for ep in range(episodes):
    state, _ = env.reset()
    done = False

    while not done:
        action = choose_action(state)                          # 选动作
        next_state, reward, terminated, truncated, _ = env.step(action)
        done = terminated or truncated

        # ★ 核心：用 next_state 的最大 Q 值更新
        best_next_action = np.argmax(Q[next_state, :])         # 找最优动作
        td_target = reward + gamma * Q[next_state, best_next_action] * (not done)
        Q[state, action] += alpha * (td_target - Q[state, action])

        state = next_state                                     # 只转移状态

SARSA 训练循环¶

for ep in range(episodes):
    state, _ = env.reset()
    action = choose_action(state)          # ★ 差异1: 循环前预选动作
    done = False

    while not done:
        next_state, reward, terminated, truncated, _ = env.step(action)
        done = terminated or truncated

        next_action = choose_action(next_state)  # ★ 差异2: 选出实际下一步动作
        # ★ 差异3: 用实际 next_action 的 Q 值更新（不是 max）
        td_target = reward + gamma * Q[next_state, next_action] * (not done)
        Q[state, action] += alpha * (td_target - Q[state, action])

        state = next_state
        action = next_action                     # ★ 差异4: 动作也跟着转移

4 个差异逐条解读¶

#	Q-learning	SARSA	为什么不同
1	循环内才选动作	循环前预选第一个动作	SARSA 需要知道"当前要执行的动作"才能进循环
2	用 `argmax` 找最优	用 `ε-greedy` 选实际动作	Q-learning 只关心理论最优；SARSA 关心实际会走哪步
3	`Q[s', best_action]`	`Q[s', next_action]`	唯一的公式差异：max vs 实际
4	只转移 `state`	同时转移 `state` 和 `action`	SARSA 中本轮的 `next_action` 就是下轮的 `action`

一个例子看懂区别¶

悬崖边状态（状态25，下方是悬崖37）：

... [25] 26 ...    ← 智能体在这
... [37] 38 ...    ← 悬崖！

智能体在状态25选了"→"到达状态26，现在要更新 Q[25, →]：

Q-learning:

td_target = -1 + 0.99 × max(Q[26])   # 假设下一步走最优（→），Q值=-5
         = -1 + 0.99 × (-5) = -5.95   # "下一步肯定不会掉悬崖"

SARSA（ε-greedy 恰好选到"↓"）:

td_target = -1 + 0.99 × Q[26, ↓]    # 实际下一步走↓（掉悬崖），Q值=-50
         = -1 + 0.99 × (-50) = -50.5  # "下一步可能掉悬崖，太危险了"

→ SARSA 的 Q[25, →] 会被大幅拉低，以后不愿走悬崖边。

超参数总结¶

超参数	典型值	作用
学习率 $\alpha$	0.1 ~ 0.5	新信息的权重，太大振荡，太小学太慢
折扣因子 $\gamma$	0.9 ~ 0.99	对未来奖励的重视程度
$\epsilon$ 初始值	1.0	初期多探索
$\epsilon$ 最小值	0.01	收敛后仍保持微小探索
$\epsilon$ 衰减率	0.995	每回合乘以衰减率
回合数	1000 ~ 10000	视环境复杂度而定

六、从表格到函数逼近¶

表格法的瓶颈

表格法要求显式存储每个 $(s, a)$ 对的 Q 值。当状态空间巨大（如游戏画面 $210 \times 160 \times 3$ 像素）或连续（如速度 $v \in \mathbb{R}$）时，Q 表格不可行。

解决方案：用神经网络来近似 Q 函数——这就是 DQN 的核心思想。

	表格法	函数逼近（DQN）
存储	$	\mathcal{S}
适用范围	小规模离散状态	大规模 / 连续状态
泛化能力	无（每个状态独立学习）	有（相似状态共享表示）

关键公式速查¶

算法	更新规则	类型
MC	$Q(s,a) \leftarrow Q(s,a) + \alpha[G_t - Q(s,a)]$	On-Policy
Sarsa	$Q(S,A) \leftarrow Q(S,A) + \alpha[R + \gamma Q(S',A') - Q(S,A)]$	On-Policy
Q-learning	$Q(S,A) \leftarrow Q(S,A) + \alpha[R + \gamma \max_{a'} Q(S',a') - Q(S,A)]$	Off-Policy

	首次访问 MC	每次访问 MC
统计方式	只在 \((s,a)\) 第一次出现时记录回报	每次出现都记录
偏差	无偏估计	有偏（但随样本增多趋于无偏）
常用程度	更常用	实践效果也不错

超参数	典型值	作用
学习率 \(\alpha\)	0.1 ~ 0.5	新信息的权重，太大振荡，太小学太慢
折扣因子 \(\gamma\)	0.9 ~ 0.99	对未来奖励的重视程度
\(\epsilon\) 初始值	1.0	初期多探索
\(\epsilon\) 最小值	0.01	收敛后仍保持微小探索
\(\epsilon\) 衰减率	0.995	每回合乘以衰减率
回合数	1000 ~ 10000	视环境复杂度而定

算法	更新规则	类型
MC	\(Q(s,a) \leftarrow Q(s,a) + \alpha[G_t - Q(s,a)]\)	On-Policy
Sarsa	\(Q(S,A) \leftarrow Q(S,A) + \alpha[R + \gamma Q(S',A') - Q(S,A)]\)	On-Policy
Q-learning	\(Q(S,A) \leftarrow Q(S,A) + \alpha[R + \gamma \max_{a'} Q(S',a') - Q(S,A)]\)	Off-Policy