An Anytime Algorithm for Good Arm Identification
Marc Jourdan Clémence Réda
In good arm identification (GAI), the goal is to identify one arm whose
average performance exceeds a given threshold, referred to as good arm, if it
exists. Few works have studied GAI in the fixed-budget setting, when the
sampling budget is fixed beforehand, or the anytime setting, when a
recommendation can be asked at any time. We propose APGAI, an anytime and
parameter-free sampling rule for GAI in stochastic bandits. APGAI can be
straightforwardly used in fixed-confidence and fixed-budget settings. First, we
derive upper bounds on its probability of error at any time. They show that
adaptive strategies are more efficient in detecting the absence of good arms
than uniform sampling. Second, when APGAI is combined with a stopping rule, we
prove upper bounds on the expected sampling complexity, holding at any
confidence level. Finally, we show good empirical performance of APGAI on
synthetic and real-world data. Our work offers an extensive overview of the GAI
problem in all settings.