QuACK: A Multipurpose Queuing Algorithm for Cooperative $k$-Armed Bandits
Abstract
This paper studies the cooperative stochastic $k$-armed bandit problem, where $m$ agents collaborate to identify the optimal action. Rather than adapting a specific single-agent algorithm, we propose a general-purpose black-box reduction that extends any single-agent algorithm to the multi-agent setting. Under mild assumptions, we prove that our black-box approach preserves the regret guarantees of the chosen algorithm, and is capable of achieving minimax-optimality up to an additive graph-dependent term. Our method applies to various bandit settings, including heavy-tailed and duelling bandits, and those with local differential privacy. Empirically, it is competitive with or outperforms specialized multi-agent algorithms.
Cite
Text
Howson et al. "QuACK: A Multipurpose Queuing Algorithm for Cooperative $k$-Armed Bandits." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.Markdown
[Howson et al. "QuACK: A Multipurpose Queuing Algorithm for Cooperative $k$-Armed Bandits." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.](https://mlanthology.org/aistats/2025/howson2025aistats-quack/)BibTeX
@inproceedings{howson2025aistats-quack,
title = {{QuACK: A Multipurpose Queuing Algorithm for Cooperative $k$-Armed Bandits}},
author = {Howson, Benjamin and Filippi, Sarah Lucie and Pike-Burke, Ciara},
booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics},
year = {2025},
pages = {1927-1935},
volume = {258},
url = {https://mlanthology.org/aistats/2025/howson2025aistats-quack/}
}