Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits

Abstract

We study agents communicating over an underlying network by exchanging messages, in order to optimize their individual regret in a common nonstochastic multi-armed bandit problem. We derive regret minimization algorithms that guarantee for each agent $v$ an individual expected regret of $\tilde{O}\left(\sqrt{\left(1+\frac{K}{|\mathcal{N}\left(v\right)|}\right)T}\right)$, where $T$ is the number of time steps, $K$ is the number of actions and $\mathcal{N}\left(v\right)$ is the set of neighbors of agent $v$ in the communication graph. We present algorithms both for the case that the communication graph is known to all the agents, and for the case that the graph is unknown. When the graph is unknown, each agent knows only the set of its neighbors and an upper bound on the total number of agents. The individual regret between the models differs only by a logarithmic factor. Our work resolves an open problem from [Cesa-Bianchi et al., 2019b].

arXiv commentTo appear in Proc. Neural Information Processing Systems (NeurIPS), 2019

References in corpus (2)

• Multi-Player Bandits: The Adversarial Case
• Cooperative Online Learning: Keeping your Neighbors Updated

Cited by in corpus (7)

• Multi-Agent Online Optimization with Delays: Asynchronicity, Adaptivity, and Optimism
• Kernel Methods for Cooperative Multi-Agent Contextual Bandits
• Medium Access Control protocol for Collaborative Spectrum Learning in Wireless Networks
• Cooperative Multi-Agent Bandits with Heavy Tails
• A survey on multi-player bandits
• My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits
• Multitask Bandit Learning Through Heterogeneous Feedback Aggregation