Multi-Armed Bandits

Latest papers 332

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

Nonlinear Bandit
Jul 8, 2026Tianshuo Zheng, Ting Wu, Zhi-Hua Zhou +1Multi-Armed Bandits Heavy-Tailed Noise
School of Mathematics, Nanjing University, Nanjing, 210093, China · School of Artificial Intelligence, Nanjing University, National Key Laboratory for Novel Software Technology, Nanjing, 210023, China · School of Mathematics and Physics, Xi’an Jiaotong-Liverpool University, Suzhou, 215123, China
Best-Arm Identification with Generative Proxy
Jul 8, 2026Tianyi Ma, Hanzhang Qin, Ruihao Zhu +1Multi-Armed Bandits Best-Arm Identification
School of Operations Research and Information Engineering, Cornell University · Department of Industrial Systems Engineering and Management, National University of Singapore · SC Johnson College of Business, Cornell University +1
Probably Correct Optimal Stable Matching under Two-Sided Uncertainty
Jul 6, 2026Andreas Athanasopoulos, Anne-Marie George, Christos DimitrakakisMulti-Armed Bandits Preference Learning
University of Neuchâtel, Neuchâtel, Switzerland · University of Oslo, Oslo, Norway
Fixed-Confidence Best-Arm Identification for Causal Mediation Analysis
Jul 5, 2026Harsh Shrivastava, Yuta Kawakami, Junpei Komiyama +1Multi-Armed Bandits Causal Effect Estimation
Mohamed bin Zayed University of Artificial Intelligence (MBZUAI), Abu Dhabi, UAE · RIKEN AIP, Tokyo, Japan
Contextual Slate GLM Bandits with Limited Adaptivity
Jun 30, 2026Tanmay Goyal, Sukruta Prakash Midigeshi, Gaurav SinhaMulti-Armed Bandits Contextual Bandits
Microsoft Research India
A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming
Jun 28, 2026Yaohui Guo, X. Jessie Yang, Cong ShiMulti-Armed Bandits Human-Robot Collaboration
Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI 48105
Bayesian Best-Arm Identification with Abstention: A Polynomial-to-Exponential Phase Transition
Jun 28, 2026Yuqi Huang, Yunlong Hou, Vincent Y. F. TanMulti-Armed Bandits Best-Arm Identification
Department of Mathematics, National University of Singapore · Department of Electrical and Computer Engineering, National University of Singapore
Randomized Exploration for Linear Bandits via Absolute Perturbations
Jun 26, 2026Toshinori Kitamura, Shuai Liu, Csaba SzepesváriThompson Sampling Multi-Armed Bandits
Department of Computing Science, University of Alberta, Canada
Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces
Jun 26, 2026Joyanta Jyoti Mondal, Ibne Farabi Shihab, Anuj SharmaMulti-Armed Bandits Graph Bandits
Department of Computer and Information Sciences, University of Delaware, USA · Department of Computer Science, Iowa State University, USA · Department of Civil, Construction & Environmental Engineering, Iowa State University, USA
Learning in Markovian bandits with non-observable states and constrained decision epochs
Jun 25, 2026Thomas Hira, Victor Boone, Urtzi Ayesta +1Multi-Armed Bandits Markov Models
IRIT, Université de Toulouse, CNRS, Toulouse INP, Toulouse, France · Ikerbasque-UPV/EHU, University of the Basque Country, Bilbao, Spain
Target-Aware Bandit Allocation for Scalable Surrogate Optimization in Chemical Space
Jun 25, 2026Mohammad Haddadnia, Yuvan Chali, Abhilash Jayaraj +4Multi-Armed Bandits Molecular Optimization
Dana-Farber Cancer Institute, Boston, MA, USA · Department of Biological Chemistry and Molecular Pharmacology, Harvard Medical School, Boston, MA, USA · Department of Biostatistics, Harvard T.H. Chan School of Public Health, Boston, MA, USA +4
Leveraging Similarities in Multi-Armed Bandits
Jun 22, 2026Khaled Eldowa, Thibaud Rahier, Augustin Cablant +2Multi-Armed Bandits Adversarial Bandits
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France · Criteo AI Lab, Paris, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
Minimax Quantile Lower Bounds for Interactive Statistical Decision Making with Privacy
Jun 22, 2026Raghav Bongole, Amirreza Zamani, Tobias J. Oechtering +1Multi-Armed Bandits Decision-Making under Uncertainty
Department of Information Science and Engineering (ISE) KTH Royal Institute of Technology
Selective Ensemble Based on Preference-Directed Multi-Objective Bandits
Jun 20, 2026Lanjihong Ma, Zhen-Yu Zhang, Masashi Sugiyama +1Multi-Armed Bandits Ensemble 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
Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approach
Jun 18, 2026Haonan Xu, Yingying LiMulti-Armed Bandits Contextual Bandits
The Grainger College of Engineering University of Illinois Urbana-Champaign Champaign, IL, 61801
Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning
Jun 18, 2026Ananya Kunisetty, Avishek GhoshMulti-Armed Bandits Decision-Making under Uncertainty
Indian Institute of Technology Bombay, Mumbai 400076, India
Manifold Bandits: Bayesian Curriculum Learning over the Latent Geometry of Large Language Models
Jun 18, 2026Darrien McKenzie, Nicklas Hansen, Xiaolong WangMulti-Armed Bandits RL for Language Model Reasoning
University of California, San Diego
Bayesian Anytime Pareto Set Identification for Multi-Objective Multi-Armed Bandits
Jun 17, 2026Lennert Saerens, Bram Silue, Eleni Litsa +2Thompson Sampling Multi-Armed Bandits
Artificial Intelligence Lab, Departement of Computer Science, Vrije Universiteit Brussel, Brussels, Belgium · imec, Leuven, Belgium
Sequential Hiring of Contingent Workers Through Learning-Based Optimization
Jun 16, 2026Chris Lee, Xiuli Chao, Izak DuenyasMulti-Armed Bandits Bandits with Delayed Feedback
Department of Industrial and Operations Engineering, University of Michigan · Ross School of Business, University of Michigan
Online LLM Selection via Constrained Bandits with Time-Varying Demand
Jun 16, 2026Yin Huang, Qingsong Liu, Jie XuMulti-Armed Bandits Cost-Aware Inference
Department of Electrical and Computer Engineering, University of Florida · Manning College of Information and Computer Sciences, University of Massachusetts Amherst
A Complexity Measure for Active Learning in Multi-group Mean Estimation
Jun 12, 2026Abdellah Aznag, Rachel Cummings, Adam N. ElmachtoubMulti-Armed Bandits Active Learning
Department of Industrial Engineering and Operations Research & Data Science Institute, Columbia University
Graph Structured Combinatorial Semi-Bandit with Nonlinear Reward Associations through Separable Signals
Jun 12, 2026Christoph Bauschmann, Setareh MaghsudiReward Modeling Multi-Armed Bandits
Department of Electrical Engineering and Information Technology Ruhr University Bochum Bochum, Germany
Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
Jun 12, 2026Tianhao Wu, Matthew Zurek, Weina Wang +1Multi-Armed Bandits Robust Markov Decision Processes
Department of Industrial and Systems Engineering, University of Wisconsin-Madison · Department of Computer Sciences, University of Wisconsin-Madison · Computer Science Department, Carnegie Mellon University
Efficient Multinomial Logistic Bandit via Frequent Directions
Jun 10, 2026Linzhe He, Yu-Jie Zhang, Sifan Yang +1Multi-Armed Bandits Contextual Bandits
State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China · Paul G. Allen School of Computer Science & Engineering, University of Washington, USA
Annealed Entropic Allocation for Ranking and Selection
Jun 9, 2026Xin Fei, Juergen BrankeMulti-Armed Bandits Adaptive Sampling
Business School · The University of Edinburgh, Edinburgh, UK · Warwick Business School +1
Bellman-sufficient Information Complexity
Jun 9, 2026Yunbei XuMulti-Armed Bandits Minimax Regret
National University of Singapore
Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts
Jun 8, 2026Udvas Das, Waris Radji, Debabrota Basu +1Multi-Armed Bandits Non-Stationary Bandits
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRIStAL F-59000 Lille, France
Asymptotic Optimality of Thompson Sampling for Risk-Averse Bandits with Sub-Gaussian Rewards
Jun 8, 2026Joel Q. L. ChangThompson Sampling Multi-Armed Bandits
Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees
Jun 8, 2026Deqi Zheng, Xiaoyang Xu, Yuhong YangMulti-Armed Bandits Dynamic Regret Minimization
Qiuzhen College, Tsinghua University · Yau Mathematical Sciences Center, Tsinghua University
Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
Jun 8, 2026Vladimir Braverman, Chen Wang, Liudeng Wang +1Multi-Armed Bandits Best-Arm Identification
Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University

