mlsanityData to 7 Oct 2026

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

arXiv 2006.14389 ↗First posted 24 Jun 2020cs.LG stat.MLcited by 75

Not on the map. Why?

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.

Key facts. Cited by 75 papers in the map (data through 7 Oct 2026). First posted on arXiv 24 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 17; 2023: 18; 2024: 12; 2025: 9; 2026: 10.

75 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  2. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  3. 2023Confronting Reward Model Overoptimization with Constrained RLHFcited by 96
  4. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimismcited by 78
  5. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  6. 2021Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challengescited by 40
  7. 2021Provably Efficient Black-Box Action Poisoning Attacks Against Reinforcement Learningcited by 29
  8. 2022Performative Reinforcement Learningcited by 25
  9. 2022Non-Stationary Bandit Learning via Predictive Samplingcited by 21
  10. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  11. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  12. 2023Structure in Deep Reinforcement Learning: A Survey and Open Problemscited by 16
38 more
  1. 2024Fast TRAC: A Parameter-Free Optimizer for Lifelong Reinforcement Learningcited by 16
  2. 2022RAPid-Learn: A Framework for Learning to Recover for Handling Novelties in Open-World Environmentscited by 13
  3. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  4. 2022Dynamics-Adaptive Continual Reinforcement Learning via Progressive Contextualizationcited by 13
  5. 2024Performative Reinforcement Learning in Gradually Shifting Environmentscited by 13
  6. 2022Testing Stationarity and Change Point Detection in Reinforcement Learningcited by 12
  7. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  8. 2022One After Another: Learning Incremental Skills for a Changing Worldcited by 10
  9. 2023Tracking Most Significant Shifts in Nonparametric Contextual Banditscited by 10
  10. 2022Continual Auxiliary Task Learningcited by 9
  11. 2022Reactive Exploration to Cope with Non-Stationarity in Lifelong Reinforcement Learningcited by 9
  12. 2024Jointly Training and Pruning CNNs via Learnable Agent Guidance and Alignmentcited by 9
  13. 2023Decision-Making Under Uncertainty: Beyond Probabilitiescited by 8
  14. 2024Performative Reinforcement Learning with Linear Markov Decision Processcited by 8
  15. 2023The complexity of non-stationary reinforcement learningcited by 7
  16. 2023Improving Intrinsic Exploration by Creating Stationary Objectivescited by 7
  17. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  18. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 5
  19. 2023AURO: Reinforcement Learning for Adaptive User Retention Optimization in Recommender Systemscited by 5
  20. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  21. 2021Lifetime policy reuse and the importance of task capacitycited by 4
  22. 2022Rotting Infinitely Many-armed Banditscited by 4
  23. 2022Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, and Separation Designcited by 4
  24. 2024MetaCURL: Non-stationary Concave Utility Reinforcement Learningcited by 4
  25. 2024Exploring Loss Landscapes through the Lens of Spin Glass Theorycited by 4
  26. 2026Tracking Drift: Variation-Aware Entropy Scheduling for Non-Stationary Reinforcement Learningcited by 4
  27. 2022Doubly Inhomogeneous Reinforcement Learningcited by 3
  28. 2023Action Pick-up in Dynamic Action Space Reinforcement Learningcited by 3
  29. 2023A Black-box Approach for Non-stationary Multi-agent Reinforcement Learningcited by 3
  30. 2023Tempo Adaptation in Non-stationary Reinforcement Learningcited by 3
  31. 2023Restarted Bayesian Online Change-point Detection for Non-Stationary Markov Decision Processescited by 2
  32. 2023Provably Efficient Algorithm for Nonstationary Low-Rank MDPscited by 2
  33. 2024Variance-Dependent Regret Bounds for Non-stationary Linear Banditscited by 2
  34. 2024Pausing Policy Learning in Non-stationary Reinforcement Learningcited by 2
  35. 2025Achieve Performatively Optimal Policy for Performative Reinforcement Learningcited by 2
  36. 2023Reinforcement Learning under External Influence: Guarantees, Algorithms, and Sample Complexitycited by 1
  37. 2024Constrained Online Two-stage Stochastic Optimization: Algorithm with (and without) Predictionscited by 1
  38. 2025A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Gamescited by 1

50 most cited of 75 All 75 (JSON)