Collaborative Min-Max Regret in Grouped Multi-Armed Bandits

2025/06/12 by Moïse Blanchard, Blanchard, Moïse, Vineet Goyal +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mobile Crowdsensing and Crowdsourcing #Recommender Systems and Techniques

paper · pdf · doi:10.48550/arxiv.2506.10313

openalex publication_date 2025/06/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Group Meritocratic Fairness in Linear Contextual Bandits
• Fair Exploration via Axiomatic Bargaining
• Fairness of Exposure in Stochastic Bandits
• Bandit Algorithms
• The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits
• Social Learning in Multi Agent Multi Armed Bandits
• Achieving Fairness in the Stochastic Multi-armed Bandit Problem
• Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
• Combinatorial Sleeping Bandits with Fairness Constraints
• Quantifying the Burden of Exploration and the Unfairness of Free Riding
• Multiplayer bandits without observing collision information
• The Externalities of Exploration and How Data Diversity Helps\n Exploitation
• Online Learning with an Unknown Fairness Metric
• Calibrated Fairness in Bandits
• Fairness in Reinforcement Learning
• Distributed Cooperative Decision-Making in Multiarmed Bandits:\n Frequentist and Bayesian Algorithms
• Fairness in Learning: Classic and Contextual Bandits
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Distributed Exploration in Multi-Armed Bandits
• Contextual Bandit Algorithms with Supervised Learning Guarantees

Related

• Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits
• Optimal Regret Bounds for Collaborative Learning in Bandits
• Near-Optimal Collaborative Learning in Bandits
• An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit
• Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits