Optimal Batched Best Arm Identification
Tianyuan Jin Yu Yang Jing Tang Xiaokui Xiao Pan Xu
We study the batched best arm identification (BBAI) problem, where the
learner's goal is to identify the best arm while switching the policy as less
as possible. In particular, we aim to find the best arm with probability
$1-\delta$ for some small constant $\delta>0$ while minimizing both the sample
complexity (total number of arm pulls) and the batch complexity (total number
of batches). We propose the three-batch best arm identification (Tri-BBAI)
algorithm, which is the first batched algorithm that achieves the optimal
sample complexity in the asymptotic setting (i.e., $\delta\rightarrow 0$) and
runs only in at most $3$ batches. Based on Tri-BBAI, we further propose the
almost optimal batched best arm identification (Opt-BBAI) algorithm, which is
the first algorithm that achieves the near-optimal sample and batch complexity
in the non-asymptotic setting (i.e., $\delta>0$ is arbitrarily fixed), while
enjoying the same batch and sample complexity as Tri-BBAI when $\delta$ tends
to zero. Moreover, in the non-asymptotic setting, the complexity of previous
batch algorithms is usually conditioned on the event that the best arm is
returned (with a probability of at least $1-\delta$), which is potentially
unbounded in cases where a sub-optimal arm is returned. In contrast, the
complexity of Opt-BBAI does not rely on such an event. This is achieved through
a novel procedure that we design for checking whether the best arm is
eliminated, which is of independent interest.