Multi-Player Bandits: The Adversarial Case

Abstract

We consider a setting where multiple players sequentially choose among a common set of actions (arms). Motivated by a cognitive radio networks application, we assume that players incur a loss upon colliding, and that communication between players is not possible. Existing approaches assume that the system is stationary. Yet this assumption is often violated in practice, e.g., due to signal strength fluctuations. In this work, we design the first Multi-player Bandit algorithm that provably works in arbitrarily changing environments, where the losses of the arms may even be chosen by an adversary. This resolves an open problem posed by Rosenski, Shamir, and Szlak (2016).

References in corpus (3)

• Distributed Learning in Multi-Armed Bandit with Multiple Players
• Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
• Delay and Cooperation in Nonstochastic Bandits

Cited by in corpus (7)

• Individual Regret in Cooperative Nonstochastic Multi-Armed Bandits
• Multi-player Multi-armed Bandits with Collision-Dependent Reward Distributions
• Medium Access Control protocol for Collaborative Spectrum Learning in Wireless Networks
• Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without
• My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits
• A survey on multi-player bandits
• Coordination without communication: optimal regret in two players multi-armed bandits