Detection Augmented Learning In Non-Stationary Bandit Environments

Argyrios Gerogiannis; Yu-Han Huang; Subhonmesh Bose; Venugopal V. Veeravalli

cs.LGOct 19, 2026

Detection Augmented Learning In Non-Stationary Bandit Environments

Authors: Argyrios Gerogiannis, Yu-Han Huang, Subhonmesh Bose, Venugopal V. Veeravalli

Organizations: ECE department and the Coordinated Science Laboratory, Grainger College of Engineering, University of Illinois at Urbana-Champaign

Abstract

We study the problem of non-stationary bandits without knowledge of the environmental changes. We propose Detection Augmented Learning (DAL) a black-box paradigm that comprises three modular components: a bandit algorithm, a change detector, and a forced exploration schedule. This modular design enables its applicability across a broad spectrum of bandit problems, from classical to highly structured settings. First, we provide theoretical insights into DAL's strong empirical performance: a single regret bound shows that DAL transfers the regret of its stationary input to the piecewise stationary setting, attaining or improving the best known bounds in every setting considered. We further identify conditions under which DAL performs well in drifting environments. Then, we showcase DAL's practical performance and versatility through extensive experimentation in which DAL consistently surpasses all state-of-the-art methods, both prior-free and prior-based, across diverse non-stationary scenarios in nine bandit settings. Finally, we investigate the effectiveness of the forced exploration and show that a bandit-driven strategy improves performance and shortens detection delay.

Figures & tables

Figure 1

Setting	Input Regret	Best Existing Regret	DAL Regret
PS-LBs	$\tilde{\mathcal{O}}(d\sqrt{T})$ [ 1 ]	$\tilde{\mathcal{O}}(d\sqrt{N_{T}T})$ [ 25 ]	$\tilde{\mathcal{O}}(d\sqrt{N_{T}T})$
PS-GLBs	$\tilde{\mathcal{O}}(d\sqrt{T})$ [ 18 ]	$\tilde{\mathcal{O}}(d^{2/3}N_{T}^{1/3}T^{2/3})^{\bullet}$ [ 48 ]	${\color[rgb]{0,0,0.8047}\tilde{\mathcal{O}}(d\sqrt{N_{T}T})}$
PS-SCBs	$\tilde{\mathcal{O}}(d\sqrt{T})$ [ 34 ]	$\tilde{\mathcal{O}}(d^{2/3}N_{T}^{1/3}T^{2/3})^{\bullet}$ [ 48 ]	${\color[rgb]{0,0,0.8047}\tilde{\mathcal{O}}(d\sqrt{N_{T}T})}$
PS-KBs	$\tilde{\mathcal{O}}(\sqrt{\gamma_{T}T})$ [ 45 ]	$\tilde{\mathcal{O}}(\sqrt{d\gamma_{T}N_{T}T})$ [ 25 ]	${\color[rgb]{0,0,0.8047}\tilde{\mathcal{O}}(\sqrt{\gamma_{T}N_{T}T})}$
PS-CBs	$\tilde{\mathcal{O}}(\sqrt{\|\mathcal{A}\|T\log\|\Pi\|})$ [ 20 ]	$\tilde{\mathcal{O}}(\sqrt{\|\mathcal{A}\|N_{T}T\log\|\Pi\|})$ [ 12 ]	$\tilde{\mathcal{O}}(\sqrt{\|\mathcal{A}\|N_{T}T\log\|\Pi\|})$
PS-HBs (General $d,\beta$ )	$\tilde{\mathcal{O}}(T^{\frac{d+\beta}{d+2\beta}})$ [ 6 ]	$\tilde{\mathcal{O}}(N_{T}^{\frac{\beta}{d+3\beta}}T^{\frac{d+2\beta}{d+3\beta}})^{\bullet}$ [ 29 ]	${\color[rgb]{0,0,0.8047}\tilde{\mathcal{O}}(N_{T}^{\frac{\beta}{d+2\beta}}T^{\frac{d+\beta}{d+2\beta}})}$

