# QuACK: A Multipurpose Queuing Algorithm for Cooperative k-Armed Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 59 references that are in the map.
- First posted on arXiv 31 Oct 2024.

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

- [Online Learning under Delayed Feedback](https://mlsanity.com/paper/1306.0686/) (2013)
- [Distributed Cooperative Decision-Making in Multiarmed Bandits: Frequentist and Bayesian Algorithms](https://mlsanity.com/paper/1606.00911/) (2016)
- [Fair Algorithms for Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.06699/) (2020)
- [Multi-Armed Bandits with Local Differential Privacy](https://mlsanity.com/paper/2007.03121/) (2020)
- [Copeland Dueling Bandits](https://mlsanity.com/paper/1506.00312/) (2015)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [Cooperative Multi-Agent Bandits with Heavy Tails](https://mlsanity.com/paper/2008.06244/) (2020)
- [Sparse Dueling Bandits](https://mlsanity.com/paper/1502.00133/) (2015)
- [Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits](https://mlsanity.com/paper/1907.03346/) (2019)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [One More Step Towards Reality: Cooperative Bandits with Imperfect Communication](https://mlsanity.com/paper/2111.12482/) (2021)
- [Maillard Sampling: Boltzmann Exploration Done Optimally](https://mlsanity.com/paper/2111.03290/) (2021)
- [Bayesian Algorithms for Decentralized Stochastic Bandits](https://mlsanity.com/paper/2010.10569/) (2020)
- [On-Demand Communication for Asynchronous Multi-Agent Bandits](https://mlsanity.com/paper/2302.07446/) (2023)
- [Distributed Online Learning in Social Recommender Systems](https://mlsanity.com/paper/1309.6707/) (2013)
- [Multi-Player Approaches for Dueling Bandits](https://mlsanity.com/paper/2405.16168/) (2024)
- [Distributed Exact Shortest Paths in Sublinear Time](https://mlsanity.com/paper/1703.01939/) (2017)

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

- [Creator Incentives in Recommender Systems: A Cooperative Game-Theoretic Approach for Stable and Fair Collaboration in Multi-Agent Bandits](https://mlsanity.com/paper/2604.08643/) (2026)

## Abstract (arXiv)

We study the cooperative stochastic k-armed bandit problem, where a network of m agents collaborate to find the optimal action. In contrast to most prior work on this problem, which focuses on extending a specific algorithm to the multi-agent setting, we provide a black-box reduction that allows us to extend any single-agent bandit algorithm to the multi-agent setting. Under mild assumptions on the bandit environment, we prove that our reduction transfers the regret guarantees of the single-agent algorithm to the multi-agent setting. These guarantees are tight in subgaussian environments, in that using a near minimax optimal single-player algorithm is near minimax optimal in the multi-player setting up to an additive graph-dependent quantity. Our reduction and theoretical results are also general, and apply to many different bandit settings. By plugging in appropriate single-player algorithms, we can easily develop provably efficient algorithms for many multi-player settings such as heavy-tailed bandits, duelling bandits and bandits with local differential privacy, among others. Experimentally, our approach is competitive with or outperforms specialised multi-agent algorithms.