# Dynamic Regret of Policy Optimization in Non-stationary Environments

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

## Key facts

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

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

- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learning](https://mlsanity.com/paper/2110.04471/) (2021)
- [A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes](https://mlsanity.com/paper/2305.08841/) (2023)
- [Performative Reinforcement Learning](https://mlsanity.com/paper/2207.00046/) (2022)
- [Provably Efficient Model-Free Algorithms for Non-stationary CMDPs](https://mlsanity.com/paper/2303.05733/) (2023)
- [Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs](https://mlsanity.com/paper/2110.08984/) (2021)
- [Nearly Optimal Policy Optimization with Stable at Any Time Guarantee](https://mlsanity.com/paper/2112.10935/) (2021)
- [Policy Optimization for Stochastic Shortest Path](https://mlsanity.com/paper/2202.03334/) (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)
- [Tracking Most Significant Shifts in Nonparametric Contextual Bandits](https://mlsanity.com/paper/2307.05341/) (2023)
- [Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation](https://mlsanity.com/paper/2405.17061/) (2024)
- [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)
- [Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/2403.04568/) (2024)
- [MetaCURL: Non-stationary Concave Utility Reinforcement Learning](https://mlsanity.com/paper/2405.19807/) (2024)
- [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)
- [Provably Efficient Algorithm for Nonstationary Low-Rank MDPs](https://mlsanity.com/paper/2308.05471/) (2023)
- [Pausing Policy Learning in Non-stationary Reinforcement Learning](https://mlsanity.com/paper/2405.16053/) (2024)
- [Achieve Performatively Optimal Policy for Performative Reinforcement Learning](https://mlsanity.com/paper/2510.04430/) (2025)
- [Online Reinforcement Learning in Periodic MDP](https://mlsanity.com/paper/2303.09629/) (2023)
- [Optimistic Regret Bounds for Online Learning in Adversarial Markov Decision Processes](https://mlsanity.com/paper/2405.02188/) (2024)
- [Provably Efficient Action-Manipulation Attack Against Continuous Reinforcement Learning](https://mlsanity.com/paper/2411.13116/) (2024)
- [Revisiting Clustering of Neural Bandits: Selective Reinitialization for Mitigating Loss of Plasticity](https://mlsanity.com/paper/2506.12389/) (2025)
- [Plasticity-Enhanced Multi-Agent Mixture of Experts for Dynamic Objective Adaptation in UAVs-Assisted Emergency Communication Networks](https://mlsanity.com/paper/2604.09028/) (2026)
- [Online Reinforcement Learning for Periodic MDP](https://mlsanity.com/paper/2207.12045/) (2022)
- [Dynamic Pricing and Learning with Long-term Reference Effects](https://mlsanity.com/paper/2402.12562/) (2024)
- [Age-of-information minimization under energy harvesting and non-stationary environment](https://mlsanity.com/paper/2504.04916/) (2025)

## Abstract (arXiv)

We consider reinforcement learning (RL) in episodic MDPs with adversarial full-information reward feedback and unknown fixed transition kernels. We propose two model-free policy optimization algorithms, POWER and POWER++, and establish guarantees for their dynamic regret. Compared with the classical notion of static regret, dynamic regret is a stronger notion as it explicitly accounts for the non-stationarity of environments. The dynamic regret attained by the proposed algorithms interpolates between different regimes of non-stationarity, and moreover satisfies a notion of adaptive (near-)optimality, in the sense that it matches the (near-)optimal static regret under slow-changing environments. The dynamic regret bound features two components, one arising from exploration, which deals with the uncertainty of transition kernels, and the other arising from adaptation, which deals with non-stationary environments. Specifically, we show that POWER++ improves over POWER on the second component of the dynamic regret by actively adapting to non-stationarity through prediction. To the best of our knowledge, our work is the first dynamic regret analysis of model-free RL algorithms in non-stationary environments.