LAS Seminar: Best-Arm Identification with Top Two Algorithms

Abstract

Top Two algorithms arose as an adaptation of Thompson sampling to best arm identification in multi-armed bandit models, for parametric families of arms. They select the next arm to sample from among two candidate arms, a leader and a challenger. Despite their simplicity and good empirical performance, theoretical guarantees for fixed-confidence best arm identification have only been obtained asymptotically (i.e. vanishing error level) when the arms are Gaussian with known variances. In this talk, I will present recent advances on the theoretical understanding of Top Two algorithms, and sketch remaining open problems. Our first contribution is a general analysis of Top Two methods in the asymptotic regime, which identifies desirable properties of the leader, the challenger, and the (possibly non-parametric) distributions of the arms. As a result, we obtain theoretically supported Top Two algorithms for best arm identification with bounded distributions. Our second contribution is to derive the first non-asymptotic upper bound on the expected sample complexity of a Top Two algorithm, which holds for any error level and any instance having a unique best arm. In particular, we identify sufficient properties of the leader (seen as a regret minimization algorithm) for it to hold. As a consequence, we propose the TTUCB (Top Two UCB) algorithm which builds on the UCB algorithm and uses tracking instead of sampling to choose between the leader and the challenger.

Marc Jourdan

PhD Student

PhD student at Scool (Inria), I study identification problems in Multi-Armed Bandits.