Individual Regret in Cooperative Stochastic Multi-Armed Bandits
This addresses the challenge of efficient decision-making in distributed multi-agent systems, providing a novel theoretical guarantee for applications like sensor networks or collaborative learning, though it is incremental in extending prior work to more general communication settings.
The paper tackles the problem of individual regret in cooperative stochastic multi-armed bandits with multiple agents communicating over arbitrary connected graphs, achieving a near-optimal regret bound of ˜O(√(AT/m) + A) that becomes independent of graph diameter and sub-optimality gaps with enough agents.
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 the diameter of the communication graph. 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.