  A Top Two sampling rule for bandit identification is a method which selects
the next arm to sample from among two candidate arms, a leader and a
challenger. Due to their simplicity and good empirical performance, they have
received increased attention in recent years. However, for fixed-confidence
best arm identification, theoretical guarantees for Top Two methods have only
been obtained in the asymptotic regime, when the error level vanishes. In this
paper, we derive the first non-asymptotic upper bound on the expected sample
complexity of a Top Two algorithm, which holds for any error level. Our
analysis highlights sufficient properties for a regret minimization algorithm
to be used as leader. These properties are satisfied by the UCB algorithm, and
our proposed UCB-based Top Two algorithm simultaneously enjoys non-asymptotic
guarantees and competitive empirical performance.

Machine Learning;Machine Learning