Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
This work addresses a foundational challenge in online learning by providing a unified solution for semi-bandit problems, which is incremental as it extends prior work on multi-armed bandits.
The paper tackles the problem of designing a semi-bandit algorithm that achieves optimal regret in both stochastic and adversarial environments without prior knowledge of the regime or time horizon, resulting in O(log T) regret for stochastic and O(sqrt(T)) for adversarial settings with optimal constants for specific instances.
We develop the first general semi-bandit algorithm that simultaneously achieves $\mathcal{O}(\log T)$ regret for stochastic environments and $\mathcal{O}(\sqrt{T})$ regret for adversarial environments without knowledge of the regime or the number of rounds $T$. The leading problem-dependent constants of our bounds are not only optimal in some worst-case sense studied previously, but also optimal for two concrete instances of semi-bandit problems. Our algorithm and analysis extend the recent work of (Zimmert & Seldin, 2019) for the special case of multi-armed bandit, but importantly requires a novel hybrid regularizer designed specifically for semi-bandit. Experimental results on synthetic data show that our algorithm indeed performs well uniformly over different environments. We finally provide a preliminary extension of our results to the full bandit feedback.