# Collaborative Min-Max Regret in Grouped Multi-Armed Bandits

arXiv: https://arxiv.org/abs/2506.10313 · HTML: https://mlsanity.com/paper/2506.10313/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 30 references that are in the map.
- First posted on arXiv 12 Jun 2025.

## Builds on (most cited first, 19 of 19)

- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Fairness in Reinforcement Learning](https://mlsanity.com/paper/1611.03071/) (2016)
- [Achieving Fairness in the Stochastic Multi-armed Bandit Problem](https://mlsanity.com/paper/1907.10516/) (2019)
- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Online Learning with an Unknown Fairness Metric](https://mlsanity.com/paper/1802.06936/) (2018)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [Calibrated Fairness in Bandits](https://mlsanity.com/paper/1707.01875/) (2017)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [The Externalities of Exploration and How Data Diversity Helps Exploitation](https://mlsanity.com/paper/1806.00543/) (2018)
- [Multiplayer bandits without observing collision information](https://mlsanity.com/paper/1808.08416/) (2018)
- [Coordination without communication: optimal regret in two players multi-armed bandits](https://mlsanity.com/paper/2002.07596/) (2020)
- [Group Meritocratic Fairness in Linear Contextual Bandits](https://mlsanity.com/paper/2206.03150/) (2022)
- [Quantifying the Burden of Exploration and the Unfairness of Free Riding](https://mlsanity.com/paper/1810.08743/) (2018)

## Abstract (arXiv)

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.