Cooperative Multi-Agent Bandits with Heavy Tails
arXiv:2008.06244
Abstract
We study the heavy-tailed stochastic bandit problem in the cooperative multi-agent setting, where a group of agents interact with a common bandit problem, while communicating on a network with delays. Existing algorithms for the stochastic bandit in this setting utilize confidence intervals arising from an averaging-based communication protocol known as~\textit{running consensus}, that does not lend itself to robust estimation for heavy-tailed settings. We propose \textsc{MP-UCB}, a decentralized multi-agent algorithm for the cooperative stochastic bandit that incorporates robust estimation with a message-passing protocol. We prove optimal regret bounds for \textsc{MP-UCB} for several problem settings, and also demonstrate its superiority to existing methods. Furthermore, we establish the first lower bounds for the cooperative bandit problem, in addition to providing efficient algorithms for robust bandit estimation of location.
arXiv comment26 pages including appendix, camera-ready for ICML 2020
References in corpus (11)
- Ising formulations of many NP problems
- The origin of bursts and heavy tails in human dynamics
- Analysis of Thompson Sampling for the multi-armed bandit problem
- Distributed Learning in Multi-Armed Bandit with Multiple Players
- A Tutorial on Formulating and Using QUBO Models
- Tail-scope: Using friends to estimate heavy tails of degree distributions in large-scale complex networks
- Distributed Clustering of Linear Bandits in Peer to Peer Networks
- Online Clustering of Bandits
- Thompson Sampling for 1-Dimensional Exponential Family Bandits
- Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits
- Multiplayer Bandit Learning, from Competition to Cooperation