Tight Lower Bounds for Combinatorial Multi-Armed Bandits
  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.
