Non-Stationary Bandits

Follow this topic Ask about this topic

Non-stationary bandits model repeated choices when an option’s reward, demand, or constraints can drift, shift abruptly, or cycle. Common approaches include sliding-window and discounted UCB or Thompson sampling, change-point detection and restarts, and dynamic-regret methods for linear, contextual, and generalized-linear rewards. These methods are studied in settings such as pricing, online experimentation, resource allocation, and model routing, often using regret against a changing best choice as the measure of performance. A central tension is how to adapt quickly without discarding useful history or sacrificing the strong guarantees available when rewards are stable, especially when the pattern of change is unknown.

Latest papers

39 papers7 papers in the last four weeks, up 17% on the four weeks before. 0.0% of all new papers.

The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits
Oct 21, 2026Sharan Sahu, Martin T. WellsNon-Stationary Bandits Dynamic Regret Minimization
Department of Statistics and Data Science, Cornell University
Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs
Oct 19, 2026Xiaojin ZhangMulti-Armed Bandits Non-Stationary Bandits
School of Computer Science and Technology, Huazhong University of Science and Technology, China
Detection Augmented Learning In Non-Stationary Bandit Environments
Oct 19, 2026Argyrios Gerogiannis, Yu-Han Huang, Subhonmesh Bose +1Non-Stationary Bandits Dynamic Regret Minimization
ECE department and the Coordinated Science Laboratory, Grainger College of Engineering, University of Illinois at Urbana-Champaign
Best Arm Identification for Bandits with Shifting Means
Oct 7, 2026Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal +2Multi-Armed Bandits Best-Arm Identification
CWI and Booking.com Science Park 123 1098 XG Amsterdam · CWI and University of Twente Science Park 123 1098 XG Amsterdam · Indian Institute of Science (IISc), Bengaluru CV Raman Rd, Bengaluru, Karnataka 560012, India +2
Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory
Oct 5, 2026Jingyuan Liu, Huiwen JiaMulti-Armed Bandits Non-Stationary Bandits
Department of Industrial Engineering and Operations Research, University of California, Berkeley
When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity
Oct 2, 2026Mayand Gulati, Kerong Wang, WeiChen AuThompson Sampling Non-Stationary Bandits
UC Santa Barbara · Purdue University
Block Optimism for Nonstationary Bandits with Latent Linear Dynamics
Oct 1, 2026Taehyun Hwang, Hyunjun Choi, Heesang Ann +1Multi-Armed Bandits Stochastic Linear Dynamical Systems
Seoul National University Soeul, South Korea
Future Information-Directed Sampling for Bayesian Nonstationary Bandits
Sep 27, 2026Yichen Song, Alessio Russo, Aldo PacchianoMulti-Armed Bandits Non-Stationary Bandits
Boston University · Broad Institute of MIT and Harvard
Odds-Ratio Thompson Sampling: A Specification and Design Guide for Contrast-Based Multi-Armed Bandits
Sep 17, 2026Sulgi KimThompson Sampling Multi-Armed Bandits
Independent researcher
Adapting to Decision-Relevant Non-Stationarity in Decentralized Heterogeneous Bandits
Sep 15, 2026Zhaojun PengMulti-Armed Bandits Dynamic Regret Minimization
Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
Sep 11, 2026Mengxiao ZhangMulti-Armed Bandits Adversarial Bandits
University of Iowa
Pooling and Drift in Delayed Bandits
Sep 1, 2026Melika BaghiMulti-Armed Bandits Non-Stationary Bandits
Georgia Institute of Technology
Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets
Sep 1, 2026Cheung Hao Lee, Patrick WongCost-Aware Inference Non-Stationary Bandits
Gated Decoupled Compositional Bandits: A Unified Theory of Contextual Bandits with Supervised-Calibrated Action Scaling and Pre-Execution Gating
Aug 22, 2026Oleg MiroshnichenkoMulti-Armed Bandits Contextual Bandits
Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration
Aug 19, 2026Matthias Mandl, Hanne KekkonenGaussian Process Bandits Bayesian Optimization
Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft
Generalized Linear Bandits with Memory
Aug 16, 2026Heesang Ann, Hyunjun Choi, Taehyun Hwang +3Generalized Linear Bandits Non-Stationary Bandits
Seoul National University, Seoul, Republic of Korea · Shinsegae, Seoul, Republic of Korea
Progressive Content Refinement with Decaying Reward Joint LinUCB
Aug 7, 2026Shion Ishikawa, Pablo Loyola, Young-joo Chung +1LLM Self-Refinement Large Language Model-Guided Optimization
Rakuten Group, Inc. Tokyo, Japan · Rakuten Group, Inc. San Mateo, USA
402Pilot: An x402 Decision Layer for Autonomous Agent Micropayments
Aug 2, 2026Yin Li, Yanbo He, Boo-Ho Yang +5Multi-Armed Bandits Non-Stationary Bandits
The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China · MOVENSYS Inc., Seongnam-si, Republic of Korea · Schneider Electric, Shanghai, China +2
On Non-Stationary Dynamic Pricing: Adaptivity and Optimality
Jul 27, 2026Feiyu Jiang, Zifeng ZhaoNon-Stationary Bandits Dynamic Pricing
School of Management, Fudan University · Mendoza College of Business, University of Notre Dame
Experimentation and Commitment under Reward Shifts
Jul 26, 2026Puping Jiang, Wei Tang, Renyu +1Multi-Armed Bandits Exploration-Exploitation Tradeoff
Philip
Periodic Bootstrap Thompson Sampling For Periodically Non-Stationary Bandit Problems
Jul 18, 2026Boning ShaoThompson Sampling Non-Stationary Bandits
Faculty of Science, University of Hong Kong, Hong Kong, China
From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensing
Jul 15, 2026Yin Huang, Qingsong Liu, Jie XuMulti-Armed Bandits Non-Stationary Bandits
Manning College of Information and Computer Sciences, University of Massachusetts Amherst
Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
Jul 3, 2026Zihao Hu, Yuan Yao, Jiheng Zhang +1Dynamic Regret Minimization Non-Stationary Bandits
Department of Mathematics, The Hong Kong University of Science and Technology
Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits
Jun 22, 2026AmirHossein Naghdi, Ali BaheriThompson Sampling Non-Stationary Bandits
Sharif University of Technology, Iran · Rochester Institute of Technology, USA
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
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
SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search
May 31, 2026Noor Khial, Naram Mhaisen, Loay Ismail +1Multi-Armed Bandits Non-Stationary Bandits
College of Engineering, Qatar University, Qatar · Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, The Netherlands
Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
May 25, 2026Joongkyu Lee, Min-hwan OhMulti-Armed Bandits Dynamic Regret Minimization
Seoul National University
Nonparametric Learning and Earning with One-Point Feedback under Nonstationarity
May 20, 2026Xiangyu Yang, Feng Xu, Jian-Qiang Hu +1Non-Stationary Bandits Dynamic Pricing
School of Management, Shandong University · School of Management, Fudan University · Department of Applied Mathematics and Statistics, Stony Brook University
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

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

