[2508.18768] Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits

Statistics > Machine Learning arXiv:2508.18768 (stat) [Submitted on 26 Aug 2025 (v1), last revised 26 Mar 2026 (this version, v2)] Title:Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits Authors:Mengmeng Li, Philipp J. Schneider, Jelisaveta Aleksić, Daniel Kuhn View a PDF of the paper titled Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits, by Mengmeng Li and 3 other authors View PDF HTML (experimental) Abstract:We introduce the first best-of-both-worlds algorithm for contextual combinatorial semi-bandits that simultaneously guarantees $\widetilde{\mathcal{O}}(\sqrt{T})$ regret in the adversarial regime and $\widetilde{\mathcal{O}}(\ln T)$ regret in the corrupted stochastic regime. Our approach builds on the Follow-the-Regularized-Leader (FTRL) framework equipped with a Shannon entropy regularizer, yielding a flexible method that admits efficient implementations. Beyond regret bounds, we tackle the practical bottleneck in FTRL (or, equivalently, Online Stochastic Mirror Descent) arising from the high-dimensional projection step encountered in each round of interaction. By leveraging the Karush-Kuhn-Tucker conditions, we transform the $K$-dimensional convex projection problem into a single-variable root-finding problem, dramatically accelerating each round. Empirical evaluations demonstrate that this combined strategy not only attains the attractive regret bounds of best-of-both-worlds algorithms but also de...