# A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit

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

## Key facts

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

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

- [Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit](https://mlsanity.com/paper/2308.10238/) (2023)
- [Fixed-Budget Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit](https://mlsanity.com/paper/2310.15681/) (2023)
- [Active Hypothesis Testing for Correlated Combinatorial Anomaly Detection](https://mlsanity.com/paper/2601.17430/) (2026)
- [FleetSieve: Decision-Critical Profiling for SLO-Aware LLM Fleet Configuration](https://mlsanity.com/paper/2608.19659/) (2026)

## Abstract (arXiv)

We study the real-valued combinatorial pure exploration problem in the stochastic multi-armed bandit (R-CPE-MAB). We study the case where the size of the action set is polynomial with respect to the number of arms. In such a case, the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We introduce an algorithm named the combinatorial gap-based exploration (CombGapE) algorithm, whose sample complexity upper bound matches the lower bound up to a problem-dependent constant factor. We numerically show that the CombGapE algorithm outperforms existing methods significantly in both synthetic and real-world datasets.