paper: Stéphane Ross、Geoffrey J. Gordon、J. Andrew Bagnell，〈A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning〉，AISTATS 2011。

这就是提出 DAgger（Dataset Aggregation，数据集聚合） 的论文。下面按原文六个一级标题组织笔记，最后单独讨论后续研究的批评。公式沿用原文主要符号；用于帮助理解的例子、推导解释和评价会明确区分。

先给出贯穿全文的问题：

当模型的输出会改变它下一步看到的输入时，如何通过监督学习，训练出在自己造成的状态分布上仍然表现良好的模型？

理解这句话，比记住“不断把新数据加入训练集”更重要。

INTRODUCTION：问题为何不能直接当作普通监督学习

模仿学习的基本做法

假设我们想教一辆车开车。专家提供状态与动作：

$$ D=\{(s_i,a_i^*)\}_{i=1}^n. $$

其中：

  • $s_i$：图像、车辆位置或其他观测；
  • $a_i^*$：专家在该状态下的动作；
  • $\pi(s)$：学习到的控制策略。

最直接的方法是监督学习：

$$ \hat\pi = \arg\min_{\pi\in\Pi} \frac1n\sum_{i=1}^n \ell\bigl(\pi(s_i),a_i^*\bigr). $$

今天通常把这种做法称为 Behavior Cloning，行为克隆，简称 BC。

问题在于，训练状态是专家开车时遇到的，部署状态却是学习者开车时遇到的。

例如：

  1. 专家总在道路中央行驶。
  2. 学习者方向盘稍微打偏。
  3. 学习者来到路边，看到训练时少见的画面。
  4. 在陌生画面上预测更差。
  5. 车辆进一步偏离正常状态。

这里存在反馈：

$$ \text{预测错误} \longrightarrow \text{状态分布改变} \longrightarrow \text{后续预测更困难}. $$

“违反 i.i.d.”应当怎样理解

原文以违反普通监督学习的 i.i.d. 假设来描述问题。更精确地说，至少有两件事：

  • 一条轨迹内部的样本具有时间依赖；
  • 训练分布与部署分布不同，而且部署分布由学习到的策略决定。

第二件事才是本文的核心。

即使你从许多独立的专家轨迹中采样，使训练数据在统计上更规整，也不能自动解决：

$$ d_{\pi^*}\neq d_{\hat\pi}. $$

其中 $d_{\pi^*}$ 是专家访问的状态分布，$d_{\hat\pi}$ 是学习者访问的状态分布。

1.3 论文的贡献是什么？

贡献可以分为三个层面：

层面核心内容
算法让学习者执行策略，在它访问的状态上请专家标注，并聚合历史数据
理论将这种交互式模仿学习归约为无遗憾在线学习
策略形式最终可以部署一个固定的确定性策略，而不必保留逐步随机切换的策略混合

“固定”指每个时间步使用同一个决策规则；“确定性”指同一输入给出同一输出。它不表示训练过程不能随机，也不表示环境必须确定。

PRELIMINARIES：符号、目标，以及旧方法为什么受限

全文最重要的符号

符号含义
$\Pi$学习者可选择的策略集合
$\pi^*$专家策略
$T$单次任务的决策步数，即 horizon
$d_\pi^t$前 $t-1$ 步执行 $\pi$ 后，第 $t$ 步的状态分布
$d_\pi$整个任务上的平均状态分布
$C(s,a)$真实任务的即时成本，假设在 $[0,1]$
$\ell(s,\pi)$用于模仿专家的替代损失
$J(\pi)$执行策略 $\pi$ 的期望总成本

平均状态分布定义为：

$$ d_\pi=\frac1T\sum_{t=1}^T d_\pi^t. $$

它可以理解为：先均匀随机选一个时间步，再观察该时间步的状态。

若策略允许随机动作，则：

$$ C_\pi(s) = \mathbb E_{a\sim\pi(\cdot\mid s)}[C(s,a)]. $$

总成本为：

$$ J(\pi) = \sum_{t=1}^T \mathbb E_{s\sim d_\pi^t}[C_\pi(s)] = T\mathbb E_{s\sim d_\pi}[C_\pi(s)]. $$

必须区分两类损失：

  • $C$：任务真正关心什么，例如碰撞、跌落、时间消耗；
  • $\ell$：训练时优化什么，例如与专家动作的分类错误或平方误差。

动作像专家，不自动等于任务完成得好。后面所有性能保证都需要处理这道转换。

真正的优化目标：分布也依赖待优化策略

论文写出的目标是：

$$ \hat\pi = \arg\min_{\pi\in\Pi} \mathbb E_{s\sim d_\pi}[\ell(s,\pi)]. $$

这里 $\pi$ 出现了两次：

  1. 决定当前状态的预测损失；
  2. 决定未来会访问什么状态。

而普通监督学习优化的是：

$$ \hat\pi_{\mathrm{sup}} = \arg\min_{\pi\in\Pi} \mathbb E_{s\sim d_{\pi^*}}[\ell(s,\pi)]. $$

在普通监督学习目标中，输入分布是固定的；在本文的优化目标中，输入分布跟着策略变化。

所以，即使对每个固定状态，$\ell(s,\pi)$ 关于策略参数是凸函数，整体目标也未必凸。

DAgger 后面并没有直接求解这个一般非凸目标的全局最优解。 它构造另一种可分析的交互学习过程，获得关于自身访问分布的性能界。

原文 §2.1：监督模仿为什么会出现 $T^2\epsilon$

假设学习者在专家状态分布上的模仿错误为：

$$ \mathbb E_{s\sim d_{\pi^*}}[\ell(s,\pi)] = \epsilon, $$

且 $\ell$ 是动作不一致的 0–1 损失，或其上界。

定理 2.1 给出：

$$ \boxed{ J(\pi)\le J(\pi^*)+T^2\epsilon. } $$

直觉推导：

在简化情形下，前 $t$ 步至少出现一次错误的概率可以用 union bound 控制为 $t\epsilon$。一旦偏离专家轨迹，后续成本可能持续增加，因此：

$$ \sum_{t=1}^T t\epsilon = \frac{T(T+1)}2\epsilon = O(T^2\epsilon). $$

这是帮助理解量级的推导；原定理允许按时间平均的专家分布误差。

两个容易误读的地方：

  • 这是最坏情况上界，并不是说行为克隆在所有任务里都会产生平方级退化。
  • 因为 $C\in[0,1]$，总成本本来就不超过 $T$。当 $T^2\epsilon>T$ 时，该界只是变得不够有信息，不能解释成成本真的能无限超过任务长度。

论文强调的是：存在任务，让小的专家分布误差造成严重的长期后果。

原文 §2.2：Forward Training 怎样改善分布匹配

Forward Training 为不同时间步分别训练：

$$ \pi_1,\pi_2,\ldots,\pi_T. $$

训练第 $t$ 个策略时：

  1. 前 $t-1$ 步执行已经学好的策略；
  2. 获得第 $t$ 步实际会遇到的状态；
  3. 让专家给这些状态标注；
  4. 训练 $\pi_t$。

好处是：训练第 $t$ 步策略时，已经考虑了前面学习者动作造成的影响。

缺点是：

  • 要顺序训练 $T$ 个策略；
  • 策略随时间步改变；
  • 长任务或没有明确终点的任务不方便使用。

这一小节还给出了后面非常关键的定理 2.2。

定理 2.2：把“自身分布上的模仿误差”转换成任务成本

定义：

$$ Q_h^{\pi^*}(s,a) $$

为：从状态 $s$ 开始，第一步执行动作 $a$，之后执行专家，总共执行 $h$ 步的期望成本。

这里还要求 $\ell(s,\pi)$ 是与专家动作不一致的 0–1 损失，或逐状态上界该损失。假设对每个时间步、学习者可能访问的状态和可选动作，一次偏离专家动作造成的额外 cost-to-go 不超过 $u$：

$$ Q_{T-t+1}^{\pi^*}(s,a) - Q_{T-t+1}^{\pi^*}(s,\pi^*(s)) \le u. $$

如果策略在自己访问的状态分布上满足：

$$ \mathbb E_{s\sim d_\pi}[\ell(s,\pi)] = \epsilon, $$

则：

$$ \boxed{ J(\pi)\le J(\pi^*)+uT\epsilon. } $$

这里 $u$ 是全文最不能忽略的量。

