Combinatorial Multi-Armed Bandits

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

35 papers4 papers in the last four weeks, level with the four weeks before. 0.0% of all new papers.

  1. Adaptive search with path-constrained mobile sensors using multi-arm bandits

    Oct 29, 2026Abraham P. Vinod, Parth K. Thaker, Gautam Dasarathy +1Adaptive SensingMulti-Robot Systems

  2. Gaussian Process Bandits for Constraint Black Box Lever Optimization

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

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

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

  4. m-Set Adversarial Bandits with Winner Feedback

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

  5. 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

  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

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

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

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

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

  9. Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

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

  10. 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

  11. Contextual Slate GLM Bandits with Limited Adaptivity

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

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

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

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

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

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

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

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

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

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

    May 10, 2026Zhiming Huang, Bingshan Hu, Jianping PanThompson SamplingMulti-Armed Bandits

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

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

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

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

  19. Offline Local Search for Online Stochastic Bandits

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

  20. Asynchronous Distributed Bandit Submodular Maximization under Heterogeneous Communication Delays

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

  21. 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-LeaderBest-of-Both-Worlds Bandits

  22. Combinatorial Allocation Bandits with Nonlinear Arm Utility

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

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

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