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

Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
May 25, 2026Joongkyu Lee, Min-hwan OhMulti-Armed Bandits Dynamic Regret Minimization
Seoul National 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
Optimizing Digital Therapeutic Interventions: Online Learning under Endogenous Adherence
May 22, 2026Eric Pulick, Stephanie Carpenter, Matthew Buman +1Dynamical Systems Multi-Armed Bandits
Department of Industrial and Systems Engineering, University of Wisconsin-Madison · College of Health Solutions, Arizona State University
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
May 22, 2026Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-GkaragkounisMulti-Armed Bandits Minimax Regret
Department of Finance University of Wisconsin–Madison · Department of Computer Sciences University of Wisconsin–Madison
When Determinants Are Not Enough: Private Rare Switching
May 22, 2026Xingyu ZhouMulti-Armed Bandits
Wayne State University, Detroit, USA.
Regret Analysis of Retry-Based Bandits
May 20, 2026Bingkui Tong, Junpei Komiyama, Soichiro Nishimori +1Multi-Armed Bandits Regret Minimization
Mohamed bin Zayed University of Artificial Intelligence · RIKEN AIP · The University of Tokyo
Spectral bandits for smooth graph functions with applications in recommender systems
May 19, 2026Tomáš Kocák, Michal Valko, Rémi Munos +2Graph Signal Processing Multi-Armed Bandits
SequeL team Inria Lille France · SequeL team, Inria France · Microsoft Research New England +2
Active Context Selection Improves Simple Regret in Contextual Bandits
May 19, 2026Mohammad Shahverdikondori, Jalal Etesami, Negar KiyavashMulti-Armed Bandits Best-Arm Identification
College of Management of Technology, EPFL · Department of Computer Science, TU Munich
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
Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity
May 18, 2026Hamed Khosravi, Xiaoming HuoMulti-Armed Bandits Non-Stationary Bandits
H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332
Learning in Position-Aware Multinomial Logit Bandits: From Multiplicative to General Position Effects
May 17, 2026Xi Chen, Shibo Dai, Jiameng Lyu +1Multi-Armed Bandits Discrete Choice Modeling
Leonard N. Stern School of Business, New York University, New York, NY 10012, USA · Qiuzhen College, Tsinghua University, Beijing 100084, China · Department of Management Science, School of Management, Fudan University, Shanghai, 200433, China +1
On the Power of Adaptivity for $\varepsilon$ -Best Arm Identification in Linear Bandits
May 15, 2026Arnab Maiti, Yunbei Xu, Kevin JamiesonMulti-Armed Bandits Best-Arm Identification
University of Washington · National University of Singapore
Efficient Multi-objective Prompt Optimization via Pure-exploration Bandits
May 14, 2026Donghao Li, Chengshuai Shi, Weijuan Ou +2Multi-Armed Bandits LLM Prompting
University of Virginia, Charlottesville, VA 22904, USA · Princeton University, Princeton, NJ 08544, USA · Southern University of Science and Technology, Shenzhen, Guangdong 518055, China
Delightful Exploration
May 13, 2026Ian OsbandMulti-Armed Bandits Value of Information
Google DeepMind
Collaborating in Multi-Armed Bandits with Strategic Agents
May 13, 2026Idan Barnea, Ofir Schlisselberg, Yishay MansourMulti-Armed Bandits Mechanism Design
Tel Aviv University · Google Research
Multi-Task Representation Learning for Conservative Linear Bandits
May 12, 2026Jiabin Lin, Shana MoothedathMulti-Armed Bandits Multi-Task Learning
Department of Computer Science and Technology, Qingdao University, China · Department of Electrical and Computer Engineering, Iowa State University, USA
Delightful Gradients Accelerate Corner Escape
May 12, 2026Jincheng Mei, Ian OsbandMulti-Armed Bandits Policy Gradient
Google DeepMind
$\varepsilon$ -Good Action Identification in Fixed-Budget Monte Carlo Tree Search
May 11, 2026Yinan Li, Tuan Nguyen, Kwang-Sung JunMulti-Armed Bandits Monte Carlo Tree Search
Department of Computer Science University of Arizona · CSE/GSAI POSTECH
Adaptive Policy Learning Under Unknown Network Interference
May 11, 2026Aidan Gleich, Eric Laber, Alexander VolfovskyThompson Sampling Multi-Armed Bandits
Department of Statistical Science Duke University
Valid Best-Model Identification for LLM Evaluation via Low-Rank Factorization
May 11, 2026Elad Tolochinsky, Yaniv Tenzer, Yaniv RomanoModel Selection Multi-Armed Bandits
Department of Computer Science, Technion – Israel Institute of Technology · Department of Electrical and Computer Engineering, Technion – Israel Institute of Technology
Nearly-Optimal Algorithm for Adversarial Kernelized Bandits
May 11, 2026Shogo IwazakiMulti-Armed Bandits Adversarial Bandits
LY Corporation Tokyo, Japan
Sample-Mean Anchored Thompson Sampling for Offline-to-Online Learning with Distribution Shift
May 11, 2026Bochao Li, Yao Fu, Wei Chen +1Distribution Shift Robustness Thompson Sampling
Southern University of Science and Technology · Microsoft Research
Learning to Sparsify Stochastic Linear Bandits
May 11, 2026Zhengmiao Wang, Ming Chi, Zhi-Wei Liu +2Multi-Armed Bandits Exploration-Exploitation Tradeoff
School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China · Department of Electronics and Telecommunications, Politecnico di Torino, 10129 Torino, Italy
The Value of Mechanistic Priors in Sequential Decision Making
May 11, 2026Itai Shufaro, Gal Benor, Shie MannorMulti-Armed Bandits Sequential Decision Making
Technion · Technion, NVIDIA Research
Selection of the Best Policy under Fairness Constraints for Subpopulations
May 11, 2026Tingyu Zhu, Yuhang Wu, Zeyu ZhengMulti-Armed Bandits Group Fairness
Department of Industrial Engineering and Operations Research & Berkeley Artificial Intelligence Research Lab University of California Berkeley
Optimal Regret for Single Index Bandits
May 10, 2026Devdan Dey, Sujoy Bhore, Avishek GhoshMulti-Armed Bandits Single-Index Models
Department of Computer Science and Engineering, Indian Institute of Technology Bombay.
Worst-Case Regret Bounds for Combinatorial Thompson Sampling in Sleeping Semi-Bandits
May 10, 2026Zhiming Huang, Bingshan Hu, Jianping PanThompson Sampling Multi-Armed Bandits
Paul G. Allen School of Computer Science & Engineering, University of Washington, WA, USA · Department of Computer Science, University of British Columbia, BC, Canada · Department of Computer Science, University of Victoria, BC, Canada
A Complete Characterization of Learnability for Adversarial Noisy Bandits
May 9, 2026Steve Hanneke, Kun WangMulti-Armed Bandits Statistical Learning Theory
Department of Computer Science, Purdue University
Beyond Static Bias: Adaptive Multi-Fidelity Bandits with Improving Proxies
May 8, 2026Muyun Lu, Haoyang Hong, Huazheng Wang +1Multi-Fidelity Optimization Multi-Armed Bandits
Department of Industrial and Systems Engineering, University of Houston · School of Electrical Engineering and Computer Science, Oregon State University
Multi-Armed Bandits With Best-Action Queries
May 8, 2026Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi +1Multi-Armed Bandits Adversarial Bandits
Politecnico di Milano

