Adversarial Bandits: Theory and Algorithms
summary
Covers adversarial multi-armed bandits with concrete algorithms and proofs: full-information FTRL/Hedge analysis, bandit reduction via importance-weighted loss estimators and the variance cancellation that yields EXP3, and a tight minimax procedure using Tsallis entropy (alpha=1/2) that removes the log K factor to achieve Θ(√(TK)). Introduces the log-barrier regularizer for L*‑dependent and path‑length bounds, optimistic FTRL with one-step predictors, and practical tricks (negative regret term, switching‑cost tradeoffs) with stated limits and lower bounds.
AI-written summary · about
chapters (14)
- 0:00Program overview
- 2:32Introduction to speaker
- 3:24Adversarial bandit model
- 6:43Motivations for regret
- 11:09Algorithmic recipe
- 13:21Full information case
- 21:57FTRL framework
- 28:15Bandit case estimator
- 33:27EXP3 regret analysis
- 38:37Lower bound discussion
- 41:45Optimal FTRL algorithm
- 47:48Adaptive regrets
- 55:17Log barrier techniques
- 1:00:58Open problems & conclusion
related talks
38mBest of Both World Algorithms from I.I.D. to Adversarial Data
22mOnline Learning and Bandits with Queried Hints
46mDynamic Regret Minimization for Bandits without Prior Knowledge
Bandits and Agents: How to Incentivize Exploration?
32mMulti-Player Multi-Armed Bandit: Can We Still Collaborate at Homes Without "Zoom"?
21mLeveraging Multi-Armed Bandit Algorithms for Dynamic Decision Making
44mBandit Learning under Differential Privacy
30mPractical Multi Armed Bandits