Efficient Pure Exploration in Adaptive Round model

Tianyuan Jin, Jieming Shi, Xiaokui Xiao, Enhong Chen

In the classic Multi-Armed Bandit (MAB) problem, a learner pulls "arms" to discover which ones yield the highest rewards. Historically, most research has focused on query complexity: minimizing the total number of pulls required to find the best options. However, in many real-world applications like medical trials, crowdsourcing, or online advertising, round complexity—the number of sequential interaction batches—is just as critical.

Imagine a clinical trial: you can test 100 drugs on 1,000 patients simultaneously (one round), but you have to wait weeks for the results before deciding which drugs to test in the next phase. If an algorithm requires 50 sequential rounds to find the best drug, the trial takes years, even if the total number of patients (queries) is small.

This paper tackles the "Adaptive Round" model, introducing new algorithms designed to identify the top-$k$ arms in as few sequential batches as possible without wasting samples. By employing a novel "double-test" elimination strategy, the authors achieve the theoretical lower bound for rounds while outperforming existing methods in query efficiency by orders of magnitude.

The Double-Test Strategy and $\log^* n$

The authors propose three primary algorithms to tackle different facets of the problem:

  1. $k$-$\delta$E (Top-$k$ $\delta$-Elimination): Designed for the PAC (Probably Approximately Correct) setting. Unlike traditional "Median Elimination" which conservatively discards only half the arms per round, $k$-$\delta$E is much more aggressive. It uses a double-test strategy: it samples arms to find a candidate set, then re-samples a small subset of those candidates to create an unbiased "indicator." This second, independent sample verifies the pruning threshold, preventing the "confirmation bias" that occurs when using the same data to both pick a threshold and eliminate arms. This allows the algorithm to safely prune a massive percentage of sub-optimal arms in just two rounds.
  2. $k$-$\delta$ER: A variant of $k$-$\delta$E designed for scenarios with a strict, pre-defined limit on the number of rounds ($R$).
  3. Exact Top-$k$ Identification: The authors integrate their PAC approach into an "Exponential-Gap Elimination" framework. This allows them to identify the exact best arms (not just $\epsilon$-approximate ones).

The core mathematical innovation here is breaking the $\log n$ barrier. Most existing algorithms scale their rounds with $\log n$ (halving the search space each time). By using the $\delta$-Elimination strategy, the authors reduce the search space much faster, matching the theoretical lower bound of $\log^* n$ (the iterated logarithm). The iterated logarithm is the number of times you must apply the logarithm function to a number before it becomes $\le 1$. For all practical purposes, this value is a small constant (e.g., $\log^*$ of the number of atoms in the observable universe is only 5).

Experimental Results: Massive Query Savings

The algorithms were evaluated using synthetic reward distributions to simulate different "difficulty" levels for bandit problems, including a Uniform Dataset (means uniformly distributed in $[0, 1]$) and a Segment Dataset (a "hard" case where $k$ arms have a mean of 0.5 and the rest have a mean of 0.4, creating a difficult-to-distinguish gap). Experiments were conducted with $n = 2000$ arms.

While many theoretical papers focus on "Big-O" notation, this paper emphasizes that their small constant factors make the algorithm significantly more efficient in practice than previous models, which often hid massive constants.

Cost comparison on the Uniform Dataset
Cost comparison on the Segment Dataset

The results demonstrate a stark contrast between the proposed methods and existing baselines:

  • Query Savings: As seen in the figures above, the $k$-$\delta$E algorithm is roughly 100x to 1000x more efficient in terms of total queries (cost) compared to state-of-the-art baselines like ME-AS across both standard and hard datasets.
  • Round Efficiency: In PAC top-$k$ tests, the proposed $\delta$E algorithm typically finished in 2 to 4 rounds, whereas the standard Median Elimination (ME) required 11 rounds.
  • Exact Identification: For exact top-$k$ identification, their method was up to 250 times faster in query cost than previous elimination-based frameworks while using fewer rounds.

Limitations and Future Work

While highly efficient, the approach does have limitations. The exact identification framework benefits from prior knowledge of the reward gaps ($\Delta_k$), which isn't always available in practice. Additionally, if a scenario imposes an extremely strict round limit (e.g., $R=1$), no adaptive algorithm can outperform simple uniform sampling.

Future work could explore how these algorithms perform in non-stationary environments where arm means change over time, or in "heavy-tailed" distributions common in financial data, moving beyond the standard synthetic distributions used in this study.

Summary updated

Abstract

In the adaptive setting, many multi-armed bandit applications allow the learner to adaptively draw samples and adjust sampling strategy in rounds. In many real applications, not only the query complexity but also the round complexity need to be optimized. In this paper, we study both PAC and exact top-$k$ arm identification problems and design efficient algorithms considering both round complexity and query complexity. For PAC problem, we achieve optimal query complexity and use only $O(\log_{\frac{k}{\delta}}^*(n))$ rounds, which matches the lower bound of round complexity, while most of existing works need $\Theta(\log \frac{n}{k})$ rounds. For exact top-$k$ arm identification, we improve the round complexity factor from $\log n$ to $\log_{\frac{1}{\delta}}^*(n)$, and achieve near optimal query complexity. In experiments, our algorithms conduct far fewer rounds, and outperform state of the art by orders of magnitude with respect to query cost.
BibTeX
@inproceedings{jin2019efficient,
  author = {Tianyuan Jin and Jieming Shi and Xiaokui Xiao and Enhong Chen},
  title = {{Efficient Pure Exploration in Adaptive Round model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
}
Figure