Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits
Preprint
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 $\widetilde{O}\left(\sqrt{\left(1+\frac{K}{\left|\mathcal{N}\left(v\right)\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].
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Collaborative Learning of Stochastic Bandits Over a Social NetworkIEEE/ACM Transactions on Networking, 2018
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit ProblemsFoundations and Trends in Machine Learning, 2012
- The Nonstochastic Multiarmed Bandit ProblemSIAM Journal on Computing, 2002
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986