{"ID":2877971,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.18768","arxiv_id":"2508.18768","title":"Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits","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 delivers substantial per-round speed-ups, making it well-suited for large-scale, real-time applications.","short_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-Regular...","url_abs":"https://arxiv.org/abs/2508.18768","url_pdf":"https://arxiv.org/pdf/2508.18768v2","authors":"[\"Mengmeng Li\",\"Philipp J. Schneider\",\"Jelisaveta Aleksić\",\"Daniel Kuhn\"]","published":"2025-08-26T07:51:22Z","proceeding":"stat.ML","tasks":"[\"stat.ML\",\"cs.LG\"]","methods":"[]","has_code":false}