mlsanityData to 14 Oct 2026

The complexity of non-stationary reinforcement learning

arXiv 2307.06877 ↗First posted 13 Jul 2023cs.LG cs.AI cs.DScited by 7

Not on the map. Why?

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.

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

29 of 65 references.

References · 29

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2018Is Q-learning Provably Efficient?cited by 487
  3. 2020Towards Continual Reinforcement Learning: A Review and Perspectivescited by 274
  4. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  5. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  6. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  7. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
  8. 2020A Survey of Reinforcement Learning Algorithms for Dynamically Varying Environmentscited by 62
  9. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  10. 2019Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexitycited by 42
  11. 2018Hashing-Based-Estimators for Kernel Density in High Dimensionscited by 33
  12. 2019Variational Regret Bounds for Reinforcement Learningcited by 32
17 more
  1. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  2. 2013On the Complexity of Solving Markov Decision Problemscited by 31
  3. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  4. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  5. 2020Algorithms and Hardness for Linear Algebra on Geometric Graphscited by 22
  6. 2013Improved and Generalized Upper Bounds on the Complexity of Policy Iterationcited by 21
  7. 2018Hardness of Approximate Nearest Neighbor Searchcited by 19
  8. 2022Memory Bounds for Continual Learningcited by 19
  9. 2014Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)cited by 18
  10. 2018On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Productcited by 12
  11. 2019Learning and Planning for Time-Varying MDPs Using Maximum Likelihood Estimationcited by 10
  12. 2016Quickest Change Detection Approach to Optimal Control in Markov Decision Processes with Model Changescited by 8
  13. 2014Popular conjectures imply strong lower bounds for dynamic problemscited by 6
  14. 2021Dynamic Influence Maximizationcited by 6
  15. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 6
  16. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  17. 2018Towards Tight Approximation Bounds for Graph Diameter and Eccentricitiescited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 3.

7 papers.

  1. 2026Tracking Drift: Variation-Aware Entropy Scheduling for Non-Stationary Reinforcement Learningcited by 4
  2. 2025Detection Augmented Bandit Procedures for Piecewise Stationary MABs: A Modular Approachcited by 1
  3. 2025DAL: A Practical Prior-Free Black-Box Framework for Piecewise Stationary Banditscited by 0
  4. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0
  5. 2025Quantum Machine Learning for Secondary Frequency Controlcited by 0
  6. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0
  7. 2026Online Change-point Detection for Cooperative Multi-Agent Reinforcement Learningcited by 0