Dynamic Regret Minimization

Follow this topic Ask about this topic

Dynamic regret measures an online learner’s cumulative loss against a comparator that can change its decisions over time, often quantified by its number of switches or total path length. Methods include restarting or aggregating online learners, tracking switching experts, adapting to gradient or parameter variation, and detecting changes; bandit settings add the challenge of learning from limited feedback. These ideas are studied in online convex optimization, multi-armed and linear bandits, reinforcement learning, and control, with evaluations often comparing regret across different kinds of drift and comparator movement. A central tension is adapting quickly to consequential changes without overreacting to noise or harmless shifts, especially when the amount of change is unknown and feedback is costly.

Latest papers

46 papers16 papers in the last four weeks, up 220% on the four weeks before. 0.1% of all new 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
Gradient-Variation Regret Bounds for Unconstrained Online Learning
Apr 13, 2026Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi +1Online Convex Optimization Dynamic Regret Minimization
Università degli Studi di Milano & Politecnico di Milano
A Perturbation Approach to Unconstrained Linear Bandits
Mar 30, 2026Andrew Jacobsen, Dorian Baudry, Shinji Ito +1Adversarial Bandits Dynamic Regret Minimization
Università degli Studi di Milano · Politecnico di Milano · Inria, Univ. Grenoble Alpes, Grenoble INP, CNRS, LIG, 38000 Grenoble, France +1
Policy-Controlled Generalized Share: A General Framework with a Transformer Instantiation for Strictly Online Switching-Oracle Tracking
Mar 30, 2026Hongkai HuOnline Learning Dynamic Regret Minimization
Antai College of Economics and Management, Shanghai Jiao Tong University
Parameter-Free Dynamic Regret for Unconstrained Linear Bandits
Mar 26, 2026Alberto Rumi, Andrew Jacobsen, Nicolò Cesa-Bianchi +1Dynamic Regret Minimization Adversarial Bandits
Intesa Sanpaolo Innovation Center
The Value of Information in Resource-Constrained Pricing
Mar 26, 2026Ruicheng Ao, Jiashuo Jiang, David Simchi-LeviDynamic Pricing Decision-Making under Uncertainty
Institute for Data, Systems, and Society, Massachusetts Institute of Technology · Department of Industrial Engineering and Decision Analytics, Hong Kong University of Science and Technology · Department of Civil and Environmental Engineering and Operations Research Center, MIT
Regret Bounds for Competitive Resource Allocation with Endogenous Costs
Mar 19, 2026Rui ChaiOnline Resource Allocation Dynamic Regret Minimization
Shanghai Sanda University
A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
Mar 15, 2026Haoran Xu, Owen Shen, Peter Glynn +2Online Resource Allocation Linear Programming
Department of Management Science and Engineering, Stanford University · Operations Research Center, Massachusetts Institute of Technology
EARCP: Self-Regulating Coherence-Aware Ensemble Architecture for Sequential Decision Making -- Ensemble Auto-Regule par Coherence et Performance
Mar 15, 2026Mike AmegaEnsemble Learning Dynamic Regret Minimization
Independent Researcher, Windsor, Ontario, Canada
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
Upper-Linearizability of Online Non-Monotone DR-Submodular Maximization over Down-Closed Convex Sets
Feb 24, 2026Yiyang Lu, Haresh Jadav, Mohammad Pedramfar +2Submodular Optimization Dynamic Regret Minimization
Purdue University, West Lafayette, IN, USA · IIT Indore, MP, India · Mila - Quebec AI Institute/McGill University, Montreal, QC, Canada
Prior-Agnostic Incentive-Compatible Exploration
Feb 24, 2026Ramya Ramalingam, Osbert Bastani, Aaron RothSwap Regret Multi-Armed Bandits
Department of Computer and Information Sciences, University of Pennsylvania
Optimal training-conditional regret for online conformal prediction
Feb 18, 2026Jiadong Liang, Zhimei Ren, Yuxin ChenConformal Prediction Dynamic Regret Minimization
Department of Statistics and Data Science, the Wharton School, University of Pennsylvania
Truly Adapting to Adversarial Constraints in Constrained MABs
Feb 16, 2026Francesco Emanuele Stradi, Kalana Kalupahana, Matteo Castiglioni +2Constrained Optimization Adversarial Bandits
Politecnico di Milano
Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations
Feb 4, 2026Hang Yu, Yu-Hu Yan, Peng ZhaoOnline Convex Optimization Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China
Risk-averse learning with delayed feedback
Sep 25, 2024Siyi Wang, Zifan Wang, Karl Henrik Johansson +1Dynamic Regret Minimization Zeroth-Order Optimization
Division of Decision and Control Systems, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, 10044 Stockholm, Sweden · Chair of Information-oriented Control (ITR), Technical University of Munich, Germany

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.