# Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control

arXiv: https://arxiv.org/abs/2010.03161 · HTML: https://mlsanity.com/paper/2010.03161/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2020.

## Built on by (most cited first, 17 of 17)

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Do LLM Agents Have Regret? A Case Study in Online Learning and Games](https://mlsanity.com/paper/2403.16843/) (2024)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [On the Foundation of Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2311.09018/) (2023)
- [Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learning](https://mlsanity.com/paper/2405.16642/) (2024)
- [Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints](https://mlsanity.com/paper/2201.11965/) (2022)
- [Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, and Separation Design](https://mlsanity.com/paper/2211.10815/) (2022)
- [Tempo Adaptation in Non-stationary Reinforcement Learning](https://mlsanity.com/paper/2309.14989/) (2023)
- [Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysis](https://mlsanity.com/paper/2503.18607/) (2025)
- [Pausing Policy Learning in Non-stationary Reinforcement Learning](https://mlsanity.com/paper/2405.16053/) (2024)
- [MNL-Bandit in non-stationary environments](https://mlsanity.com/paper/2303.02504/) (2023)
- [Solve Smart, Not Often: Policy Learning for Costly MILP Re-solving](https://mlsanity.com/paper/2509.23470/) (2025)
- [Age-of-information minimization under energy harvesting and non-stationary environment](https://mlsanity.com/paper/2504.04916/) (2025)
- [Efficient Restarts in Non-Stationary Model-Free Reinforcement Learning](https://mlsanity.com/paper/2510.11933/) (2025)
- [DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees](https://mlsanity.com/paper/2604.16684/) (2026)
- [Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPs](https://mlsanity.com/paper/2606.29092/) (2026)
- [Optimal Value Inference for Reinforcement Learning](https://mlsanity.com/paper/2609.09981/) (2026)

## Abstract (arXiv)

We consider model-free reinforcement learning (RL) in non-stationary Markov decision processes. Both the reward functions and the state transition functions are allowed to vary arbitrarily over time as long as their cumulative variations do not exceed certain variation budgets. We propose Restarted Q-Learning with Upper Confidence Bounds (RestartQ-UCB), the first model-free algorithm for non-stationary RL, and show that it outperforms existing solutions in terms of dynamic regret. Specifically, RestartQ-UCB with Freedman-type bonus terms achieves a dynamic regret bound of widetildeO(S^frac13 A^frac13 Delta^frac13 H T^frac23), where S and A are the numbers of states and actions, respectively, Delta>0 is the variation budget, H is the number of time steps per episode, and T is the total number of time steps. We further present a parameter-free algorithm named Double-Restart Q-UCB that does not require prior knowledge of the variation budget. We show that our algorithms are nearly optimal by establishing an information-theoretical lower bound of Omega(S^frac13 A^frac13 Delta^frac13 H^frac23 T^frac23), the first lower bound in non-stationary RL. Numerical experiments validate the advantages of RestartQ-UCB in terms of both cumulative rewards and computational efficiency. We demonstrate the power of our results in examples of multi-agent RL and inventory control across related products.