Multi-Armed Bandits

Ask about this topic

Overview

Multi-armed bandits model repeated choices among actions whose rewards are initially unknown, asking how to learn while avoiding too many poor choices. Classic methods such as upper confidence bounds, Thompson sampling, and successive elimination balance exploration and reward; newer work extends them to contextual, linear, and kernel models, as well as combinatorial choices and changing environments. Researchers also study best-arm identification, resource and fairness constraints, delayed or partial feedback, and robust guarantees under heavy-tailed noise or adversarial changes. A central challenge is adapting to structure and practical limits such as memory, computation, and feedback without relying on assumptions that fail in real settings or sacrificing reliable regret and inference guarantees.

Latest papers

CardsList

362 papers43 papers in the last four weeks, up 16% on the four weeks before. 0.3% of all new papers.

  1. Risk-Sensitive Non-Parametric and Kernel Bandits

    Nov 4, 2026Devdan Dey, Sujoy Bhore, Avishek GhoshMulti-Armed BanditsDecision-Making under Uncertainty

    Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

  2. Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning

    Nov 4, 2026Hanzhang Qin, Sophie H. Yu, Yuewei Zhang +1LLM RoutingCost-Aware Inference

    Department of Industrial Systems Engineering and Management, National University of Singapore · The Wharton School of Business, University of Pennsylvania, Philadelphia PA, USA · Department of Industrial Engineering, Tsinghua University, Beijing, China

  3. Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits

    Nov 3, 2026Jongyeong Lee, Hyundam YooGraph BanditsMulti-Armed Bandits

    Korea Institute of Science and Technology · Independent researcher

  4. A Parameter-Free Best-of-Both-Worlds Policy for Queueing Bandits

    Nov 2, 2026Jongyeong Lee, Chansoo KimMulti-Armed BanditsParameter-Free Online Learning

    Korea Institute of Science and Technology · University of Science and Technology

  5. Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry

    Oct 31, 2026Canzhe Zhao, Vincent Y. F. TanAdversarial BanditsFollow-the-Regularized-Leader

    Department of Mathematics, National University of Singapore · Department of Electrical and Computer Engineering, National University of Singapore

  6. Fair Recommender Systems for Intersecting Groups

    Oct 29, 2026Christine Ling, Juba ZianiRecommender SystemsFairness in Recommender Systems

    Georgia Institute of Technology.

  7. Achieving Minimax-Optimal First-Order and Best-of-Both-Worlds Regret Simultaneously in Multi-Armed Bandits

    Oct 29, 2026Mengxiao ZhangMulti-Armed BanditsMinimax Regret

    University of Iowa

  8. Satisficing Regret Minimization in Bandits with Knapsacks

    Oct 29, 2026Qing Feng, Tianyi Ma, Ruihao ZhuRegret MinimizationMulti-Armed Bandits

    School of Operations Research and Information Engineering, Cornell University · SC Johnson College of Business, Cornell University

  9. Planned Restlessness: Delayed Meta Bandits with Budgets

    Oct 28, 2026Sudipto GuhaMulti-Armed BanditsBandits with Delayed Feedback

  10. Floor It, Then Fill It: Simulating Creator Ecosystems for Fair Video-Content Recommendation Systems at Billion User Scale

    Oct 28, 2026Sohini Roychowdhury, Long Sha, Sunand Agarwal +5Recommender SystemsFairness in Recommender Systems

    Meta Platforms, Inc., Menlo Park, CA 94025, USA

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

  12. 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-GkaragkounisCombinatorial Semi-BanditsMulti-Armed Bandits

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

  13. Balanced Sampling in Stochastic Multi-objective Bandits

    Oct 26, 2026Mengfan XuMulti-Armed BanditsAdaptive Sampling

    Mechanical and Industrial Engineering, University of Massachusetts Amherst

  14. Recommender regret for improving regularised RL estimation with bandits and MCTS

    Oct 23, 2026Danilo Vucetic, Alexandre Larouche, Mohammad Pedramfar +2Regularized RLReinforcement Learning

    Université de Montréal · Mila - Québec AI Institute · Université Laval +2

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

  16. Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs

    Oct 19, 2026Xiaojin ZhangMulti-Armed BanditsNon-Stationary Bandits

    School of Computer Science and Technology, Huazhong University of Science and Technology, China

  17. Learning from a Bandit Learner

    Oct 19, 2026Michela Petriconi, Nicolas Menet, Claire VernadeMulti-Armed BanditsLearning from Suboptimal Demonstrations

    University of Tübingen · University of Technology Nuremberg · ETH Zurich

  18. Budgeted Bayesian Bandits for Future Utilization

    Oct 16, 2026Sudipto GuhaMarkovian BanditsMulti-Armed Bandits

  19. Rethinking Successive Rejects Algorithms

    Oct 15, 2026Mohamed Khair, Junpei KomiyamaBest-Arm IdentificationMulti-Armed Bandits

    Mohamed bin Zayed University of Artificial Intelligence · RIKEN AIP

  20. The Tilted Sampling Problem: Optimism, Posterior Sampling, and Logarithmic Regret

    Oct 15, 2026Mohammad Pedramfar, Siamak RavanbakhshPosterior SamplingThompson Sampling

    Mila – Québec AI Institute, McGill University

  21. Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds

    Oct 15, 2026Adrien Prevost, Timothee Mathieu, Waris Radji +1Multi-Armed BanditsTransfer Learning

    Equipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France

  22. Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence

    Oct 14, 2026Yinan Li, Kwang-Sung Jun, Kapilan Balagopalan +4Gaussian Process BanditsAdaptive Sampling

    University of Arizona · POSTECH CSE/GSAI · Meta Inc.

  23. Replicable Dueling Bandits

    Oct 14, 2026Rohan Deb, Aadirupa Saha, Udaya Ghai +2Dueling BanditsMulti-Armed Bandits

    University of Illinois, Urbana Champaign · University of Illinois, Chicago · Amazon +1

  24. Bayesian Learning to Select Fair Classifiers

    Oct 14, 2026Saatvik Kher, Hyungrok Do, Judy Zhong +1Group FairnessMulti-Armed Bandits

    University of California, Irvine · New York University · Weill Cornell Medicine

  25. Lag: A Mean-Field Optimal Policy for Online Assignment with Reusable Resources

    Oct 13, 2026Keerthana GurushankarOnline Resource AllocationMulti-Armed Bandits

    Carnegie Mellon University, Pittsburgh, PA, USA

  26. When More Objectives Make Identification Easier: The Role of Preferences and Feedback

    Oct 13, 2026Bo Xue, Ji Cheng, Yuanyu Wan +1Multi-Armed BanditsBest-Arm Identification

    City University of Hong Kong · Zhejiang University

  27. Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits

    Oct 13, 2026Sacha Arroues-Paykin, Etienne Boursier, Vianney PerchetMulti-Armed BanditsMulti-Agent Bandits

    Ecole Polytechnique · INRIA, LMO, Université Paris-Saclay · CREST, ENSAE

  28. Reliable Scale-Free Bandits via Empirical Likelihood

    Oct 13, 2026Pratham Gupta, Alhad Sethi, Shubhada AgrawalMulti-Armed BanditsBandit Learning

    Indian Institute of Science

  29. Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback

    Oct 13, 2026Shuang WuGaussian Process BanditsMulti-Armed Bandits

    UCLA

  30. Few-for-Many Best-Arm Identification in Multi-Objective Bandits

    Oct 12, 2026Bo Xue, Yilu Liu, Haodong Jing +3Multi-Armed BanditsBest-Arm Identification

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