Best of Both World Algorithms from I.I.D. to Adversarial Data
summary
Proposes using Tsallis-Inf FTRL with adaptive learning rates to get both the adversarial sqrt(kT) bound and the stochastic logarithmic regret without extra exploration, and shows experiments where it resists a hidden confounder that breaks UCB/Thompson. Analysis removes one action from the per-step stability term via a Lagrangian shift and converts the stability/penalty constraints into an optimization that yields a corruption-dependent bound for a corruption budget. Open gaps: no high-probability guarantees, multiple-equal-best-arm and linear-bandit proofs remain unresolved.
AI-written summary · about
chapters (11)
- 0:00Problem setting
- 0:59Regimes
- 6:18Adversarial bandits
- 7:56What makes the problem hard?
- 9:17Overview
- 14:03Weights with Tsallis regularization
- 17:27Closer inspection of Stability
- 23:12What is missing?
- 24:16Extension to corruption
- 26:12Building on this principle
- 28:14Drawbacks
related talks
01h 15mBridging Stochastic and Adversarial Bandits
01h 21mAdversarial Bandits: Theory and Algorithms
12mDistribution-Free Robustness
29mCorruption Robust Exploration in Episodic Reinforcement Learning
22mOnline Learning and Bandits with Queried Hints
01h 09mStochastic Bandits: Foundations and Current Perspectives
32mRevisiting the Exploration-Exploitation Trade-Off in Bandit Models
56mA Tutorial on Reinforcement Learning II