mlsanityData to 14 Oct 2026

Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs

arXiv 2110.08984 ↗First posted 18 Oct 2021cs.LG stat.MLcited by 16

Not on the map. Why?

Abstract (arXiv)

We study episodic reinforcement learning (RL) in non-stationary linear kernel Markov decision processes (MDPs). In this setting, both the reward function and the transition kernel are linear with respect to the given feature maps and are allowed to vary over time, as long as their respective parameter variations do not exceed certain variation budgets. We propose the underlineperiodically underlinerestarted underlineoptimistic underlinepolicy underlineoptimization algorithm (PROPO), which is an optimistic policy optimization algorithm with linear function approximation. PROPO features two mechanisms: sliding-window-based policy evaluation and periodic-restart-based policy improvement, which are tailored for policy optimization in a non-stationary environment. In addition, only utilizing the technique of sliding window, we propose a value-iteration algorithm. We establish dynamic upper bounds for the proposed methods and a minimax lower bound which shows the (near-) optimality of the proposed methods. To our best knowledge, PROPO is the first provably efficient policy optimization algorithm that handles non-stationarity.

Key facts. Cited by 16 papers in the map (data through 14 Oct 2026). Builds on 47 of its 81 references that are in the map. First posted on arXiv 18 Oct 2021.

Builds on

47 of 81 references.

References · 47

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2019Solving Rubik's Cube with a Robot Handcited by 734
  4. 2018Learning Dexterous In-Hand Manipulationcited by 687
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  6. 2018Is Q-learning Provably Efficient?cited by 487
  7. 2017Robust Adversarial Reinforcement Learningcited by 451
  8. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 353
  9. 2017Adversarial Attacks on Neural Network Policiescited by 320
  10. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  11. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 264
  12. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
35 more
  1. 2017Deep Reinforcement Learning framework for Autonomous Drivingcited by 225
  2. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  3. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  4. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  5. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  6. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 176
  7. 2013Non-stationary Stochastic Optimizationcited by 175
  8. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  9. 2017Robust Deep Reinforcement Learning with Adversarial Attackscited by 154
  10. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  11. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 118
  12. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
  13. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  14. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  15. 2015Online Optimization : Competing with Dynamic Comparatorscited by 99
  16. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  17. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 92
  18. 2019Weighted Linear Bandits for Non-Stationary Environmentscited by 86
  19. 2018Learning to Optimize under Non-Stationaritycited by 85
  20. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  21. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  22. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 76
  23. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  24. 2021A Simple Approach for Non-stationary Linear Banditscited by 54
  25. 2019Hedging the Drift: Learning to Optimize under Non-Stationaritycited by 46
  26. 2014Optimal Exploration-Exploitation in a Multi-Armed-Bandit Problem with Non-stationary Rewardscited by 42
  27. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 40
  28. 2020Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimensioncited by 37
  29. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 33
  30. 2019Variational Regret Bounds for Reinforcement Learningcited by 32
  31. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  32. 2018A Sliding-Window Algorithm for Markov Decision Processes with Arbitrarily Changing Rewards and Transitionscited by 30
  33. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  34. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  35. 2019On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Costcited by 12

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 1; 2022: 4; 2023: 7; 2024: 2; 2025: 1; 2026: 1.

16 papers.

Sort:

By area:

  1. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  2. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  3. 2021Nearly Optimal Policy Optimization with Stable at Any Time Guaranteecited by 13
  4. 2022Testing Stationarity and Change Point Detection in Reinforcement Learningcited by 12
  5. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  6. 2023Non-stationary Reinforcement Learning under General Function Approximationcited by 6
  7. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 5
  8. 2024Sample Complexity Characterization for Linear Contextual MDPscited by 5
  9. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  10. 2026Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPscited by 5
  11. 2022Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic Regret, Adaptive Detection, and Separation Designcited by 4
  12. 2022Doubly Inhomogeneous Reinforcement Learningcited by 3
4 more
  1. 2025Reinforcement Learning in Switching Non-Stationary Markov Decision Processes: Algorithms and Convergence Analysiscited by 3
  2. 2023Provably Efficient Algorithm for Nonstationary Low-Rank MDPscited by 2
  3. 2023Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexitycited by 2
  4. 2023Revisiting Weighted Strategy for Non-stationary Parametric Banditscited by 0