技术摘要：何时停止的学习：任意动力学偏移下的选择性模仿学习

1. 问题表述

本文探讨了在测试环境的转移动力学与训练环境任意不同的情况下，**模仿学习（IL）**所面临的挑战。在经典的离线模仿学习中，一个在源环境 $M$ 中基于专家演示训练的 learner 被部署到目标环境 $N$ 中。如果 $M$ 和 $N$ 的状态支撑集（state supports）不相交或发生显著偏移，标准策略可能会表现任意糟糕，因为它无法识别其训练数据何时不再提供可靠的指导。

作者提出了一个选择性模仿学习框架，其中 learner 被赋予在检测到当前状态超出训练数据的可靠支撑集时中止（停止执行）轨迹的选项。目标是学习一个选择性策略 $(\pi, \tau)$，由基础策略 $\pi$ 和停止时间 $\tau$ 组成，该策略需满足两个相互竞争的目标：

1. 完备性（Completeness）： 策略在训练环境 $M$ 中应极少中止（即 $\alpha_M(\pi, \tau) \le \epsilon$）。
2. 可靠性（Soundness）： 策略在测试环境 $N$ 中停止之前应产生低遗憾（即 $Regret_N(\pi, \tau) \le \epsilon$）。

该设定假设可访问：

• 带标签的训练轨迹（Labeled training rollouts）： 来自环境 $M$ 中专家 $\pi^\star$ 的状态 - 动作对 $(s, a)$。
• 无标签的测试轨迹（Unlabeled test rollouts）： 来自环境 $N$ 中专家 $\pi^\star$ 的仅状态轨迹。这种不对称性模拟了现实世界场景，其中动作遥测数据成本高昂或属于专有数据（例如，没有转向指令的自动驾驶行车记录仪 footage）。

2. 方法论：SeqRejectron

核心算法 SeqRejectron 将选择性分类中的 Rejectron 算法（Goldwasser 等人，2020）推广到序列决策中。关键洞察在于，算法不是在每个时间步做出独立决策（这会导致依赖于视界 $H$ 的样本复杂度），而是利用一组稀疏的验证器策略（validator policies）来认证整个轨迹前缀。

核心机制

1. 基础策略： Learner 选择一个与训练数据一致的基础策略 $\pi_0$（例如，最大似然估计）。
2. 验证器集合： 算法构建一个小的“验证器”策略集合 $\Phi$，这些策略从版本空间（与训练数据一致的策略）中抽取。
3. 停止规则： Learner 执行 $\pi_0$，仅当 $\Phi$ 中的每一个验证器都同意 $\pi_0$ 时才继续。第一个分歧点触发停止（中止）。
4. 稀疏验证器分布： 一个关键的理论贡献是证明了一个稀疏的验证器集合（大小独立于视界 $H$）足以保证安全性。这是通过对“挑战者”（选择竞争策略）和“验证器”（选择一组验证器）之间的零和博弈进行极小极大论证来实现的。

针对不同设定的变体

本文将该框架适应于三个日益通用的设定：

• 确定性策略：

  • 机制： 使用二元分歧测试。停止时间 $\tau$ 是任何验证器 $\pi \in \Phi$ 与 $\pi_0$ 产生分歧的第一步。
  • 实现： 验证器分布是使用无遗憾动力学构建的（具体而言，是归约到加权可实现多实例学习的 Oracle 高效归约）。
  • 结果： 在稀疏成本下实现了与视界无关的样本复杂度 $\tilde{O}(\sqrt{\log|\Pi|/n})$。

• 随机策略：

  • 挑战： 二元分歧过于粗糙；分布可能在每一步都“柔和”地不同，而没有单个令人警觉的差异。
  • 机制： 用累积 Hellinger 距离停止时间替换二元测试。当 $\pi_0$ 与任何验证器之间的累积平方 Hellinger 距离超过阈值 $\theta$ 时，learner 停止。
  • 结果： 提供了已停止轨迹的 Hellinger 距离的有限样本界限。本文建立了单步随机设定中带标签样本复杂度的 $\Omega(1/\epsilon^3)$ 下界，与成本驱动部分的上界相匹配。

• 误设策略类：

  • 挑战： 专家 $\pi^\star$ 可能不在 learner 的策略类 $\Pi$ 内。
  • 机制： 用对称正则化博弈替换硬性的版本空间约束。允许验证器在源数据上与基础策略产生分歧，但这种分歧会受到惩罚。
  • 结果： 保证随着误设量的增加而优雅地退化（由类内最佳误设误差 $\Delta$ 衡量）。

3. 主要贡献与结果

理论保证

• 与视界无关的复杂度： 对于确定性策略，样本复杂度独立于视界 $H$（除了通过总成本尺度 $C_{max}$），缩放为 $\tilde{O}(\sqrt{\log|\Pi|/n})$。这改进了朴素的分步归约，后者遭受 $O(H^2)$ 的惩罚。
• 稀疏验证： 本文证明了存在一个验证器分布，其支撑集大小为 $O(1/\epsilon)$，独立于状态空间、动作空间或视界。
• 下界： 作者证明了随机单步设定中带标签样本复杂度的 $\Omega(1/\epsilon^3)$ 下界，表明在成本驱动机制中，对 $1/\epsilon$ 的三次方依赖是不可避免的。
• 误设鲁棒性： 该框架扩展到专家不在类内的不可知设定，其遗憾界限随误设误差的平方根缩放。

实证评估

作者在 LunarLander-v3 环境中评估了 SeqRejectron。

• 设置： 训练在无风环境中进行；测试在有风且初始冲量不同的环境中进行。
• 发现： 该算法成功检测到了分布外动力学。通过调整安全阈值 $\theta$，作者展示了这种权衡：策略在分布内（训练）数据上极少中止，同时在分布外（测试）数据上可靠停止，从而防止灾难性故障。验证器的数量被证明是鲁棒的，性能迅速饱和。

4. 意义与主张

本文主张将中止确立为模仿学习中应对未预见动力学偏移的原则性、理论依据充分的响应。

• 超越启发式： 与需要关于偏移性质假设或测试分布在线访问的鲁棒 RL 或域随机化方法不同，SeqRejectron 仅使用离线数据提供分布无关的 PAC 保证。
• PQ 学习的序列类比： 该工作将自己定位为 PQ 学习框架（Goldwasser 等人，2020）的序列类比，将中止能力从单个预测扩展到整个轨迹前缀。
• 安全机制： 通过将做什么的决策与何时停止的决策解耦，该框架提供了一种安全机制，防止 learner 在训练数据缺乏信息时将系统驱动至不可恢复的状态。

作者承认了局限性，指出随机设定目前缺乏像确定性情况那样的 Oracle 高效计算归约，并且随机策略的方差驱动样本复杂度率在上下界之间仍存在未解决的差距。他们还建议未来的工作可以纳入部分结构知识（例如，有界 TV 距离），以收紧测试侧的停止率。