# Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration

arXiv: https://arxiv.org/abs/1706.01081 · HTML: https://mlsanity.com/paper/1706.01081/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jun 2017.

## Built on by (most cited first, 19 of 19)

- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Improved Algorithms for Agnostic Pool-based Active Classification](https://mlsanity.com/paper/2105.06499/) (2021)
- [A unified framework for bandit multiple testing](https://mlsanity.com/paper/2107.07322/) (2021)
- [AHA: Human-Assisted Out-of-Distribution Generalization and Detection](https://mlsanity.com/paper/2410.08000/) (2024)
- [Combinatorial Pure Exploration with Bottleneck Reward Function](https://mlsanity.com/paper/2102.12094/) (2021)
- [Thompson Sampling for (Combinatorial) Pure Exploration](https://mlsanity.com/paper/2206.09150/) (2022)
- [Optimal Exploration is no harder than Thompson Sampling](https://mlsanity.com/paper/2310.06069/) (2023)
- [Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit](https://mlsanity.com/paper/2308.10238/) (2023)
- [Best Group Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2505.17869/) (2025)
- [Best Arm Identification under Additive Transfer Bandits](https://mlsanity.com/paper/2112.04083/) (2021)
- [Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit](https://mlsanity.com/paper/2310.15681/) (2023)
- [Constrained Best Arm Identification with Tests for Feasibility](https://mlsanity.com/paper/2511.09808/) (2025)
- [A Fast Algorithm for PAC Combinatorial Pure Exploration](https://mlsanity.com/paper/2112.04197/) (2021)
- [Neural Bandits for Data Mining: Searching for Dangerous Polypharmacy](https://mlsanity.com/paper/2212.05190/) (2022)
- [Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits](https://mlsanity.com/paper/2306.01995/) (2023)
- [Cost-Aware Optimal Pairwise Pure Exploration](https://mlsanity.com/paper/2503.07877/) (2025)
- [Support Selection Beyond Smooth DAG Exactness: Completion Geometry,Score Margins, and Selective Certificates](https://mlsanity.com/paper/2608.08103/) (2026)
- [DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback](https://mlsanity.com/paper/2610.12960/) (2026)

## Abstract (arXiv)

We study the combinatorial pure exploration problem Best-Set in stochastic multi-armed bandits. In a Best-Set instance, we are given n arms with unknown reward distributions, as well as a family F of feasible subsets over the arms. Our goal is to identify the feasible subset in F with the maximum total mean using as few samples as possible. The problem generalizes the classical best arm identification problem and the top-k arm identification problem, both of which have attracted significant attention in recent years. We provide a novel instance-wise lower bound for the sample complexity of the problem, as well as a nontrivial sampling algorithm, matching the lower bound up to a factor of ln|F|. For an important class of combinatorial families, we also provide polynomial time implementation of the sampling algorithm, using the equivalence of separation and optimization for convex program, and approximate Pareto curves in multi-objective optimization. We also show that the ln|F| factor is inevitable in general through a nontrivial lower bound construction. Our results significantly improve several previous results for several important combinatorial constraints, and provide a tighter understanding of the general Best-Set problem. We further introduce an even more general problem, formulated in geometric terms. We are given n Gaussian arms with unknown means and unit variance. Consider the n-dimensional Euclidean space ℝn, and a collection O of disjoint subsets. Our goal is to determine the subset in O that contains the n-dimensional vector of the means. The problem generalizes most pure exploration bandit problems studied in the literature. We provide the first nearly optimal sample complexity upper and lower bounds for the problem.