它衡量的不是“当前动作错多少”，而是：

现在做错一步，随后交给专家补救，最多会多付出多少长期成本？

例如：

  • 轻微偏离道路，专家几步内可修正：$u$ 可能较小。
  • 一个动作导致不可逆事故，余下任务都失败：$u$ 可能随 $T$ 增长。

因此：

$$ u=O(1) \quad\Rightarrow\quad J(\pi)-J(\pi^*)=O(T\epsilon); $$

但：

$$ u=O(T) \quad\Rightarrow\quad J(\pi)-J(\pi^*)=O(T^2\epsilon). $$

所以“DAgger 把平方误差界变成线性界”需要附带条件。对任意真实任务成本，并没有无条件的线性保证。

证明的主要思路：逐步替换专家。

构造混合执行序列：先执行学习者若干步，之后交给专家。相邻两个序列只在一个时间步不同。将这些差异相加，得到：

$$ \begin{aligned} J(\pi)-J(\pi^*) &= \sum_{t=1}^T \mathbb E_{s\sim d_\pi^t} \left[ Q_{T-t+1}^{\pi^*}(s,\pi) - Q_{T-t+1}^{\pi^*}(s,\pi^*) \right]\\ &\le u\sum_{t=1}^T \mathbb E_{s\sim d_\pi^t}[\ell(s,\pi)]\\ &= uT\epsilon. \end{aligned} $$

当两个策略动作相同，差异为零；动作不同，差异由 $u$ 控制。

这个证明也解释了为什么需要 $d_\pi$：替换到第 $t$ 步时，前面已经执行的是学习者。

上一小节的推导细节

这段推导最难的是第一个等号：为什么两个完整策略的总成本之差，能拆成一系列“只改一个动作”的成本差？ 我们用一个只有 3 步的任务来展开。

先记住，成本越小越好：

  • $J(\pi)$：从头到尾都用学习者的期望总成本。
  • $J(\pi^*)$：从头到尾都用专家的期望总成本。
  • $Q_h^{\pi^*}(s,\pi)$：从状态 $s$ 出发，第一步用学习者，之后用专家，总共走 $h$ 步的期望成本。

特别注意：$Q$ 中括号里的 $\pi$ 只控制第一步，上标 $\pi^*$ 控制后面的步骤。

1. 插入几个“先学习者、后专家”的过渡策略

设 $T=3$，构造四种执行方式：

策略第 1 步第 2 步第 3 步期望总成本
$H_0$专家专家专家$J(H_0)=J(\pi^*)$
$H_1$学习者专家专家$J(H_1)$
$H_2$学习者学习者专家$J(H_2)$
$H_3$学习者学习者学习者$J(H_3)=J(\pi)$

纯代数上：

$$ \begin{aligned} J(\pi)-J(\pi^*) ={}&[J(H_1)-J(H_0)]\\ &+[J(H_2)-J(H_1)]\\ &+[J(H_3)-J(H_2)]. \end{aligned} $$

右边展开后，中间项全部抵消。这叫望远镜求和。

这样，我们就把“整个策略都换掉”，拆成了三次“只替换一个时间步的决策规则”。

2. 看懂其中一项：$J(H_2)-J(H_1)$

这两个策略是：

$$ H_2=(\text{学习者},\text{学习者},\text{专家}), $$
$$ H_1=(\text{学习者},\text{专家},\text{专家}). $$

它们的关系是：

  • 第 1 步都用学习者，所以第 1 步的期望成本相同；
  • 到达第 2 步时，状态分布相同，都是 $d_\pi^2$；
  • 第 2 步，一个用学习者，一个用专家；
  • 第 3 步都交给专家。

假设第 2 步来到状态 $s$，剩下两步的成本分别是：

$$ \underbrace{Q_2^{\pi^*}(s,\pi)}_{\text{现在用学习者，下一步用专家}}, \qquad \underbrace{Q_2^{\pi^*}(s,\pi^*)}_{\text{现在和下一步都用专家}}. $$

所以：

$$ J(H_2)-J(H_1) = \mathbb E_{s\sim d_\pi^2} \left[ Q_2^{\pi^*}(s,\pi) - Q_2^{\pi^*}(s,\pi^*) \right]. $$

虽然后面都用专家，后面的成本不一定相同！ 第 2 步的不同动作可能把系统带到不同状态。$Q$ 正是把这些后续影响也算进去了。

推广到第 $t$ 步：

$$ J(H_t)-J(H_{t-1}) = \mathbb E_{s\sim d_\pi^t} \left[ Q_{T-t+1}^{\pi^*}(s,\pi) - Q_{T-t+1}^{\pi^*}(s,\pi^*) \right]. $$

其中：

  • $d_\pi^t$：因为前 $t-1$ 步都由学习者执行；
  • $T-t+1$：因为从第 $t$ 步到第 $T$ 步，还剩这么多步。

把这些差相加，就得到你选中的第一个等号。

3. 为什么下一行能用 $u\ell(s,\pi)$ 控制？

先考虑确定性策略，并令：

$$ \ell(s,\pi)= \begin{cases} 0,&\pi(s)=\pi^*(s),\\ 1,&\pi(s)\ne\pi^*(s). \end{cases} $$

对于一个固定状态 $s$，分两种情况：

当前动作两个 $Q$ 的差
学习者与专家动作相同差为 $0$：当前动作和后续策略都一样
学习者与专家动作不同根据定理的假设，差至多为 $u$

因此，无论是哪一种情况：

$$ Q_{T-t+1}^{\pi^*}(s,\pi) - Q_{T-t+1}^{\pi^*}(s,\pi^*) \le u\,\ell(s,\pi). $$

这里的假设是：

做错这一步后，即使立即交还给专家，额外造成的长期成本也至多为 $u$。

例如，某状态下：

  • 现在由专家操作，剩余期望成本为 $2$；
  • 现在由学习者操作、随后交回专家，剩余期望成本为 $5$；

那么这次偏离造成的额外成本就是 $5-2=3$。定理要求 $u$ 能统一上界所有相关状态下的这种差。

逐状态的不等式取期望，再对时间求和，就得到：

$$ J(\pi)-J(\pi^*) \le u\sum_{t=1}^T \mathbb E_{s\sim d_\pi^t}[\ell(s,\pi)]. $$

如果使用的是 0–1 损失的上界，这一步同样成立。

4. 最后为什么是 $uT\epsilon$？

这里的 $\epsilon$ 定义为：学习者自己执行任务时，平均每一步的模仿损失：

$$ \epsilon = \mathbb E_{s\sim d_\pi}[\ell(s,\pi)]. $$

而：

$$ d_\pi=\frac1T\sum_{t=1}^T d_\pi^t, $$

所以：

$$ \epsilon = \frac1T \sum_{t=1}^T \mathbb E_{s\sim d_\pi^t}[\ell(s,\pi)]. $$

两边乘以 $T$：

$$ \sum_{t=1}^T \mathbb E_{s\sim d_\pi^t}[\ell(s,\pi)] = T\epsilon. $$

代回去：

$$ \boxed{J(\pi)-J(\pi^*)\le uT\epsilon.} $$

当 $\ell$ 是 0–1 损失时，可以把右边读成：

$$ \underbrace{u}_{\text{一次偏离造成的额外长期成本上界}} \times \underbrace{T\epsilon}_{\text{学习者执行时，预期有多少步与专家动作不同}}. $$

这个直觉之所以能严格成立，靠的就是前面的过渡策略：将整段行为的差异拆开，每次只替换一步，再把差异相加。

原文 §2.3：SMILe 的思路与代价

SMILe 从专家策略开始，每轮训练一个新策略，再逐步把专家的权重移交给这些学习者。

它的更新为：

$$ \pi_n = \pi_{n-1} + \alpha(1-\alpha)^{n-1} (\hat\pi_n-\pi_0), $$

其中 $\pi_0=\pi^*$。

展开后：

$$ \pi_n = (1-\alpha)^n\pi^* + \sum_{j=1}^n \alpha(1-\alpha)^{j-1}\hat\pi_j. $$

最终去掉专家部分并重新归一化，即可部署。

这里混合的是策略的执行概率，不必理解为对方向盘数值求平均。

代价是最终仍保留多个策略，逐步随机切换可能引入不稳定行为。原文所述保证还要求较保守的更新尺度：

