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 24

Oct 7, 2026stat.ML

Best Arm Identification for Bandits with Shifting Means

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.

Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal +2

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

Oct 5, 2026cs.LG

Bellman-Centric Learning: Near-Optimal Regret for Linear Bandits with Memory

We study linear bandits with memory, where past actions induce endogenous nonstationarity through an arbitrary known, bounded matrix-valued memory map. To trade off exploration and exploitation while accounting for the memory dynamics, we develop RSM-LinUCB, a Bellman-centric algorithm that learns as in linear bandits and plans as in reinforcement learning. This design admits a novel regret decomposition which separates the memory-induced error from the cumulative reward estimation error along the learner's trajectory. We prove a high-probability regret bound of

\widetilde O\big(dRS(M+1)+σd\sqrt T\big)

, where

T

is the learning horizon,

d

is the parameter dimension,

M

is the memory length,

R

and

S

bound the memory-map operator norm and reward-parameter norm, respectively, and

σ

is the sub-Gaussian noise scale. Our results reveal that the multiplicative memory-horizon coupling in prior bounds is not intrinsic: memory only contributes an additive cost, up to logarithmic factors. We also prove a matching minimax lower bound, establishing near-optimality. We further extend the algorithm to generalized linear rewards, preserving this separation with near-optimal memory and leading statistical dependence. Our algorithms outperform the baselines in numerical experiments on synthetic instances and semi-synthetic KV- and semantic-cache tasks.

Jingyuan Liu, Huiwen Jia

Department of Industrial Engineering and Operations Research, University of California, Berkeley

Multi-Armed Bandits Non-Stationary Bandits Generalized Linear Bandits

Oct 1, 2026stat.ML

Block Optimism for Nonstationary Bandits with Latent Linear Dynamics

We study an endogenous nonstationary stochastic bandit problem with latent linear dynamics, where actions affect both immediate rewards and the future evolution of an unobserved latent state. Rewards are bilinear in the current action and latent state, inducing history-dependent rewards and a nontrivial long-horizon planning problem. The existing explore-then-commit approach achieves

\tilde{O}(T^{2/3})

regret by uniformly exploring to estimate the latent dynamics and then committing to an optimized open-loop action sequence. We show that this rate can be improved via adaptive block-level optimism. Our key step is a cyclic approximation: under stable dynamics, the infinite-memory reward process can be truncated, and the open-loop benchmark can be approximated by optimizing a finite-memory block-level proxy. Building on this reduction, we propose a UCB-based block algorithm that maintains confidence sets for the truncated dynamics parameters and selects blocks optimistically. We prove a regret bound of order

\tilde{O}(\sqrt T)

, significantly improving over the previous

\tilde{O}(T^{2/3})

guarantee for the same model. To the best of our knowledge, this is the first

\tilde{O}(\sqrt T)

regret guarantee for latent linear-dynamics bandits with bilinear reward observations and an open-loop action-sequence benchmark.

Taehyun Hwang, Hyunjun Choi, Heesang Ann +1

Seoul National University Soeul, South Korea

Multi-Armed Bandits Stochastic Linear Dynamical Systems Non-Stationary Bandits UCB Algorithms

Sep 27, 2026cs.LG

Future Information-Directed Sampling for Bayesian Nonstationary Bandits

Exploration--exploitation is a central trade-off in bandit learning. While classical algorithms such as upper confidence bound methods and Thompson Sampling effectively balance this trade-off in stationary environments, their exploration strategies mainly reduce uncertainty about the current optimal arm, which can be insufficient in nonstationary settings where future optimal arms may differ substantially from current ones. In this paper, we propose Future Information-Directed Sampling (FIDS), a new algorithm for Bayesian nonstationary bandits that explicitly explores to gather information about future optimal arms. We show that FIDS achieves regret comparable to Thompson Sampling up to a small constant factor, while being able to exploit predictive information structures that conventional exploration objectives fail to capture. To address the practical difficulty of posterior inference, we further propose a supervised-learning-based approximation framework that learns the FIDS policy from offline data, and demonstrate its effectiveness on synthetic benchmarks.

