Bridging Stochastic and Adversarial Bandits
summary
Single algorithm requirement: derive one policy that attains log(T)/Δ regret when rewards are IID and Θ(√(KT)) worst-case when adversarial. Concrete constructions: a multi‑layered successive‑elimination ensemble runs ~log T independent copies (pick layer L with prob 2^-L) to get a C·log(T)/Δ high‑probability term when C rounds are corrupted; BARBAR uses epoched inverse‑gap sampling to make corruption additively appear as O(CK); CHARLIE‑SYNTH yields a unified bound roughly pseudo‑regret + O(√(C·...)) and extends to combinatorial/episodic RL when importance weighting applies.
AI-written summary · about
chapters (14)
- 0:00Start
- 0:59General Setting
- 4:26Bridging the Two Worlds
- 7:33Pseudo Regret
- 10:31Adversarial Advantage
- 13:35Stochastic Based Approach
- 13:45Successive Elimination
- 19:03Negative Regret
- 31:56Stochastic Bandits with Adversarial Corruptions
- 33:03Formal Model
- 34:46Adaptive Adversary
- 39:03Initial Algorithm
- 40:40Why Stochastic Approaches Fail
- 42:23Exploration Rounds
related talks
38mBest of Both World Algorithms from I.I.D. to Adversarial Data
46mDynamic Regret Minimization for Bandits without Prior Knowledge
32mMulti-Player Multi-Armed Bandit: Can We Still Collaborate at Homes Without "Zoom"?
32mRevisiting the Exploration-Exploitation Trade-Off in Bandit Models
56mA Tutorial on Reinforcement Learning II
22mOnline Learning and Bandits with Queried Hints
Bandits and Agents: How to Incentivize Exploration?
29mCorruption Robust Exploration in Episodic Reinforcement Learning