Non-Asymptotic Pure Exploration by Solving Games

Understand

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.