# Pure Exploration of Multi-armed Bandit Under Matroid Constraints

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2016.

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

- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Optimal Batched Best Arm Identification](https://mlsanity.com/paper/2310.14129/) (2023)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Combinatorial Pure Exploration with Bottleneck Reward Function](https://mlsanity.com/paper/2102.12094/) (2021)
- [Matroid Semi-Bandits in Sublinear Time](https://mlsanity.com/paper/2405.17968/) (2024)
- [Recurrent Submodular Welfare and Matroid Blocking Bandits](https://mlsanity.com/paper/2102.00321/) (2021)
- [Thompson Sampling for Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit](https://mlsanity.com/paper/2308.10238/) (2023)
- [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)
- [Multi-Metric Adaptive Experimental Design Under a Fixed Budget with Validation](https://mlsanity.com/paper/2506.03062/) (2025)
- [A Fast Algorithm for PAC Combinatorial Pure Exploration](https://mlsanity.com/paper/2112.04197/) (2021)
- [Efficient Matroid Bandit Linear Optimization Leveraging Unimodality](https://mlsanity.com/paper/2512.00605/) (2025)
- [The Price of Decentralization in Top-K Arm Identification](https://mlsanity.com/paper/2608.22120/) (2026)
- [Few-for-Many Best-Arm Identification in Multi-Objective Bandits](https://mlsanity.com/paper/2610.16840/) (2026)

## Abstract (arXiv)

We study the pure exploration problem subject to a matroid constraint (Best-Basis) in a stochastic multi-armed bandit game. In a Best-Basis instance, we are given n stochastic arms with unknown reward distributions, as well as a matroid M over the arms. Let the weight of an arm be the mean of its reward distribution. Our goal is to identify a basis of M with the maximum total weight, using as few samples as possible. The problem is a significant generalization of the best arm identification problem and the top-k arm identification problem, which have attracted significant attentions in recent years. We study both the exact and PAC versions of Best-Basis, and provide algorithms with nearly-optimal sample complexities for these versions. Our results generalize and/or improve on several previous results for the top-k arm identification problem and the combinatorial pure exploration problem when the combinatorial constraint is a matroid.