Multi-Player Bandits: The Adversarial Case
This addresses a critical issue in applications like cognitive radio networks where players cannot communicate and must avoid collisions in non-stationary settings.
The paper tackles the problem of multi-player bandits in adversarial environments where losses can change arbitrarily, designing the first algorithm that provably works without stationarity assumptions, resolving an open problem from prior work.
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).