Yichen Song, Alessio Russo, Aldo Pacchiano

Boston University · Broad Institute of MIT and Harvard

Multi-Armed Bandits Non-Stationary Bandits Policy Learning

Sep 17, 2026cs.LG

Odds-Ratio Thompson Sampling: A Specification and Design Guide for Contrast-Based Multi-Armed Bandits

Batched multi-armed bandits update on a service's own schedule, and the usual implementation carries each arm's absolute reward rate from one update to the next. When the shared level moves between batches, that memory goes stale even though the comparisons between arms may not have. Odds-Ratio Thompson Sampling (OR-TS) instead carries the joint posterior over log-odds contrasts and fits the common level afresh in every batch, marginalizing it out. This paper specifies that update, places it inside a Bayesian bandit agent with two controls, decay for how much past evidence survives an update and aggressiveness for how sharply belief becomes allocation, and evaluates it against absolute-rate memory. Across 86 public A/B series the level varies about twenty-five times more than the contrast. In prespecified synthetic environments a moving level costs absolute-rate memory five times the regret and leaves the best arm below a majority of traffic in 7 of 20 runs, against none for OR-TS. In a policy simulation built from 71 real experiments, where the contrasts are too small to resolve, expected-click differences stay within 0.1% for 58 of them, yet contrast memory still ends on the better arm more than twice as often. Where the contrasts themselves move, the bet fails, and that case is reported too.

Sulgi Kim

Independent researcher

Thompson Sampling Multi-Armed Bandits Non-Stationary Bandits A/b Testing

Sep 15, 2026cs.LG

Adapting to Decision-Relevant Non-Stationarity in Decentralized Heterogeneous Bandits

Decentralized bandit systems often contain heterogeneous agents: rewards can change at individual agents even when the best action for the network stays the same. These local changes may cancel when rewards are averaged across agents, so the number of local changes

\Stloc

can be much larger than the number of changes in the best common arm

\Stdec

. We introduce Decision-Relevant Fresh Comparison (DRFC), which uses new, balanced samples from all agents to compare arms at the network level and switches only when fresh global evidence indicates that the common best arm has changed. We prove a high-probability dynamic regret bound with no adaptation term depending on

\Stloc

, and show that every algorithm must still pay for identifying genuine decision switches and propagating them through the communication graph. Under a distinct time-average benchmark, an anytime-valid sliding-window extension handles gradual drift; experiments on synthetic, semi-real, and MovieLens-1M replays show that DRFC ignores decision-irrelevant local changes while the extension avoids false switches.

Zhaojun Peng

Multi-Armed Bandits Dynamic Regret Minimization Non-Stationary Bandits

Sep 1, 2026stat.ML

Pooling and Drift in Delayed Bandits

A system often has to act long before it learns whether the act worked: a recommender sees a click in seconds and a purchase in days. With

K

actions and a delay of

d

rounds, the best rate known for this setting is

\widetilde{O}(\sqrt{(K+d)T})

over

T

rounds, so a longer menu is always more expensive to learn from. It need not be: if the outcome depends on the action only through the state it produced, then one late outcome informs every action that could have produced the observed state, and the price is set by how many genuinely different states the actions produce rather than by how many actions there are. We measure this using an effective dimension

v_t

between

1

and the number of states, and prove

\widetilde{O}(\sqrt{(d+1)V\log K})

for a rotating algorithm and

\widetilde{O}(\sqrt{V^{-}}+\sqrt{dT})

for the single-copy algorithm used in practice, for any budget fixed in advance; merging similar states lowers the price further, at an explicit bias. Even when given the exact losses from

d

rounds ago, no algorithm escapes

Ω(\sqrt{dE\min\{1+\log J,T/d\}})

, where

J

counts the drifting directions and

E

bounds how far losses move while the learner waits. On generated data, the state channel cuts regret by up to 79 percent against action-level weighting and, on the funnel family, by 32 to 68 percent against a tuned minimax-optimal method.

Melika Baghi

Georgia Institute of Technology

