Combinatorial Multi-Armed Bandits

Ask about this topic

Overview

Combinatorial multi-armed bandits study sequential decisions where each round selects a set, slate, path, or allocation of arms, often under budgets or other constraints. The goal is to earn high cumulative reward while learning from semi-bandit feedback about individual selected arms or full-bandit feedback about the choice as a whole. Common approaches include UCB and Thompson sampling, online optimization and primal-dual methods, and approximation algorithms for structured objectives such as submodular maximization. A central tension is balancing regret, computational cost, and feedback limits, especially when action spaces are huge or decisions must also satisfy fairness, resource, or multi-objective requirements.

Latest papers

CardsList

33 papers5 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

  1. Gaussian Process Bandits for Constraint Black Box Lever Optimization

    Oct 27, 2026Bram van den Akker, Hidde Fokkema, Anastasiia KornilovaBlack-Box OptimizationMulti-Armed Bandits

    Booking.com Amsterdam, The Netherlands · University of Amsterdam Amsterdam, The Netherlands

  2. Cascading Bandits with Noisy Observations: Algorithms and Regret Bounds

    Oct 21, 2026Yashaswini Kaluguri, Nikhil KaramchandaniMulti-Armed BanditsBandit Learning

    Department of Electrical Engineering, Indian Institute of Technology Bombay, Mumbai, India

  3. m-Set Adversarial Bandits with Winner Feedback

    Oct 7, 2026Nicolò Cesa-Bianchi, Matteo PapiniMulti-Armed BanditsBandit Learning

    Universit`a degli Studi di Milano · Politecnico di Milano

  4. AFA-BANDIT: Provably Near-Optimal Online Multi-Feature Classification Under Budget Constraints

    Oct 6, 2026AbdAlRahman Odeh, Teng-Hui Huang, Hesham El GamalActive LearningActive Feature Acquisition

    The University of Sydney School of Electrical and Computer Engineering Sydney 2006, NSW, Australia · The University of Sydney Faculty of Engineering Sydney 2006, NSW, Australia

  5. Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits

    Oct 5, 2026Vikram Kakaria, Anish Kataria, Anany KotawalaThompson SamplingMulti-Armed Bandits

    Princeton University

  6. Challenges and Solutions for Bandits in the Wild: Warm-Started Mixture Bandits for Cross-Cohort Slate Recommendation

    Sep 29, 2026Serafima Lebedeva, Sumantrak Mukherjee, Ali Arshad Sadal +8Multi-Armed BanditsCold-Start Recommendation

    German Research Center for Artificial Intelligence (DFKI), Kaiserslautern · RPTU, Kaiserslautern-Landau · LMU, Munich

  7. Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits

    Sep 17, 2026Lishang Xu, Guodong Ma, Pengcheng Weng +1Multi-Armed BanditsRegret Minimization

    University of Bern · EPFL

  8. Selecting k Paths with the Minimum Longest Path Length in the Stochastic Semi-Bandit Setting

    Sep 13, 2026Shunsuke Aoki, Atsuyoshi NakamuraGraph BanditsCombinatorial Semi-Bandits

    Graduate School of Information Science and Technology, Hokkaido University Kita 14, Nishi 9, Kita-ku, Sapporo, Hokkaido, 060-0814, Japan

  9. Multinomial Subset Routing with Sum-Max Rewards and Operational Constraints

    Aug 17, 2026Quan Zhou, Yiyan HuangBlackwell ApproachabilityOnline Resource Allocation

  10. An Efficient Minimax-Optimal Algorithm for Adversarial mm-Set Bandits

    Aug 12, 2026Francesco Bacchiocchi, Tommaso Cesari, Roberto ColomboniCombinatorial Multi-Armed BanditsAdversarial Bandits

    DEIB, Politecnico di Milano, Milano, Italy · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom

  11. Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids, and Full-Bandit Learning

    Aug 12, 2026Vaneet AggarwalSubmodular OptimizationCombinatorial Multi-Armed Bandits

    V. Aggarwal is with Purdue University, West Lafayette IN, USA

  12. Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

    Aug 5, 2026Bo Xue, Ji Cheng, Haodong Jing +2Multi-Armed BanditsCombinatorial Multi-Armed Bandits

    City University of Hong Kong. · Xi’an Jiaotong University. · Northwestern Polytechnical University.

  13. Top-kk Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection

    Jul 28, 2026Nicolas Gutowski, Fabien Chhel, Alexandre Letard +1Multi-Armed BanditsCombinatorial Multi-Armed Bandits

    Université d’Angers, LERIA, SFR MATHSTIC, Angers, France · ESEO, ERIS, Angers, France · AlphaEdge, Saint-Barthélémy-d’Anjou, France +1

  14. Co-planning of Flight Corridors and Communication Infrastructure for Urban Drone Logistics Networks

    Jul 27, 2026Yingjie He, Yikang Wang, Zhenyu GaoMulti-Armed BanditsUAV Navigation

  15. Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation

    Jul 15, 2026Hao Qin, Chicheng ZhangCombinatorial Semi-BanditsContextual Bandits

    The University of Arizona

  16. Contextual Slate GLM Bandits with Limited Adaptivity

    Jun 30, 2026Tanmay Goyal, Sukruta Prakash Midigeshi, Gaurav SinhaMulti-Armed BanditsContextual Bandits

    Microsoft Research India

  17. Selective Ensemble Based on Preference-Directed Multi-Objective Bandits

    Jun 20, 2026Lanjihong Ma, Zhen-Yu Zhang, Masashi Sugiyama +1Multi-Armed BanditsEnsemble Learning

    Department of Computer Science, Zhejiang Gongshang University, China · Center for Advanced Intelligence Project, RIKEN, Japan · Graduate School of Frontier Sciences, The University of Tokyo, Japan +1

  18. Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits

    Jun 17, 2026Lennert Saerens, Bram Silue, Eleni Litsa +2Thompson SamplingMulti-Armed Bandits

    Artificial Intelligence Lab, Departement of Computer Science, Vrije Universiteit Brussel, Brussels, Belgium · imec, Leuven, Belgium

  19. Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries

    Jun 7, 2026Linfeng Cao, Ming Shi, Ness B. ShroffMulti-Armed BanditsCombinatorial Multi-Armed Bandits

    Department of Computer Science and Engineering, The Ohio State University · Department of Electrical Engineering, University at Buffalo · Department of Electrical and Computer Engineering, The Ohio State University

  20. Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits

    May 14, 2026Donghao Li, Chengshuai Shi, Weijuan Ou +2Multi-Armed BanditsLLM Prompting

    University of Virginia, Charlottesville, VA 22904, USA · Princeton University, Princeton, NJ 08544, USA · Southern University of Science and Technology, Shenzhen, Guangdong 518055, China

  21. Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits

    May 10, 2026Zhiming Huang, Bingshan Hu, Jianping PanThompson SamplingMulti-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

  22. Meritocratic Fairness in Budgeted Combinatorial Multi-armed Bandits via Shapley Values

    May 1, 2026Shradha Sharma, Swapnil Dhamal, Shweta JainMulti-Armed BanditsCooperative Game Theory

    Indian Institute of Technology Ropar

  23. Covariance-adapting algorithm for semi-bandits with application to sparse rewards

    Apr 15, 2026Pierre Perrault, Vianney Perchet, Michal ValkoCombinatorial Semi-BanditsMulti-Armed Bandits

    Inria Lille & ENS Paris-Saclay · ENSAE & Criteo AI Lab · DeepMind Paris

  24. Offline Local Search for Online Stochastic Bandits

    Apr 10, 2026Gerdus Benadè, Rathish Das, Thomas LavastidaCombinatorial Multi-Armed BanditsStochastic Optimization

    Boston University, MA, USA. · University of Houston, TX, USA. · University of Texas at Dallas, TX, USA.

  25. Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays

    Apr 7, 2026Pranjal Sharma, Zirui Xu, Vasileios TzoumasSubmodular OptimizationDistributed Optimization

    Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109, USA

  26. A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for mm-Set Semi-Bandit Problem

    Mar 12, 2026Botao Chen, Jongyeong Lee, Chansoo Kim +1Follow-the-Perturbed-LeaderCombinatorial 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

  27. Combinatorial Allocation Bandits with Nonlinear Arm Utility

    Mar 7, 2026Yuki Shibukawa, Koichi Tanaka, Yuta Saito +1Online Resource AllocationCombinatorial Multi-Armed Bandits

    The University of Tokyo and RIKEN · Keio University · Hanuku-kaso, Co., Ltd.

  28. Adapter-Augmented Bandits for Online Multi-Constrained Multi-Modal Inference Scheduling

    Mar 6, 2026Xianzhi Zhang, Yue Xu, Yinlin Zhu +4LLM Inference SchedulingMulti-Armed Bandits

    School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou, 510006, China · School of Computing, Macquarie University, NSW 2109, Australia

  29. Adaptive Combinatorial Experimental Design: Pareto Optimality for Decision-Making and Inference

    Feb 27, 2026Hongrui Xie, Junyu Cao, Kan XuCombinatorial Multi-Armed BanditsExploration-Exploitation Tradeoff

    University of Science and Technology of China · The University of Texas at Austin · Arizona State University

  30. Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization

    Feb 22, 2026Zirui Xu, Vasileios TzoumasMulti-Agent CoordinationSubmodular Optimization

    Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA