Online Learning-to-Defer with Varying Experts

问题表述
学习延迟（Learning-to-Defer, L2D）是一个旨在将预测模型与外部专家（人工或自动化）集成的框架，通过将不确定或高风险的输入路由给更胜任的代理，从而提升系统可靠性。尽管现有的 L2D 研究主要在具有固定专家池和完全监督（训练期间观察所有专家预测）的批量设置下运行，但现实世界的部署面临重大挑战：数据是顺序到达的，专家可用性会波动（例如，由于轮班或资源限制），且专家可靠性可能随时间漂移。此外，实际系统通常在部分反馈（bandit feedback）下运行，即学习者仅观察到所选动作（预测或特定专家查询）的结果，而非真实标签或所有可用专家的性能。本文通过引入首个针对多类分类、具有部分反馈且专家池动态变化的在线 L2D 框架，填补了经典 L2D 假设与这些动态、在线现实之间的空白。

方法论
作者提出了一个通用框架，在每一轮 $t$，揭示一个增强输入 $(x_t, A_t)$，由特征向量 $x_t$ 和可用专家集合 $A_t$ 组成。学习者必须决定是预测一个类别标签，还是将任务延迟给 $A_t$ 中的某一位可用专家。交互遵循半对抗设置：输入可能由对抗者选择，但标签是根据输入条件从固定（尽管未知）的分布中抽取的。

核心方法论贡献包括：

1. 真实延迟损失与代理损失：作者定义了一个真实延迟损失 $\ell_{def}$，该损失考虑了误分类成本和专家查询成本。由于该损失不可微，他们引入了一个凸代理损失 $\Phi_{def}$，将标准的基于分数的代理损失（如约束铰链损失）扩展到在线、专家变化的设置中。该代理损失的设计使其不受不可用专家分数的影响。
2. 在线学习的 H-一致性界：一个重要的理论步骤是将 $H$-一致性界从批量学习扩展到在线设置。作者证明，只要基础代理损失相对于 0-1 损失具有 $H$-一致性界，在线框架中最小化代理延迟遗憾就能确保有界的真实延迟遗憾。
3. 算法设计：所提出的算法（算法 1）利用带有投影梯度的在线梯度下降（OGD）。为了处理可用标签的分数之和必须为零的约束（这是约束铰链损失所必需的），算法将权重矩阵投影到特定于当前可用专家集合的可行子空间 $K_{A_t}$ 上。这种投影保留了假设在可用标签集上的预测。该算法包含一个探索率 $\gamma_t$ 以处理部分反馈，基于采样动作的观测结果来估计损失函数。

主要贡献
本文声称有四项主要贡献：

1. 首个在线 L2D 框架：它引入了首个在部分反馈下的在线学习延迟框架，其中数据分布和专家池均可随时间变化。
2. 理论扩展：它将 $H$-一致性界的概念扩展到在线设置，这一特性此前仅限于批量学习分析。
3. 遗憾保证：所提出的算法在一般情况下实现了 $O((n + n_e)T^{2/3})$ 的遗憾界，其中 $n$ 是类别数量，$n_e$ 是观测到的不同专家数量。在低噪声（近可实现）假设下，这一界限改进为 $O((n + n_e)\sqrt{T})$。
4. 实证验证：该方法在合成数据集和真实世界数据集（Reuters4 和 CIFAR10H）上进行了验证，证明了其适应变化的专家可用性和漂移的专家能力的能力。

结果
实验在三种复杂度递增的模式下进行：(1) 固定可用性和能力，(2) 可用性漂移但能力固定，(3) 完全动态设置，即可用性和能力均漂移。

• 合成数据：该算法成功学习了预测与延迟之间的最优边界，始终将输入路由给最胜任的可用专家。即使专家的胜任区域随时间发生偏移，它仍保持了较低的延迟损失和高准确率。
• 真实世界数据（Reuters4）：在最具有挑战性的设置（可用性和能力均漂移）中，该方法有效地跟踪了移动的专家胜任区域。它以高频率将任务延迟给当前胜任的专家，保持了稳定的校准，并实现了与固定能力基线相当的任务准确率。
• CIFAR10H：使用 WideResNet 预测器和人工标注的专家，该方法优于基于置信度且均匀随机延迟的基线。学习到的策略实现了更低的延迟损失和更高的准确率，表明它学会了将样本路由给最合适的专家，而不是不加区分地延迟。

意义
本文将自己定位为迈向使学习延迟系统适用于现实世界非平稳环境的基础性一步。通过超越固定专家池和完全监督的假设，作者证明了基于代理损失的一致方法可以变得对对抗性环境和变化的专家可靠性具有鲁棒性。在线设置中 $H$-一致性的理论确立提供了一个严格的保证，即最小化代理损失会导致最小化真实延迟遗憾，从而弥合了理论 L2D 保证与流式数据和动态专家系统的实际需求之间的关键差距。