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

2025/08/26 by Li, Mengmeng, Schneider, Philipp, Aleksić, Jelisaveta +1
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2508.18768

Abstract

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.

Citations

• Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits
• Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits
• Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm
• A Blackbox Approach to Best of Both Worlds in Bandits and Beyond
• Best of Both Worlds Model Selection
• Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs
• Adapting to Misspecification in Contextual Bandits
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions
• Bandit Algorithms
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
• Thompson Sampling for Combinatorial Semi-Bandits
• CVXPY: A Python-Embedded Modeling Language for Convex Optimization
• Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits
• First-order regret bounds for combinatorial semi-bandits
• Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems
• The Nonstochastic Multiarmed Bandit Problem

Related

• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits
• A Blackbox Approach to Best of Both Worlds in Bandits and Beyond
• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits
• Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously
• Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits