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.

Strongly Adaptive Online Learning with Time-Varying Movement Costs
Oct 23, 2026Andrew Jacobsen, Emmanuel Esposito, Hao Qiu +1Online Convex Optimization Dynamic Regret Minimization
Università degli Studi di Milano · Politecnico di Milano · National University of Singapore +1
The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits
Oct 21, 2026Sharan Sahu, Martin T. WellsNon-Stationary Bandits Dynamic Regret Minimization
Department of Statistics and Data Science, Cornell University
Minimax-Optimal Predictive Flow Matching under Distribution Drift
Oct 20, 2026Aadithya Srikanth, Vaneet AggarwalFlow Matching Dynamic Regret Minimization
Purdue University, West Lafayette
A Simple and Unified Method for Gradient-Variation Regret
Oct 19, 2026Hang Yu, Peng ZhaoOnline Learning Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China
Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs
Oct 19, 2026Xiaojin ZhangMulti-Armed Bandits Non-Stationary Bandits
School of Computer Science and Technology, Huazhong University of Science and Technology, China
Detection Augmented Learning In Non-Stationary Bandit Environments
Oct 19, 2026Argyrios Gerogiannis, Yu-Han Huang, Subhonmesh Bose +1Non-Stationary Bandits Dynamic Regret Minimization
ECE department and the Coordinated Science Laboratory, Grainger College of Engineering, University of Illinois at Urbana-Champaign
An Information-Geometric Framework for OCS-Reconfigurable Interconnect Topology in Large-Scale AI Clusters
Oct 18, 2026Shintaro YoshizawaCommunication Topology Optimization Dynamic Regret Minimization
Nagoya Mathematical and Information Science Research
Revisiting Smoothed Online Learning: Competitive Ratio, Dynamic Regret with Switching Cost, and Best of Both Worlds
Oct 17, 2026Lijun Zhang, Linzhe He, Wei Jiang +1Competitive Analysis Online Convex Optimization
State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China · School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China +1
Dimension-Optimal Dynamic Regret in Exp-Concave Online Learning
Oct 14, 2026Yanyi Li, Wendao Wu, Haihan Zhang +6Dynamic Regret Minimization Online Convex Optimization
Peking University
Data Reuse in Non-Stationary Learning
Oct 7, 2026Tomer Gafni, Garud Iyengar, Assaf ZeeviStatistical Learning Theory Dynamic Regret Minimization
Columbia University
Logarithmic Regret via Passive Change Detection in Piecewise-Stationary Self-Tuning Regulation
Oct 7, 2026A. Ch. Madhusudanarao, Rahul SinghAdaptive Control Dynamic Regret Minimization
Department of Computer Science and Automation Indian Institute of Science, Bengaluru, India · Laboratoire de Recherche de l’EPITA, Paris, France
Dynamic Minimax Regret Optimization for Robust LLM Post-Training
Oct 5, 2026Chengbo Zang, Haoyu Dong, Mehmet Kerem Turkcan +3Group Distributionally Robust Optimization Dynamic Regret Minimization
Department of Electrical Engineering, Columbia University · Department of Computer Science & Engineering, University of California, Santa Cruz · Department of Civil Engineering, Columbia University
When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity
Oct 2, 2026Mayand Gulati, Kerong Wang, WeiChen AuThompson Sampling Non-Stationary Bandits
UC Santa Barbara · Purdue University
Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise
Sep 30, 2026Vaneet AggarwalOnline Convex Optimization Dynamic Regret Minimization
Purdue University, West Lafayette, IN, USA
Universal Dynamic Portfolios
Sep 28, 2026Yu-Jie Zhang, Yu-Xiang Wang, Peng Zhao +1Online Convex Optimization Dynamic Regret Minimization
University of Washington · University of California, San Diego · State Key Laboratory for Novel Software Technology, Nanjing University School of Artificial Intelligence, Nanjing University
On the Relation Between Interval Regret and Dynamic Regret
Sep 28, 2026Yi-Han Wang, Peng Zhao, Zhi-Hua ZhouOnline Convex Optimization Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China
ASTRA: ADMM-Accelerated Topology Reconfiguration for Dynamic Satellite Constellations
Sep 27, 2026João Norberto, Ricardo Ferreira, Cláudia SoaresDynamic Regret Minimization Wireless Communications
Department of Computer Science NOVA School of Science and Technology Caparica, Portugal
Dynamic Regret in Online Convex Optimization with Indicator Switching Costs
Sep 24, 2026Naram Mhaisen, George IosifidisOnline Convex Optimization Dynamic Regret Minimization
Faculty of Electrical Engineering, Mathematics and Computer Science TU Delft, Netherlands
From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences
Sep 17, 2026Yibo Wang, Wenhao Yang, Sifan Yang +3Online Convex Optimization Dynamic Regret Minimization
State Key Laboratory for Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · School of Software Technology, Zhejiang University
Adapting to Decision-Relevant Non-Stationarity in Decentralized Heterogeneous Bandits
Sep 15, 2026Zhaojun PengMulti-Armed Bandits Dynamic Regret Minimization
Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
Sep 11, 2026Mengxiao ZhangMulti-Armed Bandits Adversarial Bandits
University of Iowa
Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration
Aug 19, 2026Matthias Mandl, Hanne KekkonenGaussian Process Bandits Bayesian Optimization
Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft
Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
Aug 17, 2026Mengxiao ZhangMulti-Armed Bandits Adversarial Bandits
University of Iowa
Online Learning of Scale Parameters in Score-Driven Filters
Aug 10, 2026Fabrizio Lillo, Giulia Livieri, Gianluca PalmariDynamic Regret Minimization Online Mirror Descent
Scuola Normale Superiore, Piazza dei Cavalieri 7, Pisa, Italy · Department of Statistics, London School of Economics and Political Science, Columbia House, 69 Aldwych, London, United Kingdom
Parameter-Free Dynamic Regret under Heavy-Tailed Noise
Jul 29, 2026Vaneet AggarwalOnline Convex Optimization Dynamic Regret Minimization
Purdue University
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
Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPs
Jun 27, 2026Kai HidajatNon-Stationary RL Markov Decision Processes
Komori Research
Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees
Jun 8, 2026Deqi Zheng, Xiaoyang Xu, Yuhong YangMulti-Armed Bandits Dynamic Regret Minimization
Qiuzhen College, Tsinghua University · Yau Mathematical Sciences Center, Tsinghua University
Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
May 25, 2026Joongkyu Lee, Min-hwan OhMulti-Armed Bandits Dynamic Regret Minimization
Seoul National University
Bandit Convex Optimization with Gradient Prediction Adaptivity
May 21, 2026Shuche Wang, Adarsh Barik, Vincent Y. F. TanOnline Convex Optimization Dynamic Regret Minimization
Department of Mathematics, National University of Singapore, Singapore · Department of Computer Science and Engineering, Indian Institute of Technology Delhi, India · Department of Electrical and Computer Engineering, National University of Singapore, Singapore

Oct 23, 2026J/K move · Enter open · S save

Strongly Adaptive Online Learning with Time-Varying Movement Costs

Andrew Jacobsen, Emmanuel Esposito, Hao Qiu, Mengxiao Zhang

Università degli Studi di Milano · Politecnico di Milano · National University of Singapore+1

Online Convex Optimization Dynamic Regret Minimization

Open paper AskPDF arXiv

We study strongly adaptive regret for Online Convex Optimization (OCO) with time-varying movement costs, a setting that evaluates a learner's performance over arbitrary sub-intervals. This framework captures complex sequential decision-making problems where both the environment and the cost of switching decisions fluctuate over time. We propose a novel algorithm which, for any interval

[a,b] \subseteq [T]

, achieves a data-dependent regret bound of

\widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\|g_t\|^2+λ_t\|g_t\|)} \right)

, where

D

is the diameter of the decision domain,

P_{[a,b]}

is the path length of the comparator sequence over

[a,b]

g_t

is the gradient of the loss, and

λ_t

is the movement-cost coefficient at round

t

. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of this development, we further establish the first strongly-adaptive guarantees under delayed feedback. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.