Combinatorial Bandits Revisited
arXiv:1502.03475
Abstract
This paper investigates stochastic and adversarial combinatorial multi-armed bandit problems. In the stochastic setting under semi-bandit feedback, we derive a problem-specific regret lower bound, and discuss its scaling with the dimension of the decision space. We propose ESCB, an algorithm that efficiently exploits the structure of the problem and provide a finite-time analysis of its regret. ESCB has better performance guarantees than existing algorithms, and significantly outperforms these algorithms in practice. In the adversarial setting under bandit feedback, we propose \textsc{CombEXP}, an algorithm with the same regret scaling as state-of-the-art algorithms, but with lower computational complexity for some combinatorial problems.
30 pages, Advances in Neural Information Processing Systems 28 (NIPS 2015)
References in corpus (2)
Cited by in corpus (47)
- Online Learning: A Comprehensive Survey
- Combinatorial Multi-Armed Bandit with General Reward Functions
- DCM Bandits: Learning to Rank with Multiple Clicks
- Thompson Sampling for Combinatorial Semi-Bandits
- A Practical Algorithm for Multiplayer Bandits when Arm Means Vary Among Players
- Multiple-Play Bandits in the Position-Based Model
- Online Influence Maximization under Linear Threshold Model
- Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
- Combinatorial Sleeping Bandits with Fairness Constraints
- Tight Lower Bounds for Combinatorial Multi-Armed Bandits
- Combinatorial Semi-Bandit in the Non-Stationary Environment
- Contextual Blocking Bandits
- Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
- Causal Bandits with Unknown Graph Structure
- Nearly Optimal Algorithms for Piecewise-Stationary Cascading Bandits
- A Near-Optimal Change-Detection Based Algorithm for Piecewise-Stationary Combinatorial Semi-Bandits
- (Locally) Differentially Private Combinatorial Semi-Bandits
- Top- eXtreme Contextual Bandits with Arm Hierarchy
- Combinatorial Blocking Bandits with Stochastic Delays
- Online Learning of Independent Cascade Models with Node-level Feedback
- A survey on multi-player bandits
- Bandit Learning with Delayed Impact of Actions
- Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback
- (Almost) Free Incentivized Exploration from Decentralized Learning Agents
- Exploiting Structure of Uncertainty for Efficient Matroid Semi-Bandits
- Efficient Learning-based Scheduling for Information Freshness in Wireless Networks
- Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time
- Recurrent Submodular Welfare and Matroid Blocking Bandits
- Non-Stationary Delayed Bandits with Intermediate Observations
- Experimental Design for Regret Minimization in Linear Bandits
- Thompson Sampling Algorithms for Cascading Bandits
- Continuous Assortment Optimization with Logit Choice Probabilities under Incomplete Information
- Combinatorial Pure Exploration with Continuous and Separable Reward Functions and Its Applications (Extended Version)
- On the Suboptimality of Thompson Sampling in High Dimensions
- Combinatorial Pure Exploration with Bottleneck Reward Function
- Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem
- Combining Reward and Rank Signals for Slate Recommendation
- Simple Combinatorial Algorithms for Combinatorial Bandits: Corruptions and Approximations
- Combinatorial Bandits without Total Order for Arms
- Screening for an Infectious Disease as a Problem in Stochastic Control
- Combinatorial Bandits under Strategic Manipulations
- Sequential ranking under random semi-bandit feedback
- The Combinatorial Multi-Bandit Problem and its Application to Energy Management
- Censored Semi-Bandits for Resource Allocation
- Constant or logarithmic regret in asynchronous multiplayer bandits
- Risk-Aware Algorithms for Combinatorial Semi-Bandits
- Sleeping Combinatorial Bandits