Combinatorial Semi-Bandits

Latest papers

13 papers3 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Three Worlds for the Price of a Logarithm: Baseline-Protected Best-of-Both-Worlds Combinatorial Semi-Bandits
Oct 26, 2026Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-GkaragkounisBest-of-Both-Worlds Bandits Combinatorial Semi-Bandits
Department of Economics, University of Wisconsin–Madison · Department of Finance, University of Wisconsin–Madison · Department of Computer Sciences, University of Wisconsin–Madison
Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems
Oct 17, 2026Zhengjia Zhuo, Viswanath NagarajanStochastic Optimization Combinatorial Semi-Bandits
Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.
Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits
Oct 5, 2026Vikram Kakaria, Anish Kataria, Anany KotawalaThompson Sampling Multi-Armed Bandits
Princeton University
Selecting k Paths with the Minimum Longest Path Length in the Stochastic Semi-Bandit Setting
Sep 13, 2026Shunsuke Aoki, Atsuyoshi NakamuraGraph Bandits Combinatorial Semi-Bandits
Graduate School of Information Science and Technology, Hokkaido University Kita 14, Nishi 9, Kita-ku, Sapporo, Hokkaido, 060-0814, Japan
Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation
Jul 15, 2026Hao Qin, Chicheng ZhangCombinatorial Semi-Bandits Contextual Bandits
The University of Arizona
Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals
Jun 12, 2026Christoph Bauschmann, Setareh MaghsudiReward Modeling Multi-Armed Bandits
Department of Electrical Engineering and Information Technology Ruhr University Bochum Bochum, Germany
Learning to Bid in FCR Markets: A Best-of-Both-Worlds Approach
May 29, 2026Marius Potfer, Cheng Wan, Pierre GruetBest-of-Both-Worlds Bandits Combinatorial Semi-Bandits
ENSAE, CREST (Fairplay joint team), 5 Av. Le Chatelier, 91120, Palaiseau, France · EDF Lab Paris-Saclay, FiME (Laboratoire de Finance des Marchés de l’Énergie), 7 Bd Gaspard Monge, 91120, Palaiseau, France
The Sample Complexity of Multiclass and Sparse Contextual Bandits
May 28, 2026Liad Erez, Fan Chen, Alon Cohen +4Combinatorial Semi-Bandits Contextual Bandits
1Tel Aviv University, Israel · 2Massachusetts Institute of Technology, USA · 3Google Research Tel Aviv, Israel +1
Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits
May 10, 2026Zhiming Huang, Bingshan Hu, Jianping PanThompson Sampling Multi-Armed Bandits
Paul G. Allen School of Computer Science & Engineering, University of Washington, WA, USA · Department of Computer Science, University of British Columbia, BC, Canada · Department of Computer Science, University of Victoria, BC, Canada
Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits
Apr 16, 2026Emre Özyıldırım, Barış Yaycı, Umut Eren Akturk +1Multi-Armed Bandits Combinatorial Semi-Bandits
Department of Electrical and Electronics Engineering, Bilkent University, Ankara, Türkiye
Covariance-adapting algorithm for semi-bandits with application to sparse rewards
Apr 15, 2026Pierre Perrault, Vianney Perchet, Michal ValkoCombinatorial Semi-Bandits Multi-Armed Bandits
Inria Lille & ENS Paris-Saclay · ENSAE & Criteo AI Lab · DeepMind Paris
A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$ -Set Semi-Bandit Problem
Mar 12, 2026Botao Chen, Jongyeong Lee, Chansoo Kim +1Follow-the-Perturbed-Leader Best-of-Both-Worlds Bandits
Department of Systems Science Graduate School of Informatics, Kyoto University Kyoto, Japan · Computational Science Research Center Korea Institute of Science and Technology Seoul, Korea · Computational Science Research Center Korea Institute of Science and Technology & University of Science and Technology Seoul, Korea +1
Online Budget Allocation with Censored Semi-Bandit Feedback
Aug 7, 2025François Bachoc, Nicolò Cesa-Bianchi, Tommaso Cesari +1Online Resource Allocation Bandit Learning
Universit´e de Lille, Institut universitaire de France (IUF), Lille, France · Universit`a degli Studi di Milano, Department of Computer Science, Milano, Italy · EECS, University of Ottawa, Ottawa, Canada, K1N 6N5 +1

Oct 26, 2026J/K move · Enter open · S save

Three Worlds for the Price of a Logarithm: Baseline-Protected Best-of-Both-Worlds Combinatorial Semi-Bandits

Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis

Department of Economics, University of Wisconsin–Madison · Department of Finance, University of Wisconsin–Madison · Department of Computer Sciences, University of Wisconsin–Madison

Best-of-Both-Worlds Bandits Combinatorial Semi-Bandits Multi-Armed Bandits Adversarial Bandits

Open paper AskPDF arXiv

Improving on a baseline requires exploring away from it, precisely where its performance may be lost. We propose DUET (Doubling Under Empirical Tests), a horizon-free phased mixing scheme for combinatorial semi-bandits with arbitrary finite action sets. Two observable tests decide when to double the learning weight and when to double the empirical-regret budget and restart. We instantiate the scheme with entropy-FTRL in mixed phases and hybrid-FTRL in pure phases. Assuming the baseline selects every arm with positive probability, this instantiation keeps expected baseline regret logarithmic in

T

, while its expected regret to every fixed action is

\widetilde{O}(\sqrt{T})

under non-anticipating adversarial losses and polylogarithmic, gap-dependent, under i.i.d. losses with a unique optimal action. All three guarantees hold at every deterministic horizon, and the algorithm knows neither the horizon, nor the gap, nor the environment type. Baseline protection, adversarial robustness, and stochastic adaptivity thus come from one scheme and two base learners, at the price of a logarithm.