Multi-Armed Bandits

Latest papers 330

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

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.
Learning to Schedule in Parallel-Server Queues with Stochastic Bilinear Rewards
Dec 13, 2021Jung-hun Kim, Milan VojnovicMulti-Armed Bandits Online Resource Allocation
CREST, ENSAE Paris, France · London School of Economics, United Kingdom
Bayesian Nonparametric Thompson Sampling for Multi-Armed Bandits
Aug 8, 2018Iñigo Urteaga, Chris H. WigginsMulti-Armed Bandits Thompson Sampling
Department of Applied Physics and Applied Mathematics Data Science Institute Columbia University New York City, NY 10027

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

Frequentist Regret Analysis of Gaussian Process Thompson Sampling via Fractional Posteriors

Somjit Roy, Prateek Jaiswal, Anirban Bhattacharya, Debdeep Pati+1

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

Thompson Sampling Bayesian Optimization Gaussian Processes Posterior Sampling Multi-Armed Bandits

Open paper AskPDF arXiv

We study Gaussian Process Thompson Sampling (GP-TS) for sequential decision-making over compact, continuous action spaces and provide a frequentist regret analysis based on fractional Gaussian process posteriors, without relying on domain discretization as in prior work. We show that the variance inflation commonly assumed in existing analyses of GP-TS can be interpreted as Thompson Sampling with respect to a fractional posterior with tempering parameter

α\in (0,1)

. We derive a kernel-agnostic regret bound expressed in terms of the information gain parameter

γ_t

and the posterior contraction rate

ε_t

, and identify conditions on the Gaussian process prior under which

ε_t

can be controlled. As special cases of our general bound, we recover regret of order

\tilde{\mathcal{O}}(T^{\frac{1}{2}})

for the squared exponential kernel,

\tilde{\mathcal{O}}(T^{\frac{2ν+3d}{2(2ν+d)}} )

for the Matérn-

ν

kernel, and a bound of order

\tilde{\mathcal{O}}(T^{\frac{2ν+3d}{2(2ν+d)}})

for the rational quadratic kernel. Overall, our analysis provides a unified and discretization-free regret framework for GP-TS that applies broadly across kernel classes.