Robust Multi-Armed Bandits

Follow this topic Ask about this topic

Robust multi-armed bandits study how to choose among uncertain actions when reward data may be heavy-tailed, corrupted, nonstationary, or otherwise unreliable. Common approaches include robust estimators and confidence bounds, corruption-aware online learning, and change detection, with variants for contextual, constrained, and decentralized settings. Their guarantees are often measured by regret against the best arm or a changing oracle, under assumptions such as bounded corruption or finite reward moments. A central tension is that stronger protection can cost efficiency, while algorithms that adapt to unknown corruption or distribution shifts may face computational or statistical limits.

Latest papers

20 papers4 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds
Oct 15, 2026Adrien Prevost, Timothee Mathieu, Waris Radji +1Multi-Armed Bandits Transfer Learning
Equipe Scool, Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France
Gaussian Process Bandits for AI System Optimization with Selectively Verified Feedback
Oct 13, 2026Shuang WuGaussian Process Bandits Multi-Armed Bandits
UCLA
On the Computational Tractability of Robust Bandits
Oct 6, 2026Vanessa Kosoy, Vinayak PathakMulti-Armed Bandits Robust Multi-Armed Bandits
Faculty of Mathematics, Technion, Haifa, Israel · CORAL† Computational Rational Agents Laboratory, Delaware, USA.
Dynamic Minimax Regret Optimization for Robust LLM Post-Training
Oct 5, 2026Chengbo Zang, Haoyu Dong, Mehmet Kerem Turkcan +3Group Distributionally Robust Optimization Dynamic Regret Minimization
Department of Electrical Engineering, Columbia University · Department of Computer Science & Engineering, University of California, Santa Cruz · Department of Civil Engineering, Columbia University
Prior-Free Competitive Ratios for Improving Bandits: Scale, Curvature and Horizon Are Free, but Not Jointly Under Noise
Sep 12, 2026Xuan LiMulti-Armed Bandits Competitive Analysis
University of New South Wales, Sydney, Australia
Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry
Aug 11, 2026Daphne Feng, Ricardo Parada, Lily Jiang +2Multi-Armed Bandits Robust Multi-Armed Bandits
Department of Mathematics, University of California, Los Angeles, Los Angeles, CA, USA · Department of Mathematics, University of California, Riverside, Riverside, CA, USA
Algorithmic Approaches to Sequential Decision-Making and Social Epistemology
Jul 22, 2026Kavya RavichandranMulti-Armed Bandits Sequential Decision Making
Toyota Technological Institute at Chicago, Chicago, IL · at the Toyota Technological Institute at Chicago Chicago, IL
Annealed Softmax Greedy in Many-Armed Bayesian Bandits
May 29, 2026William Overman, Mohsen BayatiMulti-Armed Bandits Exploration-Exploitation Tradeoff
Stanford University
A Context Augmented Multi-Play Multi-Armed Bandit Algorithm for Fast Channel Allocation in Opportunistic Spectrum Access
May 25, 2026Ruiyu Li, Guangxia Li, Xiao Lu +2Multi-Armed Bandits Robust Multi-Armed Bandits
School of Computer Science and Technology, Xidian University, China · 2Research and Development, Ericsson, Canada · 3Hainayun IoT Technology Ltd, China
Not all uncertainty is alike: volatility, stochasticity, and exploration
May 19, 2026Payam PirayMulti-Armed Bandits Exploration-Exploitation Tradeoff
Department of Psychology, University of Southern California
Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy
May 8, 2026Ishank Juneja, Carlee Joe-Wong, Osman YağanMulti-Armed Bandits Robust Multi-Armed Bandits
Department of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh, PA 15213
On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
May 4, 2026Kaixuan Ji, Qiwei Di, Heyang Zhao +2Multi-Armed Bandits Sample Complexity
Department of Computer Science, University of California, Los Angeles, CA 90095, USA
Unlearning Offline Stochastic Multi-Armed Bandits
May 1, 2026Zichun Ye, Runqi Wang, Xuchuang Wang +3Multi-Armed Bandits Robust Multi-Armed Bandits
Shanghai Jiao Tong University, Shanghai, China · University of Massachusetts Amherst, Massachusetts, United States · University of Washington, Tacoma, United States
A Modularized Framework for Piecewise-Stationary Restless Bandits
Apr 11, 2026Kuan-Ta Li, Chia-Chun Lin, Ping-Chun Hsieh +1Non-Stationary Bandits Robust Multi-Armed Bandits
Institute of Communications Engineering, National Yang Ming Chaio Tung University, Hsinchu, Taiwan · Department of Computer Science, National Yang Ming Chaio Tung University, Hsinchu, Taiwan
Towards Noise-Resilient Quantum Multi-Armed and Stochastic Linear Bandits
Mar 19, 2026Zhuoyue Chen, Kechao CaiRobust Multi-Armed Bandits
School of Electronics and Communication Engineering, Sun Yat-sen University, Shenzhen, China
Sustainable Multi-Agent Crowdsourcing via Physics-Informed Bandits
Feb 25, 2026Chayan BanerjeeMulti-Armed Bandits Robust Multi-Armed Bandits
School of Electrical Engineering and Robotics, Queensland University of Technology (QUT), Brisbane, QLD, Australia.
Truly Adapting to Adversarial Constraints in Constrained MABs
Feb 16, 2026Francesco Emanuele Stradi, Kalana Kalupahana, Matteo Castiglioni +2Constrained Optimization Adversarial Bandits
Politecnico di Milano
A Jointly Efficient and Near-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 Seoul 02455, Republic of Korea
Batched Bandits with Heavy-Tailed Rewards
Oct 4, 2025Yunwen Guo, Yunlun Shu, Gongyi Zhuo +1Lipschitz Bandits Multi-Armed Bandits
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
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

Oct 15, 2026J/K move · Enter open · S save

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

Adrien Prevost, Timothee Mathieu, Waris Radji, Odalric-Ambrym Maillard

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

Multi-Armed Bandits Transfer Learning UCB Algorithms Robust Multi-Armed Bandits

Open paper AskPDF arXiv

Transfer learning in stochastic multi-armed bandits is typically studied assuming that prior data forms a fixed offline dataset or is generated by a known source. In practice, historical observations come from a previous adaptive decision process whose policy is unknown. We study this setting for bounded rewards in

[0,1]

. Before the online game starts, the learner receives, for each arm

k

N'_k

observations drawn i.i.d.\ from an unknown distribution

ν'_k

, collected by an arbitrary and possibly data-dependent strategy, so the sample sizes

N'_k

may be random. Source and target means satisfy

|μ_k-μ'_k|<L_k

for known constants

(L_k)_k

. We derive an asymptotic problem-dependent lower bound and propose KL-UCB-Transfer, which combines online and historical data and achieves logarithmic regret with an improved leading constant whenever

μ'_a<μ_1-L_a

, and recovers the classical KL-UCB guarantee otherwise. Since bounding the source-target discrepancy is often unrealistic, we relax the assumption to the one-sided condition

μ_k-μ'_k<L_k

and show that logarithmic regret can survive under misspecification, characterizing three regimes ranging from improvement to a degraded logarithmic bound to a loss of guarantee. Simulations illustrate the practical benefits of exploiting process-generated historical data.