Cooperative Multi-Agent Bandits with Heavy Tails
  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.
