Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
arXiv:2101.08534
Abstract
Combinatorial bandits with semi-bandit feedback generalize multi-armed bandits, where the agent chooses sets of arms and observes a noisy reward for each arm contained in the chosen set. The action set satisfies a given structure such as forming a base of a matroid or a path in a graph. We focus on the pure-exploration problem of identifying the best arm with fixed confidence, as well as a more general setting, where the structure of the answer set differs from the one of the action set. Using the recently popularized game framework, we interpret this problem as a sequential zero-sum game and develop a CombGame meta-algorithm whose instances are asymptotically optimal algorithms with finite time guarantees. In addition to comparing two families of learners to instantiate our meta-algorithm, the main contribution of our work is a specific oracle efficient instance for best-arm identification with combinatorial actions. Based on a projection-free online learning algorithm for convex polytopes, it is the first computationally efficient algorithm which is asymptotically optimal and has competitive empirical performance.
arXiv comment45 pages. 3 tables. Appendices: from A to I. Figures: 1(a), 1(b), 2(a), 2(b), 3(a), 3(b), 3(c), 4(a), 4(b), 5(a), 5(b), 5(c), 5(d), 6(a), 6(b). To be published in the 32nd International Conference on Algorithmic Learning Theory and the Proceedings of Machine Learning Research vol 132:1-45, 2021
References in corpus (20)
- On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
- lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
- Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
- Combinatorial Bandits Revisited
- Optimal Best Arm Identification with Fixed Confidence
- Matroid Bandits: Fast Combinatorial Optimization with Learning
- Projection-free Online Learning
- A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
- What Doubling Tricks Can and Can't Do for Multi-Armed Bandits
- Efficient Learning in Large-Scale Combinatorial Semi-Bandits
- Gamification of Pure Exploration for Linear Bandits
- Top-k Combinatorial Bandits with Full-Bandit Feedback
- Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals
- The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
- Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling
- Polynomial-time Algorithms for Multiple-arm Identification with Full-bandit Feedback
- Structure Adaptive Algorithms for Stochastic Bandits
- Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners
- Information Directed Sampling for Linear Partial Monitoring
- Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits