样本复杂度与前沿理论¶

前置自测¶

📋 前置自测（答不出 ≥ 2 题 → 先回 6.1–6.5 复习）

Bellman 最优算子 $T^*$ 为什么是 $\gamma$-压缩映射？它在哪个范数下压缩？（回顾 6.1：$T^*$ 在 sup-norm $\|\cdot\|_\infty$ 下满足 $\|T^*V - T^*V'\|_\infty \le \gamma\|V-V'\|_\infty$，证明的关键是 max-difference lemma + 概率归一。）
Q-learning 的 SA 收敛定理需要哪三个条件（Robbins-Monro 条件）？（6.5）
Policy gradient 定理中"score function $\nabla\log\pi$"的概率含义是什么？（6.2）
什么是"致命三元组"？为什么 off-policy + function approximation + bootstrapping 会导致发散？（6.3）
模型预测误差如何通过 simulation lemma 传递到值函数误差？给出 $(1-\gamma)^{-2}$ 因子的直觉解释。（6.4）

本章目标¶

学完本章后，你能够：

完整推导 UCB1 的 regret 界，并将同一套证明技术（集中不等式 + union bound + 乐观原理）推广到 tabular MDP（UCBVI）和线性 MDP（LSVI-UCB）；
**精确陈述**并直觉理解 tabular MDP 的 minimax 样本复杂度 $\tilde\Theta(H^2SA/\varepsilon^2)$ 及其信息论下界（Le Cam 两点法）；
**独立解释**乐观主义（online）与悲观主义（offline）的数学对偶关系，以及 concentrability coefficient $C^*$ 对 offline RL 样本效率的决定性影响；
阅读并理解 CQL/IQL/Cal-QL 等 offline RL 论文的核心定理而不被术语阻挡；
掌握 Distributional RL 的 Wasserstein 压缩性证明、CMDP 的 Lagrangian 对偶与 CPO 约束满足保证、DAgger 的 compounding error 分析。

知识树¶

样本复杂度与前沿理论
├── PAC-MDP 框架 [§6.6.1]
│   ├── PAC 学习回顾
│   ├── PAC-MDP 定义（Kakade 2003）
│   ├── E³ 算法（Kearns-Singh 2002）
│   ├── R-MAX（Brafman-Tennenholtz 2003）
│   └── Simulation Lemma
├── Bandit 与 Exploration-Exploitation [§6.6.2]
│   ├── Regret 定义
│   ├── UCB1 完整证明
│   ├── Thompson Sampling
│   └── UCRL2 → MDP 推广
├── Tabular Minimax 样本复杂度 [§6.6.3]
│   ├── UCBVI-BF（Azar et al. 2017）
│   ├── Bernstein-style bonus
│   ├── 信息论下界（Le Cam 两点法）
│   └── Model-based vs Model-free 分离
├── 线性 MDP 与 LSVI-UCB [§6.6.4]
│   ├── 线性 MDP 定义与 Bellman 闭包
│   ├── Self-normalized martingale
│   ├── Elliptical potential lemma
│   └── 超越线性：bilinear class, DEC
├── Offline RL 悲观主义原理 [§6.6.5]
│   ├── Distribution shift 的形式化
│   ├── Concentrability coefficient
│   ├── PEVI（Jin et al. 2021）
│   ├── CQL 理论保证
│   └── 乐观↔悲观对偶
├── Distributional RL [§6.6.A]
│   ├── 分布 Bellman 方程
│   ├── Wasserstein 压缩性完整证明
│   ├── C51 / QR-DQN / IQN 演进
│   └── 风险敏感控制
├── Safe RL / CMDP [§6.6.B]
│   ├── CMDP 最优策略存在性
│   ├── Lagrangian 对偶与 primal-dual 收敛
│   ├── CPO / PCPO
│   └── CBF-QP 层
├── Reward-free Exploration [§6.6.C]
│   ├── 形式化与样本复杂度
│   └── 与多任务机器人的连接
├── Offline-to-Online Fine-tuning [§6.6.D]
│   ├── Cal-QL calibration
│   └── RLPD / AWAC
├── 模仿学习理论 [§6.6.E]
│   ├── BC compounding error 完整证明
│   ├── DAgger 线性化
│   ├── GAIL occupancy matching
│   └── IRL → RLHF
└── Sim2Real 学习理论视角 [§6.6.F]
    ├── Domain shift bound
    ├── DR 作为分布鲁棒优化
    └── Robustness certification

引言：从"会不会收敛"到"要多少样本" ⭐¶

前五个专题（6.1–6.5）回答的是**"算法会不会收敛"。这一节回答的是一个更尖锐的、博士 qual 必考的问题："要多少样本才能收敛到 $\varepsilon$-最优？"** 这是学习理论视角下的强化学习，把 RL 纳入了与 PAC 学习、在线学习、统计决策论同一个数学框架。核心工具不再是 Bellman 算子的压缩性（6.1）或 ODE 方法（6.5），而是**集中不等式（Hoeffding/Bernstein/Freedman）、信息论下界（KL 散度、Le Cam 两点法）和覆盖率系数（concentrability coefficient）**。

本质洞察：样本复杂度理论的根本问题不是"给定无限数据能学到什么"，而是"有限数据下你能对未见过的状态-动作做多好的推断"。这与统计学习理论（VC 维、Rademacher 复杂度）和信息论（信道容量、率失真函数）的精神完全一致——有限资源下的最优推断。

跨领域类比：样本复杂度之于 RL，就像通信中的香农极限之于编码理论——它告诉你**理论上最好能做多好**（下界），以及**用什么算法能逼近这个极限**（可达性）。UCB1/UCBVI 就像 Turbo Code/LDPC——逼近理论极限的实际算法。

本节同时覆盖三个正在主导 RL 研究议程的**前沿方向**：offline RL 的悲观主义原理（与 online 乐观原理形成对偶，是当前 robotic foundation model 训练的数学基石）、distributional RL（把"期望回报"推广为"回报分布"，Wasserstein 压缩性是 C51/QR-DQN/IQN 的理论支柱）、safe RL 与 CMDP（约束 MDP 的 Lagrangian 与投影方法，是机器人真机学习的安全门槛）。对机器人算法工程师而言，本节的价值是：当你阅读 Berkeley / Levine 组 / DeepMind 的最新 paper 时，不再被 "$C^*$ 系数" "pessimistic VI" "expectile regression" 这些术语挡在门外——它们都源自几个简洁的数学动机。

档位安排：§6.6.1–§6.6.6 为档位 3 必学（PAC-MDP、bandit regret、tabular minimax、线性 MDP、悲观原理、offline RL 算法与理论）；§6.6.A–§6.6.F 为档位 4 选学（distributional RL、safe RL/CMDP、reward-free exploration、offline-to-online fine-tuning、IL 交叉、Sim2Real 学习理论）。

§6.6.1 PAC-MDP 框架与乐观探索 ⭐⭐¶

动机：为什么需要 PAC-MDP？¶

回顾 6.5 的 Q-learning SA 定理：在 Robbins-Monro 步长下，Q-learning 几乎必然收敛**到 $Q^*$。但这个定理有一个致命缺陷——**它不告诉你要等多久。具体而言：

如果你的 MDP 有 $10^6$ 个状态、$10$ 个动作，Q-learning 需要每个 $(s,a)$ 对被访问无穷多次才收敛。
在 $\varepsilon$-greedy 探索下，某些 $(s,a)$ 可能被访问的频率极低——样本复杂度可能是指数级的。
更糟的是，如果 reward 只在状态空间的某个"角落"出现（想象一个迷宫，终点在最远处），随机探索可能需要指数时间才能到达。

这就像一个人在黑暗中摸索出口：你**知道出口存在**（收敛性保证），但不知道**要摸多久才能找到**（样本复杂度未知）。PAC-MDP 框架的目标正是回答这个问题。

反事实推理：如果不关心样本复杂度会怎样？在仿真中这无所谓——多跑几百万步即可。但在**真机**上，每一步交互都意味着磨损、电费、安全风险。一个样本复杂度为 $O(|\mathcal{S}|^3)$ 的算法与 $O(|\mathcal{S}|)$ 的算法，在 $|\mathcal{S}| = 10^6$ 时差 12 个数量级——前者永远不可能在真机上完成训练。

从 PAC 学习到 PAC-MDP¶

监督学习的 PAC 框架（Valiant 1984）问：给定 $\varepsilon, \delta$，要多少样本才能以概率 $\ge 1-\delta$ 学到一个误差 $\le \varepsilon$ 的假设？经典结果是：对有限假设类 $|\mathcal{H}|$，PAC 样本复杂度为 $O(\frac{1}{\varepsilon^2}\log\frac{|\mathcal{H}|}{\delta})$；对无限假设类，用 VC 维 $d_{\text{VC}}$ 替代 $\log|\mathcal{H}|$。

Kakade（2003 thesis，MIT，"On the Sample Complexity of Reinforcement Learning"）与 Strehl–Li–Littman 把这个问题搬进 MDP。核心困难在于：RL 不是 i.i.d. 采样——当前的策略决定了未来的数据分布。这使得标准的 PAC 分析不能直接套用。

定义（$(\varepsilon,\delta)$-PAC-MDP，Kakade 2003；Strehl–Li–Littman JCSS 2008）：一个 RL 算法 $\mathcal{A}$ 被称为 $(\varepsilon,\delta)$-PAC-MDP，如果存在一个多项式 $\text{poly}(|\mathcal{S}|,|\mathcal{A}|,1/\varepsilon,1/\delta,1/(1-\gamma))$，使得在与环境交互的过程中，$\mathcal{A}$ 采取的动作满足 $V^{\pi_t}(s_t) \ge V^*(s_t) - \varepsilon$ 的那些时刻，其补集（"sub-optimal 时刻"）的个数以概率 $\ge 1-\delta$ 不超过该多项式。

关键直觉：PAC-MDP 不要求算法"总是最优"，只要求"不最优的步数"被多项式限制住——这正好匹配 exploration 的本质（探索必然带来短暂的次优）。这与 regret 的区别是微妙的：regret 计算**所有**次优步骤的**累积代价**，而 PAC-MDP 只计算次优步骤的**个数**。

本质洞察：PAC-MDP 框架的核心贡献不是某个具体算法，而是**把 RL 的有效性变成了一个可证明的数学性质**——"以概率 $1-\delta$，次优步数不超过多项式"。这使得我们可以像比较排序算法的复杂度一样，比较 RL 算法的样本效率。

E³ 算法：Explore-or-Exploit 的第一个多项式保证 ⭐⭐⭐¶

E³（Explicit Explore or Exploit）（Kearns–Singh, Machine Learning 2002，"Near-Optimal Reinforcement Learning in Polynomial Time"）是第一个被证明多项式样本复杂度的 RL 算法。

核心思想：维护一个"已知状态集"$\mathcal{S}_{\text{known}}$——对于其中的状态，转移和 reward 已被充分估计。在每一步： - 如果当前状态 $s\in\mathcal{S}_{\text{known}}$ 且最优策略不会离开已知集，则 exploit（执行在已知模型上的最优策略）； - 否则，执行**平衡游走**（balanced wandering）以系统地探索未知状态。

E³ 的 PAC-MDP 保证（Kearns-Singh 2002, Theorem 1）： $$ \text{sub-optimal steps} \le O!\left(\frac{|\mathcal{S}|^3 |\mathcal{A}|}{\varepsilon^3(1-\gamma)^6} \log\frac{1}{\delta}\right) $$

E³ 的 $|\mathcal{S}|^3$ 依赖过于粗糙（平衡游走的覆盖引入了额外 $|\mathcal{S}|$ 因子），这促使 Brafman–Tennenholtz 设计了更优雅的 R-MAX。

集中不等式工具箱：本节所有证明的底层 ⭐⭐⭐¶

在进入 R-MAX 之前，先整理本节反复使用的三个集中不等式，它们构成了**所有样本复杂度证明的基石**：

