mlsanityData to 14 Oct 2026

Efficient Restarts in Non-Stationary Model-Free Reinforcement Learning

arXiv 2510.11933 ↗First posted 13 Oct 2025cs.LGcited by 0

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

Abstract (arXiv)

In this work, we propose three efficient restart paradigms for model-free non-stationary reinforcement learning (RL). We identify two core issues with the restart design of Mao et al. (2022)'s RestartQ-UCB algorithm: (1) complete forgetting, where all the information learned about an environment is lost after a restart, and (2) scheduled restarts, in which restarts occur only at predefined timings, regardless of the incompatibility of the policy with the current environment dynamics. We introduce three approaches, which we call partial, adaptive, and selective restarts to modify the algorithms RestartQ-UCB and RANDOMIZEDQ (Wang et al., 2025). We find near-optimal empirical performance in multiple different environments, decreasing dynamic regret by up to 91% relative to RestartQ-UCB.

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 13 of its 19 references that are in the map. First posted on arXiv 13 Oct 2025.

Builds on

13 of 19 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025Provably Efficient and Agile Randomized Q-Learning30 Jun

Other references · 12

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 734
  3. 2018Is Q-learning Provably Efficient?cited by 487
  4. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  5. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 92
  6. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
  7. 2019Variational Regret Bounds for Reinforcement Learningcited by 32
  8. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  9. 2020Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Controlcited by 17
  10. 2022Optimizing Crop Management with Reinforcement Learning and Imitation Learningcited by 13
  11. 2024Comparative Analysis of Multi-Agent Reinforcement Learning Policies for Crop Planning Decision Supportcited by 3
  12. 2023An Online Optimization-Based Decision Support Tool for Small Farmers in India: Learning in Non-stationary Environmentscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Is Prior-Free Black-Box Non-Stationary Reinforcement Learning Feasible?
  2. 2024Pausing Policy Learning in Non-stationary Reinforcement Learning
  3. 2026ReversedQ: Opportunities for Faster Q-Learning in Episodic Online Reinforcement Learning
  4. 2025Natural Policy Gradient for Average Reward Non-Stationary RL
  5. 2024Reset-free Reinforcement Learning with World Models
  6. 2026Safe Continual Reinforcement Learning in Non-stationary Environments
  7. 2026Space-sampled Value Decay: Forgetting Mechanisms for Non-stationary Reinforcement Learning
  8. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees