Non-Stationary Bandits

Follow this topic Ask about this topic

Momentum

4 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 23

All topics

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
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
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
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
Bandit Learning in General Open Multi-agent Systems
May 7, 2026Mengfan XuMulti-Armed Bandits Non-Stationary Bandits
Mechanical and Industrial Engineering University of Massachusetts Amherst
A single algorithm for both restless and rested rotting bandits
Apr 23, 2026Julien Seznec, Pierre Ménard, Alessandro Lazaric +1Multi-Armed Bandits Non-Stationary Bandits
SCOOL, Inria Lille · FAIR Paris · DeepMind Paris

Oct 7, 2026, stat.MLJ/K move · Enter open · S save

Best Arm Identification for Bandits with Shifting Means

Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal, Christina Katsimerou+1

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

Multi-Armed Bandits Best-Arm Identification Non-Stationary Bandits

Open paper AskPDF arXiv

We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the

K

arms are stable in time, in Shifting Means only the gaps

\boldsymbolΔ

between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means (

\mathsf{ISM}

). Assuming means bounded by

U

and

σ^2

-sub-Gaussian rewards, we show

\mathsf{ISM}

to be

δ

-correct and to enjoy a sample complexity bound of order

K (σ^2 + U^2) Δ_{\min}^{-2} \ln \frac{1}δ

. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.

Momentum

Related topics

Latest papers 23