Finding All ε-Good Arms in Stochastic Bandits

Blake Mason, Lalit K. Jain, Ardhendu Tripathy, Robert D. NowakarXiv 2020 · arXiv

In the field of stochastic multi-armed bandits, the "pure exploration" problem is a foundational challenge: given a set of options (arms) with unknown reward distributions, the goal is to identify the best arms using a minimal number of samples. Traditional objectives focus on finding the single best arm, the Top-$k$ arms, or all arms exceeding a fixed threshold. However, these approaches often require prior knowledge that is unavailable in practice.

In "Finding All $\epsilon$-Good Arms in Stochastic Bandits," Mason et al. introduce a more robust and flexible objective: identifying every arm that is "close enough" to the optimal choice. This ALL-$\epsilon$ problem seeks to find all arms $i$ such that their mean $\mu_i$ satisfies $\mu_i \geq \mu_1 - \epsilon$, where $\mu_1$ is the unknown maximum mean.

The ALL-ε Objective: A Relative Exam

Unlike Top-$k$ or fixed-threshold settings, the ALL-$\epsilon$ objective is distribution-free and relative. If Top-$k$ is a contest with a fixed number of winners and thresholding is an exam with a fixed passing grade, ALL-$\epsilon$ is a relative exam where the passing grade is determined by the performance of the best candidate. This is particularly useful in scenarios like drug discovery or content moderation, where the number of "good" candidates varies and the absolute quality of the best candidate is unknown beforehand.

Conceptual visualization of the ALL-ε problem, partitioning arms into the ε-good set $G_\epsilon$ and its complement $G_\epsilon^c$ based on the distance from the best mean $\mu_1$.

Algorithmic Solutions

The authors provide a theoretical lower bound for the complexity of the ALL-$\epsilon$ task and propose two novel algorithms to address it:

  1. $(ST)^2$ (Sample the Threshold, Split the Threshold): An optimistic algorithm that runs two strategies in parallel: UCB to refine the estimate of the best arm and LUCB to resolve which arms are near the resulting threshold. It is computationally efficient and highly effective in practical applications.
  2. FAREAST (Fast Arm Removal Elimination Algorithm for a Sampled Threshold): A sophisticated elimination-based algorithm designed to be "instance-optimal." It uses dual filters to identify winners and prune losers, matching the theoretical lower bound even in challenging edge cases.

Empirical Performance

The researchers evaluated their algorithms on two high-stakes real-world datasets: the New Yorker Cartoon Caption Contest (NYCCC) and a cancer drug discovery dataset (PKIS2). In the NYCCC dataset, where caption quality varies weekly, $(ST)^2$ matched or outperformed "oracle" versions of Top-$k$ algorithms that were pre-informed of the optimal $k$.

Comparison of F1 scores across different algorithms on (a) NYCCC and (b) Cancer drug discovery datasets. $(ST)^2$ (ST2) demonstrates superior performance in identifying ε-good arms compared to standard UCB or uniform sampling.

In the drug discovery scenario, the goal is high precision to ensure that only truly effective compounds move to clinical trials. $(ST)^2$ achieved significantly higher F1 scores than standard methods, identifying potent compounds much faster by dynamically adjusting the threshold based on the best-performing inhibitor.

Conclusion and Future Work

The ALL-$\epsilon$ framework offers a more realistic approach to exploration in unknown environments. While FAREAST provides asymptotic optimality, $(ST)^2$ offers a practical and robust solution for most real-world instances. Future research may explore the "unverifiable regime"—where many arms are exactly $\epsilon$-good—and extend these methods to handle heavy-tailed reward distributions.

Summary updated

Abstract

The pure-exploration problem in stochastic multi-armed bandits aims to find one or more arms with the largest (or near largest) means. Examples include finding an {\epsilon}-good arm, best-arm identification, top-k arm identification, and finding all arms with means above a specified threshold. However, the problem of finding all {\epsilon}-good arms has been overlooked in past work, although arguably this may be the most natural objective in many applications. For example, a virologist may conduct preliminary laboratory experiments on a large candidate set of treatments and move all {\epsilon}-good treatments into more expensive clinical trials. Since the ultimate clinical efficacy is uncertain, it is important to identify all {\epsilon}-good candidates. Mathematically, the all-{\epsilon}-good arm identification problem presents significant new challenges and surprises that do not arise in the pure-exploration objectives studied in the past. We introduce two algorithms to overcome these and demonstrate their great empirical performance on a large-scale crowd-sourced dataset of 2.2M ratings collected by the New Yorker Caption Contest as well as a dataset testing hundreds of possible cancer drugs.
BibTeX
@misc{mason2020finding,
  author = {Blake Mason and Lalit K. Jain and Ardhendu Tripathy and Robert D. Nowak},
  title = {{Finding All ε-Good Arms in Stochastic Bandits}},
  year = {2020},
  eprint = {2006.08850},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.08850},
}
Figure