不等式	条件	结论	适用场景
Hoeffding	$X_i \in [a,b]$, i.i.d.	$\Pr[	\bar X - \mu
Bernstein	$X_i \in [a,b]$, i.i.d., $\text{Var}(X_i)=\sigma^2$	$\Pr[	\bar X - \mu
Freedman	$\{M_t\}$ martingale, $	M_t - M_{t-1}	\le b$

Hoeffding 是最粗的：它只用了有界性，完全忽略方差信息。当真实方差 $\sigma^2 \ll (b-a)^2$ 时（如 V* 在某些状态变化很小），Hoeffding 界松得多。

Bernstein 利用了方差：它给出 $O(\sigma/\sqrt{n} + b/n)$ 的置信宽度（对比 Hoeffding 的 $(b-a)/\sqrt{n}$）。当 $\sigma \ll b-a$ 时显著更紧。

Freedman 处理 martingale（非 i.i.d.）：RL 中的数据不是 i.i.d. 的（$s_{t+1}$ 取决于 $s_t, a_t$）。Freedman 不等式允许我们对**conditional variance**（预测方差）做集中——这是 UCBVI 和 LSVI-UCB 处理非独立数据的关键工具。

为什么需要从 Hoeffding 升级到 Bernstein？ 考虑 UCBVI 的 bonus：如果用 Hoeffding，bonus $\sim H/\sqrt{N}$（因为 $V^* \in [0,H]$，range 是 $H$）。用 Bernstein，bonus $\sim \text{Var}(V^*)/\sqrt{N} + H/N$。当 $\text{Var}(V^*)$ 远小于 $H^2$ 时（很多 MDP 确实如此），Bernstein bonus 小得多。这个差异在聚合（sum over episodes）后给出 $\sqrt{S}$ 的改进。

R-MAX：乐观探索的原型 ⭐⭐¶

R-MAX（Brafman–Tennenholtz, JMLR 2003） 是 PAC-MDP 框架下最具影响力的原型算法，其数学动机极其简洁：

"optimism in the face of uncertainty (OFU)"：对任何未被充分访问的 $(s,a)$，乐观地假设它会带来**最大可能的 reward** $R_{\max}$，并指向一个吸收状态。

算法流程：

初始化：所有 $(s,a)$ 标记为"未知"；设 $m = \lceil \frac{c \cdot |\mathcal{S}|}{\varepsilon^2(1-\gamma)^2} \log\frac{|\mathcal{S}||\mathcal{A}|}{\delta} \rceil$（阈值）
对每个 $(s,a)$，维护访问计数 $N(s,a)$ 和经验统计 $\hat P(\cdot|s,a), \hat r(s,a)$
构造**乐观 MDP** $\tilde{M}$：
若 $N(s,a) \ge m$：用经验模型 $\hat P, \hat r$
若 $N(s,a) < m$：设 $\tilde r(s,a) = R_{\max}$，$\tilde P(s_{\text{absorb}}|s,a) = 1$（进入一个 reward = $R_{\max}$ 的吸收态）
在 $\tilde{M}$ 上做 value iteration，得到策略 $\tilde\pi$
执行 $\tilde\pi$；当任何 $(s,a)$ 的 $N(s,a)$ 达到 $m$，重新规划

为什么乐观有效？ 这是 OFU 原理的精髓：

如果"未知"的 $(s,a)$ 真的好：乐观估计对了，我们会选择它，获得高 reward——没损失。
如果"未知"的 $(s,a)$ 实际不好：乐观估计诱使我们去尝试它——看似亏了，实则收获了信息（$N(s,a)$ 增加，下次就不再"未知"了）。

无论哪种情况，算法都在进步——要么收获 reward，要么收获信息。这就是 OFU 的 exploration-exploitation 自动平衡。

跨领域类比：R-MAX 的乐观策略就像一个**风险中性的投资者**，对未知资产默认假设"它可能是下一个谷歌"——这迫使他**至少试一次**。试过之后发现不好，就永远不再碰。这种"先乐观假设，再用数据纠正"的范式贯穿了整个 online RL 理论。

核心定理（Brafman–Tennenholtz 2003, Theorem 5）：R-MAX 是 $(\varepsilon,\delta)$-PAC-MDP，其非最优步数上界为 $$ \tilde O!\left(\frac{|\mathcal{S}|^2|\mathcal{A}|}{\varepsilon^3(1-\gamma)^6}\right). $$

R-MAX 证明骨架 ⭐⭐⭐¶

证明分三步：

Step 1（模型精度）：用 Hoeffding 不等式。对固定的 $(s,a)$，经验转移概率 $\hat P(\cdot|s,a)$ 是 $N(s,a)$ 次独立采样的平均。由 Hoeffding： $$ \Pr\bigl[|\hat P(\cdot|s,a) - P(\cdot|s,a)|_1 > \varepsilon_P\bigr] \le 2|\mathcal{S}|\exp(-2N(s,a)\varepsilon_P^2/|\mathcal{S}|^2) $$ 取 $N(s,a) = m = O(\frac{|\mathcal{S}|}{\varepsilon_P^2}\log\frac{|\mathcal{S}||\mathcal{A}|}{\delta})$，由 union bound 覆盖所有 $|\mathcal{S}||\mathcal{A}|$ 对，以概率 $\ge 1-\delta$ 保证所有"已知"状态-动作的模型精度 $\le \varepsilon_P$。

Step 2（Simulation Lemma）：把模型误差翻译成值函数误差。

引理（Simulation Lemma，Kearns–Singh 2002）：若 $\|\hat P - P\|_1 \le \varepsilon_P$ 且 $|\hat r - r| \le \varepsilon_r$ 对所有已知 $(s,a)$，则 $$ |V^_{\hat M}(s) - V^M(s)| \le \frac{\varepsilon_r + \gamma\varepsilon_P \cdot V\right) $$}}{1-\gamma} = O!\left(\frac{\varepsilon_P}{(1-\gamma)^2

这个 $(1-\gamma)^{-2}$ 因子的物理含义：模型误差在每一步累积，而 discounted horizon 有 $1/(1-\gamma)$ 步，每步误差传播一次再乘以 horizon，给出 $(1-\gamma)^{-2}$。

Step 3（已知集单调扩张）：关键观察——如果策略进入"未知"状态-动作，它一定是在**乐观地追求高 reward**。每次这样做，$N(s,a)$ 增加 1。由于 $m$ 是有限的，每个 $(s,a)$ 最多被"误导"进入 $m$ 次。全部 $|\mathcal{S}||\mathcal{A}|$ 对加起来，sub-optimal steps $\le m \cdot |\mathcal{S}||\mathcal{A}| = O(\frac{|\mathcal{S}|^2|\mathcal{A}|}{\varepsilon^2(1-\gamma)^2})$。

将三步合并并优化 $\varepsilon_P$ 的选取，得到最终的 $\tilde O(|\mathcal{S}|^2|\mathcal{A}|/\varepsilon^3(1-\gamma)^6)$ 界。Strehl–Li–Littman（MBIE/MBIE-EB，JCSS 2008）通过更精细的 Bernstein 不等式把界改进为 $\tilde O(|\mathcal{S}|^2|\mathcal{A}|/\varepsilon^2(1-\gamma)^3)$。

⚠️ 常见陷阱¶

💡 概念误区：混淆 PAC-MDP 与 regret - 新手想法："PAC-MDP 和 regret 是一回事，都在说样本效率" - 实际区别：PAC-MDP 计算**次优步数**（0-1 衡量），regret 计算**累积次优程度**（加权衡量）。regret 更精细——它区分"稍微次优"和"严重次优"。PAC-MDP 界 $N$ 意味着 regret $\le N \cdot V_{\max}$，但反过来不一定。

🧠 思维陷阱：认为 OFU 在 offline 也适用 - 新手想法："乐观总是好的，不管 online 还是 offline" - 实际上：OFU 在 online 时有效是因为乐观导致探索，探索带来新数据纠正错误。在 offline 中，数据已经固定，探索不可能发生。乐观的 Q 值无法被新数据纠正，只会被 bootstrap 放大——这就是 offline RL 崩溃的根源（§6.6.5）。

练习¶

手推 simulation lemma：从 Bellman 方程 $V^* = \max_a[r(s,a) + \gamma\sum_{s'}P(s'|s,a)V^*(s')]$ 出发，假设 $\hat P$ 与 $P$ 的 $L_1$ 距离为 $\varepsilon_P$，推导 $|V^*_{\hat M} - V^*_M|$ 的上界。明确指出哪一步用了三角不等式，哪一步用了 $\|P-\hat P\|_1 \le \varepsilon_P$。
R-MAX 的空间复杂度：计算 R-MAX 需要存储什么？对 $|\mathcal{S}|=10^6, |\mathcal{A}|=10$ 的 MDP，存 $\hat P$ 需要多少内存（double 精度）？这与 model-free 方法（只存 $Q$ 表）相比如何？
OFU 的必要性：构造一个 3 状态 2 动作的 MDP，使得 $\varepsilon$-greedy 探索需要指数时间找到最优策略，但 R-MAX 只需多项式时间。

§6.6.2 Bandit 问题与 Exploration–Exploitation ⭐⭐¶

动机：为什么要先学 bandit？¶

要理解 MDP 的 regret 理论，必须先把 MDP 退化成 bandit（1 个状态，$|\mathcal{A}|$ 个动作，无转移）。这一步的价值是：

把分析**简化到只剩"重复试验下的统计估计"**——没有状态转移的干扰
UCB1 的证明是**所有后续 MDP regret 证明的原型**——UCBVI、LSVI-UCB 都是它的推广
bandit 理论本身在**超参数选择**（HPO）、A/B 测试（推荐系统）、贝叶斯优化（机器人控制参数调整）中有直接应用

反事实推理：如果跳过 bandit 直接学 MDP regret 会怎样？你会面对一堆"对 $V^*$ 的方差做集中""用 Freedman 不等式处理 martingale"这些技术，完全不知道它们的动机。先在 bandit 上看到"Hoeffding → UCB → regret bound"的清晰推理链，再去 MDP 就只是"把同样的技术加上 value iteration"。

Regret 的严格定义 ⭐⭐¶

在 episodic RL 中（episode 长 $H$，共 $K$ 个 episode，$T = KH$）： $$ \text{Regret}(T) = \sum_{k=1}^{K}\bigl[V_1^*(s_1^{(k)}) - V_1^{\pi_k}(s_1^{(k)})\bigr]. $$

在 Multi-Armed Bandit（MAB）中退化为： $$ \text{Regret}(T) = \sum_{t=1}^{T}(\mu^* - \mu_{a_t}), \qquad \mu^* = \max_a \mu_a. $$

与 PAC-MDP 的关系：regret $R(T) \le \varepsilon T + N \cdot V_{\max}$，其中 $N$ 是 PAC-MDP 的次优步数。因此 PAC-MDP 界自动给出 regret 上界，但精度更差。

UCB1：Hoeffding + union bound 的教科书应用 ⭐⭐¶

UCB1（Auer–Cesa-Bianchi–Fischer, Machine Learning 2002）：在 $t$ 时刻选择 $$ a_t = \arg\max_a\Bigl[\hat\mu_a(t) + \sqrt{\tfrac{2\ln t}{N_a(t)}}\Bigr]. $$ 右项称为 UCB bonus——它是 Hoeffding 置信区间的上边界宽度。

这个公式的来龙去脉： 1. 问题：$\hat\mu_a$ 是经验均值，但它有随机误差。如何在"利用当前最好 arm"和"尝试估计不确定的 arm"之间权衡？ 2. 核心想法：对每个 arm，计算"它**可能的最好表现**"（置信区间上界），选最高的那个。 3. 为什么是 $\sqrt{2\ln t / N_a}$？由 Hoeffding 不等式，对 $[0,1]$ 奖励， $$ \Pr\bigl[|\hat\mu_a - \mu_a| > c\bigr] \le 2\exp(-2N_a c^2) $$ 令 $c = \sqrt{\frac{2\ln t}{N_a}}$，则 $\Pr[\text{bad}] \le 2t^{-4}$——随 $t$ 增长快速衰减。

UCB1 Regret 完整证明 ⭐⭐⭐¶

定理（UCB1 regret 界）：对任何 $K$-arm MAB（奖励在 $[0,1]$）， $$ \mathbb{E}[\text{Regret}(T)] \le 8\sum_{a: \Delta_a > 0}\frac{\ln T}{\Delta_a} + (1 + \pi^2/3)K, $$ 其中 $\Delta_a = \mu^* - \mu_a$。worst-case（对 $\Delta_a$ 取最坏情况）为 $O(\sqrt{KT\ln T})$。

完整证明：

定义"好事件"：在时刻 $t$，对所有 arm $a$，置信区间覆盖真值： $$ E_t = \bigl{\forall a: |\hat\mu_a(t) - \mu_a| \le \sqrt{2\ln t / N_a(t)}\bigr} $$

Step 1：好事件的概率。由 Hoeffding + union bound over $K$ arms： $$ \Pr(E_t^c) \le \sum_a 2\exp(-2N_a \cdot 2\ln t / N_a) = 2K \cdot t^{-4} $$

Step 2：在好事件上，次优 arm $a$ 的拉取次数有界。若 $E_t$ 成立，$a$ 被选当且仅当 $$ \hat\mu_a + \sqrt{2\ln t / N_a} \ge \hat\mu_{a^} + \sqrt{2\ln t / N_{a^}} $$ 由 $E_t$ 有 $\hat\mu_{a^*} \ge \mu^* - \sqrt{2\ln t / N_{a^*}}$ 和 $\hat\mu_a \le \mu_a + \sqrt{2\ln t / N_a}$。代入： $$ \mu_a + 2\sqrt{2\ln t / N_a} \ge \mu^* $$ 即 $N_a \le 8\ln t / \Delta_a^2$。因此在 $E_t$ 上，arm $a$ 最多被拉 $\lceil 8\ln T / \Delta_a^2 \rceil$ 次。

Step 3：合并。 $$ \mathbb{E}[N_a(T)] \le \lceil 8\ln T/\Delta_a^2\rceil + \sum_{t=1}^T \Pr(E_t^c) \le 8\ln T/\Delta_a^2 + 1 + 2K\sum_{t=1}^\infty t^{-4} $$

Regret $= \sum_a \Delta_a \cdot \mathbb{E}[N_a(T)] \le \sum_a \frac{8\ln T}{\Delta_a} + O(K)$。这就是 instance-dependent 界。

Worst-case 推导：令 $K-1$ 个次优 arm 的 gap 均为 $\Delta$，则 regret $\le (K-1) \cdot 8\ln T / \Delta + (K-1)\Delta T$。对 $\Delta$ 求最优：$\Delta^* = \sqrt{8(K-1)\ln T / T}$，代入得 $O(\sqrt{KT\ln T})$。

这个证明为什么如此重要？ 因为后续所有 online RL 的 regret 证明——UCBVI、LSVI-UCB、PSRL——都沿用了**同样的三步**： 1. 定义好事件（集中不等式保证模型精度） 2. 在好事件上证明算法的性能界 3. 用 union bound 控制坏事件的概率

掌握了 UCB1 的证明，就掌握了 RL 样本复杂度证明的"通用模板"。

Thompson Sampling：Bayesian 替代 ⭐⭐⭐¶

Thompson Sampling（Thompson 1933——是的，1933 年！Russo–Van Roy 2014 现代分析）维护每个 arm 的后验分布，每步采样一个参数并取 greedy。对于 Bernoulli bandit：

初始化 Beta(1,1) 先验（即 Uniform[0,1]）
在时刻 $t$：对每个 arm $a$，从后验 $\text{Beta}(\alpha_a, \beta_a)$ 采样 $\theta_a$
选择 $a_t = \arg\max_a \theta_a$
观察 reward $r_t$，更新 $\alpha_{a_t} += r_t$，$\beta_{a_t} += (1-r_t)$

Thompson Sampling 的 Bayes regret 界（Russo-Van Roy 2014, Theorem 1）： $$ \text{BayesRegret}(T) \le O(\sqrt{KT\ln K}) $$ 与 UCB1 同阶，但常数更好。实证上 TS 经常强于 UCB——因为它"自然地"适应 instance 难度（后验窄的 arm 很快被排除）。

TS 的 MDP 推广——PSRL（Posterior Sampling RL）（Osband–Russo–Van Roy 2013）：在每个 episode 开始时，从转移模型的后验中采样一个 MDP，在该 MDP 上做最优规划。PSRL 的 Bayes regret 为 $\tilde O(H|\mathcal{S}|\sqrt{|\mathcal{A}|T})$，与 UCBVI 同阶。

UCRL2：bandit → MDP 的推广 ⭐⭐⭐¶

UCRL2（Jaksch–Ortner–Auer, JMLR 2010） 对 tabular MDP 给出第一个 $\sqrt{T}$ regret： $$ \text{Regret}(T) \le \tilde O\bigl(D|\mathcal{S}|\sqrt{|\mathcal{A}|T}\bigr), $$ 其中 $D$ 是 MDP 的 diameter（从任何状态到任何状态的最短期望步数的最大值）。

方法： 1. 对 $P$ 和 $r$ 建立 $L_1$-置信集 $\mathcal{C}_t = \{(\tilde P, \tilde r): \|\tilde P - \hat P\|_1 \le \varepsilon_P(t), |\tilde r - \hat r| \le \varepsilon_r(t)\}$ 2. 在所有可能的 MDP 中选**最乐观的** $\tilde M = \arg\max_{\tilde M \in \mathcal{C}_t} V^*_{\tilde M}$ 3. 在 $\tilde M$ 上做 extended value iteration，得到 policy $\tilde\pi$

UCRL2 的局限：regret 对 $|\mathcal{S}|$ 是线性（$D|\mathcal{S}|$），而下界只需要 $\sqrt{|\mathcal{S}|}$。这个 gap 在 2017 年被 Azar–Osband–Munos 的 UCBVI 补齐。

⚠️ 常见陷阱¶

💡 概念误区：$\varepsilon$-greedy 有 UCB 同等保证 - 新手想法："$\varepsilon$-greedy 也在探索，应该有类似 regret 界" - 实际上：$\varepsilon$-greedy 的 regret 是 $\Theta(\varepsilon T)$——线性增长。因为它以固定概率 $\varepsilon$ 随机探索，即使所有 arm 的统计已经足够精确。UCB 的关键优势在于 bonus 自动缩小：$\sqrt{\ln t / N_a}$ 随 $N_a$ 增长而衰减，所以探索在必要时进行，不必要时停止。

⚠️ 编程陷阱：UCB bonus 除以 0 - 错误做法：当 $N_a(t) = 0$ 时直接计算 $\sqrt{2\ln t / N_a}$ - 正确做法：未拉取的 arm 设 UCB = $+\infty$（优先选择），确保每个 arm 至少被拉一次

练习¶

手推 worst-case minimax regret 下界：用 $K$ 个 Bernoulli arm、gap $\Delta$，证明任何算法的 worst-case regret $\ge \Omega(\sqrt{KT})$（提示：考虑"所有 arm 均值相同"时的不可区分性）。
实现 UCB1 + Thompson Sampling（Python，<50 行）：在 10-arm Bernoulli bandit 上对比 UCB1、TS、$\varepsilon$-greedy 的 regret 曲线。观察 instance-dependent vs worst-case 行为。
从 UCB1 到 UCRL2 的推广：写出 UCRL2 的 "extended value iteration" 伪代码。与 R-MAX 对比：两者都是 OFU，但 UCRL2 显式搜索"最乐观 MDP"，而 R-MAX 只设 $R_{\max}$ bonus。哪种更紧？

§6.6.3 Tabular MDP 的 minimax 样本复杂度 ⭐⭐¶

动机：UCB1 到 UCBVI 的推进¶

UCB1 解决了 1-state bandit 的最优 regret。但 MDP 比 bandit 难在两方面： 1. 状态转移：当前动作影响未来状态，不再是独立重复试验 2. Credit assignment：奖励可能延迟（走了 $H$ 步才知道对错）

UCRL2（§6.6.2）给出了第一个 $\sqrt{T}$ regret，但对 $|\mathcal{S}|$ 的依赖不紧（$|\mathcal{S}|$ 而非 $\sqrt{|\mathcal{S}|}$）。问题是：tabular episodic MDP 的 minimax 最优 regret 到底是多少？

Azar–Osband–Munos 2017 定理 ⭐⭐¶

定理（Azar–Osband–Munos, ICML 2017；arXiv 1703.05449）：对有限时域 episodic tabular MDP（状态 $|\mathcal{S}|$，动作 $|\mathcal{A}|$，horizon $H$，$K$ episodes，$T = KH$），UCBVI-BF 算法在高概率下满足 $$ \text{Regret}(T) \le \tilde O!\left(\sqrt{H|\mathcal{S}||\mathcal{A}|T} + H^2|\mathcal{S}|^2|\mathcal{A}| + H\sqrt{T}\right). $$

当 $T \ge H^3|\mathcal{S}|^3|\mathcal{A}|$ 时，主导项为 $\tilde O(\sqrt{H|\mathcal{S}||\mathcal{A}|T})$。

对应的 PAC 样本复杂度（折合成"需要多少 episode 才能找到 $\varepsilon$-最优策略"）： $$ N_\varepsilon = \tilde\Theta!\left(\frac{H^2|\mathcal{S}||\mathcal{A}|}{\varepsilon^2}\right) \quad\text{(episodic)}, \qquad \tilde\Theta!\left(\frac{|\mathcal{S}||\mathcal{A}|}{\varepsilon^2(1-\gamma)^3}\right) \quad\text{(discounted)}. $$

为什么这个结果是里程碑：它与**信息论下界匹配**（$\Omega(\sqrt{H|\mathcal{S}||\mathcal{A}|T})$，Jaksch 2010、Osband–Van Roy 2016），确立了 tabular MDP 的 minimax 速率。就像 Shannon 定理确立了通信速率极限一样，这个定理确立了 tabular RL 的**学习速率极限**。

UCBVI-BF 的两把关键技术 ⭐⭐⭐¶

UCBVI 比 UCRL2 更优的原因在于两个技术创新：

技术 1：Bernstein-style bonus 替代 Hoeffding bonus

Hoeffding 不等式对 $[0,1]$ 有界随机变量给出 $O(1/\sqrt{N})$ 的置信宽度。但 Bernstein 不等式利用了**方差信息**：

\[ \Pr\bigl[|\hat\mu - \mu| > t\bigr] \le 2\exp\!\left(-\frac{Nt^2}{2(\sigma^2 + t/3)}\right) \]

这意味着：当真值的方差 $\sigma^2$ 很小时，集中更快。在 UCBVI 中，"真值"是 $V^*(s')$ 在下一状态上的值。如果 $V^*$ 在某些区域变化很小（方差低），Bernstein bonus 自动缩小——而 Hoeffding 无法利用这个信息。

具体而言：UCBVI 的 bonus 形如 $$ b_h(s,a) = c_1\sqrt{\frac{\hat{\text{Var}}{s'}[V $$}(s')] \cdot \ln(SAHT/\delta)}{N_h(s,a)}} + c_2\frac{H\ln(SAHT/\delta)}{N_h(s,a)

第一项是 Bernstein 的主项（利用方差），第二项是 Bernstein 的剩余项（高阶）。对比 Hoeffding 版本（只有 $H/\sqrt{N}$ 的粗糙项），Bernstein 在方差小时能省出 $\sqrt{|\mathcal{S}|}$ 因子。

技术 2：对 $V^*$ 做集中（而非对 $P$ 做集中）

传统方法（UCRL2）先估 $P$，再用 simulation lemma 传递到 $V^*$——传递过程中损失一个 $|\mathcal{S}|$ 因子（因为 $\|P\|_1$ 涉及对 $|\mathcal{S}|$ 个元素求和）。

UCBVI 的关键洞察：不需要精确估计整个 $P$ 矩阵。我们只需要 $P(\cdot|s,a)^\top V^*$ 的估计精确——这是一个**标量**（$V^*$ 的条件期望），可以直接用单个随机变量 $V^*(s')$（$s' \sim P(\cdot|s,a)$）来估计。

利用恒等式："$V^*$ 的方差之和 = 回报的方差"（Munos-Moore 1999 的 law of total variance 应用）： $$ \sum_h \text{Var}{s'}\bigl[V^*(s')\bigr] \le H^2 $$

这把方差项的聚合限制在 $H^2$ 内，最终给出 $\sqrt{H}$（而非 $H$）的 regret 依赖。

信息论下界：Le Cam 两点法 ⭐⭐⭐⭐¶

定理（Minimax 下界，Dann–Brunskill NeurIPS 2015；Osband–Van Roy 2016）： $$ \inf_{\text{algorithm}}\sup_{\text{MDP}} \text{Regret}(T) \ge \Omega!\left(\sqrt{H|\mathcal{S}||\mathcal{A}|T}\right) $$

证明思想（Le Cam 两点法）：

Le Cam 两点法的核心思想是：构造两个"几乎不可区分"但最优策略不同的实例，证明任何算法至少在其中一个上犯错。

Step 1：构造 hard MDP 族。考虑一个 chain MDP：$H$ 层，每层有 $S$ 个状态，每个状态有 $A$ 个动作。除了某一个"好"动作外，其余动作都给 0 reward。"好"动作给 $\varepsilon$ reward，但只在最后一层。

Step 2：计算 KL 散度。两个 MDP 的区别仅在于某个 $(s_h, a)$ 处的 reward：$M_0$ 给 0，$M_1$ 给 $\varepsilon$。经过 $N$ 次采样后的 KL 散度为 $\text{KL}(P_0^N \| P_1^N) = N \cdot \varepsilon^2 / 2$（Bernoulli KL 近似）。

Step 3：Le Cam 不等式。若 $\text{KL}(P_0^N \| P_1^N) \le c < 1$，则任何检验的误差概率 $\ge (1 - \sqrt{c})/2$。因此，要区分好/坏动作，需要 $N = \Omega(1/\varepsilon^2)$ 次访问**每个 $(s,a)$ 对**。

Step 4：聚合。全部 $SA$ 对中有 $SA$ 个需要区分，每个需 $1/\varepsilon^2$ 样本，在 $H$ 步 horizon 上展开： $$ T \ge \Omega(SAH / \varepsilon^2) \implies \text{Regret} \ge \varepsilon T \ge \Omega(\sqrt{SAHT}) $$

本质洞察：信息论下界告诉我们的不是"这个问题有多难"，而是"信息获取的基本物理限制在哪里"——就像海森堡不确定性原理告诉你"同时精确测量位置和动量"是不可能的，Le Cam 下界告诉你"用少于 $\Omega(SA/\varepsilon^2)$ 个样本区分两个 $\varepsilon$-close 的 MDP"是不可能的。

Model-based vs Model-free 的样本效率差异 ⭐⭐¶

方法	算法代表	Regret	空间	关键论文
Model-based	UCBVI	$\tilde O(\sqrt{HSAT})$	$O(S^2A)$	Azar et al. 2017
Model-free	UCB-Q-learning	$\tilde O(\sqrt{H^4SAT})$	$O(SA)$	Jin et al. 2018
Model-free（最优）	monotonic Q-learning	$\tilde O(\sqrt{H^3SAT})$	$O(SA)$	Zhang-Zhou-Ji 2020

关键差异：Model-free 多一个 $\sqrt{H}$ 到 $\sqrt{H^3}$ 的因子（取决于具体算法），代价是省去存储转移模型的 $O(S^2A)$ 空间。

Jin–Allen-Zhu–Bubeck–Jordan NeurIPS 2018 "Is Q-learning Provably Efficient?" 是第一篇证明 model-free 也有 $\sqrt{T}$ regret 的工作。核心技术：在 Q-learning 更新中加入 UCB bonus： $$ Q_{h}(s,a) \leftarrow (1-\alpha_t)\cdot Q_h(s,a) + \alpha_t\bigl[r_h + V_{h+1}(s') + b_h(s,a)\bigr] $$ 其中 $b_h$ 是 Hoeffding-style bonus。证明的难点在于：Q-learning 的更新不是"一次性估计"（像 UCBVI 那样重新计算），而是**增量更新**，需要处理 non-stationary 的 martingale。

工程含义：当你的机器人状态离散化后 $|\mathcal{S}|$ 适中（$< 10^5$），model-based 样本效率高且空间可承受；$|\mathcal{S}|$ 爆炸时（$> 10^6$），只能 model-free + 函数逼近（§6.6.4）。

Dann–Brunskill 2015 下界证明的详细展开 ⭐⭐⭐⭐¶

为了让信息论下界的证明思想更加具体，我们展示 Dann–Brunskill NeurIPS 2015 的 hard instance 构造（简化版）。

Hard MDP 构造：考虑 $H$-层 episodic MDP，每层 $S$ 个状态，每个状态 $A=2$ 个动作。MDP 结构如下：

每层的每个状态 $s$，动作 $a=0$ 转移到下一层的**固定**状态 $f(s)$
动作 $a=1$ 转移到下一层的**随机**状态——具体是哪个状态取决于 MDP instance

关键：构造 $N = S \times H$ 个 MDP instance $\{M_i\}$。每个 $M_i$ 只在一个特定的 $(s_h, a=1)$ 处给 reward $\varepsilon$（其余处 reward 为 0）。

信息论论证：

对于 agent 来说，区分 $M_i$ 和 $M_j$（$i\neq j$）需要： - 在**关键 $(s_h, a=1)$** 处收集足够样本观测到 reward 信号 - 由 Bernoulli KL 散度：$\text{KL}(\text{Bern}(0) \| \text{Bern}(\varepsilon)) = -\log(1-\varepsilon) \approx \varepsilon$ - 要以概率 $\ge 2/3$ 区分，需要 $N_{\min} = \Omega(1/\varepsilon)$ 次访问该 $(s_h, a)$

由于有 $SH$ 个可能的关键位置，agent 至少需要 $\Omega(SH/\varepsilon)$ 次 episode。每次 episode 长 $H$，总样本 $T = \Omega(SH^2/\varepsilon)$。

Regret 的贡献：agent 在前 $T$ 步中，有 $\Omega(T)$ 步在执行次优动作（因为还未识别最优策略），每步损失 $\varepsilon$。因此： $$ \text{Regret}(T) \ge \Omega(T \cdot \varepsilon) = \Omega(\sqrt{HSAT}) $$ （令 $\varepsilon = \sqrt{HSA/T}$ 做优化）。

Fano 不等式的替代路径：更精确的下界证明用 Fano 不等式。对 $N$ 个假设的假设检验问题，Fano 不等式给出： $$ \Pr(\text{error}) \ge 1 - \frac{I(\theta; \text{data}) + \log 2}{\log N} $$ 其中 $I(\theta; \text{data})$ 是 MDP instance index 和观测数据之间的互信息。在上述构造中 $I \le O(T\varepsilon^2)$（因为 KL 散度小），代入得 error rate 下界。

从 UCBVI 到 MVOI：最新进展（2021–2025） ⭐⭐⭐⭐¶

UCBVI 达到了 minimax 最优，但它的**instance-dependent** bound 不紧。后续工作进一步优化：

UCBVI-CH（Dann–Lattimore–Brunskill 2019）：用 Chernoff-Hoeffding 的"tilted" 版本，给出更紧的 instance-dependent 界
MVOI（Minimum Variance Optimistic Iteration）（Zhang–Ji–Du 2021）：直接优化方差项，达到 instance-optimal
StrongEuler（Simchowitz–Jamieson 2019）：对 communicating MDP 给出 gap-dependent regret $O(\sum_{s,a} H^2/\Delta(s,a) \cdot \log T)$

这些进展说明：即使在 tabular 设定下，样本复杂度理论仍在快速发展。每一步的改进都需要更精细的集中不等式和更巧妙的算法设计。

⚠️ 常见陷阱¶

🧠 思维陷阱：把 $\tilde O$ 当精确界 - 新手想法："UCBVI 的 regret 是 $\sqrt{HSAT}$，所以 $H$ 增大 4 倍 regret 只增大 2 倍" - 实际上：$\tilde O$ 隐藏了 $\log$ 因子和常数。实际中常数可能很大（UCBVI 的 bonus 系数涉及 $\ln(SAT/\delta)$，当 $\delta$ 很小时不可忽略）。理论界是**scaling law**（依赖如何增长），不是**绝对值**。

💡 概念误区：Bernstein bonus 一定强于 Hoeffding bonus - 实际上：Bernstein 需要估计方差 $\hat\sigma^2$，而方差估计本身也有误差。当 $N$ 很小时，$\hat\sigma^2$ 不可靠，Bernstein bonus 的"高阶项"$H\ln/N$ 可能主导——此时不如直接用 Hoeffding。真正的优势只在 $N$ 足够大（$N \gtrsim H^2/\sigma^2$）时才显现。

⚠️ 编程陷阱：Bernstein bonus 的方差估计溢出 - 错误做法：直接用 $\hat\sigma^2 = \frac{1}{N}\sum (V(s'_i) - \bar V)^2$ 估计方差 - 问题：当 $N$ 很小时（$N=1,2$），$\hat\sigma^2$ 可能为 0（恰好所有样本相同）或极大（极端值） - 正确做法：用 $\hat\sigma^2 = \max(\hat\sigma^2_{\text{sample}}, \varepsilon_{\min})$ 做下界截断，或在 Bernstein bonus 中保留 Hoeffding 项作为"保底"

练习¶

Bernstein vs Hoeffding 对比：对 $N=100$ 次观测 Bernoulli($p$) 随机变量，分别计算 $p=0.01$ 和 $p=0.5$ 时 Hoeffding 和 Bernstein 的 95% 置信区间宽度。观察方差小时 Bernstein 的优势。
Le Cam 两点法实操：构造一个 $S=3, A=2, H=5$ 的 chain MDP 和一个 $\varepsilon$-perturbation 版本。计算 KL 散度，验证 Le Cam 下界给出的样本需求。
跨章综合题：回顾 6.1 的 Bellman 算子压缩性证明。UCBVI 的 "value iteration with bonus" 本质上是在对什么算子做不动点迭代？该算子还是压缩映射吗？如果不是，UCBVI 凭什么收敛？（提示：bonus 随 $N$ 缩小，asymptotically 变回标准 Bellman 算子）
信息论下界构造：对 $S=4, A=2, H=3$，显式构造 Dann-Brunskill 式的 hard MDP 族（画出转移图），计算最优 regret 下界的数值。

§6.6.4 线性 MDP 与 LSVI-UCB ⭐⭐⭐¶

动机：tabular 的极限¶

tabular 分析告诉你"最优界是什么"，但 $|\mathcal{S}|$ 只要一过百万（机器人观测基本都是这样），整个框架直接失效。具体而言：

一个 6-DOF 关节角空间，每个维度 100 格离散化 → $|\mathcal{S}| = 100^6 = 10^{12}$
UCBVI 需要 $O(S^2A)$ 空间 → $10^{24}$ 个 double → 不可能
即使 model-free（$O(SA)$ 空间），$10^{12} \times 10$ 的 Q-table 也存不下

必须用函数逼近。但函数逼近引入了新问题：神经网络的逼近误差如何与 Bellman backup 交互？最干净的理论回答来自**线性 MDP 假设**。

反事实推理：如果不做函数逼近假设会怎样？Du–Kakade–Wang–Yang 2019 证明了一个**负面结果**：对一般的 MDP + 函数逼近（只假设 $Q^*$ 可被函数类 $\mathcal{F}$ 逼近），不存在多项式样本复杂度算法。即使 $\mathcal{F}$ 是线性函数类，如果没有额外的结构假设，样本复杂度可以是指数级的。因此，线性 MDP 假设（或更广的 Bellman 闭包假设）不仅是"方便"，更是**必要**的。

线性 MDP 假设 ⭐⭐⭐¶

定义（Jin–Yang–Wang–Jordan, COLT 2020；arXiv 1907.05388）：存在已知特征映射 $\phi:\mathcal{S}\times\mathcal{A}\to\mathbb{R}^d$（$\|\phi(s,a)\|\le 1$），以及未知测度 $\mu:\mathcal{S}\to\mathbb{R}^d$ 和向量 $\theta^*\in\mathbb{R}^d$，使得 $$ P(s'\mid s,a) = \phi(s,a)^\top \mu(s'), \qquad r(s,a) = \phi(s,a)^\top \theta^*. $$

这个假设的含义： 1. 转移核可分离：$P(s'|s,a)$ 可以写成 $(s,a)$-dependent 部分 $\phi(s,a)$ 和 $s'$-dependent 部分 $\mu(s')$ 的内积——这是一种"低秩"结构。 2. Bellman 闭包：对任何 $V:\mathcal{S}\to[0,H]$， $$ P_h V = \sum_{s'} P(s'|s,a)V(s') = \phi(s,a)^\top \underbrace{\sum_{s'}\mu(s')V(s')}_{=: w_V \in \mathbb{R}^d} $$ 因此 $Q_h(s,a) = r(s,a) + [P_h V_{h+1}](s,a) = \phi(s,a)^\top (\theta^* + w_{V_{h+1}})$——Q 函数始终是 $\phi$ 的线性组合。这就是"Bellman 闭包"的最简情形：value iteration 不会跳出线性函数类。

跨领域类比：线性 MDP 之于一般 MDP，就像**线性系统**（$\dot x = Ax + Bu$）之于一般非线性系统。线性系统有完美的理论（LQR、Kalman filter），非线性系统只能局部逼近。同理，线性 MDP 有完美的样本复杂度理论，一般 MDP + 神经网络只能做 empirical verification。

LSVI-UCB 算法 ⭐⭐⭐¶

算法核心（每个 episode $k$）：

数据收集：从 $\pi_{k-1}$ 获得 $(s_h^k, a_h^k, r_h^k, s_{h+1}^k)$
最小二乘回归（backward from $h=H$ to $h=1$）： $$ \Lambda_h^k = \lambda I + \sum_{\tau=1}^{k-1}\phi(s_h^\tau, a_h^\tau)\phi(s_h^\tau, a_h^\tau)^\top \in \mathbb{R}^{d\times d} $$ $$ w_h^k = (\Lambda_h^k)^{-1}\sum_{\tau=1}^{k-1}\phi(s_h^\tau, a_h^\tau)\bigl[r_h^\tau + V_{h+1}^k(s_{h+1}^\tau)\bigr] $$
UCB 构造： $$ Q_h^k(s,a) = \min\bigl{\phi(s,a)^\top w_h^k + \beta\sqrt{\phi(s,a)^\top(\Lambda_h^k)^{-1}\phi(s,a)}, H\bigr} $$
贪心策略：$\pi_k(s) = \arg\max_a Q_h^k(s,a)$

bonus 项 $\beta\sqrt{\phi^\top\Lambda^{-1}\phi}$ 的含义：$\Lambda^{-1}$ 是参数估计的协方差矩阵的逆（在 Bayesian 线性回归中是 posterior precision 的逆）。因此 $\phi^\top\Lambda^{-1}\phi$ 衡量的是"在方向 $\phi(s,a)$ 上的**估计不确定性**"——数据越密集的方向不确定性越小，bonus 越小。这正是 OFU 的线性 MDP 版本。

LSVI-UCB 定理与证明骨架 ⭐⭐⭐⭐¶

定理（Jin–Yang–Wang–Jordan, COLT 2020）：取 $\beta = O(dH\sqrt{\log(dT/\delta)})$，则以概率 $\ge 1-\delta$： $$ \text{Regret}(K) = \sum_{k=1}^K [V_1^(s_1) - V_1^{\pi_k}(s_1)] \le \tilde O\bigl(\sqrt{d^3 H^3 K}\bigr) $$ 折合 $T = KH$：$\text{Regret}(T) \le \tilde O(\sqrt{d^3 H^3 T})$。**与 $|\mathcal{S}|,|\mathcal{A}|$ 无关*。

证明骨架（三步）：

Step 1（Self-normalized martingale 不等式）。这是 Abbasi-Yadkori–Pál–Szepesvári 2011 的核心工具。定义 martingale difference $\eta_h^\tau = r_h^\tau + V_{h+1}(s_{h+1}^\tau) - \phi(s_h^\tau,a_h^\tau)^\top w^*_h$（真实参数与观测的差）。则： $$ |w_h^k - w_h^*|_{\Lambda_h^k} \le \beta \quad \text{以概率} \ge 1-\delta $$ 其中 $\|v\|_M = \sqrt{v^\top M v}$ 是加权范数。这保证了线性模型参数的集中。

Step 2（乐观性）。由 Step 1： $$ Q_h^k(s,a) \ge \phi(s,a)^\top w_h^* + \beta\sqrt{\phi^\top\Lambda^{-1}\phi} - \beta\sqrt{\phi^\top\Lambda^{-1}\phi} = Q_h^*(s,a) - 0 $$ 等等——实际上需要递归地证明 $V_h^k(s) \ge V_h^*(s)$（乐观性），利用 bonus 的构造和 Bellman 闭包。

Step 3（Elliptical potential lemma）。关键引理： $$ \sum_{k=1}^K \sqrt{\phi_k^\top(\Lambda_k)^{-1}\phi_k} \le \sqrt{K \cdot \sum_{k=1}^K \phi_k^\top\Lambda_k^{-1}\phi_k} \le \sqrt{K \cdot 2d\log(1 + K/\lambda d)} $$ 第一步是 Cauchy-Schwarz，第二步是 elliptical potential lemma（利用 $\det\Lambda_K \le (1 + K/\lambda d)^d$）。

合并三步：$\text{Regret}(K) \le \sum_k 2\beta\sqrt{\phi_k^\top\Lambda_k^{-1}\phi_k} \le 2\beta\sqrt{K \cdot 2d\log(\cdot)} = \tilde O(\sqrt{d^3 H^3 K})$。

Self-normalized Martingale 不等式详解 ⭐⭐⭐⭐¶

这个不等式是 LSVI-UCB 和所有线性 bandit/RL 证明的基石，值得深入理解。

引理（Abbasi-Yadkori–Pál–Szepesvári 2011, Theorem 1）：设 $\{F_t\}$ 是 filtration，$\{\eta_t\}$ 是 $R$-sub-Gaussian martingale difference（$\eta_t \in F_t$, $\mathbb{E}[\eta_t|F_{t-1}]=0$, $\mathbb{E}[e^{\lambda\eta_t}|F_{t-1}]\le e^{\lambda^2 R^2/2}$），$\{x_t\}$ 是 $F_{t-1}$-measurable（$x_t$ 在看到 $\eta_t$ 之前确定）。定义 $$ S_t = \sum_{\tau=1}^t \eta_\tau x_\tau, \qquad V_t = V_0 + \sum_{\tau=1}^t x_\tau x_\tau^\top $$ 则以概率 $\ge 1-\delta$： $$ |S_t|_{V_t^{-1}}^2 \le 2R^2\log\frac{\det(V_t)^{1/2}\det(V_0)^{-1/2}}{\delta} $$

为什么"自正则化"？ 关键在于：$S_t = \sum \eta_\tau x_\tau$ 的"能量"由 $V_t = \sum x_\tau x_\tau^\top$ 自动归一化。数据越多（$V_t$ 越大），允许的"噪声累积"越大——但方向是对的（$V_t^{-1}$ 在数据丰富的方向上权重小）。

直觉：想象你在多个方向上收集数据。某些方向数据多（$V_t$ 在该方向的特征值大），估计精度高；某些方向数据少，精度低。$\|w - w^*\|_{V_t}$ 的意义是"用数据加权的误差"——数据多的方向误差小是正常的，不应该被过度惩罚。

在 LSVI-UCB 中的应用：令 $x_t = \phi(s_h^t, a_h^t)$，$\eta_t = r_h^t + V_{h+1}(s_{h+1}^t) - \phi_t^\top w_h^*$。则线性回归估计 $w_h^k$ 满足 $\|w_h^k - w_h^*\|_{\Lambda_h^k} \le \beta$。UCB bonus $\beta\sqrt{\phi^\top\Lambda^{-1}\phi}$ 正是这个 confidence ellipsoid 在方向 $\phi$ 上的宽度。

Elliptical Potential Lemma 的几何直觉 ⭐⭐⭐⭐¶

引理：$\sum_{k=1}^K \phi_k^\top\Lambda_k^{-1}\phi_k \le 2d\log(1 + K/(\lambda d))$

证明关键步骤： $$ \phi_k^\top\Lambda_k^{-1}\phi_k = \frac{\det\Lambda_{k+1}}{\det\Lambda_k} - 1 \le \log\frac{\det\Lambda_{k+1}}{\det\Lambda_k} $$ （由 $x \le \log(1+x)$ 对 $x\le 1$ 近似成立；严格版本用 $\log(1+x) \ge x - x^2/2$）

因此： $$ \sum_k \phi_k^\top\Lambda_k^{-1}\phi_k \le \sum_k \log\frac{\det\Lambda_{k+1}}{\det\Lambda_k} = \log\frac{\det\Lambda_{K+1}}{\det\Lambda_1} = \log\frac{\det(\lambda I + \sum_k\phi_k\phi_k^\top)}{\lambda^d} $$

由 AM-GM：$\det(\lambda I + \sum\phi_k\phi_k^\top) \le (\frac{\text{tr}(\lambda I + \sum\phi_k\phi_k^\top)}{d})^d = (\lambda + K/d)^d$

合并：$\sum_k \phi_k^\top\Lambda_k^{-1}\phi_k \le d\log(1 + K/(\lambda d))$

几何含义："椭球势"衡量的是"新数据点给椭球增加了多少体积"。在 $d$ 维空间中，$K$ 个点最多把椭球体积增加 $(1+K/d)^d$ 倍——这是维度 $d$ 的几何限制。因此 $\sum_k \|\phi_k\|_{\Lambda_k^{-1}}^2$（UCB bonus 的平方和）被 $O(d\log K)$ 控制。

超越线性：结构化函数逼近的统一理论 ⭐⭐⭐⭐¶

线性 MDP 是极强的假设。后续工作逐步放宽：

结构类	代表论文	样本复杂度	关键假设
Linear MDP	Jin et al. 2020	$\tilde O(\sqrt{d^3H^3T})$	$P,r$ 都是 $\phi$ 的线性
Linear mixture MDP	Ayoub et al. 2020	$\tilde O(\sqrt{d^2H^2T})$	$P = \sum_i\phi_i \cdot P_i$（转移的线性混合）
Linear Bellman Complete	Zanette-Brunskill 2020	$\tilde O(\text{poly}(d,H)\sqrt{T})$	$Q^*$ 在 $\mathcal{F}$ 中，$\mathcal{T}\mathcal{F}\subseteq\mathcal{F}$
Bilinear class	Du et al. 2021	$\tilde O(\text{poly}(d,H)\sqrt{T})$	涵盖上述所有
Decision-Estimation Coefficient (DEC)	Foster et al. 2021	minimax optimal	统一 supervised → bandits → RL

Decision-Estimation Coefficient（Foster–Kakade–Qian–Rakhlin, COLT 2021）是目前最通用的框架：它把 RL 的 minimax regret 表示为一个**estimation problem**（模型估计能力）和**decision problem**（值函数优化能力）之间的**平衡系数** $\text{dec}(\mathcal{M}, \Pi)$。当 dec 有限时，存在 $\sqrt{T}$-regret 算法；当 dec 无限时，问题 statistically intractable。

⚠️ 常见陷阱¶

💡 概念误区：认为"线性 MDP"等于"线性 Q 函数" - 新手想法："线性 MDP 就是假设 $Q^*(s,a) = \phi(s,a)^\top w$" - 实际上：线性 MDP 是对**转移核**的假设（$P(s'|s,a) = \phi^\top\mu(s')$），比"$Q^*$ 是线性的"更强。"$Q^*$ 线性"是 Bellman Complete 假设的一部分（更弱），但 LSVI-UCB 需要线性 MDP 才能保证 bonus 的正确性。

🧠 思维陷阱：用线性 MDP 理论指导 deep RL 实践 - 新手想法："线性 MDP 界是 $\sqrt{d^3T}$，所以用更宽的网络（更大 $d$）一定更慢" - 实际上：线性 MDP 理论与 deep RL 的关系是**精神指导**（如 OFU 原理），不是**定量预测**。深度网络的逼近能力、优化 landscape、overparameterization 效应使得实际行为与线性理论大相径庭。

练习¶

验证 Bellman 闭包：对线性 MDP 定义，证明 $[\mathcal{T}^* Q](s,a) = \phi(s,a)^\top w'$ 对某个 $w' \in \mathbb{R}^d$（给出 $w'$ 的显式表达式）。
elliptical potential lemma 证明：证明对 $\phi_1,\dots,\phi_K \in \mathbb{R}^d$（$\|\phi_k\| \le 1$），$\Lambda_K = \lambda I + \sum_k \phi_k\phi_k^\top$，有 $\sum_k \phi_k^\top\Lambda_k^{-1}\phi_k \le 2d\log(1+K/\lambda d)$。（提示：利用 $\phi_k^\top\Lambda_k^{-1}\phi_k = \log\det\Lambda_{k+1}/\det\Lambda_k$ 的关系）

§6.6.5 Offline RL 的悲观主义原理 ⭐⭐¶

动机：为什么 online RL 的方法在 offline 会灾难性失败？¶

回顾 §6.6.1–6.6.4 的核心假设：算法可以与环境交互。OFU 原理的正确性完全依赖于"乐观导致探索，探索带来新数据纠正乐观估计"的正反馈环。

Offline RL（又名 batch RL） 打破了这个环：

给定固定数据集 $\mathcal{D} = \{(s_i, a_i, r_i, s'_i)\}_{i=1}^N$，由某个未知的 behavior policy $\mu$ 收集
禁止与环境交互——不能产生新数据
目标：从 $\mathcal{D}$ 中学到一个尽可能好的策略 $\hat\pi$

核心病症：distribution shift 与 extrapolation error

学到的策略 $\hat\pi$ 访问的状态-动作分布 $d^{\hat\pi}$ 可能与 $d^\mu$ 不重合。当 $(s,a) \notin \text{supp}(\mathcal{D})$ 时，Q 网络 $Q_\theta(s,a)$ 的输出就是**纯外推**——它从未在训练数据中见过这种输入，输出完全不可靠。

更致命的是：Bellman backup 中的 $\max_a Q(s', a)$ 会**选择 Q 值最高的动作**——如果外推的 Q 值虚高（随机初始化的网络在 OOD 区域输出不可控），$\max$ 操作就会**选择性地放大外推误差**。这种误差通过 bootstrap 在多步 backup 中被**几何级放大**。

实证灾难：把标准 SAC 跑在 D4RL 的 halfcheetah-medium 上（offline 数据来自中等水平 policy），Q 值在几千步内爆到 $10^6$ 量级（Kumar 等 2019 "BEAR"），策略完全崩溃。

跨领域类比：offline RL 的 distribution shift 问题就像**从一个城市的交通数据预测另一个城市的交通**——如果两个城市的道路结构不同，任何基于数据的模型都会在"从未见过的路口"上给出荒谬预测。online RL 相当于"可以去新城市实地考察"，offline RL 则"只能看现有数据"。

悲观主义 = 离线世界的乐观主义 ⭐⭐¶

这是本节最重要的概念对偶：

范式	数据来源	对不确定性的态度	目的	数学实现
Online RL（§6.6.1–6.6.4）	自采	乐观（OFU）	鼓励探索未知区域	$Q + \beta\sqrt{\phi^\top\Lambda^{-1}\phi}$
Offline RL（§6.6.5–6.6.6）	固定	悲观（PFU）	避免在未知区域外推	$Q - \beta\sqrt{\phi^\top\Lambda^{-1}\phi}$

本质洞察：乐观主义和悲观主义不是"心理倾向"，而是**统计决策原则的最优选择**——在可以获取新信息时选乐观（鼓励信息获取），在不能获取新信息时选悲观（避免信息不足导致的误判）。它们是同一个 OFU 原理在不同**信息约束**下的两个面。

直觉：在 online 中"不确定 ⇒ 加 bonus ⇒ 多去"，在 offline 中"不确定 ⇒ 减 penalty ⇒ 少去"——是同一枚硬币的两面。这一对称性由 Jin–Yang–Wang（ICML 2021 "Is Pessimism Provably Efficient for Offline RL?"）和 Rashidinejad 等（NeurIPS 2021）独立指出并形式化。

反事实推理：如果在 offline 中仍然使用乐观原则会怎样？OFU 会给 OOD 动作高 Q 值，策略会选择这些动作——但数据中没有对应的 reward 信号来纠正。结果：Q 值越来越高，策略越来越偏向 OOD 动作，直到数值溢出。这就是"offline RL + OFU = 灾难"的根本原因。

Concentrability Coefficient：覆盖率的形式化 ⭐⭐¶

要在 offline 数据上学出最优策略，最少需要什么？答案由**覆盖率系数（concentrability coefficient）**给出。

All-policy concentrability（Munos 2007，早期 approximate DP）： $$ C_{\text{all}} = \max_{\pi}\sup_{s,a}\frac{d^\pi(s,a)}{d^\mu(s,a)} $$ 要求数据覆盖**所有可能策略**访问的状态-动作——极强，现实中几乎不可能（behavior 只走了一条路，但你需要对所有路都有数据）。

Single-policy concentrability（Rashidinejad 等 2021）： $$ C^* = \sup_{s,a}\frac{d^{\pi^}(s,a)}{d^\mu(s,a)} $$ 只要求数据覆盖**最优策略* $\pi^*$ 的轨迹——大幅放宽。

$C^*$ 的直觉理解： - $C^* = 1$：behavior policy 就是**最优策略（expert dataset） - $C^* \approx SA$：behavior 是 uniform random（覆盖一切但很稀疏） - $C^* = \infty$：behavior 的支撑不包含 $\pi^*$ 的某些 $(s,a)$ → **不可能学到 $\pi^*$

跨领域类比：$C^*$ 之于 offline RL，就像 importance sampling ratio 之于蒙特卡洛估计——它衡量"目标分布"（$\pi^*$）与"采样分布"（$\mu$）的偏离程度。偏离越大，需要的样本越多。

PEVI：Pessimistic Value Iteration ⭐⭐⭐¶

Jin–Yang–Wang, ICML 2021 "Is Pessimism Provably Efficient for Offline RL?" 在线性 MDP 设定下给出了第一个 minimax optimal offline RL 算法。

算法：与 LSVI-UCB 完全相同，唯一区别是 bonus 的符号： $$ Q_h(s,a) = \phi(s,a)^\top w_h - \beta\sqrt{\phi(s,a)^\top(\Lambda_h)^{-1}\phi(s,a)} $$ 注意：减号（LCB，Lower Confidence Bound）替代了加号（UCB）。

定理（Jin–Yang–Wang 2021）：PEVI 的 suboptimality gap 满足 $$ V^*(s_1) - V^{\hat\pi}(s_1) \le \tilde O!\left(dH \cdot \sqrt{\frac{1}{N}}\right) $$ 在线性 MDP 下达到 minimax 最优（matching lower bound）。

Rashidinejad 等 2021 的 tabular 结果 ⭐⭐⭐¶

定理（Rashidinejad–Zhu–Ma–Jiao–Russell, NeurIPS 2021）：在有限时域 tabular MDP 下，LCB pessimistic value iteration 满足 $$ V^{\pi^}(s_1) - V^{\hat\pi}(s_1) \le \tilde O!\left(H\sqrt{\frac{|\mathcal{S}|C^}{N}}\right) $$ 并**达到 minimax 下界 $\Omega(\sqrt{|\mathcal{S}|C^*/N})$**。

这个定理的三个重要推论：

当 $C^* \to 1$（expert data）：收敛率变成 $\tilde O(\sqrt{S/N})$——比一般 $\sqrt{S^2A/N}$ 快，与 imitation learning 同阶。
当 $C^* \sim SA$（uniform data）：回到 $\tilde O(\sqrt{S^2A/N})$，与 online RL 的 $1/\sqrt{N}$ 同阶。
LCB/pessimism 完全不需要知道 $C^*$：自适应地达到最优率——这就是 "A Tale of Pessimism" 的核心贡献。

工程含义：如果你有一份"接近专家"的示教数据（例如遥操采集的 manipulation 轨迹），offline RL 可以**接近 imitation learning** 的效率；如果只有"乱跑"的 medium-replay 数据，效率退化——这解释了 D4RL 中 medium-expert 数据集上的分数明显高于 medium-replay。

四大主流 offline RL 算法 ⭐⭐¶

BCQ — Batch-Constrained Deep Q-learning¶

Fujimoto–Meger–Precup, ICML 2019（arXiv 1812.02900）。

数学动机：如果 $\hat\pi$ 的支撑被约束在 $\mathcal{D}$ 的支撑内，extrapolation 就不会发生。

做法： 1. 用 VAE（$G_\omega$）拟合 behavior policy $\mu(\cdot\mid s)$ 2. Actor 只在 VAE 采样的动作附近做小扰动：$a = a_{\text{VAE}} + \Phi_\xi(s, a_{\text{VAE}})$（$\Phi$ 是 perturbation network） 3. Q-network 用 clipped double Q（与 TD3 类似）

理论直觉：BCQ 是"不是 X 而是 Y"——不是学一个自由的 policy，而是学**在 behavior distribution 内的最优 policy**。缺点：如果 behavior 很差（远离最优），BCQ 的提升上限有限。

CQL — Conservative Q-Learning¶

Kumar–Zhou–Tucker–Levine, NeurIPS 2020（arXiv 2006.04779）。

数学动机：直接把 "OOD 高估" 压下去。在 Bellman backup 上加正则： $$ \mathcal{L}{\text{CQL}}(Q) = \underbrace{\alpha\bigl(\mathbb{E}},a\sim\rho}[Q(s,a)] - \mathbb{E{s,a\sim\mathcal{D}}[Q(s,a)]\bigr)}(Q) $$}} + \mathcal{L}_{\text{TD}

其中 $\rho$ 是"OOD 采样分布"（通常取当前策略 $\pi$ 或 uniform）。第一项的效果： - 对 $\mathcal{D}$ 中的动作：第二个期望抬高 Q - 对 $\rho$（通常包含 OOD 动作）中的动作：第一个期望压低 Q

CQL 的 Q 下界保证（Kumar 等 2020, Theorem 3.1–3.2）：存在 $\alpha$ 使得对任何 $s\in\mathcal{D}$、任何 $\pi$： $$ \hat Q^\pi(s,a) \le Q^\pi(s,a), \qquad \mathbb{E}_{a\sim\pi}[\hat Q^\pi(s,a)] \le V^\pi(s) $$ 即 CQL 学到的 Q 是真实 Q 的**可证下界**。Policy improvement 在下界上做，保证不会错误地"爱上" OOD 动作。

IQL — Implicit Q-Learning¶

Kostrikov–Nair–Levine, ICLR 2022（arXiv 2110.06169）。

数学动机：彻底**不 query OOD 动作**。用 expectile regression 拟合 $V(s) = \mathbb{E}^{\text{expectile}}_{a\sim\mu}[Q(s,a)]$： $$ L_V(\psi) = \mathbb{E}{(s,a)\sim\mathcal{D}}\bigl[L_2^\tau(Q(u<0)|\cdot u^2 $$ }(s,a) - V_\psi(s))\bigr], \quad L_2^\tau(u) = |\tau - \mathbb{1$\tau\in(0.5,1)$ 越大越"乐观"（越接近 $\max$）。当 $\tau\to 1$ 时 $V(s)\to\max_{a\in\text{supp}(\mu)} Q(s,a)$。

关键创新：Q-network 用 SARSA-style 更新 $Q(s,a) \leftarrow r + \gamma V(s')$——不需要 $\max$ over actions，因此完全避免了 OOD 查询。策略抽取通过 AWR（advantage-weighted regression）：$\pi(a|s) \propto \exp(\beta(Q(s,a) - V(s)))$。

优点：在 D4RL AntMaze（需要 trajectory stitching）上显著强于 CQL，调参更稳。

TD3+BC — 极简 offline¶

Fujimoto–Gu, NeurIPS 2021（arXiv 2106.06860）。

TD3 actor loss 加一项 behavior cloning 正则： $$ \mathcal{L}{\text{actor}} = -\lambda\mathbb{E}[|\pi(s) - a|^2] $$ }}[Q(s, \pi(s))] + (1-\lambda)\mathbb{E}_{(s,a)\sim\mathcal{D}单一超参。在 D4RL 上与 CQL 几乎打平但训练快 3–5 倍。

统一视角¶

Levine–Kumar–Tucker–Fu 2020 tutorial（arXiv 2005.01643，120 页必读）把所有 offline RL 方法归纳为三大类：

类别	代表	核心思想
Policy constraint	BCQ, TD3+BC, AWAC	约束 $\pi$ 靠近 $\mu$
Value regularization	CQL, Fisher-BRC	压低 OOD 的 Q 值
Uncertainty-aware	MOPO, MOReL, COMBO	用模型估计不确定性

⚠️ 常见陷阱¶

💡 概念误区："把 SAC 直接跑 offline 就是 offline RL" - 会因 OOD 高估立即崩溃。必须用 BCQ/CQL/IQL/TD3+BC 中的至少一种 mechanism。

💡 概念误区："CQL 学到的 Q 就是真 Q" - 不是。CQL 的 Q 是**下界**——可能严重低于真 Q。这就是 Cal-QL 要解决的"过度悲观"问题。

🧠 思维陷阱："offline RL = imitation learning" - 仅当 $C^* = 1$ 时样本复杂度一致。一般情况下 offline RL 可以"超过" behavior policy（trajectory stitching），这是纯 BC 做不到的。IQL 在 AntMaze 上的表现正是这一优势的体现。

💡 概念误区："IQL 的 expectile 就是 quantile" - Expectile 用不对称 $L_2$ loss，quantile 用不对称 $L_1$ loss。关键区别：expectile 保留高阶矩信息，对 reward 分布的尾部更敏感。

练习¶

CQL 下界推导：写出 $\mathcal{L}_{\text{CQL}}$ 关于 $Q$ 的一阶最优性条件（固定 $\pi$），推导在最优 $Q^*$ 处满足 $\hat Q \le Q^{\pi}$。
$C^*$ 估计：考虑一个 4 状态 2 动作的 gridworld，behavior 是 uniform random。最优策略只走"右"。计算 $C^*$ 并验证 Rashidinejad 定理的 bound。
在 CORL 中复现 CQL：在 D4RL halfcheetah-medium 上跑 CORL 的 cql.py，记录 Q 值曲线（应稳定不爆）。对比直接跑 SAC 的 Q 值曲线（应爆）。解释差异。

§6.6.6 Offline RL 的理论框架与样本复杂度 ⭐⭐⭐¶

从 BCQ/CQL/IQL 到统一理论¶

§6.6.5 介绍了四种实用算法。但它们背后的**统一理论**是什么？为什么 pessimism "just works"？本节给出形式化回答。

Pessimistic VI 的完整分析 ⭐⭐⭐⭐¶

设定：tabular episodic MDP，horizon $H$，数据 $\mathcal{D}$ 包含 $N$ 条轨迹（由 $\mu$ 收集）。设 $N_h(s,a) = \sum_i \mathbb{1}[(s_h^i, a_h^i) = (s,a)]$。

Pessimistic VI 算法：

Backward from $h = H$ to $h = 1$： $$ \hat Q_h(s,a) = \hat r_h(s,a) + \hat P_h(\cdot|s,a)^\top \hat V_{h+1} - b_h(s,a) $$ $$ \hat V_h(s) = \max_a \hat Q_h(s,a), \qquad \hat\pi_h(s) = \arg\max_a \hat Q_h(s,a) $$ 其中 $b_h(s,a) = c\sqrt{\frac{H^2\log(SAH/\delta)}{N_h(s,a)}}$（penalty）。

定理（完整版本，Rashidinejad et al. 2021 + Xie-Jiang 2021 合并）：

以概率 $\ge 1-\delta$： $$ V_1^(s_1) - V_1^{\hat\pi}(s_1) \le \tilde O!\left(H \cdot \sqrt{\frac{SC^}{N}} + H^2\sqrt{\frac{S}{N}}\right) $$

证明关键步骤（非完整，展示核心推理链）：

Step 1（悲观性保证）：由 penalty 的设计和 Hoeffding 不等式，以概率 $\ge 1-\delta$： $$ \hat V_h(s) \le V_h^(s) \quad \forall s, h $$ 即学到的 value function 是 $V^*$ 的**下界*。

Step 2（Performance Difference Lemma）： $$ V_1^(s_1) - V_1^{\hat\pi}(s_1) = \sum_{h=1}^H \mathbb{E}_{s_h\sim d_h^{\pi^}}\bigl[\bigl(r_h + P_h \hat V_{h+1}\bigr)(s_h,\pi^*) - \hat V_h(s_h)\bigr] $$ （注意：外层期望在 $d^{\pi^*}$ 下——这是 simulation lemma / performance difference lemma 的标准形式：gap 是在**比较策略**的占用测度下对 Bellman 残差求和。初学者常误写为 $d^{\hat\pi}$，但 PDL 的推导展开 telescoping 后自然出现 $\pi^*$ 的 roll-out 分布。）

Step 3（bonus 的作用）： $$ \bigl(r_h + P_h \hat V_{h+1}\bigr)(s_h,\pi^(s_h)) - \hat V_h(s_h) \le 2b_h(s_h, \pi^(s_h)) $$ 这来自悲观性 $\hat V_h \le V_h^*$ 加上 bonus 的置信区间保证：$|(\hat P_h - P_h)(\hat V_{h+1})| \le b_h$ w.h.p.。

递归展开到最后一层，得到：$V_1^* - V_1^{\hat\pi} \le 2\sum_{h=1}^H \mathbb{E}_{s_h\sim d_h^{\pi^*}}[b_h(s_h, \pi^*(s_h))]$。

Step 4（引入 concentrability $C^*$，将 $d^{\pi^*}$ 转换为数据分布）：

由于我们只有数据分布 $d^\mu$ 下的样本，需要做分布转换： $$ \mathbb{E}{s_h\sim d_h^{\pi^}}[b_h(s_h, \pi^(s_h))] = \mathbb{E}!\left[\frac{d_h^{\pi^}}(s_h,\pi^(s_h))}{d_h^{\mu}(s_h,\pi^(s_h))}\,b_h(s_h, \pi^(s_h))\right] \le \sqrt{C^*}\cdot\sqrt{\mathbb{E}_{d^\mu}[b_h^2]} $$ 这一步用了 $\sup_{s,a,h}\frac{d_h^{\pi^*}(s,a)}{d_h^\mu(s,a)} \le C^*$ 的 concentrability 定义和 Cauchy-Schwarz。结合 $\mathbb{E}_{d^\mu}[b_h^2]\le H^2 S\log(\cdot)/N$（由 Hoeffding 界），得到 $O(\sqrt{C^* H^3 S\log(\cdot)/N})$。

与 online 的完美对称：

Online UCBVI	Offline Pessimistic VI
$Q_h = \hat Q_h + b_h$（加 bonus）	$Q_h = \hat Q_h - b_h$（减 penalty）
$\hat V_h(s) \ge V_h^*(s)$（乐观性）	$\hat V_h(s) \le V_h^*(s)$（悲观性）
Regret = $\sum_k [\hat V_1^k - V_1^{\pi_k}]$（乐观值 - 实际值）	Gap = $V_1^* - \hat V_1$（最优值 - 悲观值）
依赖 $T$（exploration 积累）	依赖 $N, C^*$（数据质量）

机器人工程含义 ⭐⭐¶

推论：如果你有一份"接近专家"的示教数据（例如遥操采集的 manipulation 轨迹），offline RL 的样本效率可以**接近 imitation learning**（$1/N$ 而非 $1/\sqrt{N}$）；如果你只有"乱跑"的 medium-replay 数据，offline RL 的效率退化成 online 同阶——这解释了为什么 D4RL 中 medium-expert 数据集上的 CQL/IQL 分数明显高于 medium-replay。

实践指导： - 数据采集时：尽量让 behavior policy 接近你想学的目标（即降低 $C^*$） - 如果只有随机数据：考虑用 model-based offline RL（MOPO/COMBO），利用模型补偿覆盖不足 - 数据质量评估：估计 $C^*$ 的代理指标——计算 dataset 中 reward 的 top 10% 轨迹的 coverage - 混合数据策略：如果有少量 expert + 大量 random，IQL 的 expectile regression 天然适配——它从 random 数据中学 transition，从 expert 数据中学"哪些是好动作"

Trajectory Stitching：Offline RL 超越 BC 的本质 ⭐⭐⭐¶

Offline RL 与 Behavior Cloning 的根本区别在于 trajectory stitching——从多条次优轨迹中"拼接"出一条更优的路径。

直觉例子（AntMaze 的 U-maze）：假设 behavior 数据中有 100 条轨迹，每条都只走了迷宫的一部分（有的到了中间，有的从中间到了终点，但没有一条从头走到尾）。BC 只能复制某条轨迹的行为——但没有一条是完整的最优路径。Offline RL（如 IQL）可以把"到中间"的部分和"从中间到终点"的部分**拼接**起来——得到一条从头到尾的路径。

数学解释：Dynamic Programming 的 Bellman backup $Q(s,a) = r + \gamma V(s')$ 天然具有 stitching 能力——它不需要"连续的完整轨迹"，只需要"每个 $(s,a,s')$ 转移都被覆盖"。这就是为什么 IQL 在 AntMaze 上远强于 BC：BC 被限制在单条轨迹内，IQL 通过 Bellman backup 跨轨迹传播价值。

$C^*$ 与 stitching 的关系：当 $C^*$ 适中（不太大不太小），behavior 覆盖了最优策略的**每个局部转移**（但可能不覆盖完整轨迹），offline RL 可以有效 stitch。当 $C^* = \infty$（某些关键转移完全不在数据中），stitching 也无能为力。

反事实推理：如果 offline RL 不能 stitch 会怎样？那它就退化成 BC——只能模仿 behavior 中最好的单条轨迹，无法超越 behavior policy。这正是 BCQ 在 AntMaze 上表现差的原因：它把 policy 约束在 behavior 支撑内太紧，抑制了 stitching。IQL 通过 expectile regression + AWR 保留了 stitching 能力（同时避免 OOD 查询）。

数据量 vs 数据质量的 Trade-off ⭐⭐⭐¶

理论告诉我们 $\text{gap} \le O(\sqrt{SC^*/N})$。这意味着： - 增加 $N$（更多数据）：gap 以 $1/\sqrt{N}$ 下降 - 减少 $C^*$（更好数据）：gap 以 $\sqrt{C^*}$ 下降

两者是**乘积关系**，同样重要。具体决策： - 如果获取更多数据便宜（如仿真采集），优先增大 $N$ - 如果数据采集昂贵（如真机遥操），优先改善 behavior quality（降低 $C^*$） - 最优策略：用一个"接近目标任务但不完美"的 policy 采集（如 MPC、前版 policy），既有足够 coverage 又不太远离最优

练习¶

Stitching 实验：在一个简单的 gridworld 中，设计两种 offline 数据集：(a) 单条 expert 轨迹重复 100 次（$C^*$ 小但无 stitching 需求），(b) 100 条随机轨迹（$C^*$ 大但全覆盖）。分别跑 BC 和 IQL，观察 (b) 上 IQL 的 stitching 效果。
$C^*$ 的实证估计：对 D4RL halfcheetah-medium 数据集，用 density ratio estimation（如 DICE）近似估计 $d^{\pi^*}/d^\mu$ 的最大值，获得 $C^*$ 的 proxy。

§6.6.A Distributional RL 的数学 ⭐⭐⭐¶

动机：为什么只关心期望是不够的？¶

标准 RL 学习 $Q^\pi(s,a) = \mathbb{E}[G_t | s_t=s, a_t=a]$——回报的**期望**。但在机器人部署中：

一个策略的**平均 reward 高**但**偶尔摔倒**（高方差）
另一个策略**平均略低**但**从不摔倒**（低方差）

工程师几乎总是选后者。这需要对回报的**整个分布**建模，而非仅仅期望。

反事实推理：如果只用期望 Q 值做决策会怎样？考虑两个动作：$a_1$ 给 reward 100（概率 0.5）或 -100（概率 0.5），$a_2$ 总是给 reward 1。期望都是 0 和 1，但 $a_1$ 有 50% 概率导致机器人损坏。期望最优选 $a_2$（正确），但如果 $Q$ 估计有误差 $\pm 2$，可能错选 $a_1$——因为期望无法编码"$a_1$ 很危险"这个信息。

从 $Q^\pi$ 到 $Z^\pi$ ⭐⭐⭐¶

Bellemare–Dabney–Munos, ICML 2017（arXiv 1707.06887，C51） 把"回报的期望" $Q^\pi(s,a) = \mathbb{E}[G_t]$ 替换为"回报分布" $Z^\pi(s,a)$ 这个随机变量。

分布 Bellman 方程： $$ Z^\pi(s,a) \stackrel{D}{=} R(s,a) + \gamma Z^\pi(S', A'), \qquad S'\sim P(\cdot|s,a), A'\sim\pi(\cdot|S') $$

注意 "$\stackrel{D}{=}$" 表示**分布相等**，不是数值相等。等式两边是随机变量，不是数字。

与标准 Bellman 的关系：对 $\stackrel{D}{=}$ 两边取期望恢复标准 Bellman 方程 $Q^\pi(s,a) = r + \gamma\mathbb{E}[Q^\pi(S',A')]$。Distributional RL 是标准 RL 的**信息增强版本**。

Wasserstein 压缩性完整证明 ⭐⭐⭐⭐¶

定理（Bellemare–Dabney–Munos 2017, Lemma 3）：定义 $p$-Wasserstein 的 supremum 版本 $$ \bar d_p(Z_1, Z_2) = \sup_{s,a} W_p(Z_1(s,a), Z_2(s,a)) $$ 则分布 Bellman 算子 $\mathcal{T}^\pi$ 满足 $$ \bar d_p(\mathcal{T}^\pi Z_1, \mathcal{T}^\pi Z_2) \le \gamma \bar d_p(Z_1, Z_2) $$

完整证明：

Step 1（$W_p$ 对仿射变换的性质）。对常数 $c$ 和标量 $a > 0$： $$ W_p(aX + c, aY + c) = a \cdot W_p(X, Y) $$ 这来自 $W_p$ 的 coupling 定义：最优 coupling $(X, Y) \mapsto (aX+c, aY+c)$ 保持最优性。

Step 2（$W_p$ 对混合分布的凸性）。设 $Z_i = \sum_j p_j X_{ij}$（条件混合），则 $$ W_p(Z_1, Z_2) \le \sum_j p_j W_p(X_{1j}, X_{2j}) $$ （由 $W_p$ 的 inf over couplings 和 convexity）。

Step 3（合并）。 $$ \mathcal{T}^\pi Z(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) \sum_{a'}\pi(a'|s') Z(s',a') $$ 因此 $$ W_p(\mathcal{T}^\pi Z_1(s,a), \mathcal{T}^\pi Z_2(s,a)) $$ $$ = W_p!\left(R + \gamma\sum_{s',a'} P\pi \cdot Z_1(s',a'), R + \gamma\sum_{s',a'} P\pi \cdot Z_2(s',a')\right) $$ 由 Step 1（加 $R$ 是平移，乘 $\gamma$ 是缩放）： $$ = \gamma \cdot W_p!\left(\sum_{s',a'} P\pi \cdot Z_1(s',a'), \sum_{s',a'} P\pi \cdot Z_2(s',a')\right) $$ 由 Step 2（对 $(s',a')$ 的混合）： $$ \le \gamma \sum_{s',a'} P(s'|s,a)\pi(a'|s') \cdot W_p(Z_1(s',a'), Z_2(s',a')) $$ $$ \le \gamma \sup_{s',a'} W_p(Z_1(s',a'), Z_2(s',a')) = \gamma \bar d_p(Z_1, Z_2) $$

取 $\sup_{s,a}$ 得 $\bar d_p(\mathcal{T}^\pi Z_1, \mathcal{T}^\pi Z_2) \le \gamma \bar d_p(Z_1, Z_2)$。$\square$

关键细节：为什么 greedy 版本 $\mathcal{T}^*$ 不是压缩？

$\mathcal{T}^* Z(s,a) = R + \gamma Z(S', \arg\max_{a'} \mathbb{E}[Z(S',a')])$

问题在于 $\arg\max$ 操作：对 $Z_1$ 和 $Z_2$，$\arg\max$ 可能选择不同的动作。这破坏了 Step 2 中"对同一个 $(s',a')$ 做混合"的结构。因此在 control 情形（policy improvement）下，Wasserstein 压缩性不成立——需要额外分析（Bellemare–Dabney–Rowland 专著 Ch. 7）。

C51 / QR-DQN / IQN 的进化路径 ⭐⭐⭐¶

算法	年份	分布表示	损失函数	理论距离
C51	2017	51 个固定原子	KL divergence（投影后）	Cramér distance 近似
QR-DQN	2018	$N$ 个自适应分位数	quantile regression loss	精确 $W_1$
IQN	2018	隐式分位数函数 $F^{-1}(\tau)$	quantile regression + 随机 $\tau$	$W_1$（无限精度极限）
FQF	2019	自适应分位点分布	联合优化分位点位置	$W_1$

C51 的投影步骤：Bellman target $\mathcal{T}^\pi Z$ 可能落在固定原子 $\{z_1,\dots,z_{51}\}$ 之间。需要一个"投影"把它映射回原子集合。C51 用 $L_2$ 投影——这在理论上优化的是 Cramér distance 而非 $W_p$，但实践中表现极好。

QR-DQN（Dabney–Rowland–Bellemare–Munos, AAAI 2018） 的核心创新：直接表示**分位数函数**（CDF 的逆）。对 $N$ 个均匀分位点 $\tau_i = (2i-1)/2N$（$i=1,\dots,N$），学习 $\theta_i(s,a)$ 使得 $F_{Z(s,a)}^{-1}(\tau_i) \approx \theta_i$。

分位数回归损失： $$ \mathcal{L}{\text{QR}} = \sum}^N \mathbb{E{j}\bigl[\rho(u < 0)) $$ }(\theta_j^{\text{target}} - \theta_i)\bigr], \quad \rho_\tau(u) = u(\tau - \mathbb{1数学上精确最小化 $W_1$ 距离。

风险敏感控制应用 ⭐⭐⭐¶

有了回报分布 $Z(s,a)$，可以定义各种**风险度量**作为策略目标：

CVaR（Conditional Value at Risk）：$\text{CVaR}_\alpha(Z) = \mathbb{E}[Z | Z \le F_Z^{-1}(\alpha)]$——只关注最差 $\alpha$ 比例的情况
Wang distortion：$\rho_g(Z) = \int_0^1 F_Z^{-1}(\tau) g'(\tau) d\tau$（$g$ 是凸失真函数）
Coherent risk measures：满足单调性、平移不变性、正齐次性、次可加性的风险函数

在机器人中：CVaR 策略在"风吹草动"的不确定环境中比期望策略鲁棒。D4PG、DSAC（Duan 等 2021）、QR-SAC 在轮式机器人和无人机上，因 CVaR 对扰动的鲁棒性而被部署。

⚠️ 常见陷阱¶

💡 概念误区："Distributional RL 只是加了个分布，没什么实际用处" - 实际上：(1) Atari 上 C51/QR-DQN/IQN 一致强于 DQN；(2) 分布提供了**辅助信号**——网络需要预测更多信息，训练的 representation 更丰富；(3) 在安全要求高的场景（机器人、自动驾驶），CVaR 策略是**刚需**。

练习¶

手推 $W_1$ 压缩：对两个 Bernoulli 分布 $X\sim\text{Bern}(p)$, $Y\sim\text{Bern}(q)$，计算 $W_1(X,Y)$ 并验证 $W_1(\gamma X, \gamma Y) = \gamma W_1(X, Y)$。
QR-DQN 分位数回归：对 $N=5$ 个分位数，写出 QR loss 的显式表达式并用 PyTorch 实现梯度下降。验证收敛后的 $\theta_i$ 是否逼近目标分布的对应分位数。

§6.6.B Safe RL 与 CMDP ⭐⭐⭐¶

动机：为什么纯 reward maximization 在机器人上不够？¶

在真实机器人上训练 RL，你面对一个 reward shaping 无法解决的问题：

reward 可以告诉机器人"走得快好"，但**不能硬性禁止"摔倒"**
penalty（如 $r_{\text{fall}} = -1000$）只是"软约束"——算法会计算"快速走带来的 reward 是否能 cover 摔倒的 penalty"
但在工程上，摔倒一次 = 关节损坏，不是"扣分"那么简单

CMDP（Constrained MDP） 提供了**硬约束**的正确数学框架。

CMDP 形式化 ⭐⭐¶

定义（Altman 1999，《Constrained Markov Decision Processes》，CRC Press）：CMDP 在 MDP 基础上加 $m$ 个**成本函数** $C_i : \mathcal{S}\times\mathcal{A}\to[0,C_{\max}]$ 与阈值 $d_i$： $$ \max_\pi \mathbb{E}^\pi\Bigl[\sum_t \gamma^t R_t\Bigr] \quad\text{s.t.}\quad \mathbb{E}^\pi\Bigl[\sum_t \gamma^t C_{i,t}\Bigr] \le d_i, i=1,\dots,m $$

Altman 1999 最优策略存在性定理：CMDP 的最优策略总是**stochastic**，且至多以 $m+1$ 个 deterministic policy 的凸组合实现。

证明思想（LP 对偶）：CMDP 可以重写为对 occupancy measure $\rho(s,a) = (1-\gamma)\sum_t \gamma^t \Pr(s_t=s,a_t=a)$ 的线性规划： $$ \max_\rho \sum_{s,a} r(s,a)\rho(s,a) \quad\text{s.t.}\quad \sum_{s,a}c_i(s,a)\rho(s,a)\le d_i,\quad \rho\in\Delta_{\text{feasible}} $$ LP 的最优解是顶点（deterministic policy）或面上的点（stochastic——$m$ 个约束对应 $m$ 个自由度的混合）。

三大求解范式 ⭐⭐⭐¶

Lagrangian 方法（原始-对偶）¶

把约束乘以乘子 $\lambda\ge 0$ 变成无约束： $$ \max_\theta\min_{\lambda\ge 0} L(\theta,\lambda) = \mathbb{E}^{\pi_\theta}\Bigl[\sum_t\gamma^t(R_t - \lambda^\top C_t)\Bigr] + \lambda^\top d $$

Primal-dual gradient ascent： - Primal（$\theta$）：$\theta \leftarrow \theta + \alpha_\theta \nabla_\theta L$（policy gradient on augmented reward $R - \lambda^\top C$） - Dual（$\lambda$）：$\lambda \leftarrow [\lambda + \alpha_\lambda(J_C(\pi_\theta) - d)]_+$（subgradient ascent on constraint violation）

收敛性（Tessler–Mankowitz–Mannor, ICLR 2019 "RCPO"）：在 convex-concave minimax 的条件下（occupancy measure 空间），primal-dual 以 $O(1/\sqrt{T})$ 收敛到鞍点——约束渐近满足。但：

$\lambda$ 震荡：在训练中期 $\lambda$ 可能大幅波动，导致策略在"太保守"和"太激进"之间反复跳跃
瞬时违反不可控：收敛保证是**渐近**的——中间可能有大量约束违反
真机部署：需要叠加 CBF 层做"兜底"

CPO — Constrained Policy Optimization ⭐⭐⭐¶

Achiam–Held–Tamar–Abbeel, ICML 2017（arXiv 1705.10528）。

核心创新：在 TRPO 的 trust region 内加约束的 surrogate。每次迭代求解： $$ \max_{\theta'} L_{\pi_\theta}(\pi_{\theta'}) \quad\text{s.t.}\quad \bar D_{\text{KL}}(\theta' | \theta) \le \delta_{\text{KL}},\quad J_{C_i}(\pi_{\theta'}) \le d_i $$

近似为 QP（用 Fisher information matrix 近似 KL Hessian）： $$ \max_{s} g^\top s \quad\text{s.t.}\quad s^\top H s \le 2\delta,\quad c + a^\top s \le 0 $$ 其中 $g$ 是 reward 梯度，$a$ 是约束梯度，$H$ 是 Fisher matrix，$c$ 是当前约束违反。

理论贡献：CPO 给出了每次迭代的 worst-case constraint violation 上界： $$ J_C(\pi_{\text{new}}) - J_C(\pi_{\text{old}}) \le \frac{\sqrt{2\delta_{\text{KL}}}\cdot\max_s |A_C^\pi(s)|}{1-\gamma} $$ 这意味着即使在训练过程中，约束违反也有**显式界**——比 Lagrangian 方法强得多。

FOCOPS / PCPO / P3O¶

方法	创新点	计算代价
CPO	二阶（Fisher matrix，conjugate gradient）	高
FOCOPS（Zhang 等 NeurIPS 2020）	一阶代替（KL 约束变 penalty）	低
PCPO	投影到可行集	中
P3O	penalty 方法	低

Lagrangian 方法的收敛性分析 ⭐⭐⭐⭐¶

Lagrangian primal-dual 方法在 CMDP 中的收敛性不是显而易见的——因为 Lagrangian $L(\theta, \lambda)$ 对 $\theta$ 不是凸的（policy 是非凸的）。但可以在 occupancy measure 空间中获得理论保证。

定理（Ding–Wei–Chen–Li 2020，"Natural Policy Gradient Primal-Dual for CMDPs"）：在 tabular CMDP 下，NPG-based primal-dual 算法以 $O(1/\sqrt{T})$ 速率收敛到 Nash equilibrium $(\theta^*, \lambda^*)$： $$ \text{Duality Gap}(T) = \max_\lambda L(\theta_T, \lambda) - \min_\theta L(\theta, \lambda_T) \le O(1/\sqrt{T}) $$

实际含义：这意味着 constraint violation 和 suboptimality 都以 $O(1/\sqrt{T})$ 衰减——但不是**单调**的。训练中间可能出现约束严重违反的 spike。

PID-Lagrangian 改进：Stooke–Achiam–Abbeel 2020 "Responsive Safety in RL via PID Lagrangian Methods" 用 PID 控制器替代简单梯度更新： $$ \lambda_{t+1} = [\lambda_t + K_p e_t + K_i \sum_\tau e_\tau + K_d (e_t - e_{t-1})]_+ $$ 其中 $e_t = J_C(\pi_t) - d$（constraint violation）。PID 消除了纯 I 控制器（标准 subgradient）的震荡问题。

CBF ↔ RL 的融合 ⭐⭐⭐¶

Control Barrier Functions (CBF)（Ames–Xu–Grizzle–Tabuada 2017）是控制理论中保证"安全集不变性"的标准工具。

形式化定义：对动态系统 $\dot x = f(x) + g(x)u$，安全集 $\mathcal{C} = \{x : h(x) \ge 0\}$。函数 $h:\mathbb{R}^n\to\mathbb{R}$ 是 CBF，如果存在 extended class-$\mathcal{K}$ 函数 $\alpha$ 使得： $$ \sup_u [L_f h(x) + L_g h(x) \cdot u + \alpha(h(x))] \ge 0, \quad \forall x \in \mathcal{C} $$ 其中 $L_f h = \frac{\partial h}{\partial x} f(x)$，$L_g h = \frac{\partial h}{\partial x} g(x)$ 是 Lie 导数。

CBF 条件的物理含义：$\dot h = L_f h + L_g h \cdot u$。CBF 条件要求：总存在一个控制输入 $u$ 使得 $\dot h + \alpha(h) \ge 0$。当 $h$ 接近 0（即状态接近安全边界）时，$\alpha(h)$ 很小，要求 $\dot h \ge -\alpha(h) \approx 0$——即**不允许 $h$ 变负**（不允许离开安全集）。

CBF-QP 层 把 RL 产出的动作投影到安全半空间： $$ a_{\text{safe}} = \arg\min_a|a - a_{\text{RL}}|^2 \quad\text{s.t.}\quad L_f h(x) + L_g h(x)\cdot a + \alpha(h(x)) \ge 0 $$

这是一个单步 QP——对于单个 CBF 约束甚至有解析解（半空间投影的闭式）： $$ a_{\text{safe}} = \begin{cases} a_{\text{RL}} & \text{if } L_f h + L_g h \cdot a_{\text{RL}} + \alpha(h) \ge 0 \ a_{\text{RL}} - \frac{(L_f h + L_g h \cdot a_{\text{RL}} + \alpha(h))}{|L_g h|^2} (L_g h)^\top & \text{otherwise} \end{cases} $$

符号推导：约束为 $L_g h \cdot a + L_f h + \alpha(h) \ge 0$，即 $g^\top a \ge -c$（其中 $g=(L_g h)^\top$，$c=L_f h+\alpha(h)$）。当 $a_{\text{RL}}$ 违反约束时 $g^\top a_{\text{RL}} + c < 0$（为负数），投影到半空间边界 $g^\top a + c = 0$ 的最近点为 $a_{\text{safe}} = a_{\text{RL}} - \frac{g^\top a_{\text{RL}} + c}{\|g\|^2} g$。注意分子为**负数**，所以实际修正方向为 $+\lambda g$（$\lambda>0$），即**沿 $L_g h$ 的正方向推动**——这正确地把动作推向使 $\dot h$ 增大（更安全）的方向。若误写为 $+$ 号，则修正方向为 $-g$，会使 $\dot h$ 更小，把动作推向**更不安全**的方向。

它与 RL 的关系是"嵌套"： - RL 产出"期望动作"（可能不安全） - CBF-QP 做最小修正（保证安全） - 修正后的动作被执行 - 反向传播时可以通过 QP 层做梯度（differentiable QP，如 OptNet/qpth）

CLF-CBF-QP 统一框架：Control Lyapunov Function（CLF）保证稳定性，CBF 保证安全性，合并为： $$ \min_u |u - u_{\text{ref}}|^2 \quad\text{s.t.}\quad \underbrace{L_f V + L_g V \cdot u + c_3 V \le \delta_{\text{relax}}}{\text{CLF: 稳定性（可松弛）}},\quad \underbrace{L_f h + L_g h \cdot u + \alpha(h) \ge 0} $$}

机器人应用： - 关节限幅：$h(q) = q_{\max} - |q_i|$，CBF 防止关节超出物理极限 - 接触力上界：$h(F) = F_{\max} - \|F_{\text{EE}}\|$ - 碰撞避免：$h(x) = \text{SDF}(x) - d_{\text{safe}}$，SDF 是到障碍物的签名距离 - 真机 safe exploration：ETH ANYmal、MIT Mini Cheetah 的 CBF + RL 组合

与 CMDP 的区别：CMDP 的约束是**期望**约束（长期平均满足），CBF 是**逐步**约束（每一步都满足）。真机部署通常需要两者结合：CMDP 管"平均不超标"，CBF 管"任何时刻不危险"。

⚠️ 常见陷阱¶

🧠 思维陷阱："CPO 一定满足约束" - CPO 的保证是"每次迭代的最坏约束违反有界"——不是"零违反"。中间仍会有小幅超出。真机部署需要 CBF 层兜底。

💡 概念误区："Lagrangian-PPO 收敛就没问题" - 收敛后约束满足——但**训练过程中** $\lambda$ 的震荡可能导致大量瞬时违反。在仿真中这没事，在真机上可能意味着硬件损坏。

练习¶

CMDP → LP：对一个 3 状态 2 动作的 MDP + 1 个约束，写出 occupancy measure LP 的显式形式，并用 scipy.optimize.linprog 求解。
CBF-QP 实现：对一个 2D 点机器人 + 圆形障碍物，定义 $h(x) = \|x - x_{\text{obs}}\| - r_{\text{safe}}$，实现 CBF-QP 投影。验证轨迹始终在障碍物外。

§6.6.C Reward-free Exploration ⭐⭐⭐⭐¶

动机与形式化¶

Jin–Krishnamurthy–Simchowitz–Yu, ICML 2020 "Reward-Free Exploration for RL"：先探索（不依赖任何 reward），后用**任意** reward 函数规划。

形式化： - 探索阶段（Phase 1）：与 MDP 交互 $N$ 步，不知道 reward（甚至不观测 reward） - 规划阶段（Phase 2）：给定任意 $r:\mathcal{S}\times\mathcal{A}\to[0,1]$，输出 $\hat\pi_r$ 使得 $V^{\pi^*_r} - V^{\hat\pi_r} \le \varepsilon$ 对**所有可能的 $r$** 成立

定理（Jin et al. 2020, Theorem 1）：tabular MDP 下需 $\tilde O(H^5S^2A/\varepsilon^2)$ 次交互——对 reward 一无所知的代价只差一个多项式因子（相比 reward-dependent 的 $\tilde O(H^2SA/\varepsilon^2)$）。

额外 $S$ 因子的直觉解释 ⭐⭐⭐¶

为什么 reward-free 比 reward-dependent 多一个 $S$ 因子？

Reward-dependent（如 UCBVI）：只需要精确估计**最优策略路径上**的转移概率。如果最优策略只访问 $S_{\text{eff}} \ll S$ 个状态，实际需要的样本可以更少。
Reward-free：必须精确估计**所有状态**的转移概率——因为规划阶段可能给出任何 reward，任何状态都可能成为最优路径的一部分。

形式化：reward-free 要求对 $\hat P$ 的估计在**所有** $(s,a)$ 上都 $\varepsilon$-精确。由 union bound 和 Hoeffding，每个 $(s,a)$ 需要 $\Omega(S/\varepsilon^2)$ 次访问。确保每个 $(s,a)$ 都被访问足够多次需要额外的 $S$ 因子。

探索算法设计：RF-UCRL ⭐⭐⭐⭐¶

Jin 等 2020 的探索算法（RF-UCRL）核心思想： 1. 维护对 $P$ 的估计 $\hat P$ 和对应的 confidence set $\mathcal{C}_P$ 2. 每轮选择最"不确定"的方向探索 3. 目标：以最少的样本让所有 $(s,a)$ 的 $\hat P$ 精度达标

关键洞察：探索策略的目标不是最大化 reward（没有 reward！），而是**最大化信息增益**——尽快缩小 $\hat P$ 的 confidence set。这与 Bayesian optimal experiment design 精神一致。

与 SLAM 的精神对应¶

SLAM 先"建图"（与目标无关），再"基于已知地图 + 给定目标做 planning"。Reward-free RL 提供了这一模式的 RL 版本，正好契合**多任务机器人**（一个机器人要做 100 种任务，不可能每个任务从头学探索）。

跨领域类比：reward-free exploration 之于任务学习，就像**基因组测序**之于疾病研究——先获取全面的基础数据（不针对特定疾病），后续任何疾病研究都可以复用这份数据。

后续发展与 Foundation Model 的连接 ⭐⭐⭐¶

Kaufmann–Menard–Jonsson–Leurent 2021：线性 MDP 下 reward-free，$\tilde O(d^2H^5/\varepsilon^2)$
Zhang–Chen–Lee–Du 2022：一般函数逼近下 reward-free 不可能——需要结构假设

与 Foundation Model 的连接：RT-2、Octo 等 embodied foundation model 的"预训练"阶段，本质上是 reward-free exploration 的大规模实现——在海量多样任务上预训练 representation，然后对任何 downstream task fast-adapt。

练习¶

解释为什么 reward-free exploration 的样本复杂度比 reward-dependent 多一个 $S$ 因子。
设计思考：如果有 10 种目标任务要同时学习，比较两种策略的总样本需求：(a) 对每种任务独立跑 UCBVI；(b) 用 reward-free 一次性探索再对每种任务做 planning。什么条件下 (b) 更高效？

§6.6.D Offline-to-Online Fine-tuning ⭐⭐⭐¶

动机¶

典型管线：仿真 offline 训练 → 真机 online fine-tune。核心难点：offline 训练的 conservative 策略在 online 微调初期会"忘了怎么探索"——CQL 学出的 Q 值**过于悲观**，online fine-tune 的前 $10^4$ 步全在"修正偏差"而非"改进策略"。

Cal-QL ⭐⭐⭐¶

Nakamoto–Zhai–Singh–…–Kumar–Levine, NeurIPS 2023。

关键观察：CQL 的 Q 下界可能远低于 $Q^{\mu}$（behavior policy 的 Q 值）——即比"什么都不学，直接跟 behavior"还悲观。这在 online fine-tune 时制造了巨大的"修正债务"。

解决方案：在 CQL loss 里加 calibration term——把 Q 下界"抬到" behavior policy 的 MC return 处： $$ \mathcal{L}{\text{Cal-QL}} = \mathcal{L} $$ 保证 }} + \text{calibration penalty on } \hat Q < Q^{\mu}_{\text{MC}$\hat Q \ge Q^{\mu}$（但仍 $\le Q^*$）——比 behavior 好一点点但不过分悲观。

效果：在 D4RL AntMaze + online fine-tune 上，Cal-QL 在前 5000 步就开始提升，而 CQL online fine-tune 需要 50000 步才"回本"。

其它路线 ⭐⭐⭐¶

方法	核心思想	优点	缺点
AWAC	advantage-weighted regression	天然支持 offline + online	对 advantage 估计敏感
IQL + online	逐步抬高 expectile $\tau$ 从 0.7 → 0.99	平滑过渡，不需额外代码	$\tau$ 调度 schedule 需手动设计
RLPD（Ball 等 2023）	从头在线学习，replay buffer 同时含 offline 数据	简单，无需预训练	早期性能差（没有 pretrain 的 warm start）
SPOT（Wu 等 2022）	支撑约束 + online exploration	保留 BCQ 的安全性 + 允许探索	需要额外训练 density model

Offline-to-Online 的理论视角 ⭐⭐⭐⭐¶

为什么 offline pretrain + online fine-tune 比纯 online 更高效？

理论回答：offline 预训练提供了一个**warm start**——一个不完美但比随机好得多的初始策略。在 online 阶段： - 纯 online（从 random policy 开始）：regret $\sim \sqrt{T}$，前 $T_0$ 步几乎完全在探索 - Offline warm start：如果 pretrained policy 已经 $\varepsilon_0$-optimal，online 阶段只需要从 $\varepsilon_0$ 精度继续改进

形式化（Song et al. 2023 "Hybrid RL"）：如果 offline pretrain 给出 $\hat\pi$ 满足 $V^* - V^{\hat\pi} \le \varepsilon_0$，则从 $\hat\pi$ 开始的 online fine-tune 的 regret 为： $$ \text{Regret}(T) \le \tilde O!\left(\sqrt{d H^3 T} + \varepsilon_0 T\right) $$ 当 $T$ 足够大时，第一项主导——即 online fine-tune 的渐近速率与从头训练一样，但**常数更好**（因为初始探索少了）。

Cal-QL 的关键 insight：$\varepsilon_0$ 应该是"比 behavior 好但比 optimal 差"——即 $V^{\mu} \le V^{\hat\pi} \le V^*$。标准 CQL 把 $V^{\hat\pi}$ 压到远低于 $V^{\mu}$，浪费了 offline pretrain 的优势。Cal-QL 保证 $V^{\hat\pi} \ge V^{\mu}$，因此 online 阶段的起点比 behavior policy 好——这就是"calibration"的含义。

⚠️ 常见陷阱¶

🧠 思维陷阱："Offline pretrain 越保守，online fine-tune 越安全" - 新手想法："CQL 的 $\alpha$ 越大越好——保守一点总没错" - 实际上：过度保守 = 过低的 Q 值 = online fine-tune 阶段的巨大"修正债务"。最优的 $\alpha$ 应使 $\hat Q \approx Q^{\mu}$（calibrated），不是越大越好。

练习¶

设计实验：在 D4RL antmaze-medium-play 上对比三种 offline-to-online 策略：(a) CQL pretrain → SAC fine-tune；(b) Cal-QL pretrain → SAC fine-tune；(c) 纯 SAC from scratch。画出三条 online reward 曲线。预测哪条最先上升？

§6.6.E 模仿学习理论 ⭐⭐¶

BC 的 Compounding Error 完整证明 ⭐⭐⭐¶

定理（Ross–Bagnell, AISTATS 2010）：对 behavior cloning $\hat\pi$ 满足 $\mathbb{E}_s[\text{TV}(\hat\pi(\cdot|s), \pi^*(\cdot|s))] \le \varepsilon$，则： $$ J(\pi^*) - J(\hat\pi) \le O(\varepsilon H^2) $$

完整证明：

Step 1：定义 $d_h^{\hat\pi}$ 为 $\hat\pi$ 在第 $h$ 步的状态分布，$d_h^*$ 为 $\pi^*$ 的。

Step 2：证明分布偏移： $$ \text{TV}(d_h^{\hat\pi}, d_h^*) \le h\varepsilon $$ 归纳法：$h=1$ 时两者相同（同一初始状态）；$h \to h+1$ 时，分布差来自两个源：(a) $h$ 步的状态分布已经偏离 $h\varepsilon$；(b) 当前步的动作偏离 $\varepsilon$。合起来 $\le (h+1)\varepsilon$。

Step 3：value 偏差分解： $$ J(\pi^) - J(\hat\pi) = \sum_{h=1}^H \mathbb{E}_{d_h^{\hat\pi}}[A^(s_h, \hat\pi(s_h))] $$ 由 $\text{TV}(d_h^{\hat\pi}, d_h^*) \le h\varepsilon$ 和 $A^* \le 1$（bounded reward）：每一步贡献 $\le O(h\varepsilon)$。求和： $$ \sum_{h=1}^H O(h\varepsilon) = O(\varepsilon H^2) $$

这就是**二次 compounding error**——$H=200$ 步、$\varepsilon=10\%$ 时，total error 可达 $200^2 \times 0.1 = 4000$（远超 reward range）。

DAgger 线性化 ⭐⭐⭐¶

DAgger（Ross–Gordon–Bagnell, AISTATS 2011） 通过在线标注把 $O(\varepsilon H^2)$ 降到 $O(\varepsilon H)$：

核心想法：在 $\hat\pi$ 的**实际访问分布 $d^{\hat\pi}$** 上收集专家标签，用这些数据更新 $\hat\pi$。

$$ \hat\pi_n = \arg\min_\pi \mathbb{E}_{s\sim D_n}[\ell(\pi(s), \pi^*(s))] $$ 其中 $D_n = \bigcup_{i=1}^n \{(s_h^i, \pi^*(s_h^i))\}$——状态来自 $\hat\pi_{n-1}$ 的 rollout，标签来自专家。

定理：DAgger 的 suboptimality 为 $O(\varepsilon H)$——线性而非二次。

直觉：BC 的二次 error 来自"在 $\pi^*$ 的分布上训练，在 $\hat\pi$ 的分布上测试"——分布偏移 $\le h\varepsilon$ 随 $h$ 增长。DAgger 消除了这个偏移（训练分布 = 测试分布 = $d^{\hat\pi}$），所以 error 不再累积。

GAIL 与 occupancy matching ⭐⭐⭐¶

Ho–Ermon, NeurIPS 2016 "Generative Adversarial Imitation Learning"：不恢复 reward（vs IRL），而是直接最小化 occupancy measure 距离： $$ \min_\pi D_{\text{JS}}\bigl(\rho^\pi, \rho^{\pi_E}\bigr) $$

用 GAN 判别器 $D_\omega$ 估计 $D_{\text{JS}}$： - Generator = policy $\pi_\theta$（产出轨迹） - Discriminator $D_\omega$ 区分 $\pi_\theta$ 的轨迹和 expert 轨迹 - Policy gradient 用 $-\log D_\omega(s,a)$ 作为 reward

在 locomotion style transfer 中（从人类动作捕捉学 humanoid gait，DeepMimic Peng 等 2018）是主流方法。

DAgger 的样本复杂度分析 ⭐⭐⭐⭐¶

定理（Ross–Gordon–Bagnell 2011, Theorem 2.1）：经过 $N$ 轮 DAgger 迭代，最终策略 $\hat\pi_N$ 满足： $$ J(\pi^*) - J(\hat\pi_N) \le \varepsilon H + O!\left(\frac{H\log N}{N}\right) $$ 其中 $\varepsilon$ 是分类器在训练分布上的期望错误率。

关键区别的数学根源：

BC 的 $O(\varepsilon H^2)$ 来自两个因素的乘积： - 因素 1：每步 $\varepsilon$ 的动作误差 - 因素 2：分布偏移 $\text{TV}(d_h^{\hat\pi}, d_h^*) \le h\varepsilon$ 在 $h$ 上的累积

DAgger 消除了因素 2（训练在 $d^{\hat\pi}$ 上），只剩因素 1。因此 gap 从 $\sum_{h=1}^H h\varepsilon = O(\varepsilon H^2)$ 降到 $\sum_{h=1}^H \varepsilon = O(\varepsilon H)$。

数值对比（$H=200, \varepsilon=0.05$）： - BC：$\varepsilon H^2 = 0.05 \times 40000 = 2000$（远超 reward range [0, 200]） - DAgger：$\varepsilon H = 0.05 \times 200 = 10$（可接受）

这解释了为什么纯 BC 在长时域任务上**必然失败**（除非数据量极大使 $\varepsilon \to 0$），而 DAgger 可以成功。

从 DAgger 到现代方法的演进 ⭐⭐⭐¶

方法	需要专家在环？	样本复杂度	适用场景
BC	否	$O(\varepsilon H^2)$	短时域、大量数据
DAgger	是	$O(\varepsilon H)$	可以在线查询专家
HG-DAgger	是（偶尔）	$O(\varepsilon H)$	人类偶尔接管
ThriftyDAgger	是（极少）	~$O(\varepsilon H)$	只在"不确定"时查询
GAIL	否（但需在线交互）	$O(\varepsilon_{\text{disc}})$	有环境但无法查询专家
BC + 大规模数据	否	$O(\varepsilon H^2)$ → 数据压缩 $\varepsilon$	RT-X, OpenVLA 范式

现代"数据规模换理论保证"范式：RT-X、Open X-Embodiment（2023–2024）、OpenVLA（2024）用 $10^6+$ 轨迹把 BC 的 $\varepsilon$ 压到极小值（大力出奇迹），使得即使 $H^2$ 放大，total error 仍可接受。这是"不需要 DAgger 的在线开销，纯靠数据量补偿 compounding"的工程路线。

IRL → RLHF 的连接 ⭐⭐⭐¶

IRL（Ng–Russell 2000；Ziebart 等 MaxEnt IRL）：从示教恢复 reward 函数。现代 RLHF（Reinforcement Learning from Human Feedback）（Christiano 等 2017，InstructGPT/ChatGPT 的核心训练方法）就是 IRL 在**偏好学习**下的变体： - 人类不给出完整轨迹（太贵），而是给出偏好对 ($\tau_1 \succ \tau_2$) - 从偏好学习 reward model $r_\phi$（Bradley-Terry 模型：$P(\tau_1 \succ \tau_2) = \sigma(r_\phi(\tau_1) - r_\phi(\tau_2))$） - 用 PPO 最大化 $r_\phi$，加 KL penalty 防止 reward hacking

RLHF 的 IL 理论视角：RLHF 可以看作 "offline IRL + online RL"——offline 阶段从偏好数据学 reward（等价于 MaxEnt IRL），online 阶段用 PPO 优化该 reward。理论保证：如果 reward model 的泛化误差 $\le \varepsilon_R$，则最终策略的 suboptimality $\le O(\varepsilon_R / (1-\gamma))$——这与 simulation lemma 的结构相同。

这把 IL/IRL 与 LLM alignment 连接起来——理论工具完全相同。机器人学者学的这些工具在 NLP 领域有直接应用。

⚠️ 常见陷阱¶

💡 概念误区："DAgger 必须要专家在环" - 是——这是它的致命工程缺陷。实际机器人常用"近似专家"（MPC、前版策略）做标注，或用 偏好标注（人类只说"哪个好"，不给具体动作）配合 RLHF。

练习¶

手推 compounding error：对 $H=100, \varepsilon=0.05$，计算 BC 和 DAgger 的 worst-case performance gap。如果你只能接受 $J(\pi^*) - J(\hat\pi) \le 1$，BC 要求 $\varepsilon$ 多小？DAgger 呢？
GAIL vs BC：GAIL 需要与环境交互（online），BC 不需要（offline）。但 GAIL 避免了 compounding error。设计一个实验在 CartPole 上比较两者。

§6.6.F Sim2Real 的学习理论视角 ⭐⭐⭐⭐¶

动机：为什么 Sim2Real gap 是一个学习理论问题？¶

机器人 RL 的标准管线是"仿真训练 → 真机部署"。但仿真器不完美——动力学参数、接触模型、传感器噪声都与真实环境有偏差。这个"gap"可以用学习理论的 domain adaptation / distribution shift 框架形式化。

Domain Shift Bound ⭐⭐⭐⭐¶

设定：在源域（仿真）$M_{\text{sim}}$ 上训练策略 $\pi$，部署在目标域（真实）$M_{\text{real}}$ 上。

定理（非正式，Xu–Luo–Levine 等思想的整合）： $$ V^{\text{real}} - V^\pi \le \underbrace{V^}{\text{real}} - V^{\pi^{\text{sim}}} + \underbrace{V^{\pi^}}}_{\text{(a) sim2real gap（不可压缩）}}}{\text{real}} - V^\pi $$}}}_{\text{(b) 训练 gap（可压缩）}

项 (a) 是由**模型差异**决定的不可消除误差——除非仿真器完美。项 (b) 是训练算法的 suboptimality——可以通过更好的算法/更多数据压缩。

用 simulation lemma 量化项 (a)： $$ |V^\pi_{\text{sim}} - V^\pi_{\text{real}}| \le \frac{\gamma \varepsilon_P V_{\max} + \varepsilon_r}{(1-\gamma)^2} $$ 其中 $\varepsilon_P = \max_{s,a}\|P_{\text{sim}}(\cdot|s,a) - P_{\text{real}}(\cdot|s,a)\|_1$。

Domain Randomization 作为分布鲁棒优化 ⭐⭐⭐¶

Domain Randomization (DR)（Tobin 等 2017, OpenAI Rubik's Cube 2019）：在训练时随机化仿真参数（质量、摩擦、延迟等），希望策略对参数变化鲁棒。

学习理论视角：DR 本质上是求解一个**分布鲁棒优化 (DRO)** 问题： $$ \max_\pi \min_{\xi \in \Xi} V^\pi(M_\xi) $$ 其中 $\Xi$ 是参数不确定集。这与 robust control 的 minimax 精神完全一致。

本质洞察：Domain Randomization 不是让仿真更接近真实，而是让策略对**参数变化更加鲁棒**。真实世界只是随机化覆盖的分布中的一个点——前提是真实参数落在 $\Xi$ 内。

反事实推理：如果 $\Xi$ 设得太窄会怎样？真实参数可能在 $\Xi$ 之外，策略在真实环境中仍然失败。如果 $\Xi$ 设得太宽会怎样？minimax 策略过于保守——它要应对"最坏情况"，但最坏情况可能永远不会发生。这就是 DR 的**核心 trade-off**：覆盖性 vs 保守性。

分布鲁棒优化的理论保证 ⭐⭐⭐⭐¶

定理（非正式，Xu–Mannor 2010 框架的 RL 推广）：设 $\Xi$ 是参数不确定集，$\pi^*_{\text{DR}} = \arg\max_\pi \min_{\xi\in\Xi} V^\pi(M_\xi)$ 是 DR 最优策略。则在真实环境 $M_{\text{real}}$ 上： $$ V^{\pi^{\text{DR}}}(M V^{\pi^}}) \ge \min_{\xi\in\Xi{\text{DR}}}(M\xi) \quad \text{当且仅当} \quad \xi_{\text{real}} \in \Xi $$

含义：DR 策略的真实 performance 的**下界**就是它在"最坏参数"上的表现。如果 $\Xi$ 包含真实参数，你就有了一个**免费的 performance guarantee**。

选择 $\Xi$ 的理论指导： - 太小的 $\Xi$：可能不包含 $\xi_{\text{real}}$ → 保证失效 - 太大的 $\Xi$：minimax 策略过于保守 → 性能下降 - 正确的 $\Xi$：用 system identification 的 confidence set——即"在数据支持下，$\xi_{\text{real}}$ 以概率 $\ge 1-\delta$ 落在此集合内"

实践方法： 1. 在真实环境中收集少量数据（如 10 条轨迹） 2. 用 Bayesian system ID 得到参数后验 $p(\xi|\text{data})$ 3. 取 $\Xi =$ 95% 后验 credible region 4. 在 $\Xi$ 上做 DR 训练

这把**domain randomization 从"拍脑袋选范围"变成了有数据支撑的决策**。

Robustness Certification ⭐⭐⭐⭐¶

更近期的工作（Lechner 等 2021 "Revisiting the Robustness of Neural Network Verified Against Sim-to-Real Transfer"）把 formal verification 引入 sim2real：

对训练好的策略 $\pi_\theta$，证明对所有 $\xi \in \Xi$：$V^{\pi_\theta}(M_\xi) \ge V_{\min}$
使用 interval bound propagation / Lipschitz bound / SDP relaxation
目前只能处理小规模策略（2-3 层 MLP），scale 是 open problem

与 offline RL 的联系：如果把"仿真数据"看作 offline dataset，"real deployment"看作 target domain，则 sim2real gap 本质上是一种 distribution shift——与 offline RL 的 distribution shift 数学上同构。区别在于： - Offline RL 的 shift 来自 policy change（behavior → learned） - Sim2Real 的 shift 来自 environment change（sim → real）

两者都可以用 pessimism/conservatism 来处理：offline RL 用 LCB penalty，sim2real 用 domain randomization（worst-case over $\Xi$）。这一统一视角由 Kumar 等 2021 "DR is Not Enough" 和 Lyu 等 2022 "State Augmentation in Sim2Real" 开始形式化。

Sim2Real 的完整分类框架 ⭐⭐⭐¶

Gap 来源	具体表现	解决方法	理论工具
动力学参数	质量、摩擦、弹性系数不准	Domain Randomization	DRO, simulation lemma
未建模动力学	接触柔性、线缆弹性、空气阻力	System ID + residual learning	Transfer bound
感知差异	相机噪声、光照、纹理	Visual DR, NeRF-based augmentation	Domain adaptation bound
执行延迟	通信延迟、电机响应时间	Action delay randomization	Delayed MDP theory
状态估计	位置/速度估计误差	Observation noise injection	Robust filtering

穷举式问题分类的价值：面对一个新的 sim2real 项目，按上述五个维度逐一检查"我的仿真器在哪里不准"，可以系统地确定 DR 应该随机化哪些参数。

⚠️ 常见陷阱¶

🧠 思维陷阱："Domain Randomization 越多越好" - 新手想法："把所有参数都随机化到最大范围，策略一定最鲁棒" - 实际上：过度随机化导致"average-case good but no-case great"——策略在所有环境中表现平庸，在任何单一环境中都不如专门训练的策略。最优策略是在"覆盖性"和"性能"之间找平衡。

💡 概念误区："Sim2Real 只是工程问题" - 实际上：它有正式的学习理论框架（DRO + simulation lemma + transfer bound）。理论能告诉你"需要多少真实数据来确定 $\Xi$""给定 $\Xi$ 大小，minimax 策略的 worst-case performance 是多少"——这些是**可计算的数值**，不是模糊直觉。

练习¶

DR 的 trade-off 实验：在 CartPole 上随机化 pole length（$\pm 20\%$ vs $\pm 50\%$ vs $\pm 80\%$），分别训练 PPO，然后在固定 pole length 上测试。绘制"randomization range vs test performance"曲线。
Simulation lemma 应用：如果你的仿真器的摩擦系数与真实相差 20%（$\varepsilon_P \approx 0.2$ 在某些状态），horizon $H=100$，$\gamma=0.99$，simulation lemma 给出的 value gap 上界是多少？这个界紧吗？
DRO 形式化：对一个 2-state 2-action MDP，参数 $\xi =$ 转移概率（在 $[0.3, 0.7]$ 范围内不确定），写出 minimax value function 的求解过程。验证最优策略是否为 deterministic。

关键技术：Performance Difference Lemma ⭐⭐⭐¶

这个引理在 §6.6.5 和 §6.6.E 中被反复使用，值得独立展开。

引理（Performance Difference Lemma，Kakade–Langford 2002）：对任意两个策略 $\pi, \pi'$： $$ V^{\pi'}(s_1) - V^\pi(s_1) = \sum_{h=1}^H \mathbb{E}_{s_h \sim d_h^{\pi'}}[A^\pi(s_h, \pi'(s_h))] $$ 其中 $A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)$ 是 $\pi$ 下的 advantage function，$d_h^{\pi'}$ 是 $\pi'$ 在第 $h$ 步的状态分布。

完整证明：

\[ V^{\pi'}(s_1) - V^\pi(s_1) = \mathbb{E}^{\pi'}\Bigl[\sum_{h=1}^H r_h\Bigr] - V^\pi(s_1) \]

对 $V^\pi$ 做 telescoping： $$ V^\pi(s_1) = V^\pi(s_1) - \gamma V^\pi(s_2) + \gamma V^\pi(s_2) - \gamma^2 V^\pi(s_3) + \cdots $$

改写为（episodic 无 discount 版本更清晰）： $$ V^{\pi'}(s_1) - V^\pi(s_1) = \mathbb{E}^{\pi'}\Bigl[\sum_{h=1}^H \bigl(r_h + V^\pi(s_{h+1}) - V^\pi(s_h)\bigr)\Bigr] $$ $$ = \mathbb{E}^{\pi'}\Bigl[\sum_{h=1}^H \bigl(r(s_h, a_h) + V^\pi(s_{h+1}) - V^\pi(s_h)\bigr)\Bigr] $$

由 Bellman 方程 $Q^\pi(s,a) = r(s,a) + \mathbb{E}_{s'}[V^\pi(s')]$： $$ r(s_h, a_h) + V^\pi(s_{h+1}) - V^\pi(s_h) = Q^\pi(s_h, a_h) - V^\pi(s_h) + \underbrace{V^\pi(s_{h+1}) - \mathbb{E}{s'|s_h,a_h}[V^\pi(s')]} $$} \eta_h

