Non-Asymptotic Pure Exploration by Solving Games
arXiv:1906.10431
Abstract
Pure exploration (aka active testing) is the fundamental task of sequentially gathering information to answer a query about a stochastic environment. Good algorithms make few mistakes and take few samples. Lower bounds (for multi-armed bandit models with arms in an exponential family) reveal that the sample complexity is determined by the solution to an optimisation problem. The existing state of the art algorithms achieve asymptotic optimality by solving a plug-in estimate of that optimisation problem at each step. We interpret the optimisation problem as an unknown game, and propose sampling rules based on iterative strategies to estimate and converge to its saddle point. We apply no-regret learners to obtain the first finite confidence guarantees that are adapted to the exponential family and which apply to any pure exploration query and bandit structure. Moreover, our algorithms only use a best response oracle instead of fully solving the optimisation problem.
References in corpus (12)
- On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
- Optimal Best Arm Identification with Fixed Confidence
- Informational Confidence Bounds for Self-Normalized Averages and Applications
- Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
- Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms
- Acceleration through Optimistic No-Regret Dynamics
- Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
- The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
- Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling
- Pure Exploration with Multiple Correct Answers
- Gradient Ascent for Active Exploration in Bandit Problems
- Thresholding Bandit for Dose-ranging: The Impact of Monotonicity