Individual Regret in Cooperative Stochastic Multi-Armed Bandits over Communication Graph

Idan Barnea, Tal Lancewicki, Yishay Mansour

Abstract

We study the regret in stochastic Multi-Armed Bandits (MAB) with multiple agents that communicate over an arbitrary connected communication graph. We show a near-optimal individual regret bound of $\tilde{O}(\sqrt{AT/m}+A)$, where $A$ is the number of actions, $T$ the time horizon, and $m$ the number of agents. In particular, assuming a sufficient number of agents, we achieve a regret bound of $\tilde{O}(A)$, which is independent of the sub-optimality gaps and depends only logarithmically on the time horizon. To the best of our knowledge, our study is the first to show an individual regret bound in cooperative stochastic MAB that is independent of the graph's diameter and applicable to non-fully-connected communication graphs.
BibTeX
@inproceedings{barnea2025individual,
  author = {Idan Barnea and Tal Lancewicki and Yishay Mansour},
  title = {{Individual Regret in Cooperative Stochastic Multi-Armed Bandits over Communication Graph}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=k4wAXbEPD6},
}
Figure