May 25, 2026J/K move · Enter open · S save

Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

Joongkyu Lee, Min-hwan Oh

Seoul National University

Multi-Armed Bandits Dynamic Regret Minimization Non-Stationary Bandits Online Mirror Descent Contextual Bandits Generalized Linear Models+1

Open paper AskPDF arXiv

We study nonstationary generalized linear bandits (GLBs), where the expected reward is modeled through a nonlinear link function with an unknown time-varying parameter. This framework encompasses a broad class of reward models, including linear, Bernoulli, and binomial rewards. Existing approaches are predominantly based on maximum-likelihood estimation (MLE), using sliding-window, restart, or discounting mechanisms to handle nonstationarity. Although these methods achieve statistically efficient regret guarantees, they generally require revisiting past observations at every round, which leads to computation and memory costs that grow with time; moreover, several of them rely on a non-convex projection step. In this paper, we propose DOMD-GLB, a new algorithm for nonstationary GLBs that utilizes discounted online mirror descent (DOMD) for parameter estimation, thereby incurring only

O(1)

computation and memory costs per round. We prove dynamic regret bounds of order

\tilde{O} \big(c_μ^{-1/2} d^{3/4} P_T^{1/4} T^{3/4}\big)

in drifting environments and

\tilde{O}\big(c_μ^{-1/3} d^{2/3} Γ_T^{1/3} T^{2/3}\big)

in piecewise-stationary environments, where

d

denotes the feature dimension,

T

the time horizon,

P_T

the path length,

Γ_T

the number of change points, and

c_μ

a curvature parameter associated with the link function, while substantially improving computational efficiency over prior work. To the best of our knowledge, this is the first algorithm for nonstationary GLBs with per-round computation and memory costs independent of time.