提出协作算法，让多组用户共享探索信息，平衡各组学习负担。
Collaborative Min-Max Regret in Grouped Multi-Armed Bandits
- 设计动态协调机制，跨组共享探索信息以减少重复尝试。
- 理论证明算法在最坏情况和具体场景下均逼近最优合作后悔值。
- 适合需公平分配探索成本的群体决策场景，如医疗实验分组。
我们研究在分组多臂老虎机中共享探索的影响，其中多个组拥有重叠的可行动作集 [Baek and Farias '24]。在此设置下，各组共享奖励观测，目标是最小化协作后悔，定义为各组最大后悔值。这自然刻画了需平衡组间探索负担的应用场景——标准算法可能导致组间探索成本显著失衡。为此，我们提出算法 Col-UCB，实现跨组探索的动态协调。理论表明，Col-UCB 在最坏情况与实例相关情形下均达到最优的协同后悔界（对数因子内）。该边界能自适应共享动作集的结构，揭示协作何时显著优于各组独立学习。
原文摘要 · Abstract (English)
We study the impact of sharing exploration in multi-armed bandits in a grouped setting where a set of groups have overlapping feasible action sets [Baek and Farias '24]. In this grouped bandit setting, groups share reward observations, and the objective is to minimize the collaborative regret, defined as the maximum regret across groups. This naturally captures applications in which one aims to balance the exploration burden between groups or populations -- it is known that standard algorithms can lead to significantly imbalanced exploration cost between groups. We address this problem by introducing an algorithm Col-UCB that dynamically coordinates exploration across groups. We show that Col-UCB achieves both optimal minimax and instance-dependent collaborative regret up to logarithmic factors. These bounds are adaptive to the structure of shared action sets between groups, providing insights into when collaboration yields significant benefits over each group learning their best action independently.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。