Selfish Robustness and Equilibria in Multi-Player Bandits
summary
Claims that decentralized protocols recover the centralized regret rate under full or statistical sensing even if one agent acts selfishly, and proves impossibility without sensing. Technique combines leader election with staggered block exploration, collision-based bits for robust communication, and a credible punishment that samples top arms to deter deviation; this yields an epsilon-Nash equilibrium and an explicit alpha-stability bound. Results show an unavoidable factor-m slowdown in simpler schemes and that robustness degrades as the number of selfish agents grows.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 1:52stochastic bandits
- 4:01summary
- 6:39benchmark
- 8:58Cooperative player
- 12:51Communication trick
- 16:53Solution
- 18:52Existing protocols
- 20:25Statistical Sensing
- 24:15Without Sensing
- 25:01Socialized Regret
- 25:48Two Leaders
- 26:29Communication
- 28:03Punishment
- 30:33Proof
- 32:08Conclusions
- 32:50Question
- 35:15Questions
related talks
15mMulti-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust Control
39mBandits and Agents: How to Incentivize Exploration?
01h 15mBridging Stochastic and Adversarial Bandits
22mOnline Learning and Bandits with Queried Hints
01h 21mAdversarial Bandits: Theory and Algorithms
52mMechanisms for Honest Data Sharing under Competition
12mDistribution-Free Robustness
46mDynamic Regret Minimization for Bandits without Prior Knowledge