$$ \alpha=O(T^{-2}), \qquad N=O(T^2\log T). $$

DAgger 希望保留交互采样的优点，同时最后只部署一个学习者。

DATASET AGGREGATION：DAgger 的完整机制

Algorithm 3.1 实际做了什么

区分两个符号：

  • $\hat\pi_i$：第 $i$ 轮的学习者；
  • $\pi_i$：第 $i$ 轮用于收集数据的行为策略。

行为策略为：

$$ \pi_i = \beta_i\pi^* + (1-\beta_i)\hat\pi_i. $$

意思是在每个决策步骤：

$$ a_t= \begin{cases} \pi^*(s_t), & \text{概率 }\beta_i,\\ \hat\pi_i(s_t), & \text{概率 }1-\beta_i. \end{cases} $$

算法可以写成：

初始化聚合数据集 D 为空
初始化学习者策略

重复 N 轮：
    1. 用当前学习者与专家的混合策略执行任务
    2. 记录访问到的状态
    3. 请专家为这些状态提供正确动作
    4. 将新标注数据加入 D
    5. 用整个 D 训练下一轮学习者

通过验证选择一个学习者策略部署

关键训练数据是：

$$ D_i = \{(s,\pi^*(s)):s\text{ 是本轮访问的状态}\}. $$

注意标签不是学习者刚才执行的动作。

学习者决定“去哪里收集问题”，专家决定“这些问题应该怎样回答”。

如果把学习者自己的动作当作标签重新训练，就不再是原论文的 DAgger。

为什么一定要聚合历史数据

更新可写成：

$$ \hat\pi_{i+1} \in \arg\min_{\pi\in\Pi} \sum_{j=1}^i \sum_{(s,a^*)\in D_j} \ell(\pi(s),a^*). $$

如果每轮只训练最新数据：

  • 修好了当前状态下的错误；
  • 可能又忘了此前状态下的正确行为；
  • 策略变化进一步改变状态分布；
  • 学习过程可能反复摇摆。

聚合数据使新策略必须同时解释过去多轮遇到的状态。

更严格地说，这与在线学习中的 Follow-The-Leader，FTL 对应：每轮选择截至目前累计损失最小的决策。

不过，“聚合数据”本身并不无条件保证稳定或无遗憾，还需要底层优化器与损失满足相应条件。

$\beta_i$ 的作用：控制执行，不是控制标注量

一个简单选择是：

$$ \beta_i=\mathbf1[i=1]. $$

也就是：

  • 第一轮完全由专家执行；
  • 后续完全由学习者执行。

另一个选择是指数衰减：

$$ \beta_i=p^{i-1}, \qquad 0<p<1. $$

保留一些专家动作可能帮助早期学习者脱离毫无进展的状态，获得更多样的数据。

但必须理解：

即使 $\beta_i=0$，原始 DAgger 仍然需要专家给学习者访问的状态提供标签。

“专家不再控制系统”与“专家不再参与训练”是两回事。

论文的一般渐近要求是专家混合比例的平均值趋于零：

$$ \bar\beta_N = \frac1N\sum_{i=1}^N\beta_i \longrightarrow0. $$

用 $\bar\beta_N$ 表示平均值，避免与第 $N$ 轮的 $\beta_N$ 混淆。

理论中的 $\epsilon_N$ 到底是什么

定义：

$$ \epsilon_N = \min_{\pi\in\Pi} \frac1N\sum_{i=1}^N \mathbb E_{s\sim d_{\pi_i}}[\ell(s,\pi)]. $$

它是：

在实际收集到的这一系列状态分布上，策略类中最好的同一个固定策略所能达到的平均损失。

它不是：

  • 专家的错误率；
  • 最后一个学习者的训练损失；
  • 每轮分别挑一个最优策略后的平均损失；
  • $\min_\pi \mathbb E_{d_\pi}\ell(s,\pi)$。

尤其应比较下面两个式子：

$$ \underbrace{ \min_\pi\frac1N\sum_i \mathbb E_{d_{\pi_i}}\ell(s,\pi) }_{\text{固定同一个比较策略}} $$

与

$$ \underbrace{ \frac1N\sum_i\min_\pi \mathbb E_{d_{\pi_i}}\ell(s,\pi) }_{\text{允许每轮换比较策略}}. $$

后者通常更小，原文并没有直接保证与后者竞争。

这也意味着：如果学习者表达能力不足，聚合分布上根本不存在低误差策略，那么 $\epsilon_N$ 会很大。DAgger 不能凭数据收集机制消除模型能力限制。

定理 3.1—3.4：先看结果，再看证明

在原文给定的有界、强凸损失及专家混合衰减条件下，主要结果如下。涉及任意真实任务成本 $C$ 的定理 3.2 和 3.4 还要求 $\ell$ 上界与专家动作不一致的 0–1 损失，并满足定理 2.2 的 cost-to-go 差值上界 $u$。这里 $\tilde O$ 隐藏对数因子，表中的轮数表示达到该精度的充分量级。

情形训练轮数的充分量级保证
无限样本，定理 3.1$N=\tilde O(T)$存在 $\hat\pi$，自身分布损失 $\le\epsilon_N+O(1/T)$
无限样本，定理 3.2$N=\tilde O(uT)$存在 $\hat\pi$，$J(\hat\pi)\le J(\pi^*)+uT\epsilon_N+O(1)$
每轮常数条轨迹，定理 3.3$N=O(T^2\log(1/\delta))$以至少 $1-\delta$ 概率，自身分布损失 $\le\hat\epsilon_N+O(1/T)$
每轮常数条轨迹，定理 3.4$N=O(u^2T^2\log(1/\delta))$以至少 $1-\delta$ 概率，$J(\hat\pi)\le J(\pi^*)+uT\hat\epsilon_N+O(1)$

其中 $\hat\epsilon_N$ 是聚合采样数据上的最佳经验损失。

为什么需要每步误差项达到 $O(1/T)$？

因为转为整个任务的成本时会乘以 $T$：

$$ T\cdot O(1/T)=O(1). $$

这里的保证都是“生成的策略序列中存在一个好策略”，不是“最后一个一定好”。

算法因此写的是通过验证选择策略。定理没有免除策略选择所需的额外评估成本。

THEORETICAL ANALYSIS：为什么无遗憾能够解决这个问题

这一章是论文的理论核心。整个证明可以拆成三步：

  1. 构造在线学习损失；
  2. 控制专家混合造成的分布偏差；
  3. 把平均性能转换为“存在一个好策略”。

原文 §4.1：什么叫 no-regret

在线学习中，第 $i$ 轮先选择策略 $\hat\pi_i$，相对于其他可能的选择策略来说，对应的损失函数为 $\ell_i$。

累计遗憾为：

$$ R_N = \sum_{i=1}^N\ell_i(\hat\pi_i) - \min_{\pi\in\Pi} \sum_{i=1}^N\ell_i(\pi). $$

平均遗憾为：

$$ \begin{aligned} \frac{R_N}{N} &= \frac{1}{N}\sum_{i=1}^N\ell_i(\hat\pi_i) - \frac{1}{N}\min_{\pi\in\Pi}\sum_{i=1}^N\ell_i(\pi) \\ &= \frac{1}{N}\sum_{i=1}^N\ell_i(\hat\pi_i) - \epsilon_N \le\gamma_N. \end{aligned} $$

若：

$$ \gamma_N\longrightarrow0, $$

就称算法无遗憾。

它表示：

回头看整个学习过程，我逐轮做出的决策，平均而言不会比事先知道全部损失函数、然后选出的最佳固定策略差很多。

它不表示：

  • 每一轮损失都下降；
  • 每一轮都接近该轮最优；
  • 策略参数一定收敛；
  • 绝对损失一定很小。

最后一点尤其重要：如果最优固定策略本身就很差，无遗憾算法仍可能取得很差的绝对性能。

如何把 DAgger 写成在线学习

定义第 $i$ 轮损失：

$$ \boxed{ \ell_i(\pi) = \mathbb E_{s\sim d_{\pi_i}}[\ell(s,\pi)]. } $$

本轮执行策略产生一个状态分布；这个分布定义了一个监督学习问题。

在评估这一轮的候选策略 $\pi$ 时，分布 $d_{\pi_i}$ 是固定的。

这与直接优化：

$$ \mathbb E_{s\sim d_\pi}[\ell(s,\pi)] $$

