串行独裁赌博机新突破：精确遗憾边界可多项式求解，每个帕累托最优点都能逐点达到！
Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
📖 AI 总结
本文研究集中式串行独裁匹配多臂老虎机中的探索外部性问题。由于探索必须使用完整匹配，学习某一玩家与臂的配对会对其他玩家造成遗憾。作者在已知公共优先级顺序和单位方差高斯奖励的设定下，证明匹配层面的Graves-Lai约束可约化为有限多个成对探索配额，并在顶选分离实例上给出多项式规模的边际线性规划。核心发现是：在这些实例上，期望对数遗憾系数的精确可达集为G(θ)X(θ)，其中X为可行匹配分配集，G将分配映射为玩家遗憾；通常的上闭Graves-Lai区域虽具有相同Pareto最小边界，但可能严格更大。研究还表明，相同的探索配额因调度方式不同可导致截然不同的遗憾。作者构造了在全行严格类上一致优良的估计-求解-跟踪策略，无需假设优化器唯一即可达到任意固定正权重最优，且每个Pareto最小点均可逐点达到。该工作为理解集中式匹配中的外部性代价与调度作用提供了精确理论刻画。
🔑 关键词速览
| 串行独裁匹配赌博机 | 一种集中式匹配赌博机模型，玩家按固定优先级顺序依次选择臂，探索需使用完整匹配。 |
| Graves-Lai约束 | 匹配级别的探索约束，确保每个玩家-臂对获得足够的探索，以学习奖励分布。 |
| 遗憾系数 | 衡量策略性能的指标，表示期望遗憾随对数时间增长的系数。 |
| 帕累托最小边界 | 在多目标优化中，无法在不损害其他目标的情况下改进任何目标的解集边界。 |
| 估计-求解-跟踪策略 | 一种在线学习策略，先估计参数，求解优化问题，然后跟踪最优分配。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