Robust Multi-Armed Bandits

Follow this topic Ask about this topic

Momentum

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

Jul 13Week of Sep 28

Latest papers 13

All topics

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 +3Dynamic Regret Minimization Distributionally Robust Optimization
Department of Electrical Engineering, Columbia University · Department of Computer Science & Engineering, University of California, Santa Cruz · Department of Civil Engineering, Columbia University
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 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
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
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 6, 2026, cs.LGJ/K move · Enter open · S save

On the Computational Tractability of Robust Bandits

Vanessa Kosoy, Vinayak Pathak

Faculty of Mathematics, Technion, Haifa, Israel · CORAL† Computational Rational Agents Laboratory, Delaware, USA.

Multi-Armed Bandits Robust Multi-Armed Bandits

Open paper AskPDF arXiv

Learning when the environment does not belong to the learner's hypothesis class is typically handled using agnostic learning guarantees. However, for anything beyond supervised learning, agnostic guarantees are difficult to come by. Recently, imprecise bandits (Kosoy, 2025) (later renamed to robust bandits in Appel and Kosoy, 2025) were introduced as another approach to unrealizable learning in the bandits setting and a

Θ(\sqrt{T})

regret learner was shown for a large class. However, no computational guarantees were provided. In this paper we identify a special case that admits a polynomial-time learner with

\tilde{O}(\sqrt{T})

regret. We also show that several small generalizations of this special case are NP-hard thus indicating that the special case is at the boundary of what is tractable. It has been recently suggested (Kosoy, 2018) that computationally efficient learners for unrealizable learning problems are crucial for solving the AI alignment problem. This work is a small step in that direction.

Momentum

Related topics

Latest papers 13