直觉与动机#

要谈「最优决策」，先得把「决策问题」写清楚。MDP 给出的抽象是：智能体处于某个状态，选一个动作，环境按转移概率跳到新状态并给一个奖励，如此往复。关键的简化假设是马尔可夫性——「未来只取决于现在，与如何到达现在无关」。这个假设让「最优」变得可计算：无需记住整段历史，只看当前状态即可。

形式化#

一个（有限、折扣）MDP 是元组 $(S, A, P, R, \gamma)$：状态集 $S$、动作集 $A$、转移核 $P(s'\mid s,a)$、奖励 $R(s,a)$、折扣 $\gamma\in[0,1)$。策略 $\pi(a\mid s)$ 把状态映到动作分布。马尔可夫性：

Bellman 期望方程（评估固定策略 $\pi$）与Bellman 最优方程（刻画最优 $v_*$）：

关键结果与性质#

• 收缩性：Bellman 最优算子是 sup-范数下的 $\gamma$-收缩，$v_*$ 是其唯一不动点。
• 值迭代（Value Iteration）：反复应用最优算子，以速率 $\gamma$ 几何收敛到 $v_*$（渐近，非有限步）。
• 策略迭代（Policy Iteration）（Howard 1960）：交替「精确策略评估」与「贪心改进」，对有限 MDP 有限步内收敛到最优（单调改进 + 确定性策略只有有限个）。
• 最优策略存在性：有限折扣 MDP 总存在一个确定性平稳最优策略。

局限与延伸#

MDP 用状态、动作、转移概率与奖励函数刻画满足 Markov 性的决策过程，但这并不要求智能体事先知道转移模型 $P$ 和奖励函数 $R$。智能体能直接观测 Markov 状态时通常按 MDP 建模；观测不足时使用 POMDP。当 $P,R$ 未知时，可以通过 MC、TD 等 model-free 方法从交互样本中学习；状态空间过大时还需要函数逼近。参见 Sutton & Barto, Ch. 3。

Takeaways#

MDP 是 RL 的「坐标系」。后面每一个算法，本质都是在「模型未知 / 状态部分可见 / 状态空间巨大」这三种放松下，近似地求解 Bellman 方程。

@article{kaelbling1998planning,
  title   = {Planning and Acting in Partially Observable Stochastic Domains},
  author  = {Kaelbling, Leslie Pack and Littman, Michael L. and Cassandra, Anthony R.},
  journal = {Artificial Intelligence},
  volume  = {101},
  number  = {1--2},
  pages   = {99--134},
  year    = {1998}
}

直觉与动机#

现实里智能体几乎从不「看见完整状态」：机器人只有带噪传感器、遮挡、有限视场。此时当前观测不满足马尔可夫性——两个真实状态可能给出相同观测却需要不同动作。POMDP 的回答是：把「对隐状态的概率分布」当作真正的决策依据。

形式化#

POMDP 在 MDP 元组上增加观测集 $\Omega$ 与观测模型 $O(o\mid s',a)$，成为 $(S, A, P, R, \Omega, O, \gamma)$。智能体看不到 $s$，转而维护信念状态 $b\in\Delta(S)$——状态上的概率分布，它是最优控制的充分统计量。执行动作 $a$、收到观测 $o$ 后按贝叶斯更新：

于是 POMDP 等价于在连续信念空间 $\Delta(S)$ 上的一个「信念 MDP」。

关键结果与性质#

• 值函数结构：有限时程下，信念上的最优值函数是分段线性且凸（PWLC），可由有限组 α-向量表示（Smallwood & Sondik 1973）。
• 复杂度：有限时程精确求解 PSPACE-complete；无限时程判定最优/近优策略不可判定——这也是实践中普遍采用近似（point-based value iteration、QMDP、粒子滤波 + 规划、或直接端到端学循环策略）的原因。
• KLC 1998 本身是信念-MDP 框架与 Witness 算法的标准出处；上述硬度结论出自 Papadimitriou–Tsitsiklis、Madani 等另一支文献。

局限与延伸#

精确 POMDP 只在很小的问题上可解。现代做法要么用近似信念表示，要么在深度 RL 里用 RNN / Transformer 隐状态隐式地承担「信念」的角色（把历史压进隐藏状态）。理解 POMDP 的价值在于：它解释了为什么部分可观测任务需要记忆。

Takeaways#

MDP → POMDP 是「完全可观测 → 信念状态上的序贯决策」的一步跨越。凡是感知有噪、有遮挡、需要记忆的任务，其形式底座都是 POMDP 或其近似。

@book{sutton2018reinforcement,
  title     = {Reinforcement Learning: An Introduction},
  author    = {Sutton, Richard S. and Barto, Andrew G.},
  edition   = {Second},
  publisher = {MIT Press},
  year      = {2018},
  url       = {http://incompleteideas.net/book/the-book-2nd.html}
}

直觉与动机#

当转移与奖励未知时，最朴素的估值方式是「多试几次，看平均能拿多少回报」。这就是 MC：不建模环境、不做自举，纯靠采样的完整回报的样本均值逼近价值。它是理解无模型 RL 的起点，也是 TD 的对照面。

形式化#

用回合内从 $t$ 起的完整回报 $G_t = R_{t+1} + \gamma R_{t+2} + \dots$ 的样本均值估计 $v_\pi(s)$ 或 $q_\pi(s,a)$：

• 首次访问 MC（first-visit）：每回合只取 $s$ 首次出现之后的回报平均。在固定策略、独立生成 episode，且状态被访问的条件下，这些回报可以作为 $v_\pi(s)$ 的无偏样本；样本平均随有效访问次数增加而收敛。若策略持续变化或轨迹相关，就不能直接把样本称为 i.i.d.。
• 每次访问 MC（every-visit）：对 $s$ 的每次出现都计入。有限样本有偏（同回合内回报相关），但一致（访问数 → ∞ 时收敛）。

关键结果与性质#

• 不使用自举目标，但方差通常较高：在上述固定策略评估条件下，完整回报是无偏样本；整条轨迹累积的随机性会放大方差。
• 需要回合终止：必须观测到完整回报才能更新，不适用连续不终止任务。
• 探索：控制时需保证所有 $(s,a)$ 被采到——用探索起点（exploring starts），或改用 on-policy 的 ε-soft 策略维持探索。
• off-policy MC：用行为策略 $b$ 评估目标策略 $\pi$ 需重要性采样——普通 IS 无偏但方差可能无限；加权 IS 有偏但方差远低，实践更常用。

局限与延伸#

高方差和必须等回合结束，是回合式 MC 的两项主要限制。TD 通过自举提供另一种取舍：不必等到回合结束，目标方差通常更低，但会受当前价值估计误差影响。实际表现还取决于步长、函数逼近和数据分布。

Takeaways#

MC 给出「用完整经验回报估值」的基本范式。关键不是背诵“无偏、高方差”标签，而是说明条件：固定策略下完整回报可作为无偏样本，方差通常较高，标准更新要等到回合结束。

@article{sutton1988learning,
  title   = {Learning to Predict by the Methods of Temporal Differences},
  author  = {Sutton, Richard S.},
  journal = {Machine Learning},
  volume  = {3},
  pages   = {9--44},
  year    = {1988}
}

直觉与动机#

MC 要等回合结束才知道回报，太慢也太吵。但其实我们不必等：走一步、看到即时奖励和下个状态，就已经对「这一步好不好」有了信息——因为下个状态的价值估计 $V(S_{t+1})$ 已经包含了对未来的预测。用这个「一步真实 + 后续估计」去更新当前估计，就是自举。

形式化#

TD(0) 更新：

TD 误差 $\delta_t = R_{t+1} + \gamma V(S_{t+1}) - V(S_t)$ 是「新信息与旧估计之差」。TD(λ) 用几何权重 $(1-\lambda)\lambda^{n-1}$ 融合所有 n-step 回报；后向视角引入资格迹（eligibility trace）：

$\lambda=0$ 退化为 TD(0)，$\lambda=1$ 等价于 MC——TD(λ) 是连接二者的连续谱。

关键结果与性质#

• 自举、可在线，方差通常较低：目标依赖当前价值估计，因此有限样本误差中可能包含自举偏差；偏差与方差的实际大小还取决于步长、函数逼近和数据分布。
• 收敛性：Sutton (1988) 证明 TD(λ) 对吸收马尔可夫链均值收敛；表格 TD(0) 的几乎必然收敛由 Dayan (1992)、Jaakkola–Jordan–Singh (1994) 给出；线性逼近 + on-policy 收敛见 Tsitsiklis & Van Roy (1997)。
• 致命三要素（deadly triad）：函数逼近 + 自举 + 离策略三者同时出现时可能发散——这是深度 RL 稳定性问题的重要来源。DQN 的目标网络和经验回放在 Atari 实验中改善了稳定性，但不提供一般收敛保证。
• 标准步长条件：Robbins–Monro，$\sum_t\alpha_t=\infty,\ \sum_t\alpha_t^2<\infty$。

局限与延伸#

自举目标依赖当前价值估计；在有限样本、函数逼近或参数持续更新时，误差可能传播，并在离策略训练中放大。TD 的优势是可在线更新且通常比完整回报具有更低方差，因此成为 Q-learning 等价值方法的基础。

Takeaways#

TD 是 RL 里最核心的一个 idea：用估计更新估计。它既是 MC 与 DP 的桥梁，也埋下了「致命三要素」这颗后续深度 RL 反复要处理的雷。

@article{watkins1992q,
  title   = {Q-learning},
  author  = {Watkins, Christopher J. C. H. and Dayan, Peter},
  journal = {Machine Learning},
  volume  = {8},
  pages   = {279--292},
  year    = {1992}
}

直觉与动机#

TD 能评估一个给定策略；但我们真正想要的是最优策略。Q-learning 的巧妙在于：把 TD 目标里的「按当前策略取下一动作」换成「取贪心动作 $\max_a Q$」。这样无论行为策略如何探索，学到的都是最优 Q——评估的对象（目标策略）与产生数据的对象（行为策略）解耦，即离策略。

形式化#

更新规则（离策略 TD 控制）：

目标中的 $\max_a Q$ 是贝尔曼最优算子的采样近似；行为上常用 ε-greedy 保证探索，但它不进入目标——故为离策略。

关键结果与性质#

表格情形下，$Q$ 以概率 1 收敛到 $Q^*$，当且仅当：

1. 每个状态–动作对 $(s,a)$ 被无限次访问；
2. 步长满足 Robbins–Monro：$\sum_t\alpha_t(s,a)=\infty,\ \sum_t\alpha_t^2(s,a)<\infty$；
3. 奖励有界，$\gamma<1$（或问题为恰当的回合式 MDP）。

原始证明见 Watkins & Dayan (1992)；更一般的随机逼近证明见 Jaakkola–Jordan–Singh (1994)、Tsitsiklis (1994)。注意：保证仅对表格成立，函数逼近下不再有收敛保证。

局限与延伸#

表格 Q-learning 无法直接扩展到高维或连续状态。当多个动作价值估计含噪时，$\max$ 算子可能产生正偏差。用神经网络逼近 $Q$ 得到 DQN：经验回放与目标网络改善训练稳定性，Double DQN 解耦动作选择和价值评估以缓解过估计；连续动作无法通过枚举求 $\max$，则需要 DDPG 等不同的策略参数化。

Takeaways#

Q-learning 是价值派的代表：先学好 $Q^*$，再贪心导出策略。它的两处软肋——只能表格 / 只能离散——直接定义了下一篇 DQN、DDPG、SAC 等一系列工作的问题域。

@article{williams1992simple,
  title   = {Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning},
  author  = {Williams, Ronald J.},
  journal = {Machine Learning},
  volume  = {8},
  pages   = {229--256},
  year    = {1992}
}
@inproceedings{sutton1999policy,
title     = {Policy Gradient Methods for Reinforcement Learning with Function Approximation},
author    = {Sutton, Richard S. and McAllester, David and Singh, Satinder and Mansour, Yishay},
booktitle = {Advances in Neural Information Processing Systems 12 (NIPS 1999)},
year      = {1999}
}

直觉与动机#

价值派（Q-learning）先估价值、再贪心导出策略，对连续/高维动作或随机最优策略并不方便。策略派换个思路：把策略本身参数化为 $\pi_\theta$，直接调 $\theta$ 让期望回报变大。难点在于——回报既取决于策略选的动作，也取决于策略诱导的状态分布，后者对 $\theta$ 的依赖看似难算。策略梯度定理解决了这个难点。

形式化#

策略梯度定理：对目标 $J(\theta)$（如期望回报），

其中 $d^\pi$ 是策略诱导的（折扣）状态分布。关键：梯度中不出现 $\nabla_\theta d^\pi$——状态分布对 $\theta$ 的依赖恰好消去，于是梯度可纯由采样估计。

REINFORCE 更新（蒙特卡洛策略梯度，Williams 1992）：

用完整回报 $G_t$，无偏但高方差。

关键结果与性质#

• 基线（baseline）减方差：减去任意与动作无关的 $b(S_t)$ 不引入偏差（因 $\mathbb{E}[\nabla_\theta\log\pi\cdot b]=0$），常取 $b(s)\approx V(s)$，得优势 $G_t - V(s)$。
• 演员–评论家（actor-critic）：把 $G_t$ 换成自举的 critic 估计（如 TD 误差 $\delta_t$ 作优势），actor 更新策略、critic 学价值——用偏差换更低方差、可在线。
• 兼容函数逼近：Sutton et al. (1999) 证明用兼容特征逼近 $q_\pi$ 可得精确无偏的策略梯度。

局限与延伸#

纯 REINFORCE 方差太大、样本效率低。现代策略方法几乎都在此基础上加约束与减方差：PPO（裁剪限制更新幅度）、SAC（最大熵 + 双 Q）、DDPG（确定性策略梯度）；乃至 LLM 后训练的 RLHF/GRPO 也都是策略梯度的直系后代。

Takeaways#

Policy Gradient 是策略派的根。记住两点：梯度可采样估计（定理保证）、必须减方差（基线 / critic）。第二篇的 PPO、SAC、GRPO 全是「如何更稳、更省地做策略梯度」的不同答案。