不同：后者的分布会随候选策略一起改变。

DAgger 的 FTL 更新相当于：

$$ \hat\pi_{i+1} \in \arg\min_{\pi\in\Pi} \sum_{j=1}^i\ell_j(\pi). $$

实际运行时，用采样数据近似这些期望。

这就是“归约”的具体含义：将困难的交互任务组织成一串监督损失，再调用具有无遗憾性质的在线学习算法。

为什么强调强凸性

FTL 并不是对任意损失序列都无遗憾。

若参数为 $\theta$，强凸性可写为：

$$ \ell_i(\theta') \ge \ell_i(\theta) + \nabla\ell_i(\theta)^\top(\theta'-\theta) + \frac{\mu}{2}\|\theta'-\theta\|^2, \qquad \mu>0. $$

配合适当的梯度有界等条件，强凸性可以控制优化解在相邻轮次间的变化，并得到类似：

$$ R_N=O(\log N), \qquad \gamma_N=O\left(\frac{\log N}{N}\right). $$

需要区分：

  • 论文的一般归约只要求底层算法无遗憾；
  • 用 FTL 实现并取得较快速度时，强凸性提供了一个充分条件；
  • 不是任意神经网络训练过程都自动满足这些条件。

平方误差关于网络输出是凸的，也不意味着它关于整个深度网络参数是凸的。

对上一节的解释

先把 $\theta$ 解释清楚。

$\pi$ 表示策略，即“输入状态、输出动作”的函数；$\theta$ 表示这个函数中需要通过训练确定的参数，因此也可以把策略写成 $\pi_\theta$。

例如，线性控制器：

$$ \pi_\theta(s)=w^\top x(s)+b, \qquad \theta=(w,b). $$

这里 $x(s)$ 是状态特征，$\theta$ 就是权重和偏置组成的参数向量。如果策略是神经网络，$\theta$ 就包含网络里的所有待训练权重和偏置。

所以：

$$ \ell_i(\theta) $$

表示“参数为 $\theta$ 的策略，在第 $i$ 轮数据分布上的损失”。$\theta’$ 则是另一组参数，撇号不是求导的意思。

先看普通凸函数满足的条件：

$$ f(\theta') \ge f(\theta)+\nabla f(\theta)^\top(\theta'-\theta). $$

右边正是一阶泰勒近似。几何上，它是函数在 $\theta$ 处的切线；多维时是切平面。

这个不等式的意思是：

凸函数的实际值，始终不低于任何一个点处的切平面。

强凸性进一步要求：

