# Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism

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

## Key facts

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

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

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Confronting Reward Model Overoptimization with Constrained RLHF](https://mlsanity.com/paper/2310.04373/) (2023)
- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges](https://mlsanity.com/paper/2102.01168/) (2021)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2110.04471/) (2021)
- [Performative Reinforcement Learning](https://mlsanity.com/paper/2207.00046/) (2022)
- [Non-Stationary Bandit Learning via Predictive Sampling](https://mlsanity.com/paper/2205.01970/) (2022)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learning](https://mlsanity.com/paper/2405.16642/) (2024)
- [Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs](https://mlsanity.com/paper/2110.08984/) (2021)
- [Structure in Deep Reinforcement Learning: A Survey and Open Problems](https://mlsanity.com/paper/2306.16021/) (2023)
- [Dynamics-Adaptive Continual Reinforcement Learning via Progressive Contextualization](https://mlsanity.com/paper/2209.00347/) (2022)
- [Performative Reinforcement Learning in Gradually Shifting Environments](https://mlsanity.com/paper/2402.09838/) (2024)
- [RAPid-Learn: A Framework for Learning to Recover for Handling Novelties in Open-World Environments](https://mlsanity.com/paper/2206.12493/) (2022)
- [Dynamic Regret of Online Markov Decision Processes](https://mlsanity.com/paper/2208.12483/) (2022)
- [Testing Stationarity and Change Point Detection in Reinforcement Learning](https://mlsanity.com/paper/2203.01707/) (2022)
- [Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints](https://mlsanity.com/paper/2201.11965/) (2022)
- [One After Another: Learning Incremental Skills for a Changing World](https://mlsanity.com/paper/2203.11176/) (2022)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Continual Auxiliary Task Learning](https://mlsanity.com/paper/2202.11133/) (2022)
- [Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learning](https://mlsanity.com/paper/2207.05742/) (2022)
- [Decision-Making Under Uncertainty: Beyond Probabilities](https://mlsanity.com/paper/2303.05848/) (2023)
- [Jointly Training and Pruning CNNs via Learnable Agent Guidance and Alignment](https://mlsanity.com/paper/2403.19490/) (2024)
- [Performative Reinforcement Learning with Linear Markov Decision Process](https://mlsanity.com/paper/2411.05234/) (2024)
- [The complexity of non-stationary reinforcement learning](https://mlsanity.com/paper/2307.06877/) (2023)
- [Improving Intrinsic Exploration by Creating Stationary Objectives](https://mlsanity.com/paper/2310.18144/) (2023)
- [Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments](https://mlsanity.com/paper/2205.13044/) (2022)
- [Non-stationary Reinforcement Learning under General Function Approximation](https://mlsanity.com/paper/2306.00861/) (2023)

## Abstract (arXiv)

We consider un-discounted reinforcement learning (RL) in Markov decision processes (MDPs) under drifting non-stationarity, i.e., both the reward and state transition distributions are allowed to evolve over time, as long as their respective total variations, quantified by suitable metrics, do not exceed certain variation budgets. We first develop the Sliding Window Upper-Confidence bound for Reinforcement Learning with Confidence Widening (SWUCRL2-CW) algorithm, and establish its dynamic regret bound when the variation budgets are known. In addition, we propose the Bandit-over-Reinforcement Learning (BORL) algorithm to adaptively tune the SWUCRL2-CW algorithm to achieve the same dynamic regret bound, but in a parameter-free manner, i.e., without knowing the variation budgets. Notably, learning non-stationary MDPs via the conventional optimistic exploration technique presents a unique challenge absent in existing (non-stationary) bandit learning settings. We overcome the challenge by a novel confidence widening technique that incorporates additional optimism.