Tight Lower Bounds for Combinatorial Multi-Armed Bandits
This work addresses a gap in theoretical understanding for researchers in bandit algorithms by providing foundational lower bounds that apply broadly, though it is incremental in extending prior specific results.
The paper tackles the problem of proving regret lower bounds for combinatorial multi-armed bandits under mild assumptions for all smooth reward functions, deriving both problem-dependent and problem-independent bounds and showing they are tight up to log-factors.
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.