Pure Exploration Problems
summary
Defines fixed‑confidence, instance‑dependent pure exploration where sample complexity scales like f(mu)·log(1/δ) and gives an information‑theoretic lower bound as a max‑min over alternative bandits; shows the only way to match it asymptotically is to sample in oracle proportions (the W argmax) and implements an algorithm that estimates W and forces sample counts to converge, matching the lower bound. Addresses discontinuities with sticky sampling for multiple answers, uses online‑learning for max‑min (two learners, optimism, regret→finite guarantees), and derives martingale‑mixture deviations for heavy‑tailed CVaR.
AI-written summary · about
chapters (14)
- 0:00Intro
- 0:55Expectation Management for the Experts
- 2:55Best Arm Identification (BAI)
- 5:48Best Arm Identification, prototypical solution
- 7:49Many Variations of BAI Problem in Literature
- 9:15Major Variations
- 9:40Nash Equilibrium Identification Problem
- 11:58Minimax Action Identification Problem
- 13:10Optimal Policy Identification Problem
- 17:48Lower Bounds Inspire Strategies
- 19:43Asymptotic Optimality
- 20:51Sticky Track-and-Stop for Multiple Correct Answers
- 22:13Saddle Point Techniques
- 24:50Open problems
related talks
32mRevisiting the Exploration-Exploitation Trade-Off in Bandit Models
39mBandits and Agents: How to Incentivize Exploration?
01h 09mStochastic Bandits: Foundations and Current Perspectives
44mBandit Learning under Differential Privacy
15mFundamental Limits Of Learning In Data-Driven Problems
01h 01mStochastic Bandits: Foundations and Current Perspectives
55mLearning Minimax Estimators Via Online Learning
33mOnline Multivalid Learning: Means, Moments, and Prediction Intervals