# Non-Stationary Markov Decision Processes, a Worst-Case Approach using Model-Based Reinforcement Learning, Extended version

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2019.

## Built on by (most cited first, 30 of 36)

- [Confronting Reward Model Overoptimization with Constrained RLHF](https://mlsanity.com/paper/2310.04373/) (2023)
- [Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges](https://mlsanity.com/paper/2102.01168/) (2021)
- [Trustworthy Reinforcement Learning Against Intrinsic Vulnerabilities: Robustness, Safety, and Generalizability](https://mlsanity.com/paper/2209.08025/) (2022)
- [Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning](https://mlsanity.com/paper/2006.16785/) (2020)
- [Continual Learning In Environments With Polynomial Mixing Times](https://mlsanity.com/paper/2112.07066/) (2021)
- [Testing Stationarity and Change Point Detection in Reinforcement Learning](https://mlsanity.com/paper/2203.01707/) (2022)
- [Dynamic Dialogue Policy for Continual Reinforcement Learning](https://mlsanity.com/paper/2204.05928/) (2022)
- [Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learning](https://mlsanity.com/paper/2207.05742/) (2022)
- [Group Distributionally Robust Reinforcement Learning with Hierarchical Latent Variables](https://mlsanity.com/paper/2210.12262/) (2022)
- [Improving Intrinsic Exploration by Creating Stationary Objectives](https://mlsanity.com/paper/2310.18144/) (2023)
- [Explicit Explore, Exploit, or Escape (E4): near-optimal safety-constrained reinforcement learning in polynomial time](https://mlsanity.com/paper/2111.07395/) (2021)
- [Lifetime policy reuse and the importance of task capacity](https://mlsanity.com/paper/2106.01741/) (2021)
- [Act as You Learn: Adaptive Decision-Making in Non-Stationary Markov Decision Processes](https://mlsanity.com/paper/2401.01841/) (2024)
- [Decision Making in Non-Stationary Environments with Policy-Augmented Search](https://mlsanity.com/paper/2401.03197/) (2024)
- [Doubly Inhomogeneous Reinforcement Learning](https://mlsanity.com/paper/2211.03983/) (2022)
- [SoK: Adversarial Machine Learning Attacks and Defences in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2301.04299/) (2023)
- [Reinforcement learning-based estimation for partial differential equations](https://mlsanity.com/paper/2302.01189/) (2023)
- [Coarse-Grained Smoothness for RL in Metric Spaces](https://mlsanity.com/paper/2110.12276/) (2021)
- [Efficient Action Robust Reinforcement Learning with Probabilistic Policy Execution Uncertainty](https://mlsanity.com/paper/2307.07666/) (2023)
- [Time-Constrained Robust MDPs](https://mlsanity.com/paper/2406.08395/) (2024)
- [Solving robust MDPs as a sequence of static RL problems](https://mlsanity.com/paper/2410.06212/) (2024)
- [Safe Continual Reinforcement Learning Methods for Nonstationary Environments. Towards a Survey of the State of the Art](https://mlsanity.com/paper/2601.05152/) (2026)
- [Reinforcement Learning under External Influence: Guarantees, Algorithms, and Sample Complexity](https://mlsanity.com/paper/2305.16056/) (2023)
- [Tolerance of Reinforcement Learning Controllers against Deviations in Cyber Physical Systems](https://mlsanity.com/paper/2406.17066/) (2024)
- [Non-Stationary Online Resource Allocation: Learning from a Single Sample](https://mlsanity.com/paper/2602.18114/) (2026)
- [BAPR: Bayesian amnesic piecewise-robust reinforcement learning for non-stationary continuous control](https://mlsanity.com/paper/2605.16170/) (2026)
- [Non-Parametric Stochastic Policy Gradient with Strategic Retreat for Non-Stationary Environment](https://mlsanity.com/paper/2203.14905/) (2022)
- [Set-based value operators for non-stationary Markovian environments](https://mlsanity.com/paper/2207.07271/) (2022)
- [Prioritizing emergency evacuations under compounding levels of uncertainty](https://mlsanity.com/paper/2210.08975/) (2022)
- [Model-Free Learning and Optimal Policy Design in Multi-Agent MDPs Under Probabilistic Agent Dropout](https://mlsanity.com/paper/2304.12458/) (2023)

## Abstract (arXiv)

This work tackles the problem of robust zero-shot planning in non-stationary stochastic environments. We study Markov Decision Processes (MDPs) evolving over time and consider Model-Based Reinforcement Learning algorithms in this setting. We make two hypotheses: 1) the environment evolves continuously with a bounded evolution rate; 2) a current model is known at each decision epoch but not its evolution. Our contribution can be presented in four points. 1) we define a specific class of MDPs that we call Non-Stationary MDPs (NSMDPs). We introduce the notion of regular evolution by making an hypothesis of Lipschitz-Continuity on the transition and reward functions w.r.t. time; 2) we consider a planning agent using the current model of the environment but unaware of its future evolution. This leads us to consider a worst-case method where the environment is seen as an adversarial agent; 3) following this approach, we propose the Risk-Averse Tree-Search (RATS) algorithm, a zero-shot Model-Based method similar to Minimax search; 4) we illustrate the benefits brought by RATS empirically and compare its performance with reference Model-Based algorithms.