技术摘要：学习将预测任务分配给具有容量约束的代理

问题定义

本文解决了在线顺序任务分配问题，其中任务按顺序到达，必须分配给一组可用的代理（人类或人工智能）。核心挑战涉及两个同时存在的约束：

1. 异质性、上下文依赖的专业知识：代理拥有不同程度的专业知识，且这些知识取决于任务的具体上下文（例如，放射科医生可能在特定医疗案例中表现出色，但在其他案例中则不然；大语言模型可能在特定查询类型上表现更好）。这种专业知识最初是未知的，必须在线学习。
2. 容量约束：与成本预算约束（理论上单个廉价代理可处理所有任务）不同，该设定对单个代理施加了长期容量限制。每个代理 $a$ 有一个目标比例 $\alpha_a$，代表其能处理的总工作量份额。这反映了现实世界的运营限制，如人类疲劳、倦怠或人员配置水平，防止将过多任务分配给单一高性能代理。

目标是学习一种分配策略，在严格遵守这些长期容量约束的同时，最大化整体预期奖励（例如预测准确性），尽管最初对代理性能存在不确定性。

方法论

理论框架

作者将问题建模为上下文多臂老虎机（MAB）。

• 最优无约束策略：在代理专业知识 $\mu_a(x)$ 已知的神谕设定中，最优策略将每个上下文 $x$ 分配给具有最高条件预期奖励的代理。
• 最优有约束策略：当引入容量约束 $\alpha_a$ 时，作者利用拉格朗日乘数推导出最优策略。他们证明最优有约束策略具有以下形式：
  $$\phi^*(x) = \arg\max_{a} \{ \mu_a(x) - \lambda_a \}$$
  其中 $\lambda_a$ 充当容量约束的“影子价格”。这意味着最优策略是将任务分配给具有最高调整后奖励的代理，从而有效地惩罚那些接近容量限制的代理。
• 双代理分析：本文提供了双代理情况的具体特征，表明最优策略将容量为 $\alpha$ 的代理分配给奖励差距 $\Delta(x) = \mu_1(x) - \mu_2(x)$ 最大的 $\alpha$ 质量上下文。理论分析表明，只要代理性能随上下文变化，上下文策略就严格优于非上下文（随机或固定代理）基线。

在线学习算法

为了处理 $\mu_a(x)$ 未知的实际场景，作者提出了一种基于队列的在线学习框架：

1. 上下文建模：代理专业知识使用逻辑回归（采用拉普拉斯近似进行后验估计）或基于树的模型（随机森林）进行建模。该框架支持汤普森采样（通过后验采样进行探索）和贪婪选择（使用点估计）。
2. 基于队列的约束执行：为了在不了解未来的情况下执行长期容量约束，算法为每个代理维护一个虚拟队列 $Q_{t,a}$。该队列跟踪实现分配与目标容量 $\alpha_a$ 之间的累积偏差：
   $$Q_{t+1,a} = [Q_{t,a} + \mathbb{I}(a_t = a) - \alpha_a]_+$$
3. 决策规则：在每一步 $t$，通过最大化平衡估计奖励和队列压力的调整后分数来选择代理：
   $$a_t = \arg\max_{a} \{ \mu_{a,t}(x_t) - \eta Q_{t,a} \}$$
   这里，$\eta$ 是控制奖励最大化与约束满足之间权衡的惩罚参数。队列长度 $Q_{t,a}$ 充当影子价格 $\lambda_a$ 的动态、时变估计。

作者证明，即使增加了虚拟队列的复杂性，该算法也继承了上下文汤普森采样文献中的标准次线性后悔界。

实验结果

该框架在涉及表格、图像和文本预测任务的各种设定中进行了评估，使用了机器学习分类器、大语言模型（LLM）以及人类标注员（真实和模拟）。

• 数据集：实验包括 Camelyon17（医学成像）、MMLU（LLM 路由）、ImageNet16H（人类与 AI）以及四个表格数据集（银行、信用、优惠券、心血管）。
• 性能：上下文分配策略（包括基于逻辑和基于树的策略，使用汤普森采样或贪婪策略）在所有容量水平上系统地优于非上下文基线。
  • 组合策略通常比最佳单个代理的边际错误率更低的错误率，验证了利用互补专业知识可提高整体系统性能的理论主张。
  • 基于树的模型通常优于逻辑模型，这表明捕捉代理专业知识中的非线性模式至关重要。
  • 贪婪策略和汤普森采样表现相似，约束本身提供了足够的隐式探索。
• 小批量设定：作者探索了小批量设定，即在观察结果之前为一批任务进行分配。他们发现相对于批量大小存在 U 形错误曲线：小批量允许频繁更新但容量执行噪声较大，而大批量则延迟学习。中间批量大小提供了最佳权衡，但以增加延迟为代价。
• 敏感性：对队列惩罚参数 $\eta$ 的敏感性分析表明，较小的值优先考虑奖励最大化（接近无约束性能），而较大的值更积极地执行容量（接近非上下文随机分配）。

主要贡献

1. 理论特征：本文提供了具有容量约束代理的任务分配的一般理论框架，根据影子价格和上下文依赖的专业知识差异来刻画最优策略。
2. 算法框架：它引入了一种实用的在线学习算法，该算法联合学习代理专业知识并利用基于队列的机制执行长期容量约束，适用于人类和 AI 代理。
3. 实证验证：通过在多种模态（文本、图像、表格）和代理类型（LLM、人类、分类器）上的广泛实验，本文证明了上下文容量约束策略比非上下文基线产生系统性增益。

意义与主张

本文主张，有效的人机协作和大规模组织任务分配不仅取决于提高单个代理的性能，还取决于设计能够学习异质性专业知识同时尊重现实世界容量限制的分配策略。

作者强调，他们的方法解决了先前工作（如学习推迟或 LLM 路由）中的关键差距，这些工作通常假设离线学习或忽略特定代理的工作量限制。通过建模在线学习专业知识和管理容量的联合问题，该框架使系统能够动态适应分布偏移和运营约束。结果表明，忽略上下文或容量约束会导致次优性能，而联合建模它们则可以利用代理的互补性，从而可能超越系统中甚至最好的单个代理。

本文在其范围方面保持谦逊，指出评估是在受控环境中使用代理代理进行的，上下文维度相对较低。它承认现实世界的应用可能涉及高维、多模态上下文、延迟反馈以及不断变化的代理行为，并将这些确定为未来的工作方向。