mlsanityData to 14 Oct 2026

Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible?

arXiv 2410.13772 ↗First posted 17 Oct 2024cs.LG cs.AI stat.MLcited by 5

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

Abstract (arXiv)

We study the problem of Non-Stationary Reinforcement Learning (NS-RL) without prior knowledge about the system's non-stationarity. A state-of-the-art, black-box algorithm, known as MASTER, is considered, with a focus on identifying the conditions under which it can achieve its stated goals. Specifically, we prove that MASTER's non-stationarity detection mechanism is not triggered for practical choices of horizon, leading to performance akin to a random restarting algorithm. Moreover, we show that the regret bound for MASTER, while being order optimal, stays above the worst-case linear regret until unreasonably large values of the horizon. To validate these observations, MASTER is tested for the special case of piecewise stationary multi-armed bandits, along with methods that employ random restarting, and others that use quickest change detection to restart. A simple, order optimal random restarting algorithm, that has prior knowledge of the non-stationarity is proposed as a baseline. The behavior of the MASTER algorithm is validated in simulations, and it is shown that methods employing quickest change detection are more robust and consistently outperform MASTER and other random restarting approaches.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. First posted on arXiv 17 Oct 2024.

Builds on

0 of 0 references.

No references here yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 2.

5 papers.

  1. 2025Non-Stationary Lipschitz Banditscited by 3
  2. 2025Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approachcited by 1
  3. 2025DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Banditscited by 0
  4. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0
  5. 2026Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descentcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Natural Policy Gradient for Average Reward Non-Stationary RL
  2. 2025Efficient Restarts in Non-Stationary Model-Free Reinforcement Learning
  3. 2024Non-Stationary Learning of Neural Networks with Automatic Soft Parameter Reset
  4. 2025Optimal Dynamic Regret by Transformers for Non-Stationary Reinforcement Learning
  5. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learning
  6. 2024Pausing Policy Learning in Non-stationary Reinforcement Learning
  7. 2026Space-sampled Value Decay: Forgetting Mechanisms for Non-stationary Reinforcement Learning
  8. 2022Testing Stationarity and Change Point Detection in Reinforcement Learning