Multi-Player Bandits With No Collisions
summary
Claims that exact collision-free algorithm constructions achieve minimax square-root(T) regret (up to log and poly(K) factors) with independent Bernoulli rewards, with probability of any collision ≲ T^{-2}. Construction uses a pre-shared random padding/tree partition of the simplex to avoid topological collision obstructions, plus safe-zone schedules that trade off pad randomness to realize Pareto trade-offs for gap-dependent regret; lower bounds use circle/pigeonhole topological arguments to show those trade-offs are tight.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:27Plan for Today
- 1:00Classical Bandits
- 1:17Ordinary Bandits
- 2:10Multi-player (Cooperative) Bandits
- 3:41Multiplayer Bandits Without Communication
- 4:02The Power of Communication
- 8:04Precise Setup
- 15:02Optimal Algorithms with Weakly Detectable Collisions
- 17:4071/2 Minimax Regret with No Collisions
- 21:36Topological Obstruction for 2 players and 3 arms
- 24:25Collision Free Solution for 2 players and 3 arms
- 26:02General Collision Free Strategy
- 29:55A Modified Gap-Dependent Algorithm
- 31:47Pareto Optimal Gap Dependence
- 33:58A One Step Lower Bound
- 35:42Summary
related talks
32mMulti-Player Multi-Armed Bandit: Can We Still Collaborate at Homes Without "Zoom"?
41mSpotlight Talks
48mLearning by Local Entropy Maximization
59mPCPs and Global Hyper-contractivity 1
45mAGT and Machine Learning
30mUnfamiliar Terrain
45mOn Spurious Associations and LLM Alignment
01h 17mGeneralization I