# Near-Optimal Collaborative Learning in Bandits

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 47 references that are in the map.
- First posted on arXiv 31 May 2022.

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

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Differentially-Private Federated Linear Bandits](https://mlsanity.com/paper/2010.11425/) (2020)
- [Explore First, Exploit Next: The True Shape of Regret in Bandit Problems](https://mlsanity.com/paper/1602.07182/) (2016)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals](https://mlsanity.com/paper/1811.11419/) (2018)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Federated Bandit: A Gossiping Approach](https://mlsanity.com/paper/2010.12763/) (2020)
- [Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1311.0800/) (2013)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1904.03293/) (2019)
- [Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection](https://mlsanity.com/paper/1702.03605/) (2017)
- [A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players](https://mlsanity.com/paper/1902.01239/) (2019)
- [Collaborative Top Distribution Identifications with Limited Interaction](https://mlsanity.com/paper/2004.09454/) (2020)
- [Exploiting Heterogeneity in Robust Federated Best-Arm Identification](https://mlsanity.com/paper/2109.05700/) (2021)
- [Structure Adaptive Algorithms for Stochastic Bandits](https://mlsanity.com/paper/2007.00969/) (2020)
- [A/B/n Testing with Control in the Presence of Subpopulations](https://mlsanity.com/paper/2110.15573/) (2021)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [(Almost) Free Incentivized Exploration from Decentralized Learning Agents](https://mlsanity.com/paper/2110.14628/) (2021)

## Built on by (most cited first, 18 of 18)

- [Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards](https://mlsanity.com/paper/2306.05579/) (2023)
- [Doubly Adversarial Federated Bandits](https://mlsanity.com/paper/2301.09223/) (2023)
- [Collaborative Learning in Kernel-based Bandits for Distributed Users](https://mlsanity.com/paper/2207.07948/) (2022)
- [Parallel Best Arm Identification in Heterogeneous Environments](https://mlsanity.com/paper/2207.08015/) (2022)
- [Pure Exploration in Asynchronous Federated Bandits](https://mlsanity.com/paper/2310.11015/) (2023)
- [Collaborative Algorithms for Online Personalized Mean Estimation](https://mlsanity.com/paper/2208.11530/) (2022)
- [Collaborative Multi-Agent Heterogeneous Multi-Armed Bandits](https://mlsanity.com/paper/2305.18784/) (2023)
- [Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits](https://mlsanity.com/paper/2301.11442/) (2023)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Regret Lower Bounds in Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2308.08046/) (2023)
- [Harnessing the Power of Federated Learning in Federated Contextual Bandits](https://mlsanity.com/paper/2312.16341/) (2023)
- [Fairness and Privacy Guarantees in Federated Contextual Bandits](https://mlsanity.com/paper/2402.03531/) (2024)
- [Decentralized Blockchain-based Robust Multi-agent Multi-armed Bandit](https://mlsanity.com/paper/2402.04417/) (2024)
- [Distributed Optimization via Kernelized Multi-armed Bandits](https://mlsanity.com/paper/2312.04719/) (2023)
- [Optimal Regret Bounds for Collaborative Learning in Bandits](https://mlsanity.com/paper/2312.09674/) (2023)
- [Federated X-armed Bandit with Flexible Personalisation](https://mlsanity.com/paper/2409.07251/) (2024)
- [Near Optimal Best Arm Identification for Clustered Bandits](https://mlsanity.com/paper/2505.10147/) (2025)
- [Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback](https://mlsanity.com/paper/2602.16183/) (2026)

## Abstract (arXiv)

This paper introduces a general multi-agent bandit model in which each agent is facing a finite set of arms and may communicate with other agents through a central controller in order to identify, in pure exploration, or play, in regret minimization, its optimal arm. The twist is that the optimal arm for each agent is the arm with largest expected mixed reward, where the mixed reward of an arm is a weighted sum of the rewards of this arm for all agents. This makes communication between agents often necessary. This general setting allows to recover and extend several recent models for collaborative bandit learning, including the recently proposed federated learning with personalization (Shi et al., 2021). In this paper, we provide new lower bounds on the sample complexity of pure exploration and on the regret. We then propose a near-optimal algorithm for pure exploration. This algorithm is based on phased elimination with two novel ingredients: a data-dependent sampling scheme within each phase, aimed at matching a relaxation of the lower bound.