The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits

Sharan Sahu, Martin T. Wells

Department of Statistics and Data Science, Cornell University

Non-Stationary Bandits Dynamic Regret Minimization Minimax Estimation

Open paper AskPDF arXiv

Adaptive experiments use bandit algorithms to favor interventions with higher expected rewards. However, decision-makers also require reliable inference on current treatment effects: differences between intervention and reference-arm mean rewards at the present time, rather than historical averages. These objectives conflict: reward maximization favors better interventions, whereas current-effect inference requires continued exploration of potentially suboptimal interventions as outcomes change over time. We characterize this tradeoff for

K

-arm bandits with Hölder-smooth mean rewards of exponent

β\in(0,1]

and constant

L

. Requiring high-probability simultaneous coverage of all current effects by confidence intervals of width at most

w

, we establish matching minimax bounds, up to logarithmic factors, on expected dynamic regret. Over horizon

T

, our algorithm TRACE (Tracking Rewards and Current Effects) achieves regret of order

\widetilde{O}_β\left(\sqrt{KT}+K^{β/(2β+1)}L^{1/(2β+1)}T^{(β+1)/(2β+1)}+Kw^{-2}(1+L^{1/β}w^{-1/β})\right)

, where the notation hides logarithms and constants depending only on

β

. This regret--precision tradeoff separates reward-learning regret from the cost of refreshing current-effect estimates, which remains unavoidable even when one arm is uniformly optimal. An empirical-Bernstein e-process extension adapts exploration to realized prediction errors while preserving worst-case guarantees. When within-block drift is negligible relative to sampling error, all observations, including reward-learning observations, can be reused for asymptotically normal pointwise inference and stronger local stationarity yields local asymptotic efficiency. Finally, we show that regret constraints can prevent honest adaptation to unknown smoothness and support our theory with extensive numerical experiments.