本应用旨在深入解读强化学习 (Reinforcement Learning, RL) 中的三种核心模型无关算法：蒙特卡洛 (Monte Carlo, MC) 方法、时序差分 (Temporal-Difference, TD) 学习以及 Sarsa 算法。强化学习是人工智能领域的一个重要分支，智能体通过与环境交互并从试错中学习，以最大化累积奖励。这三种算法为理解价值函数估计和策略优化提供了基础框架。
强化学习 (Reinforcement Learning, RL) 是人工智能领域中一个极其活跃的研究分支。其核心思想在于，一个智能体 (agent) 在与一个复杂且通常不确定的环境 (environment) 进行交互的过程中，通过试错 (trial-and-error) 的方式学习如何行动，以期最大化其接收到的累积奖励 (cumulative reward)。与监督学习 (supervised learning) 不同，强化学习中的智能体不会被明确告知在特定情况下应该采取哪个“正确”动作；相反，它必须通过自身的经验来发现哪些行为能够带来最大的长期回报。
在强化学习的众多方法中，基于价值 (value-based) 的方法占据了核心地位。这类方法致力于估计价值函数 (value function)，例如状态价值函数 $V(s)$ 或状态-动作价值函数 $Q(s,a)$。状态价值函数 $V(s)$ 衡量的是从状态 $s$ 出发，遵循某一特定策略所能获得的期望累积奖励；而状态-动作价值函数 $Q(s,a)$ 则衡量在状态 $s$ 下采取动作 $a$，然后遵循某一特定策略所能获得的期望累积奖励。这些价值函数为智能体提供了一种评估不同状态或行动“好坏”程度的量化标准。
许多强大的强化学习算法属于模型无关 (model-free) 的范畴。这意味着它们可以直接从与环境交互获得的经验数据中学习价值函数和（或）策略，而无需事先了解或构建环境的完整动态模型，即状态转移概率 $P(s'|s,a)$ 和奖励函数 $R(s,a)$。这种特性使得模型无关算法在处理那些环境模型未知或过于复杂以至于难以建模的现实问题时，具有显著的优势。蒙特卡洛 (Monte Carlo, MC) 方法和时序差分 (Temporal-Difference, TD) 学习是模型无关方法中最具代表性的两类。
蒙特卡洛方法、时序差分学习以及 Sarsa 算法是强化学习理论与实践中的基石。它们不仅为解决复杂的决策制定问题提供了有效的计算框架，也为理解更高级的强化学习技术（例如深度Q网络 (Deep Q-Networks, DQN) 和各种策略梯度方法）奠定了坚实的基础。这些算法代表了从经验中学习价值函数的几种基本范式。MC 方法依赖于完整的经验序列（回合）来估计回报，而 TD 方法则利用了自举 (bootstrapping) 的思想，基于单步或多步的奖励和后续状态的价值估计来更新当前状态的价值。Sarsa 算法是 TD 学习在控制问题（即寻找最优策略）上的一个重要同策略 (on-policy) 应用。本应用将详细解读这三种算法的原理、流程及其数学内涵，并进行比较分析。
蒙特卡洛方法是强化学习中一类重要的模型无关算法。它们通过经验学习，即直接从与环境交互产生的完整回合数据中估计价值函数和（或）寻找最优策略。本节将详细介绍MC算法的基本原理、预测（价值估计）和控制（策略搜索）方法。
MC方法的一个根本特征是它们从完整的经验回合 (episodes) 中学习。一个回合是指智能体从某个起始状态开始，经过一系列的状态、动作和奖励，最终达到一个终止状态的完整序列。MC方法要求智能体完成整个回合的交互后，才能收集到用于价值函数估计的全部信息。因此，价值函数的更新通常发生在每一回合结束之后。
MC方法估计价值函数的核心思想非常直观：它通过对多次独立试验（即多个完整回合）中观测到的实际回报 (sample returns) 进行平均，来作为对该状态或状态-动作对期望回报的估计。回报 $G_t$ 被定义为从时间步 $t$ 开始，直至该回合结束所获得的折扣奖励的总和： $$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots + \gamma^{T-t-1} R_T$$ 其中，$R_{t+k+1}$ 是在时间步 $t+k+1$ 获得的即时奖励，$\gamma \in [0,1]$ 是折扣因子，$T$ 是该回合的最终时间步。
MC 方法因其直接使用实际观测到的完整回报进行平均，其对价值函数的估计在某种意义上是“无偏”的。这里的“无偏”指的是它不依赖于对其他状态价值的估计（即不进行自举）来进行当前状态价值的更新。每个完整的回报 $G_t$ 都可以看作是目标价值 $V_\pi(s)$（或 $Q_\pi(s,a)$）的一个独立样本。根据大数定律，当样本数量足够多时，这些独立样本的均值会收敛到其真实的期望值。
然而，这种不依赖其他估计的“纯粹性”是有代价的。MC 方法的估计通常具有较高的方差 (variance)。回报 $G_t$ 是一个回合中所有未来奖励的总和，而一个回合的长度可能很长，并且其中可能包含许多随机的决策和状态转移。因此，在不同的回合中，即使从相同的状态开始，所获得的完整回报 $G_t$ 也可能因环境的随机性或策略的随机性而产生剧烈波动。这种波动性导致了样本均值的高方差，意味着可能需要经历非常多的回合才能获得对价值函数的稳定且准确的估计。
MC预测的目标是，在给定一个固定策略 $\pi$ 的情况下，估计该策略下的状态价值函数 $V_\pi(s)$ 或动作价值函数 $Q_\pi(s,a)$。
对于状态价值函数 $V(s)$ 的估计，MC方法主要有两种变体：首次访问MC (First-Visit MC) 和每次访问MC (Every-Visit MC)。
与 $V(s)$ 类似，$Q(s,a)$ 的估计也有首次访问和每次访问两种MC方法，流程相似，只是记录和平均的是状态-动作对 $(S_t, A_t)$ 的回报。
首次访问 MC (First-Visit MC) 和每次访问 MC (Every-Visit MC) 都是有效的价值估计算法，并且在理论上，当对一个状态（或状态-动作对）的访问次数趋于无穷时，它们的估计都会收敛到真实的价值函数 $V_\pi(s)$ (或 $Q_\pi(s,a)$)。
首次访问 MC 的一个理论优势在于其分析相对简单，因为每次收集的回报都是独立同分布的样本。每次访问 MC 的估计则不是独立同分布的，但也被证明可以收敛。在实践中，两者表现差异不大，但首次访问 MC 因其理论简洁性更常被讨论。
MC控制的目标是利用MC预测方法来找到最优策略 $\pi_*$。这通常在广义策略迭代 (GPI) 框架下进行：交替进行策略评估 (估计 $Q_\pi(s,a)$) 和策略改进 (基于 $Q_\pi(s,a)$ 贪婪化策略)。
学习目标策略 $\pi$ (通常贪婪)，用行为策略 $b$ (探索性) 生成数据。核心技术是重要性采样。
同策略 MC 方法（如 ε-贪心）直接学习一个兼顾探索的策略，通常更简单、方差较低、收敛较快，但学习的是一个“折衷”策略。
异策略 MC 方法将学习策略与行为策略分离，理论上可以直接学习最优策略，灵活性更大。但依赖重要性采样，若采样率方差过大，会导致估计不稳定、收敛慢甚至发散。
MC方法的核心是估计期望回报。对于策略 $\pi$，状态价值 $V_\pi(s) = E_\pi[G_t | S_t=s]$，动作价值 $Q_\pi(s,a) = E_\pi[G_t | S_t=s, A_t=a]$。MC通过计算大量样本回报的算术平均值来逼近这些期望，依据是大数定律。
MC方法不直接使用贝尔曼方程 $V_\pi(s) = E_\pi[R_{t+1} + \gamma V_\pi(S_{t+1}) | S_t=s]$ 的递归结构进行更新（即不自举）。但其估计的价值函数若收敛到真实值，则必然满足贝尔曼方程。MC方法可视为直接估计贝尔曼方程的“解”。
时序差分 (TD) 学习是强化学习中最核心和最具创新性的思想之一。它结合了蒙特卡洛 (MC) 方法和动态规划 (DP) 方法的优点：像MC一样从经验中学习，无需模型；像DP一样使用自举，基于现有估计更新估计。
TD学习的关键特征是自举。与MC等待完整回合不同，TD在每一步后，利用对后续状态价值的当前估计来更新当前状态的价值估计。例如，TD(0) 在状态 $S_t$ 执行动作后，得到 $R_{t+1}$ 和 $S_{t+1}$，然后使用 $R_{t+1}$ 和对 $V(S_{t+1})$ 的当前估计来更新 $V(S_t)$。
由于自举，TD无需等待回合结束即可更新，适用于连续性任务或回合非常长的任务，通常学习速度更快。
TD学习的自举和单步更新赋予其“在线”学习能力，适合快速适应环境变化。然而，TD更新的目标（如 $R_{t+1} + \gamma V(S_{t+1})$）依赖于对 $V(S_{t+1})$ 的当前估计。若此估计不准（尤其在学习早期），TD更新就是朝一个“有偏”的目标移动，偏差会传播。这是TD获得较低方差和在线学习能力的权衡。MC的目标 $G_t$ 是对真实期望回报的无偏样本。
TD(0) (单步TD) 是最基础的TD方法，用于估计给定策略 $\pi$ 下的状态价值 $V_\pi(s)$。
TD(0)的目标是找到满足贝尔曼期望方程 $V_\pi(s) = E_\pi[R_{t+1} + \gamma V_\pi(S_{t+1}) | S_t=s]$ 的 $V_\pi(s)$。TD(0)的更新规则可视为对此方程的一种随机近似或基于采样的迭代求解。TD目标 $R_{t+1} + \gamma V(S_{t+1})$ 是对期望项 $E_\pi[\dots]$ 的单样本估计。通过不断调整 $V(S_t)$ 向此目标移动，在合适条件下，$V(s)$ 收敛到 $V_\pi(s)$。
Sarsa (State-Action-Reward-State-Action) 是一种同策略 (on-policy) 时序差分 (TD) 控制算法。它在学习动作价值函数 $Q(s,a)$ 的过程中，用于生成经验数据的策略与正在被评估和改进的策略是同一个。
Sarsa评估并改进的是智能体当前实际执行的那个策略。智能体根据当前估计的 $Q$ 值（通常结合 ε-贪心探索）选择动作，并利用这些交互产生的经验来更新同一个 $Q$ 值函数。
Sarsa的学习依赖五元组 $(S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1})$：当前状态 $S_t$，当前动作 $A_t$，即时奖励 $R_{t+1}$，下一状态 $S_{t+1}$，以及在 $S_{t+1}$ 根据当前策略选择的下一动作 $A_{t+1}$。$A_{t+1}$ 是Sarsa的关键。
Sarsa的更新目标 $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$ 中，$A_{t+1}$ 是实际选择的动作。若行为策略含探索（如 ε-贪心），$A_{t+1}$ 可能是探索性动作。如果探索性动作导致低 $Q(S_{t+1}, A_{t+1})$（如走向危险区域），这个低 $Q$ 值会影响 $Q(S_t, A_t)$，使其降低。因此，Sarsa学习的 $Q$ 值反映了实际执行策略（含探索）的性能。在探索可能导致负面后果时（如悬崖行走问题），Sarsa倾向于学习更安全的路径，即使不是理论最优。这与异策略的Q-learning（更新目标用 $\max_{a'} Q(S_{t+1}, a')$）不同，后者更“激进”。
Sarsa的首要目标是估计当前行为策略 $\pi$ (通常 ε-贪心) 下的动作价值函数 $Q_\pi(s,a)$。其更新规则可视为对 $Q_\pi(s,a)$ 的贝尔曼期望方程 $Q_\pi(s,a) = E_\pi[R_{t+1} + \gamma Q_\pi(S_{t+1}, A_{t+1}) | S_t=s, A_t=a]$ 的采样更新。
Sarsa是广义策略迭代 (GPI) 的实例。策略评估：每步更新估计当前 ε-贪心策略的 $Q$ 值。策略改进：选择动作时采用 ε-贪心，倾向于利用已学到的较优动作。若满足GLIE条件，Sarsa理论上可收敛到 $Q^*$ 和 $\pi^*$。
贝尔曼最优方程为 $Q^*(s,a) = E[R_{t+1} + \gamma \max_{a'} Q^*(S_{t+1}, a') | S_t=s, A_t=a]$。Sarsa更新规则不直接用 $\max_{a'} Q(S_{t+1}, a')$，而是用 $Q(S_{t+1}, A_{t+1})$。但当 $\epsilon \to 0$ 时，ε-贪心策略接近纯贪婪，$A_{t+1} \approx \arg\max_{a'} Q(S_{t+1}, a')$，此时Sarsa更新目标接近Q-learning。Sarsa通过同策略学习和策略迭代间接朝满足贝尔曼最优方程的 $Q^*$ 收敛。
本节对蒙特卡洛 (MC) 方法、时序差分 (TD) 学习（以TD(0)为例）以及 Sarsa 算法的核心特性、学习效率、收敛性、优缺点及应用场景进行总结和比较。这有助于理解它们在不同情境下的适用性。
MC、TD(0) 和 Sarsa 均为模型无关算法，直接从经验中学习。它们的主要区别在于更新时点、是否自举以及价值更新的依据。
| 特性 (Characteristic) | 蒙特卡洛 (Monte Carlo) | 时序差分 (TD(0) 预测) | Sarsa |
|---|---|---|---|
| 是否需要环境模型 | 否 | 否 | 否 |
| 是否自举 (Bootstrapping) | 否 | 是 | 是 (作为TD方法) |
| 价值更新时机 | 回合结束后 | 每步之后 | 每步之后 |
| 价值更新依据 | 完整回合的实际回报 $G_t$ | 即时奖励与下一状态的估计价值 $R_{t+1} + \gamma V(S_{t+1})$ | 即时奖励与下一状态-动作对的估计价值 $R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})$ |
| 控制算法策略类型 | 同策略 (ε-greedy) 或 异策略 (Importance Sampling) | (TD(0)主要用于预测) | 同策略 (On-Policy) |
MC方法的价值估计是无偏的（不依赖其他估计），但通常方差较高。TD(0)和Sarsa由于自举，其价值估计有偏（依赖后续不准确的估计），但通常方差较低。TD(0)试图找到与最大似然马尔可夫过程参数一致的价值估计，而MC方法试图最小化训练数据上的均方误差。
MC方法（如首次访问MC）在i.i.d.样本下依大数定律收敛，但高方差可能导致收敛慢。TD方法通常比MC收敛更快，尤其在长回合任务中。在满足适当条件下（学习率衰减、充分探索），TD方法有收敛到真实价值的理论保证。Sarsa若采用GLIE策略，可收敛到 $Q^*$ 和 $\pi^*$。
TD方法通常数据效率更高，因其从每步经验中提取信息。在非平稳环境中，TD方法（尤其用固定小学习率时）通常比标准MC表现更好，能更快适应变化。
自举是TD方法与MC的核心区别，是其在线学习、低方差、高数据效率等优势的来源，但也是引入偏差的根本原因。TD更新依赖对下一状态价值的当前估计 $V(S_{t+1})$，若其不准，偏差会传播。MC不使用其他价值估计，直接用完整回报 $G_t$，在自举层面无偏。自举通过牺牲一定无偏性换取学习效率提升和方差降低。选择MC还是TD取决于问题对偏差-方差权衡的偏好及其他需求。
| 算法 (Algorithm) | 优点 (Advantages) | 缺点 (Disadvantages) | 典型应用 (Typical Applications) |
|---|---|---|---|
| 蒙特卡洛 (MC) | 无自举偏差；概念简单；可能更适合非马尔可夫环境 | 高方差；需完整回合；不适用于连续任务 | 回合制游戏 (如二十一点)，回合不长的模拟环境 |
| 时序差分 (TD(0) 预测) | 低方差；在线单步更新；通常收敛快；适用于连续任务 | 自举引入偏差；对初始值敏感 | 各种预测问题，作为更复杂算法的基础 (如Q-learning, Sarsa) |
| Sarsa | 继承TD优点 (在线, 单步, 低方差)；同策略评估实际执行策略的性能；在某些风险敏感场景下可能更安全 | 同策略可能导致收敛慢或次优；受探索策略影响 | 机器人导航，需要考虑探索成本或策略稳定性的控制问题 |
本应用对强化学习中的蒙特卡洛方法、时序差分学习和Sarsa算法进行了深入的探讨和比较。这些算法是理解更复杂强化学习技术的基础，并在理论和实践中均占有重要地位。
MC、TD和Sarsa在学习机制、更新时点及统计特性上存在关键区别。MC依赖完整回合，无自举，估计无偏但高方差。TD（含Sarsa）采用自举，单步在线更新，估计有偏但低方差，通常效率更高。Sarsa是同策略TD控制算法。尽管存在区别，它们都遵循广义策略迭代框架，通过评估和改进策略来逼近最优解。TD可视为MC与DP思想的结合。
这些算法不仅是入门基础，更在强化学习理论体系和实际应用中扮演关键角色。它们为理解高级算法（如DQN, Actor-Critic）奠定概念基础，揭示了从经验中学习决策的基本原理和途径，并体现了探索与利用、偏差与方差、同策略与异策略等核心权衡。即便在新算法涌现的今天，这些经典算法及其变种在特定问题或作为复杂算法组件时仍具应用价值，是分析、设计新方法及评估性能的起点和基准。