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

arXiv: https://arxiv.org/abs/2508.18768 · HTML: https://mlsanity.com/paper/2508.18768/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 26 Aug 2025.

## Builds on (most cited first, 19 of 19)

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [Real-Time Bidding with Multi-Agent Reinforcement Learning in Display Advertising](https://mlsanity.com/paper/1802.09756/) (2018)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2002.00287/) (2020)
- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Practical Data Poisoning Attack against Next-Item Recommendation](https://mlsanity.com/paper/2004.03728/) (2020)
- [First-order regret bounds for combinatorial semi-bandits](https://mlsanity.com/paper/1502.06354/) (2015)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits](https://mlsanity.com/paper/1503.05087/) (2015)
- [Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm](https://mlsanity.com/paper/2303.06825/) (2023)
- [Best of Both Worlds Model Selection](https://mlsanity.com/paper/2206.14912/) (2022)
- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions](https://mlsanity.com/paper/2101.07957/) (2021)
- [Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits](https://mlsanity.com/paper/2409.20440/) (2024)

## Built on by (most cited first, 2 of 2)

- [Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation](https://mlsanity.com/paper/2607.13686/) (2026)
- [Learning Safely Without Knowing the World:COMPASS-Hedge](https://mlsanity.com/paper/2603.22348/) (2026)

## Abstract (arXiv)

We introduce the first best-of-both-worlds algorithm for contextual combinatorial semi-bandits that simultaneously guarantees widetildeO(√T) regret in the adversarial regime and widetildeO(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.