Lag：可复用资源在线分配的平均场最优策略

arXiv:2610.19038v1 公告类型：新论文 摘要：我们研究可复用资源的在线任务分配问题。该问题出现在同行评审人分配、基于技能的呼叫路由、网约车匹配、应急调度和众包等场景中：任务按照几何过程到达，必须立即分配给服务者；服务者随后会暂时处于忙碌状态，产生的奖励取决于任务与服务者的配对。目标是最大化长期平均奖励。我们将该问题建模为上下文非静止多臂老虎机（CRMAB）。我们推导了一个占用测度线性规划（OCC-LP），为任何工作守恒策略的奖励提供上界。通过其对偶问题，我们得到了一种具有闭式表达式的指数策略 Lag。我们引入了一种缩放机制，使每个服务者的副本数量与每步到达的任务数量同步增长。该机制给出了上下文老虎机的首个确定性流体极限。在此极限下，Lag 具有渐近最优性。最后，我们在同行评审数据集和呼叫中心路由场景中评估了所提出的算法。在所有负载水平下，拉格朗日指数均达到线性规划上界的 83–99%。此外，拉格朗日指数策略显著优于直观的贪心分配方案，在期刊数据上将奖励最多提高了 12.3%，在结构化合成实例上最多提高了 36%。