Non-Asymptotic Pure Exploration by Solving Games
This work addresses the need for efficient, non-asymptotic algorithms in active testing for researchers and practitioners in machine learning, offering a novel approach that improves upon existing asymptotic methods.
The paper tackles the problem of pure exploration in stochastic environments by proposing algorithms that use iterative strategies and no-regret learners to estimate saddle points, achieving the first finite confidence guarantees adapted to exponential families for any query and bandit structure.
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.