# The complexity of non-stationary reinforcement learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 65 references that are in the map.
- First posted on arXiv 13 Jul 2023.

## Builds on (most cited first, 29 of 29)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Towards Continual Reinforcement Learning: A Review and Perspectives](https://mlsanity.com/paper/2012.13490/) (2020)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [A Survey of Reinforcement Learning Algorithms for Dynamically Varying Environments](https://mlsanity.com/paper/2005.10619/) (2020)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity](https://mlsanity.com/paper/1908.11071/) (2019)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Variational Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1905.05857/) (2019)
- [A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces](https://mlsanity.com/paper/2007.05078/) (2020)
- [On the Complexity of Solving Markov Decision Problems](https://mlsanity.com/paper/1302.4971/) (2013)
- [Efficient Learning in Non-Stationary Linear Markov Decision Processes](https://mlsanity.com/paper/2010.12870/) (2020)
- [Nonstationary Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2010.04244/) (2020)
- [Algorithms and Hardness for Linear Algebra on Geometric Graphs](https://mlsanity.com/paper/2011.02466/) (2020)
- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [Hardness of Approximate Nearest Neighbor Search](https://mlsanity.com/paper/1803.00904/) (2018)
- [Memory Bounds for Continual Learning](https://mlsanity.com/paper/2204.10830/) (2022)
- [Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)](https://mlsanity.com/paper/1412.0348/) (2014)
- [On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product](https://mlsanity.com/paper/1802.02325/) (2018)
- [Learning and Planning for Time-Varying MDPs Using Maximum Likelihood Estimation](https://mlsanity.com/paper/1911.12976/) (2019)
- [Quickest Change Detection Approach to Optimal Control in Markov Decision Processes with Model Changes](https://mlsanity.com/paper/1609.06757/) (2016)
- [Popular conjectures imply strong lower bounds for dynamic problems](https://mlsanity.com/paper/1402.0054/) (2014)
- [Dynamic Influence Maximization](https://mlsanity.com/paper/2110.12602/) (2021)
- [Non-stationary Reinforcement Learning under General Function Approximation](https://mlsanity.com/paper/2306.00861/) (2023)
- [A Black-box Approach for Non-stationary Multi-agent Reinforcement Learning](https://mlsanity.com/paper/2306.07465/) (2023)
- [Towards Tight Approximation Bounds for Graph Diameter and Eccentricities](https://mlsanity.com/paper/1808.08494/) (2018)

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

- [Tracking Drift: Variation-Aware Entropy Scheduling for Non-Stationary Reinforcement Learning](https://mlsanity.com/paper/2601.19624/) (2026)
- [Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approach](https://mlsanity.com/paper/2501.01291/) (2025)
- [DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Bandits](https://mlsanity.com/paper/2501.19401/) (2025)
- [Natural Policy Gradient for Average Reward Non-Stationary RL](https://mlsanity.com/paper/2504.16415/) (2025)
- [Quantum Machine Learning for Secondary Frequency Control](https://mlsanity.com/paper/2512.02065/) (2025)
- [DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees](https://mlsanity.com/paper/2604.16684/) (2026)
- [Online Change-point Detection for Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2609.05298/) (2026)

## Abstract (arXiv)

The problem of continual learning in the domain of reinforcement learning, often called non-stationary reinforcement learning, has been identified as an important challenge to the application of reinforcement learning. We prove a worst-case complexity result, which we believe captures this challenge: Modifying the probabilities or the reward of a single state-action pair in a reinforcement learning problem requires an amount of time almost as large as the number of states in order to keep the value function up to date, unless the strong exponential time hypothesis (SETH) is false; SETH is a widely accepted strengthening of the P neq NP conjecture. Recall that the number of states in current applications of reinforcement learning is typically astronomical. In contrast, we show that just textitadding a new state-action pair is considerably easier to implement.