Multi-Armed Bandits Non-Stationary Bandits State Abstraction Bandits with Delayed Feedback

Sep 1, 2026cs.AI

Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets

A multi-model language service must route each request while preserving workload-level budgets for compute, latency, memory, or monetary cost. Two features make this problem materially harder than static model selection. Prompt representations are high dimensional, so only a small subset of embedding directions may predict the incremental value of a model, and both the request mix and the model frontier drift after launches, fine-tunes, quantization changes, and system updates. We formulate nonstationary sparse contextual routing with multiple knapsack constraints and an optional shadow-audit stream that evaluates a small fraction of prompts on several models. We propose Drift-Aware Sparse Routing (DRS). The policy estimates reward and resource use from a rolling audit window, routes using pessimistic reward and optimistic cost estimates, updates resource shadow prices online, and applies a hard meter before commitment. The analysis separates control from statistics. On any event with uniform prediction radii

\{β_t\}

, regret against a paced dynamic fluid benchmark is bounded by the sum of the radii, a capacity-buffer term, and an

O(\sqrt{T})

pacing term. Under a sparse linear model and bounded drift

V_T

, rolling estimation gives

\widetilde O\left( T\sqrt{\frac{s}{ρW}}+WV_T+\sqrt{T} \right),

where

s

is sparsity,

ρ

is the audit rate, and

W

is the window length. Optimizing

W

yields the usual stationary

O(\sqrt{sT/ρ})

rate when

V_T=0

and a

O(T^{2/3}(s/ρ)^{1/3}V_T^{1/3})

adaptation term under drift.

Cheung Hao Lee, Patrick Wong

Cost-Aware Inference Non-Stationary Bandits LLM Routing Contextual Bandits

Aug 7, 2026cs.CL

Progressive Content Refinement with Decaying Reward Joint LinUCB

Iterative refinement has significantly enhanced Large Language Model (LLM) performance; however, existing methods ranging from feedback-based Self-Refine to traditional bandit approaches often rely on static options or overlook the saturation effect. This neglect leads to over-exploitation, where the continuous use of identical prompts or arms results in diminishing rewards over time. To address this challenge, we propose a novel contextual bandit algorithm that explicitly incorporates reward decay modeling. Utilizing an Expectation-Maximization (EM) algorithm, our method simultaneously estimates both arm-specific and decay parameters. Furthermore, by embedding prompts as arms, we facilitate the joint learning of arm values, distinguishing our approach from the traditional disjoint Linear Upper Confidence Bound (LinUCB) framework. Experimental results on Sentiment Reversal and GSM8K benchmarks demonstrate that our method achieves significant performance gains over strong baselines. Finally, our ablation study confirms that the integration of reward decay modeling within the bandit framework is crucial for mitigating over-exploitation and optimizing the iterative refinement process.

Shion Ishikawa, Pablo Loyola, Young-joo Chung +1

Rakuten Group, Inc. Tokyo, Japan · Rakuten Group, Inc. San Mateo, USA

LLM Self-Refinement Large Language Model-Guided Optimization Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

Aug 2, 2026cs.AI

402Pilot: An x402 Decision Layer for Autonomous Agent Micropayments

Programmable-payment protocols such as x402 enable per-request micropayments, but they do not determine which payable service an autonomous agent should buy under a finite wallet. We formulate this buyer-side problem as agent-native payment decision-making: contextual provider selection under wallet pressure, chosen-only paid feedback, and changing market conditions. We propose 402Pilot, a protocol-agnostic buyer-side decision layer between autonomous agents and payment execution that implements purchasing policies for selecting among payable providers. We instantiate it with PA-DCT, a payment-aware discounted contextual Thompson-sampling policy that adapts purchasing decisions under wallet pressure while learning from post-payment feedback. To evaluate buyer-side payment policies, we introduce 402Pilot-Bench, a frozen-replay benchmark spanning 823 tasks, five heterogeneous provider pipelines, and three market regimes, each evaluated over 30 paired seeds. PA-DCT achieves the strongest fixed-wallet adaptive trade-off among non-oracle policies: it maintains competitive service quality while spending only 39 to 43 percent of the wallet and reallocates spending as market conditions change. It attains the best non-oracle PA-gap/T under the price shock and the best mean and worst-case ranks across the nine scenario-metric combinations of quality, ROI, and PA-gap/T. Comparisons with learning baselines and component ablations further support the effectiveness and design of the proposed decision policy. These results suggest that programmable payment must be complemented by buyer-side decision-making capable of learning service value and adapting purchasing decisions accordingly.