取期望后 martingale noise 消失： $$ V^{\pi'}(s_1) - V^\pi(s_1) = \sum_{h=1}^H \mathbb{E}{s_h\sim d_h^{\pi'}, a_h\sim\pi'(\cdot|s_h)}[Q^\pi(s_h,a_h) - V^\pi(s_h)] $$ $$ = \sum[A^\pi(s_h, \pi'(s_h))] \qquad\square $$}^H \mathbb{E}_{s_h\sim d_h^{\pi'}

这个引理为什么如此重要？

Policy gradient 定理（6.2）是它的特例：令 $\pi' = \pi + \delta\pi$，一阶展开得到 $\nabla_\theta J = \mathbb{E}_{d^\pi}[A^\pi \nabla\log\pi]$。
Offline RL 的 decomposition（§6.6.6）：令 $\pi' = \pi^*$，$\pi = \hat\pi$，得到 gap $= \sum_h \mathbb{E}_{d^{\pi^*}}[A^{\hat\pi}]$。
BC 的 compounding error（§6.6.E）：用 $d^{\hat\pi}$ 替代 $d^{\pi^*}$ 引入的误差，由 TV 距离控制。
CPO 的约束近似：把 $J_C(\pi') - J_C(\pi)$ 表示为 $\sum_h \mathbb{E}_{d^{\pi'}}[A_C^\pi]$，再用 trust region 近似。

本质洞察：Performance Difference Lemma 把"两个策略的 value 差"拆成了"逐步的 advantage 累加"——这使得我们可以**分别控制每一步的 advantage 误差**，然后简单求和。它是几乎所有 RL 理论分析的"万能起点"。

本章常见误解汇总¶

误解	正确理解
"样本复杂度 $\tilde O(H^2SA/\varepsilon^2)$ 说明 RL 在大状态空间下不可行"	这个 bound 是tabular MDP 的 minimax 结果。函数逼近（线性/核/神经网络）通过将 $S$ 替换为特征维度 $d$ 来打破维数灾难：线性 MDP 的样本复杂度为 $\tilde O(d^2H^3/\varepsilon^2)$，不依赖 $S$。实际机器人 RL 正是通过参数化逼近绕开了 tabular 的不可行性
"乐观主义（Optimism）只是一种启发式探索策略"	乐观主义是 regret 最优性的数学必要条件。UCB1 / UCBVI / LSVI-UCB 的 regret bound 都依赖于"面对不确定性时选乐观估计"这一原则。Le Cam 的信息论下界证明了任何非乐观算法的 regret 不可能达到 minimax 最优。乐观主义不是启发式，而是最优探索的唯一选择（在最坏情况意义下）
"Offline RL 只要数据够多就能学好"	Offline RL 的性能瓶颈不是数据量，而是分布覆盖度。Concentrability coefficient $C^$ 衡量离线数据分布 $\mu$ 对最优策略占用测度 $d^{\pi^}$ 的覆盖程度。即使有无限数据，如果 $\mu$ 没覆盖到关键状态-动作对，学出的策略在那些区域就是"盲猜"。CQL/IQL 通过悲观主义（Pessimism）在未覆盖区域给出保守估计
"Distributional RL 只是学更多信息，性能提升是偶然的"	Distributional RL 的理论基础是 Wasserstein 压缩性：分布 Bellman 算子 $\mathcal{T}^\pi$ 在 $\bar d_p$ 度量下是 $\gamma$-压缩映射。学习完整分布而非均值提供了更丰富的学习信号（避免了均值聚合导致的信息损失），且 quantile regression 天然对异常值具有鲁棒性。Rainbow 的 ablation 实验验证了 C51 是单项贡献最大的改进之一
"Constrained MDP（CMDP）直接在 reward 里加惩罚项就行"	惩罚系数法（$r - \lambda c$）把约束优化转化为无约束优化，但 $\lambda$ 的最优值依赖于未知的最优策略——形成鸡生蛋的问题。Lagrangian 对偶方法（CPO、Lagrangian PPO）在线更新 $\lambda$，保证在满足约束的同时最大化奖励。强对偶定理保证了 CMDP（在线性规划意义下）无对偶间隙，因此 Lagrangian 方法是精确的，不是近似

本章小结¶

知识点	核心结果	关键工具	关键文献
PAC-MDP	sub-opt steps $\le$ poly$(S,A,1/\varepsilon)$	Hoeffding + simulation lemma	Kakade 2003, Brafman 2003
UCB1	$O(\sqrt{KT\ln T})$ regret	Hoeffding + union bound	Auer et al. 2002
UCBVI	$\tilde O(\sqrt{HSAT})$ minimax	Bernstein bonus + variance	Azar et al. 2017
Le Cam 下界	$\Omega(\sqrt{HSAT})$	KL divergence + 两点法	Dann-Brunskill 2015
LSVI-UCB	$\tilde O(\sqrt{d^3H^3T})$	Self-normalized martingale	Jin et al. 2020
Pessimistic VI	$\tilde O(H\sqrt{SC^*/N})$	LCB + concentrability	Rashidinejad 2021
CQL	$\hat Q \le Q^\pi$	Conservative regularizer	Kumar et al. 2020
IQL	expectile $\to$ implicit max	Asymmetric L2 loss	Kostrikov et al. 2022
Distributional Bellman	$\gamma$-contraction in $W_p$	Wasserstein coupling	Bellemare et al. 2017
CMDP	LP 对偶 + Lagrangian	Primal-dual convergence	Altman 1999, Achiam 2017
DAgger	$O(\varepsilon H)$ vs BC's $O(\varepsilon H^2)$	Online aggregation	Ross et al. 2011
Sim2Real	$\le$ simulation lemma gap	DRO + domain randomization	Tobin 2017, Lechner 2021

累积项目：本章新增模块¶

项目方向：RL 理论实验平台

本章新增： - 模块 6：实现 tabular UCBVI-Hoeffding 和 UCBVI-Bernstein，在 RiverSwim MDP 上对比 regret 曲线；验证 Bernstein 在 low-variance 环境中的优势。 - 模块 7：实现 offline pessimistic VI（tabular），在合成数据上验证 Rashidinejad 定理——改变 $C^*$（通过调整 behavior policy），观察 suboptimality 如何随 $C^*$ 变化。 - 模块 8：用 CORL 在 D4RL halfcheetah-medium 上跑 CQL + IQL + TD3+BC，记录并对比 Q 值曲线和最终 normalized score。

延伸阅读¶

资源	难度	推荐读法
Agarwal–Jiang–Kakade–Sun "RL: Theory and Algorithms"（草稿）	⭐⭐⭐	Ch. 6–10，本节首选教材
Lattimore–Szepesvári "Bandit Algorithms"（Cambridge，免费 PDF）	⭐⭐	Ch. 7–9（UCB/TS），bandit 深入
Bellemare–Dabney–Rowland "Distributional RL"（MIT Press 2023，免费）	⭐⭐⭐	§6.6.A 专用教材
Levine–Kumar–Tucker–Fu "Offline RL Tutorial"（arXiv 2005.01643）	⭐⭐	120 页必读综述
Altman "Constrained MDP"（CRC 1999，免费 PDF）	⭐⭐⭐⭐	CMDP 原典
Nan Jiang, UIUC CS 598 lecture notes	⭐⭐⭐⭐	最透彻的 offline RL 理论公开课
Sergey Levine, Berkeley CS 285 Lecture 15–16（YouTube）	⭐⭐	offline RL 直觉讲解
CORL（corl-team/CORL）单文件代码	⭐⭐	博士 offline RL 复现首选
OmniSafe + Safety-Gymnasium	⭐⭐	Safe RL 完整框架

🔧 故障排查手册¶

症状	可能原因	排查步骤	相关小节
Offline RL 的 Q 值爆到 $10^6$	使用了标准 SAC/DQN 跑 offline 数据	1. 确认算法是否有 OOD 惩罚 2. 加 CQL loss 或切换到 IQL	§6.6.5
CQL 训练后 Q 值过低，策略太保守	$\alpha$ 太大，悲观过度	1. 降低 $\alpha$ 2. 用 Cal-QL 的 calibration 3. 用 IQL 替代	§6.6.5, §6.6.D
Safe RL 的 $\lambda$ 剧烈震荡	Lagrangian 步长不匹配	1. 降低 $\alpha_\lambda$ 2. 用 PID-based lambda 更新 3. 换 CPO	§6.6.B
UCB 算法在早期 regret 很高	初始探索阶段（每个 arm 至少拉一次）	正常现象；若持续高 → 检查 bonus 系数是否正确	§6.6.2
Distributional RL 训练不稳定	分位数交叉（quantile crossing）	1. 检查分位数排序 2. 加 sorting 后处理 3. 降低学习率	§6.6.A
DAgger 性能下降	近似专家（MPC）质量不够	1. 检查专家在测试分布上的表现 2. 增大训练数据量 3. 考虑 GAIL	§6.6.E

与其他章节的知识桥梁¶

本章 ↔ 概率与集中不等式基础：Hoeffding, Bernstein, Freedman 不等式、union bound、Fano 不等式——本章所有证明的底层工具。
本章 ↔ MDP 与动态规划基础：Bellman 算子是 UCBVI、pessimistic VI 的语法基础；CMDP 在 MDP 章简介后本章展开。
本章 ↔ 策略梯度与 Actor-Critic：PPO/SAC 是 online policy learning 的代表，与 offline RL 形成 online↔offline 对偶。Lagrangian-PPO 是策略梯度+本章约束理论的直接组合。
本章 ↔ 逼近动态规划与 TD 学习：offline RL 的病症（distribution shift + bootstrap + 外推）是致命三元组在 offline 情形下的极端形态。
本章 ↔ 连续控制与 RL 统一视角：MOReL、COMBO 是 offline MBRL——offline + model-based + pessimism 三合一。
本章 ↔ 随机逼近与 ODE 方法：off-policy evaluation 的收敛性分析用 SA 的一致性结果。
延伸 → 控制理论方向（MPC / 约束最优控制）：CMDP 与约束 MPC 的对应；CBF-QP 与 MPC 的一步约束投影。
延伸 → 深度学习与具身智能方向：VLA 的 offline 训练完全基于本章框架；Diffusion Policy 是 BC 的生成模型版本。

与控制理论的映射¶

RL 概念	控制理论对应物	对应关系解释
PAC-MDP worst-case	$H_\infty$ robust control	两者都关注最坏情况保证
Online RL 的 OFU / UCB	Adaptive control 的 probing	都需要"激励"系统获取信息
Offline RL 的 pessimism	Robust design（保守设计）	模型不确定时取保守策略
CMDP	约束最优控制	同一问题的不同求解范式
CBF	Lyapunov barrier	保证集合不变性的工具
Distributional RL	随机最优控制 + 风险度量	CVaR 等风险函数
Reward-free exploration	System identification	模型辨识先于控制设计
Sim2Real / DR	鲁棒控制 / $\mu$-synthesis	参数不确定集上的 minimax

最重要的一条：CMDP + MPC + CBF 是真机部署的"三位一体"——CMDP 给你可学习的约束框架，MPC 给你短时域严格约束的规划器，CBF 给你一阶安全兜底。三者在实际机器人栈中通常**嵌套**使用。

开放问题（2025–2026 前沿）¶

以下是本领域目前尚未完全解决的问题，适合博士研究方向选择参考：

开放问题	当前进展	难度
Model-free offline RL 的 minimax 最优算法	有 model-based 最优（PEVI），model-free 尚差一个 $\sqrt{H}$	⭐⭐⭐⭐
General function approximation 下的 offline RL 样本复杂度	DEC 框架给出 online 的统一答案，offline 版本仍 open	⭐⭐⭐⭐
Safe exploration 的 minimax regret（同时保证安全）	目前的 bound 比不安全版本松很多	⭐⭐⭐⭐
Distributional RL 在 control case 的收敛速率	$\mathcal{T}^*$ 不是 $W_p$-contraction	⭐⭐⭐⭐
Reward-free + 函数逼近	一般情况不可能（Du et al.），何种结构可以？	⭐⭐⭐⭐
Offline RL with POMDP（部分观测）	几乎完全 open	⭐⭐⭐⭐
Sim2Real gap 的 data-dependent tight bound	Simulation lemma 太松	⭐⭐⭐

跨章综合练习¶

综合题 1（综合 6.1 + 6.5 + 6.6）：Q-learning 的收敛性（6.5）与 PAC-MDP 保证（6.6）之间有什么关系？证明：如果一个算法的 regret 为 $\tilde O(\sqrt{T})$，则它的 sub-optimal steps 为 $\tilde O(1/\varepsilon^2)$（PAC-MDP 形式）。这两个概念等价吗？

综合题 2（综合 6.2 + 6.6.5）：PPO 是 online RL（§6.2），CQL 是 offline RL（§6.6.5）。如果你把 PPO 的数据全部存到 replay buffer，然后跑 CQL，理论上会发生什么？这和直接跑 PPO 相比如何？用 concentrability coefficient 分析。

综合题 3（综合 6.3 + 6.6.A）：DQN 的致命三元组（6.3）在 distributional RL 中是否依然致命？C51/QR-DQN 使用了 function approximation + bootstrapping + off-policy——为什么它不崩溃？（提示：distributional Bellman 的 target 比 scalar Bellman 的 target 提供了更丰富的梯度信号）

自测题目¶

UCB1 证明：写出 UCB1 在 $K$-arm MAB 上的 regret 证明，要求明确指出 Hoeffding 不等式、union bound、$\Delta_a$ 依赖关系三处出现的位置。
线性 MDP 的 Bellman 闭包：为什么线性 MDP 假设 $P(s'|s,a) = \phi(s,a)^\top\mu(s')$ 同时等价于"Bellman 算子作用下 $Q$ 保持线性"？如果只假设 $r$ 线性而 $P$ 不线性，LSVI-UCB 还成立吗？
CQL 下界证明：给定 $\mathcal{L}_{\text{CQL}}$ 的 first-order 最优性条件，推导 $\hat Q^\pi(s,a)\le Q^\pi(s,a)$。
Offline vs Online 对偶：分别给出 Jin 2020（online, LSVI-UCB）与 Jin–Yang–Wang 2021（offline, PEVI）的关键 lemma，说明 bonus 符号如何翻转。
Single-policy concentrability：解释 $C^*=1$ / $C^*=SA$ / $C^*=\infty$ 的物理含义。给一个机器人任务的 $C^*$ 估计。
Distributional Bellman 压缩性：证明 $\mathcal{T}^\pi$ 在 $W_p$ 下 $\gamma$-压缩。指出哪一步在 $\mathcal{T}^*$ 中 break。
CPO vs Lagrangian-PPO：比较两者在训练过程中的约束满足保证。真机部署时应该选哪个？为什么？
DAgger compounding：证明 BC 的 $O(\varepsilon H^2)$ 界；说明 DAgger 如何降到 $O(\varepsilon H)$；对 $H=200, \varepsilon=10\%$ 给出数值估计。

常见陷阱速查¶

陷阱	正确认识
"PAC-MDP 讲的就是收敛"	不是——是收敛率（样本复杂度）；收敛性是 6.5 的事。
"Q-learning 一定有 PAC 保证"	原始 Q-learning 无；Q-learning + UCB bonus 才有（Jin 等 2018）。
"把 SAC 直接跑 offline 就是 offline RL"	会因 OOD 高估立即崩溃。需要 BCQ/CQL/IQL/TD3+BC。
"CQL 学到的 Q 就是真 Q"	不是——是下界。Policy improvement 在下界上做。
"IQL 的 expectile 就是 quantile"	不同。Expectile 用不对称 L2 loss，quantile 用不对称 L1。
"offline RL = imitation learning"	仅当 $C^*=1$ 时样本复杂度一致；一般 offline RL 可以"超过" behavior。
"concentrability 是工程超参数"	是数据质量指标，决定你的 offline 算法能有多好。
"Distributional RL 没实际用"	在风险敏感场景显著更好；Atari 上 C51 也胜过 DQN。
"CPO 一定满足约束"	渐近 + 每次迭代 worst-case 有界；中间会有小幅违反。
"Lagrangian-PPO 收敛就没问题"	$\lambda$ 震荡在训练中造成大量约束违反——真机不可接受。
"DAgger 必须要专家在环"	是，这是工程缺陷；实际用"近似专家"或偏好标注。
"reward-free exploration 没有 reward 就没目标"	目标是学习 transition 模型，为下游任意 reward 规划。
"Sim2Real 只是调参数"	是一个分布鲁棒优化问题，有正式的学习理论界。

核心教材深度对照¶

教材	章节	覆盖度	适合档位
Agarwal–Jiang–Kakade–Sun "RL: Theory and Algorithms"（草稿免费）	Ch. 6–10	全面，最接近本节	档位 3–4 首选
Lattimore–Szepesvári "Bandit Algorithms"（Cambridge, 免费 PDF）	Ch. 7–9, 19	bandit 深入，MDP 点到	档位 3 bandit 章
Szepesvári "Algorithms for RL"（2010，免费）	短，偏 TD/LSPI	经典但较旧	参考
Sutton–Barto 第二版 Ch. 11–13	无样本复杂度	浅	非本节重点
Bellemare–Dabney–Rowland "Distributional RL", MIT Press 2023（免费）	全书	distributional 唯一权威	§6.6.A 专用

经典论文清单（按时间顺序）¶

年份	论文	会议	专题贡献
1999	Altman 《Constrained MDP》	CRC Press	CMDP 最优策略存在性
2002	Kearns–Singh "Near-optimal RL in polynomial time"	Machine Learning	$E^3$ 算法
2002	Auer–Cesa-Bianchi–Fischer "Finite-time Analysis of MAB"	Machine Learning	UCB1
2003	Brafman–Tennenholtz "R-MAX"	JMLR	OFU 原型
2003	Kakade "On the Sample Complexity of RL"	PhD Thesis	PAC-MDP 框架奠基
2008	Strehl–Li–Littman "MBIE-EB"	JCSS	改进 PAC-MDP 界
2010	Jaksch–Ortner–Auer "UCRL2"	JMLR	第一个 $\sqrt{T}$ regret
2011	Ross–Gordon–Bagnell "DAgger"	AISTATS	compounding error
2011	Abbasi-Yadkori–Pál–Szepesvári	NIPS	self-normalized martingale
2016	Ho–Ermon "GAIL"	NeurIPS	occupancy matching
2017	Bellemare–Dabney–Munos "C51"	ICML	distributional RL 开山
2017	Azar–Osband–Munos "UCBVI"	ICML	tabular minimax regret
2017	Achiam 等 "CPO"	ICML	safe RL 里程碑
2018	Jin–Allen-Zhu–Bubeck–Jordan	NeurIPS	model-free $\sqrt{T}$
2018	Dabney 等 "QR-DQN"	AAAI	分位数回归
2018	Dabney 等 "IQN"	ICML	隐式分位数
2019	Fujimoto–Meger–Precup "BCQ"	ICML	offline 约束
2020	Jin–Yang–Wang–Jordan "LSVI-UCB"	COLT	linear MDP
2020	Kumar 等 "CQL"	NeurIPS	悲观主义代表作
2020	Jin 等 "Reward-Free Exploration"	ICML	exploration-exploitation 分离
2021	Rashidinejad 等 "Tale of Pessimism"	NeurIPS	single-policy concentrability
2021	Jin–Yang–Wang "Is Pessimism Provably Efficient"	ICML	PEVI
2021	Foster–Kakade–Qian–Rakhlin "DEC"	COLT	统一框架
2022	Kostrikov–Nair–Levine "IQL"	ICLR	expectile regression
2023	Nakamoto 等 "Cal-QL"	NeurIPS	calibrated offline-to-online

C++/Python 库对照¶

Offline RL / benchmark¶

D4RL（Farama-Foundation/D4RL）：offline RL 黄金 benchmark。Apache-2.0。
Minari（Farama-Foundation/Minari）：新一代 offline RL 数据 API。MIT。
CORL（corl-team/CORL）：单文件实现 11+ offline 算法。Apache-2.0。博士研究首选。
d3rlpy（takuseno/d3rlpy）：高度模块化 offline RL 库。MIT。

Safe RL¶

OmniSafe（PKU-Alignment/omnisafe）：safe RL 最完整统一框架。Apache-2.0。
Safety-Gymnasium（PKU-Alignment/safety-gymnasium）：safe RL 环境。Apache-2.0。

适用场景对照¶

场景	推荐栈
Offline RL 论文复现	CORL 单文件
Offline RL 工程集成	d3rlpy
Safe RL 研究	OmniSafe + Safety-Gymnasium
CBF-QP + RL	qpth/cvxpylayers + SB3

机器人应用映射¶

Offline RL 在 sim-to-real：常见管线 "仿真 medium-expert 数据 → offline CQL/IQL 预训练 → 真机 Cal-QL fine-tune"。QT-Opt、Q-Transformer 是先驱；Robomimic 是 manipulation benchmark。

Safe RL 在机器人：关节限幅、接触力上界、碰撞避免（SDF + CBF）。ETH Ankymal、MIT Cheetah 是真机标杆。

Distributional RL 在机器人：D4PG、DSAC 在轮式机器人和无人机上因 CVaR 鲁棒性被部署。

Imitation Learning 在机器人：RT-X、OpenVLA 把 BC 推到 "$10^6$ 轨迹"规模；GAIL/AMP 用于 locomotion style transfer。

Reward-free exploration ↔ SLAM：先建图后规划——embodied AI multi-task foundation model 的理论基础。

时间预算与节奏建议¶

档位 3 必学部分（§6.6.1–§6.6.6），约 3–4 周（每周 10–12 小时）：

第 1 周：§6.6.1–§6.6.2。读 Lattimore–Szepesvári Ch. 7（UCB1），亲手证明 UCB1 regret。
第 2 周：§6.6.3–§6.6.4。精读 Azar 2017 前 6 页 + Jin 2020 §2–§3。
第 3 周：§6.6.5。必读 Levine 等 2020 tutorial §1–§6；跑 CORL cql.py + iql.py。
第 4 周：§6.6.6。精读 Rashidinejad 2021 §1–§4；做自测题。

档位 4 选学部分（§6.6.A–§6.6.F），每个 2–5 天。

证明技术的依赖图¶

理解本章各定理之间的逻辑关系，有助于把握"学什么、按什么顺序学"：

Hoeffding 不等式
    │
    ├──→ UCB1 regret 证明 [§6.6.2]
    │       └──→ template for all online RL proofs
    │
    ├──→ Simulation Lemma [§6.6.1]
    │       ├──→ R-MAX PAC-MDP [§6.6.1]
    │       └──→ Sim2Real gap bound [§6.6.F]
    │
    └──→ Bernstein 不等式 (升级)
            │
            ├──→ UCBVI Bernstein bonus [§6.6.3]
            │       └──→ minimax optimal tabular regret
            │
            └──→ Freedman 不等式 (martingale 版本)
                    │
                    └──→ Self-normalized martingale [§6.6.4]
                            ├──→ LSVI-UCB linear MDP [§6.6.4]
                            └──→ PEVI offline linear MDP [§6.6.5]

Le Cam 两点法 / Fano 不等式
    └──→ Minimax lower bound [§6.6.3]
            └──→ 确认 UCBVI 的 optimality

Performance Difference Lemma
    ├──→ Offline RL decomposition [§6.6.6]
    ├──→ BC compounding error [§6.6.E]
    ├──→ CPO constraint surrogate [§6.6.B]
    └──→ Policy Gradient (回顾 6.2)

Wasserstein 距离性质
    └──→ Distributional Bellman contraction [§6.6.A]

LP 对偶 / KKT 条件
    └──→ CMDP optimal policy existence [§6.6.B]
            └──→ Lagrangian primal-dual convergence

学习建议：先完全理解 Hoeffding → UCB1 这条线（§6.6.1–6.6.2），它是所有后续的基础。再学 Bernstein → UCBVI（§6.6.3）感受"利用方差"的威力。最后学 self-normalized → LSVI-UCB（§6.6.4）进入函数逼近。Offline（§6.6.5–6.6.6）是 online 的"符号翻转"——如果你理解了 online，offline 很快就能掌握。

总结¶

本节把强化学习从"会不会收敛"推进到"要多少样本"，并打开了前沿方向的大门。核心收获有五：

(1) 统一的证明范式。从 UCB1 的 Hoeffding + union bound，到 UCBVI 的 Bernstein bonus + 方差传递，到 LSVI-UCB 的 self-normalized martingale + elliptical potential——是同一套推理的逐步复杂化。掌握了 UCB1 的三步证明（好事件 → 性能分析 → union bound），就握住了后续所有证明的钥匙。

(2) 乐观 ↔ 悲观的对偶。这是本节最重要的"模式识别"：数据可自采时乐观（+bonus）、数据固定时悲观（-penalty）——数学上完全对称。理解这一点，你看 Berkeley 组的任何 offline RL paper 都能立刻抓住动机。

(3) Single-policy concentrability 是新的工程指标。$C^* \to 1$ 时 offline RL 快到 $1/N$，$C^*$ 大时退化成 $1/\sqrt N$——直接指导数据采集策略。这把"数据质量"从模糊概念变成了可量化的数学量。

(4) Safe RL 不再是"加个约束那么简单"。CPO / Lagrangian / CBF 三条路线各有适用场景：Lagrangian 简单但收敛慢且有瞬时违反、CPO 理论强但二阶计算贵、CBF 工程可靠但需要已知 barrier 函数。真机部署几乎总是嵌套使用三者。

(5) Sim2Real 有正式的学习理论框架。Domain Randomization 是分布鲁棒优化（DRO），simulation lemma 量化模型误差的值函数影响。选择"随机化多大范围"不再是拍脑袋——而是一个有 confidence set 支撑的数据驱动决策。

再往上走，博士阶段的研究前沿可能落在：（i）offline RL 在 POMDP / partial observability 下；（ii）offline RL 的 foundation model 化（Decision Transformer + VLA）；（iii）safe exploration 的样本复杂度下界（目前仍有 gap）；（iv）distributional RL 的控制理论收敛证明；（v）reward-free 在一般函数逼近下的可能性/不可能性边界。

附录 A：免费 PDF / 在线资源¶

Agarwal–Jiang–Kakade–Sun "RL: Theory and Algorithms"（草稿，rltheorybook.github.io）
Lattimore–Szepesvári "Bandit Algorithms"（tor-lattimore.com/downloads/book/book.pdf）
Bellemare–Dabney–Rowland "Distributional RL"（MIT Press 2023，开放获取）
Altman "Constrained MDP"（CRC Press 1999，作者主页免费）
Levine–Kumar–Tucker–Fu "Offline RL Tutorial"（arXiv 2005.01643）

附录 B：视频课程资源¶

Sergey Levine, Berkeley CS 285：Lecture 15–16 offline RL 专章
Emma Brunskill, Stanford CS 234：偏 theory
Nan Jiang, UIUC CS 598：offline RL 理论最透彻
RLChina 暑期学校（中文）：每年有 offline/safe/distributional 专题

附录 C：中文资源¶

《动手学强化学习》 张伟楠等，第 13–17 章
离线强化学习中文综述：自动化学报相关文章
RLChina 论坛（rlchina.org）

附录 D：开源代码仓库¶

仓库	License
D4RL（Farama）	Apache-2.0
Minari	MIT
CORL	Apache-2.0
d3rlpy	MIT
OmniSafe	Apache-2.0
Safety-Gymnasium	Apache-2.0
rlkit (IQL 官方)	MIT
CQL 官方	MIT
imitation (DAgger)	MIT
awesome-offline-rl	CC-0

附录 E：社区与论坛¶

NeurIPS Offline RL Workshop（2020–2024 每年）
ICML Safe & Robust RL Workshop
Reinforcement Learning Conference (RLC)（2024 首届）
Farama Foundation Discord
Reddit r/reinforcementlearning

Online UCBVI	Offline Pessimistic VI
\(Q_h = \hat Q_h + b_h\)（加 bonus）	\(Q_h = \hat Q_h - b_h\)（减 penalty）
\(\hat V_h(s) \ge V_h^*(s)\)（乐观性）	\(\hat V_h(s) \le V_h^*(s)\)（悲观性）
Regret = \(\sum_k [\hat V_1^k - V_1^{\pi_k}]\)（乐观值 - 实际值）	Gap = \(V_1^* - \hat V_1\)（最优值 - 悲观值）
依赖 \(T\)（exploration 积累）	依赖 \(N, C^*\)（数据质量）

不等式	条件	结论	适用场景
Hoeffding	\(X_i \in [a,b]\), i.i.d.	$\Pr[	\bar X - \mu
Bernstein	\(X_i \in [a,b]\), i.i.d., \(\text{Var}(X_i)=\sigma^2\)	$\Pr[	\bar X - \mu
Freedman	\(\{M_t\}\) martingale, $	M_t - M_{t-1}	\le b$

方法	算法代表	Regret	空间	关键论文
Model-based	UCBVI	\(\tilde O(\sqrt{HSAT})\)	\(O(S^2A)\)	Azar et al. 2017
Model-free	UCB-Q-learning	\(\tilde O(\sqrt{H^4SAT})\)	\(O(SA)\)	Jin et al. 2018
Model-free（最优）	monotonic Q-learning	\(\tilde O(\sqrt{H^3SAT})\)	\(O(SA)\)	Zhang-Zhou-Ji 2020

结构类	代表论文	样本复杂度	关键假设
Linear MDP	Jin et al. 2020	\(\tilde O(\sqrt{d^3H^3T})\)	\(P,r\) 都是 \(\phi\) 的线性
Linear mixture MDP	Ayoub et al. 2020	\(\tilde O(\sqrt{d^2H^2T})\)	\(P = \sum_i\phi_i \cdot P_i\)（转移的线性混合）
Linear Bellman Complete	Zanette-Brunskill 2020	\(\tilde O(\text{poly}(d,H)\sqrt{T})\)	\(Q^*\) 在 \(\mathcal{F}\) 中，\(\mathcal{T}\mathcal{F}\subseteq\mathcal{F}\)
Bilinear class	Du et al. 2021	\(\tilde O(\text{poly}(d,H)\sqrt{T})\)	涵盖上述所有
Decision-Estimation Coefficient (DEC)	Foster et al. 2021	minimax optimal	统一 supervised → bandits → RL

类别	代表	核心思想
Policy constraint	BCQ, TD3+BC, AWAC	约束 \(\pi\) 靠近 \(\mu\)
Value regularization	CQL, Fisher-BRC	压低 OOD 的 Q 值
Uncertainty-aware	MOPO, MOReL, COMBO	用模型估计不确定性

方法	需要专家在环？	样本复杂度	适用场景
BC	否	\(O(\varepsilon H^2)\)	短时域、大量数据
DAgger	是	\(O(\varepsilon H)\)	可以在线查询专家
HG-DAgger	是（偶尔）	\(O(\varepsilon H)\)	人类偶尔接管
ThriftyDAgger	是（极少）	~\(O(\varepsilon H)\)	只在"不确定"时查询
GAIL	否（但需在线交互）	\(O(\varepsilon_{\text{disc}})\)	有环境但无法查询专家
BC + 大规模数据	否	\(O(\varepsilon H^2)\) → 数据压缩 \(\varepsilon\)	RT-X, OpenVLA 范式

误解	正确理解
"样本复杂度 \(\tilde O(H^2SA/\varepsilon^2)\) 说明 RL 在大状态空间下不可行"	这个 bound 是tabular MDP 的 minimax 结果。函数逼近（线性/核/神经网络）通过将 \(S\) 替换为特征维度 \(d\) 来打破维数灾难：线性 MDP 的样本复杂度为 \(\tilde O(d^2H^3/\varepsilon^2)\)，不依赖 \(S\)。实际机器人 RL 正是通过参数化逼近绕开了 tabular 的不可行性
"乐观主义（Optimism）只是一种启发式探索策略"	乐观主义是 regret 最优性的数学必要条件。UCB1 / UCBVI / LSVI-UCB 的 regret bound 都依赖于"面对不确定性时选乐观估计"这一原则。Le Cam 的信息论下界证明了任何非乐观算法的 regret 不可能达到 minimax 最优。乐观主义不是启发式，而是最优探索的唯一选择（在最坏情况意义下）
"Offline RL 只要数据够多就能学好"	Offline RL 的性能瓶颈不是数据量，而是分布覆盖度。Concentrability coefficient \(C^\) 衡量离线数据分布 \(\mu\) 对最优策略占用测度 \(d^{\pi^}\) 的覆盖程度。即使有无限数据，如果 \(\mu\) 没覆盖到关键状态-动作对，学出的策略在那些区域就是"盲猜"。CQL/IQL 通过悲观主义（Pessimism）在未覆盖区域给出保守估计
"Distributional RL 只是学更多信息，性能提升是偶然的"	Distributional RL 的理论基础是 Wasserstein 压缩性：分布 Bellman 算子 \(\mathcal{T}^\pi\) 在 \(\bar d_p\) 度量下是 \(\gamma\)-压缩映射。学习完整分布而非均值提供了更丰富的学习信号（避免了均值聚合导致的信息损失），且 quantile regression 天然对异常值具有鲁棒性。Rainbow 的 ablation 实验验证了 C51 是单项贡献最大的改进之一
"Constrained MDP（CMDP）直接在 reward 里加惩罚项就行"	惩罚系数法（\(r - \lambda c\)）把约束优化转化为无约束优化，但 \(\lambda\) 的最优值依赖于未知的最优策略——形成鸡生蛋的问题。Lagrangian 对偶方法（CPO、Lagrangian PPO）在线更新 \(\lambda\)，保证在满足约束的同时最大化奖励。强对偶定理保证了 CMDP（在线性规划意义下）无对偶间隙，因此 Lagrangian 方法是精确的，不是近似

知识点	核心结果	关键工具	关键文献
PAC-MDP	sub-opt steps \(\le\) poly\((S,A,1/\varepsilon)\)	Hoeffding + simulation lemma	Kakade 2003, Brafman 2003
UCB1	\(O(\sqrt{KT\ln T})\) regret	Hoeffding + union bound	Auer et al. 2002
UCBVI	\(\tilde O(\sqrt{HSAT})\) minimax	Bernstein bonus + variance	Azar et al. 2017
Le Cam 下界	\(\Omega(\sqrt{HSAT})\)	KL divergence + 两点法	Dann-Brunskill 2015
LSVI-UCB	\(\tilde O(\sqrt{d^3H^3T})\)	Self-normalized martingale	Jin et al. 2020
Pessimistic VI	\(\tilde O(H\sqrt{SC^*/N})\)	LCB + concentrability	Rashidinejad 2021
CQL	\(\hat Q \le Q^\pi\)	Conservative regularizer	Kumar et al. 2020
IQL	expectile \(\to\) implicit max	Asymmetric L2 loss	Kostrikov et al. 2022
Distributional Bellman	\(\gamma\)-contraction in \(W_p\)	Wasserstein coupling	Bellemare et al. 2017
CMDP	LP 对偶 + Lagrangian	Primal-dual convergence	Altman 1999, Achiam 2017
DAgger	\(O(\varepsilon H)\) vs BC's \(O(\varepsilon H^2)\)	Online aggregation	Ross et al. 2011
Sim2Real	\(\le\) simulation lemma gap	DRO + domain randomization	Tobin 2017, Lechner 2021

症状	可能原因	排查步骤	相关小节
Offline RL 的 Q 值爆到 \(10^6\)	使用了标准 SAC/DQN 跑 offline 数据	1. 确认算法是否有 OOD 惩罚 2. 加 CQL loss 或切换到 IQL	§6.6.5
CQL 训练后 Q 值过低，策略太保守	\(\alpha\) 太大，悲观过度	1. 降低 \(\alpha\) 2. 用 Cal-QL 的 calibration 3. 用 IQL 替代	§6.6.5, §6.6.D
Safe RL 的 \(\lambda\) 剧烈震荡	Lagrangian 步长不匹配	1. 降低 \(\alpha_\lambda\) 2. 用 PID-based lambda 更新 3. 换 CPO	§6.6.B
UCB 算法在早期 regret 很高	初始探索阶段（每个 arm 至少拉一次）	正常现象；若持续高 → 检查 bonus 系数是否正确	§6.6.2
Distributional RL 训练不稳定	分位数交叉（quantile crossing）	1. 检查分位数排序 2. 加 sorting 后处理 3. 降低学习率	§6.6.A
DAgger 性能下降	近似专家（MPC）质量不够	1. 检查专家在测试分布上的表现 2. 增大训练数据量 3. 考虑 GAIL	§6.6.E

RL 概念	控制理论对应物	对应关系解释
PAC-MDP worst-case	\(H_\infty\) robust control	两者都关注最坏情况保证
Online RL 的 OFU / UCB	Adaptive control 的 probing	都需要"激励"系统获取信息
Offline RL 的 pessimism	Robust design（保守设计）	模型不确定时取保守策略
CMDP	约束最优控制	同一问题的不同求解范式
CBF	Lyapunov barrier	保证集合不变性的工具
Distributional RL	随机最优控制 + 风险度量	CVaR 等风险函数
Reward-free exploration	System identification	模型辨识先于控制设计
Sim2Real / DR	鲁棒控制 / \(\mu\)-synthesis	参数不确定集上的 minimax

开放问题	当前进展	难度
Model-free offline RL 的 minimax 最优算法	有 model-based 最优（PEVI），model-free 尚差一个 \(\sqrt{H}\)	⭐⭐⭐⭐
General function approximation 下的 offline RL 样本复杂度	DEC 框架给出 online 的统一答案，offline 版本仍 open	⭐⭐⭐⭐
Safe exploration 的 minimax regret（同时保证安全）	目前的 bound 比不安全版本松很多	⭐⭐⭐⭐
Distributional RL 在 control case 的收敛速率	\(\mathcal{T}^*\) 不是 \(W_p\)-contraction	⭐⭐⭐⭐
Reward-free + 函数逼近	一般情况不可能（Du et al.），何种结构可以？	⭐⭐⭐⭐
Offline RL with POMDP（部分观测）	几乎完全 open	⭐⭐⭐⭐
Sim2Real gap 的 data-dependent tight bound	Simulation lemma 太松	⭐⭐⭐

样本复杂度与前沿理论¶

前置自测¶

本章目标¶

知识树¶

引言：从"会不会收敛"到"要多少样本" ⭐¶

§6.6.1 PAC-MDP 框架与乐观探索 ⭐⭐¶

动机：为什么需要 PAC-MDP？¶

从 PAC 学习到 PAC-MDP¶

E³ 算法：Explore-or-Exploit 的第一个多项式保证 ⭐⭐⭐¶

集中不等式工具箱：本节所有证明的底层 ⭐⭐⭐¶

R-MAX：乐观探索的原型 ⭐⭐¶

R-MAX 证明骨架 ⭐⭐⭐¶

⚠️ 常见陷阱¶

练习¶

§6.6.2 Bandit 问题与 Exploration–Exploitation ⭐⭐¶

动机：为什么要先学 bandit？¶

Regret 的严格定义 ⭐⭐¶

UCB1：Hoeffding + union bound 的教科书应用 ⭐⭐¶

UCB1 Regret 完整证明 ⭐⭐⭐¶

Thompson Sampling：Bayesian 替代 ⭐⭐⭐¶

UCRL2：bandit → MDP 的推广 ⭐⭐⭐¶

⚠️ 常见陷阱¶

练习¶

§6.6.3 Tabular MDP 的 minimax 样本复杂度 ⭐⭐¶

动机：UCB1 到 UCBVI 的推进¶

Azar–Osband–Munos 2017 定理 ⭐⭐¶

UCBVI-BF 的两把关键技术 ⭐⭐⭐¶

信息论下界：Le Cam 两点法 ⭐⭐⭐⭐¶

Model-based vs Model-free 的样本效率差异 ⭐⭐¶

Dann–Brunskill 2015 下界证明的详细展开 ⭐⭐⭐⭐¶

从 UCBVI 到 MVOI：最新进展（2021–2025） ⭐⭐⭐⭐¶

⚠️ 常见陷阱¶

练习¶

§6.6.4 线性 MDP 与 LSVI-UCB ⭐⭐⭐¶

动机：tabular 的极限¶

线性 MDP 假设 ⭐⭐⭐¶

LSVI-UCB 算法 ⭐⭐⭐¶

LSVI-UCB 定理与证明骨架 ⭐⭐⭐⭐¶

Self-normalized Martingale 不等式详解 ⭐⭐⭐⭐¶

Elliptical Potential Lemma 的几何直觉 ⭐⭐⭐⭐¶

超越线性：结构化函数逼近的统一理论 ⭐⭐⭐⭐¶

⚠️ 常见陷阱¶

练习¶

§6.6.5 Offline RL 的悲观主义原理 ⭐⭐¶

动机：为什么 online RL 的方法在 offline 会灾难性失败？¶

悲观主义 = 离线世界的乐观主义 ⭐⭐¶

Concentrability Coefficient：覆盖率的形式化 ⭐⭐¶

PEVI：Pessimistic Value Iteration ⭐⭐⭐¶

Rashidinejad 等 2021 的 tabular 结果 ⭐⭐⭐¶

四大主流 offline RL 算法 ⭐⭐¶

BCQ — Batch-Constrained Deep Q-learning¶

CQL — Conservative Q-Learning¶

IQL — Implicit Q-Learning¶

TD3+BC — 极简 offline¶

统一视角¶

⚠️ 常见陷阱¶

练习¶

§6.6.6 Offline RL 的理论框架与样本复杂度 ⭐⭐⭐¶

从 BCQ/CQL/IQL 到统一理论¶

Pessimistic VI 的完整分析 ⭐⭐⭐⭐¶

机器人工程含义 ⭐⭐¶

Trajectory Stitching：Offline RL 超越 BC 的本质 ⭐⭐⭐¶

数据量 vs 数据质量的 Trade-off ⭐⭐⭐¶

练习¶

§6.6.A Distributional RL 的数学 ⭐⭐⭐¶

动机：为什么只关心期望是不够的？¶

从 \(Q^\pi\) 到 \(Z^\pi\) ⭐⭐⭐¶

Wasserstein 压缩性完整证明 ⭐⭐⭐⭐¶

C51 / QR-DQN / IQN 的进化路径 ⭐⭐⭐¶

风险敏感控制应用 ⭐⭐⭐¶

⚠️ 常见陷阱¶

练习¶

§6.6.B Safe RL 与 CMDP ⭐⭐⭐¶

动机：为什么纯 reward maximization 在机器人上不够？¶

CMDP 形式化 ⭐⭐¶

三大求解范式 ⭐⭐⭐¶

Lagrangian 方法（原始-对偶）¶

CPO — Constrained Policy Optimization ⭐⭐⭐¶

FOCOPS / PCPO / P3O¶

Lagrangian 方法的收敛性分析 ⭐⭐⭐⭐¶