Breaking the log⁡(1/Δ2) Barrier: Better Batched Best Arm Identification with Adaptive Grids

We investigate the problem of batched best arm identification in multi-armed bandits, where we aim to identify the best arm from a set of n arms while minimizing both the number of samples and batches. We introduce an algorithm that achieves near-optimal sample complexity and features an instance-sensitive batch complexity, which breaks the log(1/∆ 2 ) 1 barrier. The main contribution of our algorithm is a novel sample allocation scheme that effectively balances exploration and exploitation for batch sizes. Experimental results indicate that our approach is more batch-efficient across various setups. We also extend this framework to the problem of batched best arm identification in linear bandits and achieve similar improvements.

• Alphabetic author order 1 ∆2 is the difference of means between the best arm and the second best arm. 2 In this paper, we consider the fixed-confidence variant of BAI-M. The other variant is referred to as fixed-budget, where given a sample budget T , we want to identify the best arm with the smallest error probability.