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

Abstract

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.

arXiv comment21 pages

References in corpus (13)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Powers of Tensors and Fast Matrix Multiplication
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph
• Best-Arm Identification in Linear Bandits
• Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays
• On the Optimal Sample Complexity for Best Arm Identification
• Multiple-Play Bandits in the Position-Based Model
• Fully adaptive algorithm for pure exploration in linear bandits
• Pure Exploration of Multi-armed Bandit Under Matroid Constraints
• Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
• PAC Identification of Many Good Arms in Stochastic Multi-Armed Bandits
• Exploiting Structure of Uncertainty for Efficient Matroid Semi-Bandits

Cited by in corpus (5)

• Adversarial Combinatorial Bandits with General Non-linear Reward Functions
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
• Combinatorial Pure Exploration with Full-Bandit or Partial Linear Feedback
• Combinatorial Pure Exploration with Bottleneck Reward Function
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation