Summary
This paper studies the Batched Best Arm Identification (BBAI) problem in multi-armed bandits. The goal is to design an efficient algorithm that correctly finds the arm with the highest mean with probability $\ge 1 - \delta$, while minimizing: (1) the sample complexity, defined as the total number of arm pulls; (2) the "batch complexity", defined as the number of rounds in which the algorithm requests arm pulls. (Formally, the algorithm specifies the number of times it pulls each arm in the $r$-th round after observing all the outcomes in the previous $r-1$ rounds.)
The main results of this work are:
- An algorithm (termed Tri-BBAI) that achieves an asymptotically (i.e., as $\delta \to 0^{+}$) optimal sample complexity in three batches in expectation.
- Another algorithm (termed Opt-BBAI) that achieves: (1) near-optimal sample and batch complexities in the non-asymptotic setting; (2) the same guarantees as Tri-BBAI in the asymptotic setting.
Strengths
- This work studies a fairly natural problem. While the setup is not new, I liked that the authors explored certain perspectives that are different from prior work, namely: (1) asymptotic optimality of sample complexity; (2) focusing on the expected number of rounds, rather than treating it as a hard constraint.
- The results are pretty strong: The algorithms achieve asymptotically optimal sample complexities within a (small) constant number of rounds (in expectation).
- The presentation is clear in general. I found the main paper fairly easy to follow.
Weaknesses
I think a major weakness of the work is that its main result is fairly intuitive, and arguably, its proof does not give new insights to the design of pure exploration algorithms. Here is why: For simplicity, suppose that we only have two arms with means $1/2+\epsilon$ and $1/2-\epsilon$, and the parameter $\epsilon > 0$ is *unknown*.
In this case, the "natural" algorithm is to make geometrically decreasing guesses on $\epsilon$: $\epsilon_1, \epsilon_2, \ldots$, where each $\epsilon_k = 2^{-k}$. At guess $\epsilon_k$, we would pull each arm $(1/\epsilon_k)^2$ times to get an $O(\epsilon_k)$-approximation of the means. If the means are clearly separated, we get the answer; otherwise, we continue with smaller guesses. Clearly, this approach requires many rounds ($\Omega(\log(1/\epsilon))$ rounds) of adaptivity.
On this instance, very roughly speaking, the authors' approach is to start with the guess, say, $\epsilon_k = 1/\log^{1/3}(1/\delta)$. For each fixed $\epsilon$, when $\delta$ is small enough, the guess would be smaller than the actual $\epsilon$, and the algorithm wins the game in $O(1)$ rounds. Also, this first round only takes $(1/\epsilon_k)^2 = \log^{2/3}(1/\delta) \ll \log(1/\delta)$ samples, so this will not affect the asymptotic behavior as $\delta \to 0^{+}$.
In general, the Tri-BBAI algorithm uses a round-robin strategy as an inefficient exploration round. The length of this round is chosen as a function of $\delta$, so that the asymptotic behavior is not affected. Therefore, for each fixed instance, there exists some $\delta_0 > 0$ such that whenever $\delta < \delta_0$, this inefficient exploration succeeds with a good probability, and may guide the algorithm to sample in an asymptotically optimal way in the rest. As a result, this asymptotic optimality might only hold for extremely small values of $\delta$: From Line 492, the analysis needs $1/\log\log(1/\delta) = \epsilon \le \Delta_2$ to go through; in other words, $1/\delta$ needs to be **doubly exponential** in $1/\Delta_2$.
Admittedly, this weakness was addressed by the other algorithm Opt-BBAI, which achieves a sample complexity bound for finite $\delta$ as well. However, it should be noted that the complexity contains a $\sum_{i=2}^{n}(1/\Delta_i)^2\log n$ term, which could be higher than the optimal sample complexity by a $\log n$ factor. In contrast, the state-of-the-art bounds for (non-batched) BAI (e.g., [Karnin-Koren-Somekh, ICML'13][Jamieson-Malloy-Nowak-Bubeck, COLT'14][Chen-Li, arXiv'15][Chen-Li-Qiao, COLT'17]) are tight up to a doubly-logarithmic factor.
Despite the weakness mentioned above, I think this submission presents some solid work and a nice observation (Lines 72-73), namely, the need for many rounds of adaptivity only arises when $\delta$ is small (or moderate), and goes away when we focus on the asymptotic regime. Therefore, I lean towards accepting the paper.