Gradient Ascent for Active Exploration in Bandit Problems

Abstract

We present a new algorithm based on an gradient ascent for a general Active Exploration bandit problem in the fixed confidence setting. This problem encompasses several well studied problems such that the Best Arm Identification or Thresholding Bandits. It consists of a new sampling rule based on an online lazy mirror ascent. We prove that this algorithm is asymptotically optimal and, most importantly, computationally efficient.

21 pages, 1 figure

References in corpus (6)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Optimal Best Arm Identification with Fixed Confidence
• Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
• Pure Exploration with Multiple Correct Answers
• Thresholding Bandit for Dose-ranging: The Impact of Monotonicity

Cited by in corpus (6)

• Fixed-Confidence Guarantees for Bayesian Best-Arm Identification
• Non-Asymptotic Pure Exploration by Solving Games
• A Novel Confidence-Based Algorithm for Structured Bandits
• Price of Safety in Linear Best Arm Identification
• Chernoff Sampling for Active Testing and Extension to Active Regression
• Stochastic Bandits with Vector Losses: Minimizing ${\ell }^{\infty }$-Norm of Relative Losses