Jul 8, 2026J/K move · Enter open · S save

Nonlinear Bandit

Tianshuo Zheng, Ting Wu, Zhi-Hua Zhou, Keqin Liu

School of Mathematics, Nanjing University, Nanjing, 210093, China · School of Artificial Intelligence, Nanjing University, National Key Laboratory for Novel Software Technology, Nanjing, 210023, China · School of Mathematics and Physics, Xi’an Jiaotong-Liverpool University, Suzhou, 215123, China

Multi-Armed Bandits Heavy-Tailed Noise Online Mirror Descent Contextual Bandits Generalized Linear Bandits

Open paper AskPDF arXiv

In this paper we first study the problem of generalized linear bandit (GLB) under heavy-tailed noise. The characteristics of heavy-tailed distributions are widely observed in real-world applications such as personalized recommendation, financial markets, and medical treatments. Based on the online mirror descent (OMD) method, we propose an algorithm EHM that extends the adaptive Huber loss method (Wang et al., 2025) with one-pass update (

\mathcal{O}(1)

computational complexity with respect to current round

t

and the time horizon

T

), which simultaneously achieves an almost optimal regret of

\widetilde{\mathcal{O}}(T^{\frac{1}{1+ε}})

where

T

is the time horizon. In addition, by utilizing a special property of some link function (Sawarni et al., 2025), our algorithm eliminates the need to know a commonly used parameter. Next, we study the GLB problem under the case when contextual characteristic becomes piecewise constant, and we slightly revised former algorithm to obtain the PGLB-EHM algorithm. After theoretical analysis, we prove that the regret upper bound order stays the same. Furthermore, we look deeper into a special case of nonlinear bandit (NB) and present the NB-EHM algorithm with bisection method and special restriction. Eventually we utilize the affine lifting approach and show that the general NB problem can be applied with NB-EHM to achieve a sublinear regret bound.