An Optimal Elimination Algorithm for Learning a Best Arm

Abstract

We consider the classic problem of (,)-PAC learning a best arm where the goal is to identify with confidence 1- an arm whose mean is an -approximation to that of the highest mean arm in a multi-armed bandit setting. This problem is one of the most fundamental problems in statistics and learning theory, yet somewhat surprisingly its worst-case sample complexity is not well understood. In this paper, we propose a new approach for (,)-PAC learning a best arm. This approach leads to an algorithm whose sample complexity converges to exactly the optimal sample complexity of (,)-learning the mean of n arms separately and we complement this result with a conditional matching lower bound. More specifically:

Tasks

Reproductions