Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback
From MaRDI portal
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.
Recommendations
- On the complexity of best-arm identification in multi-armed bandit models
- On Sequential Elimination Algorithms for Best-Arm Identification in Multi-Armed Bandits
- Statistically Robust, Risk-Averse Best Arm Identification in Multi-Armed Bandits
- Asymptotically optimal multi-armed bandit policies under a cost constraint
- Best arm identification in generalized linear bandits
- A Structured Multiarmed Bandit Problem and the Greedy Policy
- Finite-time analysis of the multiarmed bandit problem
- The multi-armed bandit problem: an efficient nonparametric solution
- The Multi-Armed Bandit Problem: Decomposition and Computation
Cites work
- Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems
- Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designs
- Approximation of the quadratic knapsack problem
- Asymptotically efficient adaptive allocation rules
- Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: I.I.D. rewards
- Combinatorial bandits
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- Efficient crowdsourcing of unknown experts using bounded multi-armed bandits
- Greedily Finding a Dense Subgraph
- scientific article; zbMATH DE number 2089367 (Why is no real title available?)
- Multi-armed bandit problems with multiple plays and switching cost
- On the complexity of best-arm identification in multi-armed bandit models
- Optimal Design of Experiments
- Powers of tensors and fast matrix multiplication
- Prediction, Learning, and Games
- Random sampling and greedy sparsification for matroid optimization problems
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- Submodularity and randomized rounding techniques for optimal experimental design
- The dense \(k\)-subgraph problem
- The Equivalence of Two Extremum Problems
This page was built for publication: Polynomial-Time Algorithms for Multiple-Arm Identification with Full-Bandit Feedback
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386400)
