Nearly Optimal Best-of-Both-Worlds Individual Regret in Cooperative Bandits

We study the best-of-both-worlds problem of cooperative multi-armed bandits in the uninformed setting, where $V$ agents interact with a common set of $K$ arms over an arbitrary connected communication graph, and each agent initially knows only its local neighborhood. Over a horizon of $T$ rounds, each agent selects an arm, observes only its local loss, and exchanges information with its neighbors. The environment can be either stochastic or adversarial, and the agents do not know the regime in advance. The objective is to simultaneously achieve small individual regret for every agent in both regimes while minimizing communication cost. We propose a single algorithm that achieves individual regret $$\begin{gathered} \tilde{\mathcal{O}}(\sqrt{K}+\min \\ {\sum }_{i:{\Delta }_i>0}1/(V{\Delta }_i),\sqrt{KT/V} \\ ) \end{gathered}$$ in the stochastic regime, where ${\Delta }_i$ is the suboptimality gap of arm $i$, and individual regret $\tilde{\mathcal{O}}(\sqrt{KT/V}+K^{1/4}\sqrt{T})$ in the adaptive adversarial regime. We establish matching worst-graph lower bounds up to logarithmic factors for both regimes. Our regret guarantees strictly improve the best known results in the stochastic regime. We further show that our algorithm requires only $\mathcal{O}(\log T)$ communication rounds per agent in the stochastic regime, while every packet has $\mathcal{O}(K\log V)$ bits in both regimes. Finally, we reveal a polynomial separation between adaptive and oblivious adversaries, showing that adaptivity can make cooperative bandit learning polynomially harder.