Abstract
In pure exploration problems for stochastic multi-armed bandits, the objective is to answer inquiries regarding a set of unknown distributions (modeling for example the efficacy of a treatment) from which we can collect samples (measure its effect), and subsequently provide guarantees on the candidate answer. The archetypal example is the best arm identification problem, in which the agent aims at identifying the arm with the highest mean. This thesis delves into the class of Top Two algorithms, wherein a leader is pitted against a challenger, directing subsequent sampling efforts to validate the superiority of the leader. We introduce a unified definition of the Top Two approach, putting forward four key components. Given their simplicity, interpretability, generalizability, and versatility, Top Two algorithms are promising for widespread adoption among practitioners. This thesis endeavors to establish the Top Two approach as a principled methodology offering nearly optimal theoretical guarantees alongside state-of-the-art empirical performance. We address several stochastic multi-armed bandits settings, such as various classes of distributions or structural assumptions on the means. We also study different pure exploration problems, including the identification of the best arm or one of acceptable quality. The principal contribution of this thesis lies in establishing theoretical guarantees for the Top Two approach across several performance metrics. In the fixed-confidence setting, we prove that many Top Two algorithms have an asymptotically optimal expected sample complexity (number of collected samples when the confidence level goes to one). In the anytime setting, we propose a Top Two algorithm which has guarantees on the probability of misidentifying a good enough arm at any time.