$$ \boxed{ f(\theta') \ge \underbrace{f(\theta)+\nabla f(\theta)^\top(\theta'-\theta)} _{\text{切平面}} + \underbrace{\frac{\mu}{2}\|\theta'-\theta\|^2} _{\text{至少还要高出这么多}}. } $$

因此，强凸函数不仅位于切平面上方，还必须以一定速度向上弯曲。这个“最低弯曲程度”就是 $\mu>0$。

例如，取一维函数：

$$ f(\theta)=\theta^2. $$

因为 $f’(\theta)=2\theta$，所以：

$$ \underbrace{(\theta')^2}_{f(\theta')} = \underbrace{\theta^2+2\theta(\theta'-\theta)} _{\text{一阶泰勒近似}} + \underbrace{(\theta'-\theta)^2}_{\text{二次项}}. $$

它恰好满足强凸性，取 $\mu=2$。

在最低点 $\theta=0$ 处，这个条件尤其直观：

$$ f(\theta')\ge f(0)+\frac{\mu}{2}|\theta'|^2. $$

意思是：离最低点越远，损失至少按距离的平方增长。

------ 和泰勒展开的关系 ------

对泰勒展开的联想，还可以更精确地写出来。

如果 $f$ 二阶连续可微，令 $\Delta=\theta’-\theta$，局部二阶展开为：

$$ f(\theta+\Delta) = f(\theta) +\nabla f(\theta)^\top\Delta +\frac12\Delta^\top\nabla^2 f(\theta)\Delta +o(\|\Delta\|^2). $$

其中 $\nabla^2 f(\theta)$ 是 Hessian 矩阵，描述各个方向的曲率。

在凸参数域上，如果每个位置、每个方向的曲率都至少为 $\mu$，即：

$$ \nabla^2 f(\theta)\succeq\mu I, $$

就能得到前面的强凸不等式。在一维时，这简化为：

$$ f''(\theta)\ge\mu>0. $$

这里不能只把泰勒展开的余项删掉就得到强凸性；需要的是沿两点之间整条路径的曲率都有统一下界。

也不是“看起来像碗”就足够。例如：

$$ f(\theta)=\theta^4 $$

是严格凸函数，但在零点处：

$$ f''(0)=0. $$

因此无法在包含零点附近的区间上找到统一的 $\mu>0$，它在那里不是强凸的。

------ 和泰勒展开的关系 end ------

最后，这为什么对 FTL 有帮助？

FTL 每轮最小化此前的累计损失：

$$ \theta_{i+1} = \arg\min_\theta \sum_{j=1}^{i}\ell_j(\theta). $$

如果每个 $\ell_j$ 都是 $\mu$-强凸的，那么累计损失就是 $i\mu$-强凸的：随着数据轮数增加，累计目标对偏离最优参数的惩罚越来越强。

在梯度有界等条件下，新加入一轮损失，就越来越难把最优参数推得很远。相邻更新的变化可以控制在类似：

$$ \|\theta_{i+1}-\theta_i\|=O(1/i) $$

的量级。这个稳定性最终带来：

$$ R_N=O\left(\sum_{i=1}^N\frac1i\right) =O(\log N). $$

所以这部分的逻辑是：

损失具有统一的最低曲率 → 累计目标越来越能约束参数变化 → FTL 的更新更稳定 → 可以控制累计遗憾。

本小节的剩下部分解释上面的 $O(1/i)$ 是怎么来的。

可以把这个 $O(1/i)$ 推出来，而且在下面的条件下能得到具体上界：

$$ \boxed{ \|\theta_{i+1}-\theta_i\| \le \frac{G}{i\mu}. } $$

其中 $\mu$ 是每轮损失的强凸系数，$G$ 是每轮损失梯度的统一上界。先考虑参数不受约束、损失可微、每次都精确求出最优解的情况。

第一步：写出更新前后的目标函数。

令累计损失为：

$$ F_i(\theta)=\sum_{j=1}^i\ell_j(\theta). $$

FTL 的相邻两次参数分别满足：

$$ \theta_i=\arg\min_\theta F_{i-1}(\theta), \qquad \theta_{i+1}=\arg\min_\theta F_i(\theta). $$

因此，一阶最优条件给出：

$$ \nabla F_{i-1}(\theta_i)=0, \qquad \nabla F_i(\theta_{i+1})=0. $$

新加入的只有 $\ell_i$，所以在旧最优点处，新目标的梯度为：

$$ \begin{aligned} \nabla F_i(\theta_i) &=\nabla F_{i-1}(\theta_i)+\nabla\ell_i(\theta_i)\\ &=\nabla\ell_i(\theta_i). \end{aligned} $$

如果每轮梯度满足：

$$ \|\nabla\ell_i(\theta)\|\le G, $$

那么：

$$ \boxed{\|\nabla F_i(\theta_i)\|\le G.} $$

也就是说，加入新损失后，旧最优点处出现的梯度大小至多为 $G$。

第二步：强凸性把“梯度大小”转成“离最优点的距离”。

一个 $\lambda$-强凸的可微函数 $F$ 满足：

$$ \bigl(\nabla F(x)-\nabla F(y)\bigr)^\top(x-y) \ge \lambda\|x-y\|^2. $$

这个性质可以直接从强凸定义得到：分别写出 $F(x)$ 在 $y$ 处的下界，以及 $F(y)$ 在 $x$ 处的下界，再相加即可。

若 $y$ 是最优点，$\nabla F(y)=0$，则上式成为：

$$ \nabla F(x)^\top(x-y) \ge\lambda\|x-y\|^2. $$

另一方面，由柯西–施瓦茨不等式：

$$ \nabla F(x)^\top(x-y) \le\|\nabla F(x)\|\,\|x-y\|. $$

柯西–施瓦茨不等式： 在实数向量空间中，任意两个向量 u 和 v，$|u^\top v| \le \|u\| \|v\|$ .

两者合起来，约掉一个距离因子，得到：

$$ \boxed{ \|x-y\| \le\frac{\|\nabla F(x)\|}{\lambda}. } $$

如果 $x=y$，这个界当然也成立。

它的含义是：曲率越大，同样大小的梯度所对应的“离最优点距离”就越小。

第三步：代入累计目标的曲率。

每个 $\ell_j$ 都是 $\mu$-强凸的，所以它们的和 $F_i$ 是 $i\mu$-强凸的。

在上式中取：

$$ F=F_i,\qquad x=\theta_i,\qquad y=\theta_{i+1},\qquad \lambda=i\mu, $$

就得到：

$$ \begin{aligned} \|\theta_i-\theta_{i+1}\| &\le \frac{\|\nabla F_i(\theta_i)\|}{i\mu}\\ &= \frac{\|\nabla\ell_i(\theta_i)\|}{i\mu}\\ &\le \frac{G}{i\mu}. \end{aligned} $$

当 $G,\mu$ 不随轮数变化时，这就是：

$$ \|\theta_{i+1}-\theta_i\|=O(1/i). $$

证毕。

还可以用一个一维例子直接看到这个量级。假设：

$$ \ell_j(\theta)=\frac{\mu}{2}(\theta-a_j)^2. $$

每轮损失都希望参数接近自己的 $a_j$。累计损失的最优点就是这些 $a_j$ 的平均值：

$$ \theta_i=\frac1{i-1}\sum_{j=1}^{i-1}a_j. $$

加入第 $i$ 个目标 $a_i$ 后：

$$ \theta_{i+1} = \frac{(i-1)\theta_i+a_i}{i}. $$

于是：

$$ \boxed{ \theta_{i+1}-\theta_i = \frac{a_i-\theta_i}{i}. } $$

如果 $a_i$ 与旧均值的距离始终有界，每次更新自然就是 $O(1/i)$：新加入的一轮，在累计的 $i$ 轮里只占 $1/i$ 的影响。

一般强凸损失未必能写成平均值，但前面的梯度推导给出了同样的控制。这个估计依赖梯度有界与精确优化；若新损失的梯度可以无限大，或者每轮只近似求解，就需要另外计入这些影响。

Lemma 4.1：混合执行和纯学习者执行有多不同

训练用的是：

$$ \pi_i=\beta_i\pi^*+(1-\beta_i)\hat\pi_i, $$

部署用的是：

$$ \hat\pi_i. $$

因此还需要控制：

$$ d_{\pi_i} \quad\text{与}\quad d_{\hat\pi_i} $$

之间的差异。

在 $T$ 步中，混合策略一次也不选择专家的概率为：

$$ (1-\beta_i)^T. $$

在这个事件上，行为与纯学习者一致。于是有：

$$ \begin{aligned} \|d_{\pi_i}-d_{\hat\pi_i}\|_1 &\le 2\left[1-(1-\beta_i)^T\right]\\ &\le 2T\beta_i. \end{aligned} $$

再结合两个分布的 $L_1$ 距离至多为 2：

$$ \boxed{ \|d_{\pi_i}-d_{\hat\pi_i}\|_1 \le 2\min(1,T\beta_i). } $$

注意，若使用标准定义：

$$ \operatorname{TV}(p,q)=\frac12\|p-q\|_1, $$

则总变差距离对应少一个系数 2。原文这里写的是 $L_1$ 范数形式。

直观含义：

单步专家介入概率很小，不代表整条长轨迹中专家几乎不起作用。只要 $T\beta_i$ 不小，训练分布与纯学习者分布仍可能相差很大。

上一小节的详细推导

关键是把混合策略产生的状态分布拆成两部分：整段执行都没有选择专家，以及至少选择过一次专家。

暂时省略下标 $i$，写成：

  • $\hat\pi$：纯学习者；
  • $\pi$：每一步以概率 $\beta$ 选择专家、以概率 $1-\beta$ 选择学习者。

每一步的选择是独立的。

第一步：按“是否选过专家”拆分分布。

令事件 $E$ 表示“$T$ 步中一次也没选择专家”。它的概率是：

$$ q:=P(E)=(1-\beta)^T. $$

在事件 $E$ 下，每一步都执行学习者，因此状态分布就是 $d_{\hat\pi}$。

再用 $r$ 表示“至少选过一次专家”条件下的状态分布。我们不需要知道 $r$ 具体是什么。

由全概率公式：

$$ \boxed{ d_\pi=q\,d_{\hat\pi}+(1-q)\,r. } $$

这表示：混合策略有比例 $q$ 的执行完全等同于学习者，剩余比例 $1-q$ 的执行可能不同。

第二步：算它与纯学习者分布的距离。

两边减去 $d_{\hat\pi}$：

$$ \begin{aligned} d_\pi-d_{\hat\pi} &=q\,d_{\hat\pi}+(1-q)r-d_{\hat\pi}\\ &=(1-q)(r-d_{\hat\pi}). \end{aligned} $$

所以：

$$ \boxed{ \|d_\pi-d_{\hat\pi}\|_1 =(1-q)\|r-d_{\hat\pi}\|_1. } $$

现在用到一个基本事实：任意两个概率分布的 $L_1$ 距离至多为 2。

以离散状态为例：

$$ \begin{aligned} \|r-d_{\hat\pi}\|_1 &=\sum_s|r(s)-d_{\hat\pi}(s)|\\ &\le\sum_s\bigl(r(s)+d_{\hat\pi}(s)\bigr)\\ &=1+1=2. \end{aligned} $$

因此：

$$ \|d_\pi-d_{\hat\pi}\|_1 \le2(1-q) = \boxed{2\left[1-(1-\beta)^T\right]}. $$

这里的直觉是：只有“至少选过一次专家”的那部分执行可能造成分布差异；即使那部分的分布完全不同，距离也最多是 2。

第三步：为什么又能上界为 $2T\beta$？

令 $A_t$ 表示“第 $t$ 步选择专家”。那么：

$$ 1-(1-\beta)^T = P\left(\bigcup_{t=1}^T A_t\right). $$

根据 union bound（并集概率不超过各事件概率之和）：

$$ P\left(\bigcup_{t=1}^T A_t\right) \le \sum_{t=1}^T P(A_t) = T\beta. $$

于是：

$$ \boxed{ \|d_\pi-d_{\hat\pi}\|_1 \le 2\left[1-(1-\beta)^T\right] \le 2T\beta. } $$

例如，$T=10,\ \beta=0.01$，至少选过一次专家的概率为：

$$ 1-0.99^{10}\approx0.0956. $$

所以：

$$ \|d_\pi-d_{\hat\pi}\|_1 \le0.1912 \le0.2. $$

注意这是上界。即使选择了专家，如果专家恰好给出与学习者相同的动作，也可能根本没有改变轨迹。因此，“选过专家”只是轨迹可能发生变化的条件，并不意味着一定变化。

Theorem 4.1：论文最重要的不等式

假设：

$$ 0\le\ell(s,\pi)\le\ell_{\max}. $$

把定理写成更容易理解的形式，记为 (★) 式：

$$ \boxed{ \min_{1\le i\le N} \mathbb E_{s\sim d_{\hat\pi_i}} [\ell(s,\hat\pi_i)] \le \epsilon_N+\gamma_N+ \frac{2\ell_{\max}}N \sum_{i=1}^N\min(1,T\beta_i). } $$

右侧三项分别是：

项含义
$\epsilon_N$策略类在聚合分布上的可达到误差
$\gamma_N$在线算法未能达到最佳固定策略的代价
混合项训练时有专家介入，与部署时纯学习者执行的分布差异

原文假设 $\beta_i$ 非增，并定义最后一个满足 $\beta_i>1/T$ 的轮次为 $n_\beta$，于是将混合项写成：

$$ \frac{2\ell_{\max}}N \left[ n_\beta + T\sum_{i=n_\beta+1}^N\beta_i \right]. $$

证明可以完整压缩为下面三行：

$$ \begin{aligned} \min_i \mathbb E_{d_{\hat\pi_i}}\ell(s,\hat\pi_i) &\le \frac1N\sum_i \mathbb E_{d_{\hat\pi_i}}\ell(s,\hat\pi_i)\\ &\le \frac1N\sum_i \mathbb E_{d_{\pi_i}}\ell(s,\hat\pi_i) + \frac{2\ell_{\max}}N \sum_i\min(1,T\beta_i)\\ &\le \epsilon_N+\gamma_N + \frac{2\ell_{\max}}N \sum_i\min(1,T\beta_i). \end{aligned} $$

三行分别用了：

  1. 最小值不超过平均值。
  2. 状态分布距离界。
  3. 在线学习的遗憾界，上文中有一个不等式可以解释。

这就是整篇论文最值得掌握的证明结构。

对于第二行，需要另一个基本关系：对于有界函数 $f$，如果 $|f(s)|\le M$，那么：

$$ |\mathbb E_p f-\mathbb E_q f| \le M\|p-q\|_1. $$

以离散状态为例：

$$ \begin{aligned} |\mathbb E_p f-\mathbb E_q f| &= \left|\sum_s[p(s)-q(s)]f(s)\right|\\ &\le \sum_s|p(s)-q(s)|\,|f(s)|\\ &\le M\sum_s|p(s)-q(s)|. \end{aligned} $$

于是：

$$ \begin{aligned} \mathbb E_{d_{\hat\pi_i}}\ell(s,\hat\pi_i) &\le \mathbb E_{d_{\pi_i}}\ell(s,\hat\pi_i) + \ell_{\max}\|d_{\hat\pi_i}-d_{\pi_i}\|_1\\ &\le \mathbb E_{d_{\pi_i}}\ell(s,\hat\pi_i) + 2\ell_{\max}\min(1,T\beta_i). \end{aligned} $$

注意，此处被评估的策略始终是同一个 $\hat\pi_i$；改变的只有状态分布：

$$ d_{\hat\pi_i} \longrightarrow d_{\pi_i}. $$

额外项用来支付这次换分布的代价。

所以其实可以这样理解其意义： 要约束一个纯学习者部署时的模仿损失，可以用它在本轮采样分布上的模仿损失，加上一个分布差异附加项，作为上界。 右边虽然用混合策略 $\pi_i$ 收集状态，但在这些状态上，仍然比较学习者 $\hat\pi_i(s)$ 与专家 $\pi^*(s)$ 的动作。并不是评估混合策略自身的动作损失。

为什么最简单的 $\beta_i$ 已经足够

若：

$$ \beta_1=1,\qquad \beta_i=0\quad(i\ge2), $$

则：

$$ \frac{2\ell_{\max}}N \sum_i\min(1,T\beta_i) = \frac{2\ell_{\max}}N. $$

所以：

$$ \min_i \mathbb E_{d_{\hat\pi_i}}\ell(s,\hat\pi_i) \le \epsilon_N+\gamma_N+\frac{2\ell_{\max}}N. $$

若 $\gamma_N=O(\log N/N)$，取足够大的、约为 $T$ 乘对数因子的训练轮数，就能让额外误差达到 $O(1/T)$。

若用指数衰减：

$$ \beta_i=(1-\alpha)^{i-1}, $$

原文给出混合项中括号的平均量级：

$$ \frac1N \left[ n_\beta+ T\sum_{i>n_\beta}\beta_i \right] \le \frac{\log T+1}{N\alpha}. $$

因此，衰减足够快的专家介入不会阻碍渐近保证。

“存在一个好策略”不等于“解出了原始目标”

这是对理论力度的关键判断。

式（★）比较的是：

$$ \min_\pi \frac1N\sum_i \mathbb E_{d_{\pi_i}}\ell(s,\pi), $$

并没有直接比较：

$$ \min_\pi \mathbb E_{d_\pi}\ell(s,\pi). $$

因此，不能从式（★）直接声称：

DAgger 找到了策略类中、按各自状态分布计算的全局最优策略。

要让绝对误差足够小，还需要额外条件，例如聚合状态分布上确实存在能够很好模仿专家的策略。

原文还指出，均匀随机挑选一个历史策略，并让它执行整条轨迹，也能得到相应的平均保证。但这与“每一步随机挑一个策略”不同，不能混淆。

Theorem 4.2：有限数据与轨迹相关性

实际每轮只收集 $m$ 条轨迹。关于这点，之前折叠了一些细节，实际上，每轮要重复执行 $m$ 次任务，每次任务包含 $T$ 个时间步。具体来说：

初始化学习者 π̂₁
初始化聚合数据集 D = 空

for i = 1, ..., N:                  # 第 i 轮训练
    固定当前学习者 π̂ᵢ
    构造本轮执行策略 πᵢ
    本轮数据集 Dᵢ = 空

    for j = 1, ..., m:              # 本轮第 j 次驾驶
        重置环境，采样初始状态

        for t = 1, ..., T:          # 本次驾驶第 t 次决策
            观察状态 sᵢⱼₜ
            获取专家标签 π*(sᵢⱼₜ)
            将状态与专家标签加入 Dᵢ

            以概率 βᵢ 执行专家动作
            否则执行当前学习者 π̂ᵢ 的动作
            环境进入下一状态

    D = D ∪ Dᵢ
    用聚合数据 D 训练下一轮学习者 π̂ᵢ₊₁

DAgger 并不为每个时间步分别训练一个策略。那是前文介绍的 Forward Training。DAgger 在一轮数据收集期间使用固定的当前学习者，收集完数据后才更新它。

定义最佳经验损失：

$$ \hat\epsilon_N = \min_{\pi\in\Pi} \frac1N\sum_{i=1}^N \mathbb E_{s\sim D_i}[\ell(s,\pi)]. $$

有限样本界为：

$$ \boxed{ \begin{aligned} \min_i \mathbb E_{d_{\hat\pi_i}} [\ell(s,\hat\pi_i)] \le\;& \hat\epsilon_N+\gamma_N\\ &+\frac{2\ell_{\max}}N \left[ n_\beta+ T\sum_{i>n_\beta}\beta_i \right]\\ &+\ell_{\max} \sqrt{\frac{2\log(1/\delta)}{mN}}, \end{aligned} } $$

以至少 $1-\delta$ 的概率成立。这里的 $\gamma_N$ 对应采样损失上的平均遗憾。

原论文的 Theorem 4.2 用 Azuma–Hoeffding 不等式控制上述采样误差。

为什么分母是 $mN$，而不是 $mNT$？

因为同一条轨迹中的 $T$ 个状态并不能直接当作 $T$ 个独立样本。

原文将第 $i$ 轮第 $j$ 条轨迹的误差差值写成：

$$ Y_{ij} = \mathbb E_{s\sim d_{\pi_i}} [\ell(s,\hat\pi_i)] - \frac1T\sum_{t=1}^T \ell(s_{ijt},\hat\pi_i). $$

在给定此前历史后：

  • 当前策略已经确定；
  • 新采样轨迹的平均损失具有正确的条件期望；
  • 因此这些差值构成鞅差序列；
  • 可以使用 Azuma–Hoeffding 不等式。

这避免了错误地假设轨迹中每一帧独立。

要使抽样误差达到 $O(1/T)$，需要：

$$ mN=O(T^2\log(1/\delta)) $$

量级的轨迹数。

注意样本单位：这是轨迹数，不是状态标注数。 每条轨迹若包含 $T$ 个需要标注的状态，专家调用量还要考虑这个额外因子。

原文提出，利用强凸性的更精细分析可能改善这个界；应把这一点视作改进方向，而不是本文已经完成的证明。

EXPERIMENTS：实验究竟验证了哪些主张

论文没有现代意义上的深度网络架构。它使用简单的线性回归和 SVM，主要比较数据收集与训练流程。

原文共有五张图：

  • 图 1、图 3：任务画面；
  • 图 2、图 4、图 5：实验结果曲线。

下面按图号解读；结果表是为了阅读方便重新整理的，并非原论文中的表格。

Super Tux Kart：连续控制与恢复能力

任务和模型。

车辆在固定赛道上以固定速度行驶，模型只控制转向：

$$ \hat y=w^\top x+b. $$

输入由游戏画面缩小到 $25\times19$ 后的 LAB 色彩值构成。训练使用岭回归：

$$ L(w,b) = \frac1n\sum_{i=1}^n (w^\top x_i+b-y_i)^2 + \frac{\lambda}{2}w^\top w, $$

其中：

$$ \lambda=10^{-3}. $$

控制频率为 5 Hz，专家是人类，转向标签位于 $[-1,1]$。

图 1 的意义。

赛道悬浮在空中，车辆偏离赛道会跌落，再被放回赛道中央。这个环境适合观察：

  • 是否会偏离；
  • 偏离后能否修正；
  • 错误是否不断放大。

图 2：横轴为训练样本量，纵轴为每圈平均跌落次数，越低越好。

结果曲线带有 95% 置信区间：

方法原图与正文表现
普通监督学习增加专家数据后没有持续改善，仍频繁跌落
SMILe有改善，但 20 轮后仍约每圈跌落两次
DAgger5 轮后已很少跌落；15 轮后的所报告评估中没有跌落

这里 DAgger 使用最简单的：

$$ \beta_i=\mathbf1[i=1]. $$

图 2 的主要证据是：更多同类专家数据，不等于覆盖了学习者需要的恢复状态。

如何评价？

这个实验很好地隔离了分布问题，因为底层学习器很简单。

但“评估中没有跌落”不能解释为安全证明；训练与评估也围绕特定赛道展开，不能据此断言它能泛化到任意道路。

Super Mario Bros：离散动作、卡住问题与混合比例

专家与学习者。

专家是一个能够访问游戏内部状态、模拟未来动作后果的近似最优规划器。

学习者输出四个二元动作：

$$ a= (a_{\mathrm{left}}, a_{\mathrm{right}}, a_{\mathrm{jump}}, a_{\mathrm{speed}}). $$

四个动作分别由线性 SVM 预测：

$$ \hat a_k = \mathbf1[w_k^\top x+b_k>0]. $$

输入不是直接端到端处理原始像素，而是较丰富的手工表示：

  • Mario 周围 $22\times22$ 网格；
  • 每格 14 个二元语义特征；
  • 最近四帧的特征；
  • 最近六个动作；
  • Mario 的形态及是否接地等状态。

总计 27,152 个稀疏二元特征。

因此，这个实验包含明显的专家与学生能力差异：专家有内部状态和规划能力，学生使用有限特征和线性决策。

图 3 展示游戏场景；图 4 展示每关平均前进距离，越高越好。

每轮收集 5,000 个数据点，运行 20 轮。正文报告：

$$ \text{DAgger，}\beta_i=0.5^{i-1}: \quad 3030, $$
$$ \text{DAgger，仅首轮专家执行}: \quad 2980. $$

从图 4 可以观察到：

  • 普通监督学习大约停留在 1,450 附近；
  • DAgger 的快速衰减版本整体表现最好；
  • $\beta_i=0.9^{i-1}$ 的版本改善更慢；
  • SEARN 的纯策略迭代版本波动明显。

其中普通监督学习的数值是读图近似，3030 和 2980 是正文给出的结果。

为什么行为克隆容易卡住？

专家在离障碍物还有一段距离时就跳过去了。

于是专家数据缺少：

已经贴到障碍物边缘、跳跃时机已经错过，现在应该怎么办？

学习者却经常进入这种状态，随后不断重复无效动作。

DAgger 会收集这些状态，并获得专家的脱困动作。这是整个实验中最直观的机制证据。

为什么少量专家介入反而有帮助？

完全由早期学习者执行时，可能产生大量重复的“原地卡住”状态。少量专家介入让它脱困，继续接触后面的场景。

所以 $\beta_i$ 存在实际权衡：

  • 太大：训练过于依赖专家，学习者真实分布覆盖不足；
  • 太小：早期可能困在低信息、重复状态中；
  • 适当衰减：既暴露错误，又保持数据多样性。

还应注意：关卡平均长度约为 4200—4300，3030 的平均前进距离并不等于成功率接近 100%。

Handwriting Recognition：为何结构化预测也是模仿学习

任务是逐字符识别一个手写单词。

模型从左到右预测：

$$ \hat y_t = \pi(x_t,\hat y_{t-1}). $$

其中 $x_t$ 是当前字符图像，$\hat y_{t-1}$ 是上一个字符的预测。

普通监督训练可能使用：

$$ (x_t,y_{t-1}^*)\mapsto y_t^*, $$

而测试时使用：

$$ (x_t,\hat y_{t-1})\mapsto\hat y_t. $$

这又出现了训练与部署输入不一致。

可以把它解释为一个简单的决策过程：

  • 状态：当前字符图像及之前预测；
  • 动作：预测当前字符；
  • 转移：把这个预测传给下一个位置；
  • 专家：训练集中的正确字符标签。

这里的特殊便利是： 上一个字符即使预测错了，当前图像的正确字符标签仍然已知。因此可以在模型生成的错误上下文上继续提供正确监督。

并非所有结构化任务都有这么容易获得的“偏离后专家”；复杂解析或生成任务可能需要额外设计。

实验设置。

  • 约 6600 个单词，超过 52,000 个字符；
  • 十折实验，每次九折训练、一折测试；
  • 当前字符使用 $8\times16=128$ 个像素特征；
  • 上一个预测字符使用 26 维编码；
  • 采用线性 SVM 和单遍贪心解码。

图 5：横轴为训练轮数，纵轴为测试字符准确率。

正文给出的主要结果：

方法字符准确率
独立识别每个字符约 82%
加入前一个字符，但训练时总给正确前缀约 83.6%
DAgger可达到约 85.5%

从 83.6% 到 85.5%：

$$ \text{绝对准确率提升}=1.9\text{ 个百分点}. $$

换算成错误率的相对下降：

$$ \frac{16.4-14.5}{16.4}\approx11.6\%. $$

后一数值是根据正文数据计算的，不是原文直接报告。

最值得注意的比较结果：

调参后的 SEARN，以及该任务中的纯策略迭代版本，表现与 DAgger 接近。图 5 并不支持“DAgger 全面优于 SEARN”。

作者的解释是：学习者只改变输入中的一小部分——前一个字符的特征；当前字符图像并没有被改变。因此该任务中的分布反馈没有机器人控制那么剧烈。

三个实验放在一起，应当得出怎样的结论

证据比较充分地支持：

  1. 单纯增加专家轨迹，可能无法消除学习者特有的错误状态。
  2. 收集学习者访问状态并获得专家纠正，可以明显改善性能。
  3. 聚合数据、部署单个策略，在这些任务中具有实用优势。
  4. 专家混合比例会影响数据覆盖和训练速度。

证据不足以支持：

  • 任意任务上都优于行为克隆；
  • 任意神经网络上都有同样的理论保证；
  • 任意真实成本都获得 $O(T\epsilon)$ 界；
  • 训练全过程安全；
  • 最后一个策略必然最好；
  • 三个实验已经验证了所有理论样本复杂度量级。

FUTURE WORK

原文最后提出三个方向：

方向要进一步解决什么
更复杂的结构化解码超越单遍贪心预测，例如多遍或搜索式解码
结合逆最优控制学习供规划器使用的成本函数，而不只直接预测动作
利用 cost-to-go 扩展让数据聚合与在线学习处理更一般的强化学习问题

第三个方向尤其值得注意。

DAgger 的监督信号主要回答：

$$ \text{“专家在这个状态会做什么？”} $$

但真实控制还关心：

$$ \text{“如果选另一个动作，长期后果有多坏？”} $$

这正是后续 AggreVaTe 工作展开的方向。

后续研究有哪些批评

有，而且不少来自延续这条研究路线的学者，包括原作者本人。

这些批评主要是在说明理论与实际应用的边界，并不等于原始定理被推翻。

批评一：动作不一致损失没有充分反映错误的长期严重程度

来源：Ross 与 Bagnell，2014，AggreVaTe。

后续论文直接指出：仅仅学习与专家动作一致，无法充分利用动作成本信息。

他们使用悬崖驾驶来说明：在悬崖边，一个偏差动作可能造成不可逆灾难；其他偏差动作可能只是稍微绕路。若都按一次分类错误处理，就没有体现后果的差别。

可以用下面的比较理解：

$$ \ell_{\mathrm{DAgger}}(s,a) = \mathbf1[a\neq\pi^*(s)]. $$

只要动作不同，两者都记一次错。

而真正的长期差异是：

$$ A^{\pi^*}(s,a) = Q^{\pi^*}(s,a) - Q^{\pi^*}(s,\pi^*(s)). $$

它可以区分轻微失误与灾难性失误。

这与原论文矛盾吗？

不矛盾。原论文通过 $u$ 已经留下了这个限制：灾难性失误会让 $u$ 很大，保证随之变弱。

AggreVaTe 的改进方向是：训练时就利用 cost-to-go，而不是等到分析时用一个最坏情况 $u$ 统一兜底。

需要补充的判断： 原论文允许一般替代损失，并非逻辑上禁止设计有成本意识的损失；问题在于，标准动作模仿目标与 DAgger 数据聚合机制本身，并不会自动提供这种长期成本信息。

批评二：专家查询昂贵，减少专家执行并没有减少专家标注需求

来源：Zhang 与 Cho 的 SafeDAgger 工作。

原始 DAgger 需要为大量学习者状态查询参考策略。若专家是昂贵规划器或真人，这会成为核心瓶颈。

SafeDAgger 明确针对这一问题，学习预测学习者何时明显偏离参考策略，从而选择性地查询专家，降低调用量。

根据原始流程，若每轮有 $m$ 条长为 $T$ 的轨迹，总共 $N$ 轮，那么全部状态都标注时：

$$ \text{专家标签数量}\approx NmT. $$

即使 $\beta_i$ 已经降到零，这项成本仍然存在。

对应用的含义是：在决定使用 DAgger 前，首先要确认是否有能力对学习者造成的状态获得可靠专家答案。

只有一份固定专家示范数据集，通常不能直接执行原始 DAgger。

批评三：人类擅长亲自操作，不一定擅长给别人的错误轨迹逐状态标注

来源：Laskey 等人 2017 年的人类中心/机器人中心采样研究；DART 作者的研究说明。 下述十人实验出自前一篇研究，不是 DART 论文的实验。

研究者报告了一个具体困难：让人看机器人执行后的画面，再指出当时应采取的动作，可能比让人亲自遥操作更困难。

原因是反馈方式不同：

  • 亲自操作时，人不断观察动作后果并修正；
  • 事后标注时，人必须在脑中推测“这个动作本来会产生什么后果”。

研究者还报告，在其特定的十人实验中，由人类直接演示训练的策略，成功率约为 60%；使用 DAgger 式机器人中心采样、事后纠正标注训练的策略，成功率约为 40%。他们分析了两种可能原因：纠正状态更难学习，以及事后标注与真人实际操作不一致。这里比较的是 DAgger 式采样，不应把结果误写成原始 DAgger 算法在所有真人专家任务中都不如行为克隆。

技术含义：

理论通常把专家当作稳定的查询接口：

$$ s\mapsto\pi^*(s). $$

但真人给出的标签可能依赖：

  • 是否在实际控制；
  • 能否看到动态上下文；
  • 对当前状态的熟悉程度；
  • 标注界面和反应时间。

因此，改进采样分布的同时，可能降低了标签质量。

这是很有价值的批评：统计理论里理想化的“专家 oracle”，在真实人机交互里并不是免费的。

批评四：训练时执行不成熟策略，会带来安全与计算成本

DART 的研究者还明确讨论了两类工程负担：

  • 学习阶段必须执行尚未学好的策略，可能进入危险状态；
  • 不断收集、聚合、重训的闭环可能计算昂贵，且较大的策略更新会使已有数据对新分布不够适用。

原文的：

$$ \pi_i=\beta_i\pi^*+(1-\beta_i)\hat\pi_i $$

只是随机混合，并不是根据危险程度触发的安全控制器。

所以，小概率专家介入不能解释为“训练时不会发生事故”。

从原始算法还能直接推导一个资源问题：若每轮新增 $M$ 个样本，每次都完整扫描聚合数据，那么单次扫描量的累计为：

$$ M+2M+\cdots+NM = \frac{MN(N+1)}2. $$

这是关于朴素实现的计算，不是说所有 DAgger 实现都必须具有相同复杂度。增量优化、抽样回放和数据压缩能减轻负担，但实现与理论条件需要重新对齐。

批评五：无遗憾不保证策略序列收敛，更不保证最后策略最佳

来源：Cheng 与 Boots，2018，〈Convergence of Value Aggregation for Imitation Learning〉。

这项后续研究明确反对一种常见误解：

数据聚合会自动产生不断改善并最终收敛的策略序列。

他们研究了更一般的 value aggregation 框架，给出收敛所需的稳定性条件，并分析最后一个策略的性能。

应区分三件事：

$$ \underbrace{\frac{R_N}{N}\to0}_{\text{平均遗憾消失}}, $$
$$ \underbrace{\exists i:\;J(\hat\pi_i)\text{较好}}_{\text{序列中存在好策略}}, $$
$$ \underbrace{\hat\pi_N\text{收敛且性能好}}_{\text{最后迭代保证}}. $$

前两件事不能直接推出第三件事。

实际影响：

  • 不应只因为最后一个模型见过最多数据，就假定它最好；
  • 需要保留候选模型并执行评估；
  • 在随机环境中，可靠比较策略又需要额外样本。

这并不是原论文的漏洞：原算法已经写明返回验证最好的策略。后续工作批评的是对原理论过度延伸的理解，以及原保证在部署时的不便。

批评六：强凸假设与现代策略优化之间有距离

来源：Lavington、Vaswani、Schmidt，2022，〈Improved Policy Optimization for Online Imitation Learning〉。

这项工作专门研究 DAgger 理论与实践之间的差距，在策略类足够有表达能力时给出更强结果，并放宽了原有分析对参数层面强凸性的要求，还提出正则化的在线优化方法。

对阅读 2011 年论文的启示是：

  • DAgger 的数据流程可以用于深度网络；
  • 但换成深度网络后，原始 FTL 强凸分析不能自动照搬；
  • 原论文提供的是一套有条件的归约，不是对所有策略参数化和优化器的统一保证。

此外，连续控制中常用的平方误差：

$$ \|\pi(s)-\pi^*(s)\|^2 $$

并不一般性地上界“动作是否完全相同”的 0–1 损失。两个连续动作可以只差极小量，但“不完全相同”的指示量仍为 1。

因此，把连续动作回归误差转换成任务成本，往往需要额外的平滑性、敏感度或成本联系，不能机械套用离散分类的论证。这是根据原文定理条件作出的适用性分析。

对原文实验的独立评价

以下是根据原文设计作出的评价，不冒充已有研究的统一结论：

  • 优点：机制清晰。 简单学习器配合不同采样流程，使分布反馈的作用比较容易看出来。
  • 优点：覆盖两类任务。 连续控制、离散控制和结构化预测说明思想具有一定通用性。
  • 限制：规模与表示受时代限制。 手工特征和线性模型不足以验证现代高容量模型上的全部行为。
  • 限制：无法得出全局胜负。 OCR 中调参后的 SEARN 与 DAgger 接近。
  • 限制：成本维度不完整。 样本量相近，不代表人类标注时间、规划器查询成本或重训练成本相近。
  • 限制：有限环境中的恢复能力，不等于普遍安全。 特定赛道的零跌落评估尤其不能如此外推。

读完后应当能够准确回答的几个问题

问题准确回答
DAgger 主要解决什么？学习者动作导致的训练与部署状态分布失配
谁决定训练状态？当前学习者，或学习者与专家的混合执行策略
谁提供标签？专家
为什么聚合旧数据？对应累计损失优化，保留对历次访问分布的约束
理论最核心的要求？底层在线学习具有无遗憾性质，并满足相应损失、采样等条件
无遗憾是否意味着低绝对损失？不意味着，还取决于 $\epsilon_N$
是否保证最后一个策略最好？不保证
是否无条件把真实成本变为线性误差界？不保证，还取决于 cost-to-go 敏感度 $u$
是否不再需要专家？部署时可以不需要；训练时仍需要查询
是否直接求出了原始非凸目标的全局最优？没有

最值得保留的两个公式是：

$$ \boxed{ \text{自身分布上的模仿损失} \le \underbrace{\epsilon_N}_{\text{策略类可达到的误差}} + \underbrace{\gamma_N}_{\text{在线学习遗憾}} + \underbrace{\text{分布混合误差}}_{\text{专家介入}} + \underbrace{\text{采样误差}}_{\text{有限轨迹}} } $$

以及：

$$ \boxed{ J(\hat\pi)-J(\pi^*) \le uT\, \mathbb E_{s\sim d_{\hat\pi}} [\ell(s,\hat\pi)]. } $$

第一个公式解释 DAgger 如何获得对自身访问状态的监督学习保证；第二个公式说明，这种保证何时能够转化为真正的任务表现。