mlsanityData to 14 Oct 2026

Non-stationary Reinforcement Learning under General Function Approximation

arXiv 2306.00861 ↗First posted 1 Jun 2023cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

General function approximation is a powerful tool to handle large state and action spaces in a broad range of reinforcement learning (RL) scenarios. However, theoretical understanding of non-stationary MDPs with general function approximation is still limited. In this paper, we make the first such an attempt. We first propose a new complexity metric called dynamic Bellman Eluder (DBE) dimension for non-stationary MDPs, which subsumes majority of existing tractable RL problems in static MDPs as well as non-stationary MDPs. Based on the proposed complexity metric, we propose a novel confidence-set based model-free algorithm called SW-OPEA, which features a sliding window mechanism and a new confidence set design for non-stationary MDPs. We then establish an upper bound on the dynamic regret for the proposed algorithm, and show that SW-OPEA is provably efficient as long as the variation budget is not significantly large. We further demonstrate via examples of non-stationary linear and tabular MDPs that our algorithm performs better in small variation budget scenario than the existing UCB-type algorithms. To the best of our knowledge, this is the first dynamic regret analysis in non-stationary MDPs with general function approximation.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 32 of its 65 references that are in the map. First posted on arXiv 1 Jun 2023.

Builds on

32 of 65 references.

References · 32

  1. 2017Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithmcited by 734
  2. 2019A Survey of Autonomous Driving: Common Practices and Emerging Technologiescited by 379
  3. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  7. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  8. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  9. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  10. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  11. 2017Real-Time Bidding by Reinforcement Learning in Display Advertisingcited by 91
  12. 2018Learning to Optimize under Non-Stationaritycited by 85
20 more
  1. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  2. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  3. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
  4. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  5. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  6. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  7. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
  8. 2014Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewardscited by 42
  9. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 33
  10. 2022On the Complexity of Adversarial Decision Makingcited by 33
  11. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  12. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  13. 2018A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitionscited by 30
  14. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  15. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  16. 2019Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory managementcited by 22
  17. 2019√n-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rankcited by 20
  18. 2022Off-Policy Fitted Q-Evaluation with Differentiable Function Approximators: Z-Estimation and Inference Theorycited by 18
  19. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  20. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 1; 2026: 1.

6 papers.

  1. 2023The complexity of non-stationary reinforcement learningcited by 7
  2. 2024Sample Complexity Characterization for Linear Contextual MDPscited by 5
  3. 2024Predictive Control and Regret Analysis of Non-Stationary MDP with Look-ahead Informationcited by 2
  4. 2026In-Context Reinforcement Learning under Non-Stationarity: A Surveycited by 1
  5. 2023Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Gamescited by 0
  6. 2025Natural Policy Gradient for Average Reward Non-Stationary RLcited by 0