Best Arm Identification in Spectral Bandits
This addresses the problem of selecting optimal arms under dependencies for applications like parameter tuning, though it is incremental as it extends existing graph-based methods from regret minimization to best arm identification.
The paper tackles best arm identification in bandit models with graph smoothness constraints by proposing an asymptotically optimal strategy, showing through numerical experiments that it efficiently handles the sample complexity impact of these constraints.
We study best-arm identification with fixed confidence in bandit models with graph smoothness constraint. We provide and analyze an efficient gradient ascent algorithm to compute the sample complexity of this problem as a solution of a non-smooth max-min problem (providing in passing a simplified analysis for the unconstrained case). Building on this algorithm, we propose an asymptotically optimal strategy. We furthermore illustrate by numerical experiments both the strategy's efficiency and the impact of the smoothness constraint on the sample complexity. Best Arm Identification (BAI) is an important challenge in many applications ranging from parameter tuning to clinical trials. It is now very well understood in vanilla bandit models, but real-world problems typically involve some dependency between arms that requires more involved models. Assuming a graph structure on the arms is an elegant practical way to encompass this phenomenon, but this had been done so far only for regret minimization. Addressing BAI with graph constraints involves delicate optimization problems for which the present paper offers a solution.