mlsanityData to 7 Oct 2026

Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPs

arXiv 2106.02684 ↗First posted 4 Jun 2021cs.LGcited by 78

Not on the map. Why?

Abstract (arXiv)

We address the issue of safety in reinforcement learning. We pose the problem in an episodic framework of a constrained Markov decision process. Existing results have shown that it is possible to achieve a reward regret of tildeO(√K) while allowing an tildeO(√K) constraint violation in K episodes. A critical question that arises is whether it is possible to keep the constraint violation even smaller. We show that when a strictly safe policy is known, then one can confine the system to zero constraint violation with arbitrarily high probability while keeping the reward regret of order tildeO(√K). The algorithm which does so employs the principle of optimistic pessimism in the face of uncertainty to achieve safe exploration. When no strictly safe policy is known, though one is known to exist, then it is possible to restrict the system to bounded constraint violation with arbitrarily high probability. This is shown to be realized by a primal-dual algorithm with an optimistic primal estimate and a pessimistic dual update.

Key facts. Cited by 78 papers in the map (data through 7 Oct 2026). Builds on 25 of its 34 references that are in the map. First posted on arXiv 4 Jun 2021.

Builds on

25 of 34 references.

References · 25

  1. 2015Trust Region Policy Optimizationcited by 2,503
  2. 2016Concrete Problems in AI Safetycited by 1,582
  3. 2017Constrained Policy Optimizationcited by 928
  4. 2018Reward Constrained Policy Optimizationcited by 397
  5. 2017Safe Model-based Reinforcement Learning with Stability Guaranteescited by 347
  6. 2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 302
  7. 2019Challenges of Real-World Reinforcement Learningcited by 282
  8. 2019End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Taskscited by 256
  9. 2020Projection-Based Constrained Policy Optimizationcited by 195
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  11. 2020Exploration-Exploitation in Constrained MDPscited by 146
  12. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 131
13 more
  1. 2018Learning-based Model Predictive Control for Safe Explorationcited by 116
  2. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  3. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  4. 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 75
  5. 2020Stochastic Bandits with Linear Constraintscited by 68
  6. 2018Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learningcited by 61
  7. 2016Conservative Banditscited by 58
  8. 2016Conservative Contextual Linear Banditscited by 56
  9. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  10. 2020Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Losscited by 46
  11. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 38
  12. 2019Safe Linear Thompson Sampling with Side Informationcited by 37
  13. 2020Improved Algorithms for Conservative Exploration in Banditscited by 16

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 12; 2023: 20; 2024: 15; 2025: 14; 2026: 11.

78 papers.

Sort:

By area:

  1. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 169
  2. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 46
  3. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
  4. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  5. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 29
  6. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  7. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 26
  8. 2023Long-Term Fairness with Unknown Dynamicscited by 25
  9. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  10. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  11. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 22
  12. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
38 more
  1. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 19
  2. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
  3. 2022Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learningcited by 15
  4. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 15
  5. 2023Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilitiescited by 15
  6. 2024Learning Adversarial MDPs with Stochastic Hard Constraintscited by 15
  7. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 13
  8. 2024A CMDP-within-online framework for Meta-Safe Reinforcement Learningcited by 12
  9. 2025Probabilistic Shielding for Safe Reinforcement Learningcited by 12
  10. 2021Reinforcement Learning with Almost Sure Constraintscited by 11
  11. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 11
  12. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  13. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  14. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 10
  15. 2023A safe exploration approach to constrained Markov decision processescited by 10
  16. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  17. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  18. 2023A Primal-Dual-Critic Algorithm for Offline Constrained Reinforcement Learningcited by 9
  19. 2023Directional Optimism for Safe Linear Banditscited by 8
  20. 2023Provably Learning Nash Policies in Constrained Markov Potential Gamescited by 7
  21. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  22. 2022A Near-Optimal Primal-Dual Method for Off-Policy Learning in CMDPcited by 5
  23. 2023Online Nonstochastic Control with Adversarial and Static Constraintscited by 5
  24. 2023Cancellation-Free Regret Bounds for Lagrangian Approaches in Constrained Markov Decision Processescited by 5
  25. 2023Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Explorationcited by 5
  26. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  27. 2024Learning Constrained Markov Decision Processes With Non-stationary Rewards and Constraintscited by 5
  28. 2025An Optimistic Algorithm for online CMDPS with Anytime Adversarial Constraintscited by 5
  29. 2025No-Regret Learning Under Adversarial Resource Constraints: A Spending Plan Is All You Need!cited by 5
  30. 2023Near-optimal Conservative Exploration in Reinforcement Learning under Episode-wise Constraintscited by 4
  31. 2024Avoiding Catastrophe in Online Learning by Asking for Helpcited by 4
  32. 2024Confident Natural Policy Gradient for Local Planning in qπ-realizable Constrained MDPscited by 4
  33. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximationcited by 4
  34. 2025Tail-Risk-Safe Monte Carlo Tree Search under PAC-Level Guaranteescited by 4
  35. 2022Constrained Reinforcement Learning via Dissipative Saddle Flow Dynamicscited by 3
  36. 2024Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budgetcited by 2
  37. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Samplingcited by 2
  38. 2025Session-Level Dynamic Ad Load Optimization using Offline Robust Reinforcement Learningcited by 2

50 most cited of 78 All 78 (JSON)