Revisiting the Exploration-Exploitation Trade-Off in Bandit Models
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23·
summary
Characterizes when regret and pure-exploration diverge: sampling must follow information-theoretic Wstar proportions computed by a 1‑D optimization over KL divergences, and a practical track-and-stop algorithm forces sqrt(T) exploration, uses a GLR stopping rule, and attains expected sample complexity ≈ T(mu)·log(1/δ). For two Gaussian arms an explore-then-commit* scheme yields regret ≈ (4/Δ) log T, provably about twice the Lai–Robbins optimum (≈(2/Δ) log T), so mixed ETC approaches are suboptimal.
AI-written summary · about
chapters (16)
- 0:00Intro
- 1:15The multi-armed bandit mode
- 2:02Regret minimization in a bandit model
- 4:23A motivation should we minimize regret?
- 5:53Two different objectives
- 8:13Optimal algorithms for regret minimization
- 9:51Miocing Exploration and Exploitation: the UCB approach
- 11:42Outline
- 15:23Sampling rule: Tracking the optimal proportions
- 16:25An asymptotically optimal algorithm
- 17:53Regret minimization versus Best Arm Identification
- 19:47Gaussian two-armed bandits
- 20:50Explore-Then-Commit (ETC) strategies
- 22:44Is this the best we can do? Lower bounds.
- 26:58An interesting matching algorithm
- 28:40Conclusion
related talks
29mPure Exploration Problems
49mIncentivized Exploration
46mDynamic Regret Minimization for Bandits without Prior Knowledge
01h 15mBridging Stochastic and Adversarial Bandits
01h 01mStochastic Bandits: Foundations and Current Perspectives
38mBest of Both World Algorithms from I.I.D. to Adversarial Data
01h 21mAdversarial Bandits: Theory and Algorithms
01h 09mStochastic Bandits: Foundations and Current Perspectives