# Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits

Source: [Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits](<https://www.sota2.com/research/paper/68fa7ae71e209131cea85cf7>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-03-28T05:00:12.409Z

Authors: Mengmeng Li, Philipp J. Schneider, Jelisaveta Aleksi\\'c, Daniel Kuhn

Published: 2025-08-26T07:51:22.000Z

## 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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Regret Minimization on Contextual Combinatorial Bandits](<https://www.sota2.com/research/sota/regret-minimization-on-contextual-combinatorial-bandits.md>): Regret Minimization; Contextual Combinatorial Bandits; Stochastic Regret: 3.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2508.18768>)

[PDF](<https://arxiv.org/pdf/2508.18768.pdf>)
