Multi-Player Multi-Armed Bandit: Can We Still Collaborate at Homes Without "Zoom"?
summary
Models non-stochastic (oblivious adversary) multi-player bandits and gives concrete algorithms: one uses a low-switching leader plus exploration by the follower to achieve root-T regret while sending only √T bits of communication, and another uses shared public randomness with a follow-the-soft-perturbed-leader style sampling to get T^{2/3} regret with zero communication. Assumptions: no collisions ever, bandit feedback, shared random seed for the zero-communication result; algorithms are efficient and provably meet the stated regret bounds.
AI-written summary · about
chapters (10)
- 0:00Multiplayer bandit problem
- 1:10Defining the core problem
- 2:58Motivations and constraints
- 5:42Defining no-collision goals
- 8:45Communication trade-offs
- 12:13Setting and implications
- 14:02The non-stationary challenge
- 17:28Overview of new results
- 19:43Two-player algorithm logic
- 23:52Communication-free strategy
related talks
41mMulti-Player Bandits With No Collisions
22mOnline Learning and Bandits with Queried Hints
01h 15mBridging Stochastic and Adversarial Bandits
01h 21mAdversarial Bandits: Theory and Algorithms
30mPractical Multi Armed Bandits
39mBandits and Agents: How to Incentivize Exploration?
01h 01mStochastic Bandits: Foundations and Current Perspectives
46mDynamic Regret Minimization for Bandits without Prior Knowledge