Yin Li, Yanbo He, Boo-Ho Yang +5

The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China · MOVENSYS Inc., Seongnam-si, Republic of Korea · Schneider Electric, Shanghai, China +2

Multi-Armed Bandits Non-Stationary Bandits Contextual Bandits

Jul 27, 2026stat.ML

On Non-Stationary Dynamic Pricing: Adaptivity and Optimality

We study the contextual dynamic pricing problem under non-stationarity, where a firm sells products to

T

sequentially arriving consumers that behave according to an unknown demand model that can change over time. The demand model is assumed to be a generalized linear model (GLM), allowing for a feature vector in

\mathbb{R}^d

that encodes products and consumer information. To achieve optimal revenue (i.e., least regret), the firm needs to learn and exploit the unknown GLMs while monitoring for potential changes. We propose a multiscale change-point detection based algorithm that achieves a regret of order

\widetilde{O}(\sqrt{s_TdT}\wedge\{V_T^{1/3}d^{1/3}T^{2/3}+\sqrt{dT}\})

, where

s_T

is the number of piecewise stationary segments and

V_T

is a newly defined notion of design-adjusted variation budget of model parameters. Our algorithm is adaptive and does not require knowing

s_T

or

V_T

. Moreover, to our knowledge, this is the first dynamic pricing algorithm that is adaptive to the nature of changes and achieves the best-of-both-worlds rate, thus closing a long-standing gap in the literature. We remark that, due to the varying contexts, existing works in the adaptive non-stationary bandit literature cannot be applied to achieve optimality for contextual dynamic pricing. The regret is further accompanied with a newly constructed minimax lower bound, confirming the optimality of our algorithm (up to logarithmic factors). Extensive numerical experiments are conducted to illustrate the efficiency and robustness of the proposed algorithm in non-stationary dynamic pricing.

Feiyu Jiang, Zifeng Zhao

School of Management, Fudan University · Mendoza College of Business, University of Notre Dame

Non-Stationary Bandits Dynamic Pricing Generalized Linear Bandits

Jul 26, 2026cs.LG

Experimentation and Commitment under Reward Shifts

Decision-makers in learning environments face a dilemma when their short-term optimal actions may not favor their long-term benefits the most. To understand the fundamental tradeoff behind the dilemma, we study adaptive experimentation with post-commitment reward shifts. During an experiment phase, the decision-maker may adaptively test multiple options; during a subsequent commitment phase, the decision-maker must commit to a single option, whose reward may differ from its pre-commitment reward. We propose the Reserved Arm Eliminations for Commitment (RAEC) algorithm, which reserves a predetermined portion of the experiment phase to identify the best post-shift option while using the remaining rounds to minimize short-run regret. We establish regret upper bounds for RAEC across all parameter regimes and matching minimax lower bounds, providing a tight characterization of the cost of balancing short-term performance and long-term commitment. A key implication is that deciding in advance how much of the experiment phase to reserve for the commitment decision is sufficient to achieve the best possible worst-case regret rate; adapting this amount as more data are observed does not improve the rate. We further study extensions with structural knowledge of reward shifts and with concave commitment rewards and portfolio choice. Numerical experiments confirm that our proposed algorithms achieve the regret predicted by our theory and outperform other baselines.

Puping Jiang, Wei Tang, Renyu +1

Philip

Multi-Armed Bandits Exploration-Exploitation Tradeoff Minimax Regret Non-Stationary Bandits

Jul 18, 2026cs.LG

Periodic Bootstrap Thompson Sampling For Periodically Non-Stationary Bandit Problems

