Research map / Bandits and online learning / RL theory and MDPs

DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees

NeurIPS 2026 · Bandits and online learning › RL theory and MDPs · approach: Non-stationary and structured MDPs · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes DARLING, a prior-free detection-restart wrapper for piecewise-stationary episodic RL that uses forced probing episodes and GLR-based mean-shift tests on reward and transition streams, with minimax lower bounds for tabular and linear PS-MDPs.

Problem

Model-free RL in non-stationary finite-horizon episodic MDPs with abrupt (piecewise-stationary) changes at unknown times, without prior knowledge of the number or timing of changes; existing prior-free methods (e.g., MASTER) have flawed analysis and poor empirical performance.

Approach

Separate change detection from learning by inserting forced uniform-random probing episodes whose samples only feed per-(s,a,h) reward and transition mean-shift detectors (GLR), restarting the base stationary learner upon detection; extend to linear MDPs by probing a finite linearly-independent set and monitoring expected features of next states.

Key results

• In tabular MDPs DARLING improves the best known dynamic regret to Õ(sqrt(SAH^3 N_T T)), matching the new Ω(sqrt(SAH^3 N_T T)) lower bound (under separability and reachability assumptions).
• In linear MDPs DARLING attains Õ(d sqrt(H^3 N_T T)), matching the Ω(d sqrt(H^3 N_T T)) lower bound when reachability parameters are known.
• Across 10 PS and drifting benchmarks, DARLING achieves the highest cumulative reward versus MASTER and prior-based baselines, with about 0.83 ms/episode (tabular) and 1.67 ms/episode (linear) runtime.

Surprising findings

• The paper reports an error in MASTER's regret analysis (Lemma 17 conditioning) that it believes cannot be easily fixed, invalidating its upper bound.
• MASTER would need at least 1.442e19 episodes in tabular MDPs before its detection could possibly trigger.

Limitations

• Theory relies on change-point separation and reachability assumptions that are violated in most experiments.
• Cannot be applied to infinite action spaces due to finite memory requirements.
• Analysis restricted to finite-horizon episodic MDPs; infinite-horizon not covered.

Experimental setup

Datasets: Bidirectional Diabolical Combination Lock DeepSea FourRoom NRoom Forked RiverSwim Chain Lock Simplex-based linear MDP GARNET Anchor-feature MDP Block-structured low-rank linear MDP

Benchmarks: NS Bidirectional Diabolical Combination Lock NS DeepSea NS FourRoom NS NRoom NS Forked RiverSwim NS Chain Lock NS Simplex-based linear MDP NS GARNET NS Anchor-feature MDP NS Block-structured low-rank linear MDP

Metrics: cumulative reward dynamic regret runtime per episode

Baselines: MASTER Restart-Q-UCB Double-Restart Q-UCB OPT-WLSVI LSVI-UCB-Restart ADA-LSVI-UCB-Restart

Builds on: MASTER UCB-MQ LSVI-UCB++ Restart-Q-UCB GLR change detection

Closest papers by meaning

• Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs (ICML 2021 · similarity 0.93)
• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (ICML 2020 · similarity 0.91)
• Non-stationary Risk-Sensitive Reinforcement Learning: Near-Optimal Dynamic Regret, Adaptive Detection, and Separation Design (AAAI 2023 · similarity 0.91)
• Optimal Regret Bounds via Low-Rank Structured Variation in Non-Stationary Reinforcement Learning (NeurIPS 2025 · similarity 0.91)
• Horizon-Free Regret for Linear Markov Decision Processes (ICLR 2024 · similarity 0.89)
• MetaCURL: Non-stationary Concave Utility Reinforcement Learning (NeurIPS 2024 · similarity 0.89)