DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees

arXiv 2604.16684 ↗First posted 17 Apr 2026cs.LG stat.MLcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (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.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 39 of its 53 references that are in the map. First posted on arXiv 17 Apr 2026.

Builds on

39 of 53 references.

Closest ancestors · 2

Same direction, newest first

Other references · 37

2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
2019Behaviour Suite for Reinforcement Learningcited by 132
2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
2017Real-Time Bidding by Reinforcement Learning in Display Advertisingcited by 91
2019Weighted Linear Bandits for Non-Stationary Environmentscited by 86
2018Learning to Optimize under Non-Stationaritycited by 85
2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
2017Efficient Contextual Bandits in Non-stationary Worldscited by 62

25 more

2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
2021A Simple Approach for Non-stationary Linear Banditscited by 54
2018Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Banditcited by 50
2017A Change-Detection based Framework for Piecewise-stationary Multi-Armed Bandit Problemcited by 49
2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
2019Variational Regret Bounds for Reinforcement Learningcited by 32
2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
2018A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitionscited by 30
2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
2020Self-Concordant Analysis of Generalized Linear Bandits with Forgettingcited by 29
2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
2020Algorithms for Non-Stationary Generalized Linear Banditscited by 24
2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
2019Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory managementcited by 22
2021No-Regret Algorithms for Time-Varying Bayesian Optimizationcited by 19
2020Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Controlcited by 17
2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
2021Regret Bounds for Generalized Linear Bandits under Parameter Driftcited by 13
2023The complexity of non-stationary reinforcement learningcited by 7
2025Sequential Change Detection for Learning in Piecewise Stationary Bandit Environmentscited by 5
2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
2023Provably Efficient Algorithm for Nonstationary Low-Rank MDPscited by 2
2025Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approachcited by 1
2025Finite-Horizon Quickest Change Detection Balancing Latency with False Alarm Probabilitycited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way