Timezone: »
Poster
Individual Regret in Cooperative Nonstochastic MultiArmed Bandits
Yogev BarOn · Yishay Mansour
Tue Dec 10 05:30 PM  07:30 PM (PST) @ East Exhibition Hall B + C #13
We study agents communicating over an underlying network by exchanging messages, in order to optimize their individual regret in a common nonstochastic multiarmed 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 [CesaBianchi et al., 2019b].
Author Information
Yogev BarOn (TelAviv University)
Yishay Mansour (Tel Aviv University / Google)
More from the Same Authors

2019 Poster: Online Stochastic Shortest Path with Bandit Feedback and Unknown Transition Function »
Aviv Rosenberg · Yishay Mansour 
2019 Poster: Graphbased Discriminators: Sample Complexity and Expressiveness »
Roi Livni · Yishay Mansour 
2019 Spotlight: Graphbased Discriminators: Sample Complexity and Expressiveness »
Roi Livni · Yishay Mansour 
2019 Poster: Learning to Screen »
Alon Cohen · Avinatan Hassidim · Haim Kaplan · Yishay Mansour · Shay Moran 
2016 Poster: Online Pricing with Strategic and Patient Buyers »
Michal Feldman · Tomer Koren · Roi Livni · Yishay Mansour · Aviv Zohar 
2013 Poster: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · NicolĂ˛ CesaBianchi · Claudio Gentile · Yishay Mansour 
2013 Oral: From Bandits to Experts: A Tale of Domination and Independence »
Noga Alon · NicolĂ˛ CesaBianchi · Claudio Gentile · Yishay Mansour