mlsanityData to 7 Oct 2026

Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints

arXiv 2201.11965 ↗First posted 28 Jan 2022cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

We consider primal-dual-based reinforcement learning (RL) in episodic constrained Markov decision processes (CMDPs) with non-stationary objectives and constraints, which plays a central role in ensuring the safety of RL in time-varying environments. In this problem, the reward/utility functions and the state transition functions are both allowed to vary arbitrarily over time as long as their cumulative variations do not exceed certain known variation budgets. Designing safe RL algorithms in time-varying environments is particularly challenging because of the need to integrate the constraint violation reduction, safe exploration, and adaptation to the non-stationarity. To this end, we identify two alternative conditions on the time-varying constraints under which we can guarantee the safety in the long run. We also propose the underlinePeriodically underlineRestarted underlineOptimistic underlinePrimal-underlineDual underlineProximal underlinePolicy underlineOptimization (PROPD-PPO) algorithm that can coordinate with both two conditions. Furthermore, a dynamic regret bound and a constraint violation bound are established for the proposed algorithm in both the linear kernel CMDP function approximation setting and the tabular CMDP setting under two alternative conditions. This paper provides the first provably efficient algorithm for non-stationary CMDPs with safe exploration.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 33 of its 52 references that are in the map. First posted on arXiv 28 Jan 2022.

Builds on

33 of 52 references.

References · 33

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2015Trust Region Policy Optimizationcited by 2,503
  3. 2016Concrete Problems in AI Safetycited by 1,582
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  6. 2018Is Q-learning Provably Efficient?cited by 485
  7. 2019Challenges of Real-World Reinforcement Learningcited by 282
  8. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  9. 2017Deep Reinforcement Learning framework for Autonomous Drivingcited by 224
  10. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  11. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  12. 2013Non-stationary Stochastic Optimizationcited by 173
21 more
  1. 2020Exploration-Exploitation in Constrained MDPscited by 146
  2. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
  3. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  4. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  5. 2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
  6. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  7. 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 75
  8. 2020Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimismcited by 75
  9. 2019Convergent Policy Optimization for Safe Reinforcement Learningcited by 55
  10. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  11. 2013Dynamical Models and Tracking Regret in Online Convex Programmingcited by 42
  12. 2020Optimizing for the Future in Non-Stationary MDPscited by 37
  13. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  14. 2019Variational Regret Bounds for Reinforcement Learningcited by 32
  15. 2020Dynamic Regret of Policy Optimization in Non-stationary Environmentscited by 32
  16. 2020A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spacescited by 32
  17. 2020Efficient Learning in Non-Stationary Linear Markov Decision Processescited by 26
  18. 2020Nonstationary Reinforcement Learning with Linear Function Approximationcited by 23
  19. 2020Learning in Markov Decision Processes under Constraintscited by 20
  20. 2021Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPscited by 16
  21. 2020Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Controlcited by 15

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 3; 2024: 4; 2025: 1.

10 papers.

  1. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  2. 2023Constraint-Conditioned Policy Optimization for Versatile Safe Reinforcement Learningcited by 17
  3. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 15
  4. 2024Optimal Strong Regret and Violation in Constrained MDPs via Policy Optimizationcited by 11
  5. 2023A Best-of-Both-Worlds Algorithm for Constrained MDPs with Long-Term Constraintscited by 9
  6. 2023Gradient Shaping for Multi-Constraint Safe Reinforcement Learningcited by 7
  7. 2022Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environmentscited by 6
  8. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraintscited by 5
  9. 2024Pausing Policy Learning in Non-stationary Reinforcement Learningcited by 2
  10. 2025Data-Dependent Regret Bounds for Constrained MABscited by 2