DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees
For RL practitioners dealing with non-stationary environments, DARLING provides a theoretically grounded and empirically superior method without requiring prior knowledge of changes.
DARLING is a modular wrapper for model-free RL in piecewise-stationary MDPs that improves dynamic regret bounds in both tabular and linear settings, achieving the first nearly optimal algorithm with minimax lower bounds, and outperforms state-of-the-art methods in experiments.
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 the reward and transition dynamics can change an arbitrary number of times. We propose Detection Augmented Reinforcement Learning (DARLING), a modular wrapper for PS-RL that applies to both tabular and linear MDPs, without knowledge of the changes. Under certain change-point separation and reachability conditions, DARLING improves the best available dynamic regret bounds in both settings and yields strong empirical performance. We further establish the first minimax lower bounds for PS-RL in tabular and linear MDPs, showing that DARLING is the first nearly optimal algorithm. Experiments on standard benchmarks demonstrate that DARLING consistently surpasses the state-of-the-art methods across diverse non-stationary scenarios.