This paper introduces Periodic Bootstrap Thompson Sampling (PBTS), an innovative extension of the classic Thompson Sampling (TS) algorithm tailored for bandit problems with periodic non-stationarity. Conventional TS accumulates all past observations, leading to biased posteriors when reward distributions cycle over time. PBTS overcomes this by synchronizing belief resets with known or inferred period intervals and embedding structured bootstrap exploration phases, effectively purging obsolete data while preserving uncertainty estimates. PBTS is tested in artificially constructed environments, which include skewed and balanced reward distributions, along with different bootstrap proportions and misaligned periodic intervals. Results indicate that PBTS generally achieves statistically significant reductions in cumulative regret against traditional TS in periodic non-stationary environments. Subsequent discussion further articulates the potential of PBTS's real-world deployment. The study mentions limitations like extreme periodic misalignment and proposes future research such as self-adjusting cycle-recognition. With memory reset and bootstrap phase, PBTS introduces a novel approach to optimizing bandit algorithms in periodic reward contexts.

Boning Shao

Faculty of Science, University of Hong Kong, Hong Kong, China

Thompson Sampling Non-Stationary Bandits

Jul 15, 2026cs.LG

From Novice to Expert: Cost-Aware Bandits for Evolving Worker Performance in Crowdsensing

Mobile crowdsensing (MC) recruits mobile users to perform sensing tasks using their smartphones, enabling large-scale applications such as traffic monitoring and environmental sensing. A fundamental challenge is online worker recruitment under uncertainty, where the platform must learn workers' sensing performance while operating with a limited budget. Existing learning-based MC recruitment methods typically assume that each worker's sensing quality is stationary with a fixed mean over time. In practice, however, worker performance often improves with experience and eventually stabilizes, while the incurred sensing cost can be unknown in advance due to time-varying device and context states. In this paper, we study a budget-constrained online recruitment problem in which the platform selects one worker in each round, observes the sensing quality and incurred cost, where the expected sensing quality of each worker increases with experience and eventually converges to a plateau, and repeats until the budget is exhausted. We formulate this problem as a structured bandit model where each worker's expected reward evolves according to an unknown increasing-then-converging function of its participation count, and each worker has an unknown expected cost. We develop a cost-aware online learning framework that jointly learns evolving reward trajectories and heterogeneous costs, detects performance saturation, and allocates the limited budget to maximize long-term sensing utility. We provide theoretical performance guarantees and validate the proposed approach through extensive experiments, demonstrating consistent improvements over baselines that ignore experience-driven dynamics or assume known costs.

Yin Huang, Qingsong Liu, Jie Xu

Manning College of Information and Computer Sciences, University of Massachusetts Amherst

Multi-Armed Bandits Non-Stationary Bandits Online Resource Allocation

Jul 3, 2026cs.LG

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

Many online decision-making problems involve both round-specific feasible actions and drifting reward models: eligible ad impressions, feasible prices, and available treatments can change over time, while user preferences, demand curves, and patient responses may evolve. Motivated by these applications, we study non-stationary linear bandits with round-specific feasible decision sets. Existing methods that obtain the optimal

\widetilde O(T^{2/3}P_T^{1/3})

dependence, where

P_T

is the path length of the reward-parameter sequence, impose an orthogonal-structure assumption on round-specific decision sets, which can be restrictive in contextual applications. We address this gap through a unified misspecification-reduction viewpoint: after partitioning the horizon into blocks, we relate each block's dynamic regret to regret against a fixed-parameter linear bandit benchmark, with the within-block parameter drift entering as bounded misspecification. Restarting algorithms with misspecification-dependent regret guarantees then yields the optimal

T^{2/3}P_T^{1/3}

dynamic-regret dependence for both linear bandits with general compact decision sets and

K

-armed contextual linear bandits.

Zihao Hu, Yuan Yao, Jiheng Zhang +1

Department of Mathematics, The Hong Kong University of Science and Technology

Dynamic Regret Minimization Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

Jun 22, 2026eess.SY

Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits

