Multi-Armed Bandits

Follow this topic Ask about this topic

Latest papers 332

48 papers in the last four weeks, up 109% on the four weeks before. 0.3% of all new papers.

All topics

Replicable Constrained Bandits
Feb 16, 2026Matteo Bollini, Gianmarco Genalti, Francesco Emanuele Stradi +2Multi-Armed Bandits ML Reproducibility
Politecnico di Milano
One Good Source is All You Need: Near-Optimal Regret for Bandits under Heterogeneous Noise
Feb 16, 2026Amith Bhat, Haipeng Luo, Aadirupa SahaMulti-Armed Bandits UCB Algorithms
UIC · USC
Frequentist Regret Analysis of Gaussian Process Thompson Sampling via Fractional Posteriors
Feb 16, 2026Somjit Roy, Prateek Jaiswal, Anirban Bhattacharya +2Thompson Sampling Bayesian Optimization
Department of Statistics, Texas A&M University, College Station, TX 77843, USA · Daniels School of Business, Purdue University, West Lafayette, IN 47907, USA · Department of Statistics, University of Wisconsin-Madison, Madison, WI 53706, USA
A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions
Feb 11, 2026Sanghwa Kim, Junghyun Lee, Se-Young YunMulti-Armed Bandits Online Mirror Descent
Kim Jaechul Graduate School of AI, KAIST
Rising Multi-Armed Bandits with Known Horizons
Feb 11, 2026Seockbean Song, Chenyu Gan, Youngsik Yoon +3Multi-Armed Bandits UCB Algorithms
Graduate School of AI, POSTECH, Pohang, Republic of Korea · Qiuzhen College, Tsinghua University, Beijing, China · Department of CSE, POSTECH, Pohang, Republic of Korea +1
Improved Algorithms for Nash Welfare in Linear Bandits
Jan 30, 2026Dhruv Sarkar, Nishant Pandey, Sayak Ray ChowdhuryMulti-Armed Bandits Algorithmic Fairness
Indian Institute of Technology Kharagpur · Indian Institute of Technology Kanpur
Nonparametric Kernel Clustering with Bandit Feedback
Jan 12, 2026Victor Thuot, Sebastian Vogt, Debarghya Ghoshdastidar +1Clustering Multi-Armed Bandits
MISTEA, UMPA-ENSL · INRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France · LRR-TUM +2
Prior Diffusiveness and Regret in the Linear-Gaussian Bandit
Jan 5, 2026Yifan Zhu, John C. Duchi, Benjamin Van RoyThompson Sampling Multi-Armed Bandits
Department of Electrical Engineering, Stanford University, California, United States.
No-Regret Gaussian Process Optimization of Time-Varying Functions
Nov 29, 2025Eliabelle Mauduit, Eloïse Berthier, Andrea SimonettoMulti-Armed Bandits Bayesian Optimization
Unit´e de Math´ematiques Appliqu´ees ENSTA, Institut Polytechnique de Paris Palaiseau, France · U2IS ENSTA, Institut Polytechnique de Paris Palaiseau, France
Self-Concordant Perturbations for Linear Bandits
Oct 28, 2025Lucas Lévy, Jean-Lou Valeau, Arya Akhavan +1Multi-Armed Bandits Exploration-Exploitation Tradeoff
Ecole Polytechnique and University of Oxford · ENSAE Paris and University of Oxford · University of Oxford and Ecole Polytechnique +1
Managing Self-Learning Experts under Per-Round Budget Constraints
Oct 26, 2025Ilgam Latypov, Alexandra Suvorikova, Alexey Kroshnin +2Multi-Armed Bandits Algorithm Selection
AI Center, Lomonosov Moscow State University MSU Institute for Artificial Intelligence Moscow, Russia · Weierstrass Institute for Applied Analysis and Stochastics Berlin, Germany · IITP RAS Moscow, Russia +1
Learning Peer Influence Probabilities with Linear Contextual Bandits
Oct 21, 2025Ahmed Sayeed Faruk, Mohammad Shahverdikondori, Elena ZhelevaMulti-Armed Bandits Contextual Bandits
University of Illinois Chicago, Chicago, USA · École Polytechnique Fédérale de Lausanne, Switzerland
Best-of-Both Worlds for linear contextual bandits with paid observations
Oct 8, 2025Nathan Boyer, Dorian Baudry, Patrick RebeschiniMulti-Armed Bandits Follow-the-Regularized-Leader
ENS Paris-Saclay, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France · Department of Statistics, University of Oxford
Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective
Oct 6, 2025Weixin Wang, Haoyang Zheng, Guang Lin +2Thompson Sampling Multi-Armed Bandits
Duke University · Purdue University · Morgan Stanley
Batched Bandits with Heavy-Tailed Rewards
Oct 4, 2025Yunwen Guo, Yunlun Shu, Gongyi Zhuo +1Multi-Armed Bandits Heavy-Tailed Noise
School of Mathematical Sciences, Fudan University, 220 Handan Rd., 200433, Shanghai, China · Shanghai Center for Mathematical Sciences, Fudan University, 220 Handan Rd., 200433, Shanghai, China
Non-Linear Model-Based Sequential Decision-Making in Agriculture
Sep 2, 2025Sakshi Arya, Wentao LinMulti-Armed Bandits Sequential Decision Making
Department of Mathematics, Applied Mathematics and Statistics, Case Western Reserve University, Cleveland, OH 44106, USA · CTrees, Pasadena, CA 91105, USA
DynamixSFT: Dynamic Mixture Optimization of Instruction Tuning Collections
Aug 16, 2025Haebin Shin, Lei Ji, Xiao Liu +4Multi-Armed Bandits Instruction Tuning
University of Michigan · Microsoft Research · KAIST AI +1
Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation: The Case of Multi-Armed Bandits
May 6, 2025Max Qiushi Lin, Jincheng Mei, Matin Aghaei +6Multi-Armed Bandits Policy Gradient
Simon Fraser University · Google DeepMind · Google Research +1
Towards More Efficient, Robust, Instance-adaptive, and Generalizable Sequential Decision making
Apr 12, 2025Zhiyong WangMulti-Armed Bandits Reinforcement Learning
Department of Computer Science and Engineering, The Chinese University of Hong Kong
On the Sublinear Regret of Continuous K-Max Bandits
Feb 19, 2025Yu Chen, Siwei Wang, Longbo Huang +1Multi-Armed Bandits UCB Algorithms
Institute for Interdisciplinary Information Sciences, Tsinghua University · 2Microsoft Research Asia
Linear Bandits beyond Inner Product Spaces, the case of Bandit Optimal Transport
Feb 11, 2025Lorenzo CroissantMulti-Armed Bandits UCB Algorithms
CREST,FAIRPLAY,ENSAE Paris
The Minimal Search Space for Conditional Causal Bandits
Feb 10, 2025Francisco N. F. Q. Simoes, Itai Feigenbaum, Mehdi Dastani +1Multi-Armed Bandits Causal Intervention
Department of Computer Science, Delft University of Technology, The Netherlands · Lehman College and The Graduate Center, City University of New York, New York · Department of Information and Computing Sciences, Utrecht University, The Netherlands
Bandits with Anytime Knapsacks
Jan 30, 2025Eray Can Elumar, Cem Tekin, Osman YaganMulti-Armed Bandits
Dept. of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh, PA · Dept. of Electrical Engineering Bilkent University Ankara, Turkey
Impatient Bandits: Optimizing for the Long-Term Without Delay
Jan 14, 2025Kelly W. Zhang, Thomas Baldwin-McDonald, Kamil Ciosek +2Multi-Armed Bandits Sequential Recommendation
Imperial College London · University of Manchester · Spotify +2
Allocation Stability and Wald Inference under Variance-Aware UCB
Dec 12, 2024Yingying Fan, Yuxuan Han, Jinchi Lv +2Multi-Armed Bandits UCB Algorithms
Data Sciences and Operations Department University of Southern California Los Angeles, CA 90089, USA · Stern School of Business, New York University, New York, NY 10003, USA
Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting
Sep 9, 2024Gianmarco Genalti, Marco Mussi, Nicola Gatti +3Multi-Armed Bandits Graph Bandits
Politecnico di Milano2026 Piazza Leonardo da Vinci 32, Milan, 20133, Italy
Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distribution
Jun 10, 2024Qing Feng, Tianyi Ma, Ruihao ZhuMulti-Armed Bandits Regret Minimization
School of Operations Research and Information Engineering, Cornell University · SC Johnson College of Business, Cornell University
Replicability is Asymptotically Free in Multi-armed Bandits
Feb 12, 2024Junpei Komiyama, Shinji Ito, Yuichi Yoshida +1Multi-Armed Bandits ML Reproducibility
New York University · Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) · RIKEN AIP +2
Semi-Bandit Learning for Monotone Stochastic Optimization
Dec 24, 2023Arpit Agarwal, Rohan Ghuge, Viswanath Nagarajan +1Stochastic Optimization Multi-Armed Bandits
Department of Computer Science & Engineering, Indian Institute of Technology Bombay, Mumbai, India. · Department of Information, Risk, and Operations Management, University of Texas at Austin, Austin, USA. · Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.
Generalized Regret Analysis of Thompson Sampling using Fractional Posteriors
Sep 12, 2023Prateek Jaiswal, Debdeep Pati, Anirban Bhattacharya +1Thompson Sampling Multi-Armed Bandits
Department of Quantitative Methods, Daniels School of Business, Purdue University, West Lafayette, IN 47906, USA. · Department of Statistics, University of Wisconsin-Madison, Madison, WI 53706, USA. · Department of Statistics, Texas A&M University, College Station, TX 77843, USA.

Feb 16, 2026J/K move · Enter open · S save

Replicable Constrained Bandits

Matteo Bollini, Gianmarco Genalti, Francesco Emanuele Stradi, Matteo Castiglioni+1

Politecnico di Milano

Multi-Armed Bandits ML Reproducibility UCB Algorithms

Open paper AskPDF arXiv

Algorithmic replicability has recently been introduced to address the need for reproducible experiments in machine learning. A replicable online learning algorithm is one that takes the same sequence of decisions across different executions in the same environment, with high probability. We initiate the study of algorithmic replicability in constrained MAB problems, where a learner interacts with an unknown stochastic environment for

T

rounds, seeking not only to maximize reward but also to satisfy multiple constraints. Our main result is that replicability can be achieved in constrained MABs. Specifically, we design replicable algorithms whose regret and constraint violation match those of non-replicable ones in terms of

T

. As a key step toward these guarantees, we develop the first replicable UCB-like algorithm for unconstrained MABs, showing that algorithms that employ the optimism in-the-face-of-uncertainty principle can be replicable, a result that we believe is of independent interest.