TABLE I: Regret comparisons for PS bandits, under Assumption III.8 . “

\bullet

” denotes prior-based tuning. DAL attains the best regret or improves the best existing bounds ( blue = improvement).

Fig. 1: Final dynamic regret vs. radius

\delta

of the drift, mean

\pm

one standard deviation over

30

runs: DAL vs. WeightUCB; the range of

\delta

differs between panels. DAL performs best at small drift radii; WeightUCB overtakes DAL beyond

\delta\approx 0.1

in LBs and

\delta\approx 1

in SCBs.

Fig. 2: Dynamic regret in all synthetic benchmarks (lower is better), averaged over $15$ runs. Rows correspond to the bandit settings and action families; the four columns use geometric change-points with $\xi=0.4,0.6,0.8$ and drift, respectively.

Fig. 3: Real-world results, averaged over $15$ independent runs. Top: dynamic regret (lower is better). Bottom: cumulative reward (higher is better).

Fig. 4: Round-robin versus bandit-driven forced exploration in DAL (GLR), with

\xi=0.8

. Means and one standard error over

15

runs for

T\leq 2\times 10^{5}

and

10

otherwise.

Panel of Figure 7 — Fig. 5: Round-robin and bandit-driven forced exploration across horizons. Left: final regret with one-standard-error bars. Right: mean delay over detected changes.

Non-Stationary Bandits

Non-Stationary Bandits study sequential choices when rewards or constraints change over time, requiring learners to balance exploration with adaptation.

See all 39 papers

DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees
Apr 17, 2026Argyrios Gerogiannis, Yu-Han Huang, Venugopal V. VeeravalliNon-Stationary RL Regret Minimization in RL
ECE and CSL, The Grainger College of Engineering University of Illinois at Urbana-Champaign
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
Learning When to Update: A Near-Optimal Timing Bandit Approach
Sep 29, 2026Qiulin Lin, Junyan Su, Liyuan Wang +1Multi-Armed Bandits
City University of Hong Kong,, Hong Kong, China · The Chinese University of Hong Kong (Shenzhen), China

Apr 17, 2026J/K move · Enter open · S save

DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees

Argyrios Gerogiannis, Yu-Han Huang, Venugopal V. Veeravalli

ECE and CSL, The Grainger College of Engineering University of Illinois at Urbana-Champaign

Non-Stationary RL Regret Minimization in RL Markov Decision Processes Dynamic Regret Minimization Linear Markov Decision Processes Model-Free RL

Open paper AskPDF arXiv

We study model-free reinforcement learning (RL) in non-stationary finite-horizon episodic Markov decision processes (MDPs) without prior knowledge of the non-stationarity. We focus on the piecewise stationary (PS) setting, where both rewards and transition dynamics can change at unknown times. We first revisit existing state-of-the-art approaches and identify theoretical and practical limitations that change the current landscape of performance guarantees. To characterize the difficulty of the problem, we establish the first minimax lower bounds for PS-RL in tabular and linear MDPs. We then introduce Detection Augmented Reinforcement Learning (DARLING), a modular wrapper for PS-RL that applies to both tabular and linear MDPs, without knowledge of the changes. In tabular MDPs, under change-point separability and reachability conditions, DARLING improves the best known dynamic regret bounds and matches our minimax lower bound. In linear MDPs, DARLING matches the minimax lower bound when the relevant reachability parameters are known, and our analysis clarifies the structural obstacles that distinguish this setting from the tabular case. Finally, through extensive experimentation across diverse non-stationary benchmarks, we show that DARLING consistently surpasses the state-of-the-art methods.

Abstract

Non-Stationary Bandits

Explore similar work

DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees

A Modularized Framework for Piecewise-Stationary Restless Bandits

Learning When to Update: A Near-Optimal Timing Bandit Approach