We study non-stationary linear contextual bandits where the reward model drifts over time, rendering classical contextual bandit algorithms brittle because historical data becomes systematically biased. We propose Flow-Corrected Thompson Sampling (fcTS), a Bayesian method that reuses experience by transporting past rewards to the present using an explicit drift model and incorporating each transported observation with a confidence weight that reflects transport reliability. This yields a unified template that specializes in (i) linear parameter drift via online slope estimation and reward correction, (ii) periodic variation via phase-aware reuse across cycles, and (iii) recurring regime switches via changepoint detection and regime-specific posterior memory. The resulting posterior updates remain closed-form under a linear Gaussian model and can be implemented efficiently with truncated, incrementally updated sufficient statistics. Across five controlled case studies and a semi-synthetic portfolio-selection benchmark with multiple overlapping non-stationarities, fcTS outperforms standard forgetting-based baselines (discounting, sliding windows, and periodic restarts), with the largest gains in settings exhibiting recurring temporal structure. These results demonstrate that when non-stationarity is structured, correcting and reweighting historical observations can be substantially more sample-efficient than uniformly discarding them.

AmirHossein Naghdi, Ali Baheri

Sharif University of Technology, Iran · Rochester Institute of Technology, USA

Thompson Sampling Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

Jun 16, 2026cs.LG

Online LLM Selection via Constrained Bandits with Time-Varying Demand

Large Language Models (LLMs) are increasingly deployed in edge-cloud inference systems to handle diverse user tasks with heterogeneous accuracy, latency, and cost profiles. Selecting the appropriate LLM for each incoming task is critical for ensuring service quality and efficient resource utilization. However, model heterogeneity, stochastic and unknown performance characteristics, and time-varying task demands make static selection strategies inadequate. Real-world deployments often impose hard resource budgets such as monetary expenditure limits, along with soft service-level requirements such as latency guarantees. These constraints introduce additional challenges for online decision-making. We formulate this problem as a constrained stochastic bandit learning task, where the learner sequentially selects models under both packing-type (hard) and covering-type (soft) constraints, while adapting to time-varying task demand. The learner operates without access to the underlying reward, cost, or latency distributions and must rely on partial feedback. We develop a novel online learning algorithm that leverages confidence-bound estimates and demand predictions to balance reward maximization with long-term constraint satisfaction. We provide theoretical guarantees showing sublinear regret and sublinear covering constraint violations compared to an offline benchmark with full information. Experimental results on synthetic workloads demonstrate the effectiveness and robustness of our approach in dynamic, resource-constrained environments.

Yin Huang, Qingsong Liu, Jie Xu

Department of Electrical and Computer Engineering, University of Florida · Manning College of Information and Computer Sciences, University of Massachusetts Amherst

Multi-Armed Bandits Cost-Aware Inference Non-Stationary Bandits LLM Routing

Jun 8, 2026cs.LG

Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts

We consider a variant of the linear contextual stochastic multi-armed bandits, where the learner must provide recommendations to a group of users, each having its personalized preference vector, and in the presence of context distributions that are drifting over time. Under practitioner-friendly assumptions, we reduce this setting to linear bandit with stationary mean but heteroskedastic and non-stationary noise. We further study the case when the learner must ensure the mean reward of each decision must exceed that of a baseline strategy

\boldsymbolπ_0

at each decision step. We introduce Dri-MED, an algorithm inspired from the linear version of the MED strategy, and carefully adapted to handle the non-stationary heteroskedastic noise. We show that the instance-dependent regret scales as

