Multiplayer Bandit Learning - From Competition to Cooperation
summary
Two-player bandits compare safe arm p to a risky arm with prior μ and Gittins index g. Competitive play reduces exploration: there is a threshold p_star < g so for p > p_star both players avoid the risky arm, yet there is a separate threshold p_tilde > m (m = mean(μ)) so for p < p_tilde someone still explores initially. Cooperation increases exploration: there is p_hat > g where players explore even above the Gittins index. Long-run: neutral and competitive pairs converge to the same arm.
AI-written summary · about
chapters (25)
- 0:00Introduction
- 0:43Setting
- 1:39Example
- 2:16Utilities
- 3:27Competitive
- 4:09Selfish
- 4:28Alignment
- 5:21Strategies
- 6:57Optimal Strategies
- 7:10Multiplayer Learning
- 10:07Competitive Setting
- 10:26Minimax Theorem
- 13:30Threshold ptilt
- 13:58Risky arm
- 14:31Cooperative setting
- 14:42Theorem
- 16:13Neutral Setting
- 17:09Perfect Basic Equilibrium
- 19:11Nash Equilibrium
- 20:49Ross Child
- 22:33Salmans Agreement Theorem
- 22:48Bandit Setting
- 25:02Bandit Intuition
- 26:03Open Questions
- 27:43Amina
related talks
04mOn gradient-based methods for finding game-theoretic equilibria
30mPractical Multi Armed Bandits
39mBandits and Agents: How to Incentivize Exploration?
32mRevisiting the Exploration-Exploitation Trade-Off in Bandit Models
22mOnline Learning and Bandits with Queried Hints
27mOn the Complexity of Best Arm Identification in Multi-Armed Bandit Models
01h 21mAdversarial Bandits: Theory and Algorithms
44mBandit Learning under Differential Privacy