Best Of Both Worlds: Stochastic & Adversarial Best-Arm Identification

on YouTube ↗45m

" summary

Main claim: no single learner can be simultaneously optimal for all stochastic instances and for worst-case adversaries; a lower bound introduces the HBOB complexity which can be up to a sqrt(K) factor worse than the stochastic H_SR. Tools: importance-weighted unbiased estimation and a rank-based allocation that samples arms with 1/rank sampling (normalized). Result: a simple parameter-free algorithm attains HBOB (up to log K) in stochastic problems and matches uniform-optimal rates against adversaries; experiments roughly match the theory.

AI-written summary · about

" chapters (8)

1. 0:00Start
2. 1:10Bandit Problem
3. 2:35What Is the Best Army Notification Problem
4. 5:27Banded Problem
5. 12:24Successive Reject
6. 17:06Elimination Phases
7. 25:23Lower Bound
8. 34:51The Algorithm

" related talks

• 27mOn the Complexity of Best Arm Identification in Multi-Armed Bandit ModelsAurélien Garivier · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 01h 15mBridging Stochastic and Adversarial BanditsThodoris Lykouris · Data-Driven Decision Processes Boot Camp 2022
• 01h 21mAdversarial Bandits: Theory and AlgorithmsHaipeng Luo · Data-Driven Decision Processes Boot Camp 2022
• 22mOnline Learning and Bandits with Queried HintsAditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, Kamesh Munagala · ITCS 2023
• 01h 01mRobustness, Stochastics, Uncertainty 1Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 01mRobustness, Stochastics, Uncertainty 2Sasha Rakhlin, Ben Recht, Laurent El Ghaoui · Bridging Continuous and Discrete Optimization Boot Camp 2017
• 01h 01mStochastic Bandits: Foundations and Current PerspectivesShipra Agrawal · Data-Driven Decision Processes Boot Camp 2022
• 01h 14mCompetitive Analysis Meets Stochastic Input: Secretary Problems And Prophet InequalitiesShuchi Chawla · Data-Driven Decision Processes Boot Camp 2022