Abstract
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.
Introduction
In online learning, the combinatorial semi-bandit is a significant extension of the classic Multi-Armed Bandit (MAB) problem. In this setting, a learner selects a subset of arms (a combinatorial action) and observes the individual loss of each chosen arm. The objective is to minimize regret—the cumulative loss difference between the learner's choices and the best fixed action in hindsight.
Historically, algorithms have been tailored for either stochastic environments (where losses follow a fixed distribution) or adversarial environments (where losses are arbitrary). Stochastic settings typically allow for logarithmic regret ($\mathcal{O}(\log T)$), while adversarial settings necessitate square-root regret ($\mathcal{O}(\sqrt{T})$). Achieving "best-of-both-worlds" performance—optimality in both regimes without prior knowledge of the environment—has been a long-standing challenge for semi-bandits.
The HYBRID Algorithm
The proposed solution utilizes the Follow-the-Regularized-Leader (FTRL) framework, centered around a novel hybrid regularizer. This regularizer is designed to handle the unique information structure of semi-bandits, where chosen arms provide full information while unchosen arms provide none.
The hybrid regularizer combines two components:
- Tsallis Entropy ($-\sqrt{x}$): Optimal for bandit settings with limited information, dominating the behavior for arms with low selection probability.
- Shannon Entropy ($(1-x)\log(1-x)$): Optimal for full-information settings, dominating for arms frequently included in the optimal subset.
By blending these, the algorithm naturally transitions between exploration and exploitation. Coupled with a simple time-decaying learning rate $\eta_t = 1/\sqrt{t}$, the algorithm remains computationally efficient and easy to implement.
Experimental Evaluation
The authors evaluated the HYBRID algorithm against synthetic datasets simulating both stochastic and adversarial regimes. The primary test case was the $m$-set problem, where the learner selects exactly $m=5$ arms from a total of $d=10$ over $T=10^7$ rounds.
- Stochastic Regime: Arm losses were sampled from fixed distributions with a defined gap $\Delta$ between optimal and sub-optimal arms.
- Adversarial Regime: A "stochastically constrained adversarial" setup was used, where mean losses shift periodically, testing the algorithm's ability to adapt to non-stationary conditions.
Key Results
The HYBRID algorithm demonstrates theoretical and empirical superiority. Theoretically, it achieves the optimal $\mathcal{O}(\log T)$ and $\mathcal{O}(\sqrt{T})$ bounds for stochastic and adversarial settings, respectively.
Empirically, as shown in the figure above, the HYBRID algorithm (dark blue) maintains low regret across both environments. In stochastic settings (a), it is competitive with specialized algorithms like CombUCB. Crucially, in adversarial settings (b), while stochastic-only algorithms like CUCB suffer linear regret, HYBRID maintains the expected square-root growth, outperforming standard adversarial baselines like EXP2.
Conclusion and Future Work
This work provides the first general, optimal best-of-both-worlds algorithm for semi-bandits. While the results are robust for semi-bandit feedback, extending this optimality to full bandit feedback (where only the total subset loss is observed) remains an open challenge for general combinatorial sets. Additionally, while the algorithm is worst-case optimal, future research may investigate "instance-optimality" to determine if the constants can be further refined for specific arm configurations.
Summary updated