\tilde{\mathcal O}\left(\fracκ{\tildeΔ}d^2(\log(T)\right)

, where

\tildeΔ

is the constraint-aware sub-optimality gap subject to policy

π_0

, with variance-aware multiplicative term

κ

that we carefully handle using heteroskedastic regression. We further show Dri-MED enjoys

\tilde{\mathcal{O}}(d)

expected constraint violations. Our numerical results suggest that Dri-MED significantly outperforms conservative baselines that ignores the drift and preference structure.

Udvas Das, Waris Radji, Debabrota Basu +1

Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRIStAL F-59000 Lille, France

Multi-Armed Bandits Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

May 31, 2026cs.NI

SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search

Unmanned Aerial Vehicles (UAVs) equipped with radar sensors are deployed for target search missions in diverse environments, where targets exhibit characteristic signatures (e.g., respiration micro-motion in human search) detectable through occlusions. A fundamental challenge arises from shifts in radar statistics as the UAV moves through a dynamic and potentially non-stationary environment, rendering any fixed signal-processing strategy suboptimal; yet perception and adaptation must run onboard a resource-constrained aerial node in real time. Since no single detector performs well across all conditions, we adopt a multi-policy paradigm and formulate UAV target search as an online policy selection problem over a library of specialized detectors, with performance measured by regret, the cumulative loss gap relative to the best policy in each scene. The setting couples in-scene stochastic noise with inter-scene shifts. Whereas prior methods capture only one regime, we account for both through the Stochastically Extended Adversary (SEA) framework, without requiring oracle knowledge of scene dynamics. Because adaptation must run at the UAV, we instantiate SEA through \textsc{SEArch}, a lightweight optimistic Follow the Regularized Leader (OFTRL) selector with an adaptive learning rate, achieving regret

O(\barσ_T \sqrt{T} + \sqrt{J})

, where

\barσ_T

captures radar measurement noise and

J

is the number of scene transitions over the mission horizon

T

. To enable rapid adaptation under frequent scene changes, we further introduce \textsc{W-SEArch}, a windowed variant that restarts every

w

rounds and achieves regret

O(\barσ_I \sqrt{w})

under at most one transition per window. Experiments show up to 30% regret reduction compared to non-adaptive baselines across a range of non-stationary settings.

Noor Khial, Naram Mhaisen, Loay Ismail +1

College of Engineering, Qatar University, Qatar · Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, The Netherlands

Multi-Armed Bandits Non-Stationary Bandits Follow-the-Regularized-Leader Adversarial Bandits

May 25, 2026stat.ML

Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

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.

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

May 20, 2026cs.LG

Nonparametric Learning and Earning with One-Point Feedback under Nonstationarity

Firms increasingly rely on dynamic pricing to respond to evolving customer demand, yet in many applications they observe only the revenue generated by a single posted price in each period. At the same time, market conditions may shift gradually or abruptly due to changes in customer preferences, competition, or external shocks. These features create two intertwined challenges: learning the revenue--demand relationship from limited feedback and adapting pricing decisions to a changing environment. We study how a seller can learn and earn effectively under these constraints, without assuming a specific parametric form for demand. We develop a learning framework that updates prices using revenue-based gradient approximations constructed from one observation per period. To address environmental changes, we incorporate a restarting mechanism that periodically refreshes the learning process so that outdated information is discounted. When the degree of nonstationarity is unknown, we further introduce a meta-learning layer to adaptively hedge across multiple restarting schedules. We provide performance guarantees for our approach, showing how cumulative revenue loss relative to a fully informed benchmark depends on both the time horizon and the magnitude of market variation. Simulation experiments using synthetic and real-world data illustrate the effectiveness of the proposed procedures.

Xiangyu Yang, Feng Xu, Jian-Qiang Hu +1

School of Management, Shandong University · School of Management, Fudan University · Department of Applied Mathematics and Statistics, Stony Brook University

Non-Stationary Bandits Dynamic Pricing Adaptive Learning

May 18, 2026cs.LG

Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity

Many bandit deployments (recommendation, clinical dosing, ad targeting) share two facts prior work handles only in isolation: rewards live on a low-dimensional latent subspace, and that subspace drifts. Stationary low-rank bandits exploit rank but break under subspace change; non-stationary linear bandits adapt to drift but pay ambient rate

\widetilde{O}(d\sqrt{T})

. We study piecewise-stationary low-rank linear contextual bandits with scalar feedback:

θ_t = B_k^\star w_t

with rank-

r

factor

B_k^\star\in\mathbb{R}^{d\times r}

constant within each of

K

unknown segments and able to shift at boundaries. Our results are tight along three axes. (i) Identification boundary. With single-play scalar rewards, the moving subspace is recoverable through quadratic functionals of rewards iff three probe-side conditions hold: known noise variance, bounded state-noise coupling, and full-dimensional probe support. Each is necessary in the unrestricted-second-moment problem, and jointly they are sufficient, characterizing the boundary of the solvable region. (ii) Algorithm and dynamic regret. SPSC interleaves isotropic probes with windowed projected ridge-UCB exploitation inside the learned

r

-dimensional subspace; a CUSUM-style variant discovers segment boundaries online. The costed dynamic regret is

\widetilde{O}(r\sqrt{T})+\widetilde{O}(T^{2/3})+O(W\,V_{\mathrm{in}})

, replacing the ambient

d\sqrt{T}

rate with the intrinsic rank. (iii) Empirics. On eleven benchmarks spanning synthetic, UCI/MovieLens, semi-synthetic clinical, and ZOZOTOWN production-log data, SPSC outperforms non-stationary and low-rank baselines whenever

d-r\gtrsim T^{1/6}

, matching the analytical crossover. To our knowledge, this is the first work to characterize the identification boundary and attain the intrinsic-rank dynamic-regret rate in this setting.

Hamed Khosravi, Xiaoming Huo

H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332

Multi-Armed Bandits Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

May 7, 2026cs.LG

Bandit Learning in General Open Multi-agent Systems

Recent developments in digital platforms have highlighted the prevalence of open systems, where agents can arrive and depart over time. While bandit learning in open systems has recently received initial attention, existing work imposes structural assumptions that are frequently violated in practice. A learning paradigm for general open systems creates fresh challenges: newly arriving agents induce endogenous non-stationarity; agent patterns determine how quickly information accumulates; and new agents make regret scale further with the time horizon. To this end, we formulate a unified open-system bandit problem with general dynamics, including heterogeneous rewards and general agent patterns. We introduce new concepts to capture the inherent complexities: the \emph{pre-training degree} of new agents quantifies how much information an agent carries upon entry, \emph{stability} measures the impact of new agents on the system, and \emph{global dynamic regret} compares the cumulative expected reward of all active agents with that of the varying optimal arms. We develop certified global-UCB learning methodologies with provable guarantees. Our regret bounds reveal that entry uncertainty enters linearly via the pre-training degree, while in stable regimes, regret is governed by the time needed to identify a persistent optimal arm, as well as by the agent patterns. We further show that these dependencies are tight via lower bounds in hard instances.

Mengfan Xu

Mechanical and Industrial Engineering University of Massachusetts Amherst

Multi-Armed Bandits Non-Stationary Bandits UCB Algorithms

Apr 23, 2026stat.ML

A single algorithm for both restless and rested rotting bandits

In many application domains (e.g., recommender systems, intelligent tutoring systems), the rewards associated to the actions tend to decrease over time. This decay is either caused by the actions executed in the past (e.g., a user may get bored when songs of the same genre are recommended over and over) or by an external factor (e.g., content becomes outdated). These two situations can be modeled as specific instances of the rested and restless bandit settings, where arms are rotting (i.e., their value decrease over time). These problems were thought to be significantly different, since Levine et al. (2017) showed that state-of-the-art algorithms for restless bandit perform poorly in the rested rotting setting. In this paper, we introduce a novel algorithm, Rotting Adaptive Window UCB (RAW-UCB), that achieves near-optimal regret in both rotting rested and restless bandit, without any prior knowledge of the setting (rested or restless) and the type of non-stationarity (e.g., piece-wise constant, bounded variation). This is in striking contrast with previous negative results showing that no algorithm can achieve similar results as soon as rewards are allowed to increase. We confirm our theoretical findings on a number of synthetic and dataset-based experiments.

Julien Seznec, Pierre Ménard, Alessandro Lazaric +1

SCOOL, Inria Lille · FAIR Paris · DeepMind Paris

Multi-Armed Bandits Non-Stationary Bandits UCB Algorithms