Combinatorial Semi-Bandits

Follow this topic Ask about this topic

Latest papers

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

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 GruetCombinatorial Semi-Bandits Automated Bidding
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 Combinatorial Semi-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

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

Near-Optimal Regret for Semi-Bandit Learning of Monotone Stochastic Problems

Zhengjia Zhuo, Viswanath Nagarajan

Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.

Stochastic Optimization Combinatorial Semi-Bandits

Open paper AskPDF arXiv

We consider the task of learning an (approximately) optimal policy for stochastic optimization problems where the true distributions are unknown. In each period, the algorithm plays a policy for the stochastic problem and observes semi-bandit feedback, i.e., it only receives new samples from the random variables that were selected by the policy. We obtain an algorithm that works for a large class of

monotone'' stochastic problems, including prophet inequality, Pandora's box, series testing, stochastic knapsack and stochastic matching. We obtain $\tilde{O}(\sqrt{nkT})$ regret for

weakly'' monotone problems and

\tilde{O}(\sqrt{nT})

regret for

strongly'' monotone problems, where $T$ is the number of periods, $n$ is the problem dimension (number of random variables) and $k$ is the maximum support size of any random variable. This improves over previous regret bounds by a $\sqrt{n}$ factor. In fact, our dependence on $n$ and $T$ is the best-possible due the $Ω(\sqrt{nT})$ lower bound for multi-armed-bandits. Our main technique is the use of Hellinger distance in bounding the

error'' between the true and learned distributions, and the use of a constant-factor chain rule for the Hellinger distance of dependent random variables.