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.
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:
- $(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.
- 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$.
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