Tight Lower Bounds for Combinatorial Multi-Armed Bandits
arXiv:2002.05392
Abstract
The Combinatorial Multi-Armed Bandit problem is a sequential decision-making problem in which an agent selects a set of arms on each round, observes feedback for each of these arms and aims to maximize a known reward function of the arms it chose. While previous work proved regret upper bounds in this setting for general reward functions, only a few works provided matching lower bounds, all for specific reward functions. In this work, we prove regret lower bounds for combinatorial bandits that hold under mild assumptions for all smooth reward functions. We derive both problem-dependent and problem-independent bounds and show that the recently proposed Gini-weighted smoothness parameter (Merlis and Mannor, 2019) also determines the lower bounds for monotone reward functions. Notably, this implies that our lower bounds are tight up to log-factors.
arXiv commentAccepted to COLT 2020
References in corpus (13)
- On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
- Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
- Combinatorial Bandits Revisited
- Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
- Cascading Bandits: Learning to Rank in the Cascade Model
- Combinatorial Multi-Armed Bandit with General Reward Functions
- Combinatorial Cascading Bandits
- Thompson Sampling for Combinatorial Semi-Bandits
- Improving Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms and Its Applications
- Combinatorial semi-bandit with known covariance
- Top-k Combinatorial Bandits with Full-Bandit Feedback
- Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
- Thompson Sampling for Combinatorial Network Optimization in Unknown Environments