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.
arXiv comment30 pages, Advances in Neural Information Processing Systems 28 (NIPS 2015)
References in corpus (5)
- The on-line shortest path problem under partial monitoring
- Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
- Matroid Bandits: Fast Combinatorial Optimization with Learning
- Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
- Efficient Learning in Large-Scale Combinatorial Semi-Bandits
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