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.

Bandit Learning in General Open Multi-agent Systems
May 7, 2026Mengfan XuMulti-Armed Bandits Multi-Agent 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
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
ParetoBandit: Budget-Paced Adaptive Routing for Non-Stationary LLM Serving
Mar 31, 2026Annette Taberner-MillerAdaptive Model Routing LLM Routing
Independent Researcher.
On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization
Mar 19, 2026Yixuan Zhang, Ruihao Zhu, Qiaomin XieRegret Minimization Non-Stationary Bandits
Department of Industrial & Systems Engineering, University of Wisconsin-Madison · SC Johnson College of Business, Cornell University
A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems
Mar 17, 2026Wei Min Loh, Sajib Kumer Sinha, Ankur Agarwal +1Bandit Learning Multi-Armed Bandits
University of Waterloo, Vector Institute · Manulife Financial
On the Complexity of Best-Arm Identification in Non-Stationary Linear Bandits
Mar 11, 2026Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson +1Multi-Armed Bandits Best-Arm Identification
University of Washington
Invariance-Based Dynamic Regret Minimization
Mar 4, 2026Margherita Lazzaretto, Jonas Peters, Niklas PfisterNon-Stationary Bandits Linear Contextual Bandits
University of Copenhagen · ETH Zürich · Lakera Zürich
Truly Adapting to Adversarial Constraints in Constrained MABs
Feb 16, 2026Francesco Emanuele Stradi, Kalana Kalupahana, Matteo Castiglioni +2Constrained Optimization Adversarial Bandits
Politecnico di Milano

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

Bandit Learning in General Open Multi-agent Systems

Mengfan Xu

Mechanical and Industrial Engineering, University of Massachusetts Amherst

Multi-Armed Bandits Multi-Agent Bandits Non-Stationary Bandits UCB Algorithms Bandit Learning

Open paper AskPDF arXiv

Open systems, where agents arrive and depart over time, are growing in digital platforms. Existing work on online learning in such systems, however, often relies on structural assumptions that may be restrictive in practice. In particular, heterogeneous rewards and general agent patterns create three new challenges: arrivals induce endogenous non-stationarity, agent patterns govern the rate of information accumulation, and uncertainty brought by new agents accumulates over time and scales regret. To this end, we formulate a learning problem for open systems that accommodates both forms of generality. We introduce new concepts to capture the inherent complexities: the pre-training degree of new agents quantifies how much information an agent carries upon entry, stability measures the impact of population changes on the global optimum, and global dynamic regret compares the cumulative expected reward with that of the varying optimal arms. We also study a manifold representation of agents and introduce a dynamic population embedding that directly encodes the population functional for each arm. We develop two UCB-based methods. The first combines entry information with online observations through agent-wise confidence bounds and aggregates the estimates and uncertainties for arm selection. The second pools agent-level observations through kernel regression on the manifold and constructs UCBs by projecting the confidence sets onto the current population embedding. Entry uncertainty enters the regret linearly through the pre-training error, while in stable regimes, regret is governed by the time needed to identify the stable optimal arm. With the manifold as a handle, regret is governed by the information gained from agent representations. These bounds all depend on population dynamics, but in different ways.