# Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2019.

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

- [Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback](https://mlsanity.com/paper/2101.08534/) (2021)
- [Adversarial Combinatorial Bandits with General Non-linear Reward Functions](https://mlsanity.com/paper/2101.01301/) (2021)
- [Query-Efficient Correlation Clustering with Noisy Oracle](https://mlsanity.com/paper/2402.01400/) (2024)
- [Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget](https://mlsanity.com/paper/2202.04487/) (2022)
- [Combinatorial Pure Exploration with Bottleneck Reward Function](https://mlsanity.com/paper/2102.12094/) (2021)
- [Thompson Exploration with Best Challenger Rule in Best Arm Identification](https://mlsanity.com/paper/2310.00539/) (2023)
- [Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget](https://mlsanity.com/paper/2506.02386/) (2025)
- [Master-slave Deep Architecture for Top-K Multi-armed Bandits with Non-linear Bandit Feedback and Diversity Constraints](https://mlsanity.com/paper/2308.12680/) (2023)

## Abstract (arXiv)

We study the problem of stochastic combinatorial pure exploration (CPE), where an agent sequentially pulls a set of single arms (a.k.a. a super arm) and tries to find the best super arm. Among a variety of problem settings of the CPE, we focus on the full-bandit setting, where we cannot observe the reward of each single arm, but only the sum of the rewards. Although we can regard the CPE with full-bandit feedback as a special case of pure exploration in linear bandits, an approach based on linear bandits is not computationally feasible since the number of super arms may be exponential. In this paper, we first propose a polynomial-time bandit algorithm for the CPE under general combinatorial constraints and provide an upper bound of the sample complexity. Second, we design an approximation algorithm for the 0-1 quadratic maximization problem, which arises in many bandit algorithms with confidence ellipsoids. Based on our approximation algorithm, we propose novel bandit algorithms for the top-k selection problem, and prove that our algorithms run in polynomial time. Finally, we conduct experiments on synthetic and real-world datasets, and confirm the validity of our theoretical analysis in terms of both the computation time and the sample complexity.