无模型方法

蒙特卡洛方法的思想极其朴素：多次采样取平均。

对状态 $s_t$ 进行 $n$ 次采样，得到 $n$ 个真实回报 $g_t^1, g_t^2, \ldots, g_t^n$。根据大数定律：

增量更新形式

为了不保存所有历史值，使用增量形式：

但 $\frac{1}{n}$ 作为学习率有个问题：随着 $n$ 增大，新数据对均值的影响越来越小。因此实际中常用固定学习率 $\alpha \in (0, 1]$：

时序差分（Temporal Difference, TD）解决了蒙特卡洛"必须等回合结束"的问题：走一步就能更新。

生活类比：从昆明开车去北京。出发前导航预计 20 小时。开了 10 小时到西安后，这 10 小时是真实值，你可以用"实际行驶的 10 小时 + 折扣后的剩余估计"来更新总时长预测。

TD(0) 更新公式

其中 $r_{t+1} + \gamma V(s_{t+1})$ 叫做TD 目标，$\delta_t = r_{t+1} + \gamma V(s_{t+1}) - V(s_t)$ 叫做TD 误差。

SARSA 的名字来源于其更新所需的五元组：$S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}$。

更新公式

其中 $A'$ 是由当前执行的策略在 $S'$ 下实际选出的动作。

算法流程

1. 初始化 $Q(s,a) = 0$ 对所有 $s, a$
2. 对每个回合：
   1. 获取初始状态 $S$，用 $\epsilon$-Greedy 选择动作 $A$
   2. 循环每一步：
      1. 执行 $A$，获取 $R$ 和 $S'$
      2. 用 $\epsilon$-Greedy 选择 $A'$
      3. 更新 $Q(S, A)$
      4. $S \leftarrow S'$，$A \leftarrow A'$

Q-Learning 是最经典的无模型 RL 算法。你可以把它想象成训练一只小狗：做对了给饼干（正奖励），做错了就没有。

Q 值是什么？

"Q" 代表 Quality（质量）。$Q(s,a)$ 衡量在状态 $s$ 下采取动作 $a$ 后，预期能获得的长期奖励总和。

Q 表是智能体的"大脑"——一张查找表，横轴是动作，纵轴是状态。智能体查表选 Q 值最高的动作。

更新公式

注意与 SARSA 的区别：这里用的是 $\max_{a'} Q(s', a')$，而不是 $Q(s', A')$。也就是说：

• 与环境交互用 $\epsilon$-Greedy（探索）
• 更新 Q 表用贪婪策略（$\max$，利用）

环境设定：4 状态线性 MDP。

参数：$\gamma = 0.9$，$\alpha = 0.5$，$\epsilon = 0$（纯贪婪，简化演示）。

初始 Q 表

第一回合：$s_1 \to s_2 \to s_3 \to s_4$

步骤 1：在 $s_1$ 执行 →，获得 $r = -1$，到达 $s_2$。

步骤 2：在 $s_2$ 执行 →，获得 $r = -1$，到达 $s_3$。

步骤 3：在 $s_3$ 执行 →，获得 $r = +10$，到达 $s_4$（终止）。

第一回合结束后的 Q 表：

第二回合

步骤 1：$s_1$ → $s_2$，$r = -1$。现在 $Q(s_2, →) = -0.5$。

步骤 2：$s_2$ → $s_3$，$r = -1$。现在 $Q(s_3, →) = 5.0$。

步骤 3：$s_3$ → $s_4$，$r = +10$。

第二回合结束后的 Q 表：

第三回合

步骤 1：$s_1$ → $s_2$，$r = -1$，$Q(s_2) = 1.5$。

步骤 2：$s_2$ → $s_3$，$r = -1$，$Q(s_3) = 7.5$。

步骤 3：$s_3$ → $s_4$，$r = +10$。

收敛过程总结

环境：简化的悬崖漫步。1×5 网格，5 个状态。

状态编号：0（起点）、1（安全）、2（悬崖）、3（安全）、4（终点）。动作：左、右。每步奖励 -1。掉入悬崖奖励 -100 并重置到起点。

SARSA 的学习过程

SARSA 是 On-Policy 的。当智能体走到状态 3（紧邻悬崖右边），$\epsilon$-Greedy 有一定概率选择"左"——如果运气不好走进了悬崖，得到 -100 的惩罚。

这个惨痛经验被 SARSA 忠实记录在 Q 表中：$Q(s_3, \text{左})$ 会变得很低。结果：SARSA 学到的策略会刻意远离悬崖，选择一条更安全但可能更长的路径。

Q-Learning 的学习过程

Q-Learning 是 Off-Policy 的。即使 $\epsilon$-Greedy 偶尔走到悬崖，更新 Q 表时用的是 $\max_{a'} Q(s', a')$——即假设下一步选最优动作。这意味着偶尔的探索失败不会过度拉低 Q 值。

结果：Q-Learning 学到的策略会紧贴悬崖走最短路，因为在贪婪策略下（$\epsilon = 0$），它不会真的掉下去。

MC 方法看完整的轨迹（无偏，高方差），TD(0) 只看一步（有偏，低方差）。TD($\lambda$) 在两者之间取折中：回看 $n$ 步，用 $n$ 步回报作为更新目标。

$n$ 步回报

当 $n=1$ 时就是 TD(0)，$n \to \infty$ 时就是 MC。

前向视角与后向视角

• 前向视角：从当前状态向前看 $n$ 步，需要等 $n$ 步才能更新。
• 后向视角（资格迹）：维护一个"迹"（trace）$E_t(s)$，记录每个状态最近被访问的程度。每步更新所有状态的 V 值，但访问越久远的状态更新幅度越小。

参数 $\lambda \in [0,1]$ 控制迹的衰减速度。$\lambda = 0$ 退化为 TD(0)，$\lambda = 1$ 接近 MC。

标准 Q-Learning 使用 $\max$ 操作选择下一状态的 Q 值。这会导致最大化偏差（Maximization Bias）：因为 max 选的是估计值中最大的，而估计本身有噪声，所以结果倾向于高估。

Double Q-Learning 的解决方案

维护两张独立的 Q 表：$Q_1$ 和 $Q_2$。

• 更新 $Q_1$ 时，用 $Q_2$ 来评估价值：$\text{target} = R + \gamma Q_2(S', \arg\max_{a'} Q_1(S', a'))$
• 更新 $Q_2$ 时，用 $Q_1$ 来评估价值：对称操作

每次随机选择更新 $Q_1$ 还是 $Q_2$。这样，即使一个 Q 表高估了，另一个表提供无偏的价值评估，从而消除最大化偏差。