Multi-agent Multi-armed Bandit with Fully Heavy-tailed Dynamics

We study decentralized multi-agent multi-armed bandits, where clients communicate over sparse random graphs with heavy-tailed degree distributions and observe heavy-tailed reward distributions with potentially infinite variance. We are the first to address such fully heavy-tailed scenarios, capturing the dynamics and challenges of communication and inference among multiple clients in real-world systems, and provide regret bounds that match or improve upon existing results developed in even simpler settings. Under homogeneous rewards, we exploit hub-like structures unique to heavy-tailed graphs to aggregate rewards and reduce noises when constructing UCB indices; under $M$ clients and degree distributions with power-law index $\alpha>1$, we attain a regret (almost) of order $O\left(M^{1-\frac{1}{\alpha}} \log T\right)$. Under heterogeneous rewards, clients synchronize by communicating with neighbors and aggregating exchanged estimators in UCB indices; by establishing information delay bounds over sparse random graphs, we attain a $O(M \log T)$ regret.