Timezone: »

 
Poster
Non-Asymptotic Pure Exploration by Solving Games
Rémy Degenne · Wouter Koolen · Pierre Ménard

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #17
in Algorithms -- Bandit Algorithms »

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.

Keywords: Bandit Algorithms · Exploration · Algorithms · Reinforcement Learning and Planning
[ Paper]  [ Slides] 

Author Information

Rémy Degenne (Centrum Wiskunde & Informatica, Amsterdam)
Wouter Koolen (Centrum Wiskunde & Informatica, Amsterdam)
Pierre Ménard (Institut de Mathématiques de Toulouse)

More from the Same Authors