mlsanityData to 14 Oct 2026

A safe exploration approach to constrained Markov decision processes

arXiv 2312.00561 ↗First posted 1 Dec 2023cs.LG math.OCcited by 10

Not on the map. Why?

Abstract (arXiv)

We consider discounted infinite-horizon constrained Markov decision processes (CMDPs), where the goal is to find an optimal policy that maximizes the expected cumulative reward while satisfying expected cumulative constraints. Motivated by the application of CMDPs in online learning for safety-critical systems, we focus on developing a model-free and simulator-free algorithm that ensures constraint satisfaction during learning. To this end, we employ the LB-SGD algorithm proposed in citeusmanova2022log, which utilizes an interior-point approach based on the log-barrier function of the CMDP. Under the commonly assumed conditions of relaxed Fisher non-degeneracy and bounded transfer error in policy parameterization, we establish the theoretical properties of the LB-SGD algorithm. In particular, unlike existing CMDP approaches that ensure policy feasibility only upon convergence, the LB-SGD algorithm guarantees feasibility throughout the learning process and converges to the varepsilon-optimal policy with a sample complexity of tildeO(varepsilon-6). Compared to the state-of-the-art policy gradient-based algorithm, C-NPG-PDA citebai2022achieving2, the LB-SGD algorithm requires an additional O(varepsilon-2) samples to ensure policy feasibility during learning with the same Fisher non-degenerate parameterization.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 49 of its 82 references that are in the map. First posted on arXiv 1 Dec 2023.

Builds on

49 of 82 references.

References · 49

  1. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,103
  2. 2017Constrained Policy Optimizationcited by 983
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2018Reward Constrained Policy Optimizationcited by 417
  6. 2017Safe Model-based Reinforcement Learning with Stability Guaranteescited by 366
  7. 2020Responsive Safety in Reinforcement Learning by PID Lagrangian Methodscited by 316
  8. 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 297
  9. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  10. 2019End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Taskscited by 289
  11. 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 250
  12. 2017A General Safety Framework for Learning-Based Control in Uncertain Robotic Systemscited by 163
37 more
  1. 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 159
  2. 2019Lyapunov-based Safe Policy Optimization for Continuous Controlcited by 145
  3. 2021High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspacescited by 141
  4. 2016Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Roboticscited by 134
  5. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 134
  6. 2019IPO: Interior-point Policy Optimization under Constraintscited by 132
  7. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  8. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  9. 2021A general sample complexity analysis of vanilla policy gradientcited by 76
  10. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 68
  11. 2017Sub-sampled Cubic Regularization for Non-convex Optimizationcited by 63
  12. 2018Accelerated Primal-Dual Policy Optimization for Safe Reinforcement Learningcited by 62
  13. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 60
  14. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 58
  15. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
  16. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  17. 2021State Augmented Constrained Reinforcement Learning: Overcoming the Limitations of Learning with Rewardscited by 40
  18. 2019Stochastic First-order Methods for Convex and Nonconvex Functional Constrained Optimizationcited by 38
  19. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
  20. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 35
  21. 2022Model-based Safe Deep Reinforcement Learning via a Constrained Proximal Policy Optimization Algorithmcited by 29
  22. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  23. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 27
  24. 2021On the Global Optimum Convergence of Momentum-based Policy Gradientcited by 26
  25. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 23
  26. 2019Smoothing Policies and Safe Policy Gradientscited by 21
  27. 2022Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Functioncited by 20
  28. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 20
  29. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 17
  30. 2019Learning-based Model Predictive Control for Safe Exploration and Reinforcement Learningcited by 16
  31. 2023Identifiability and Generalizability in Constrained Inverse Reinforcement Learningcited by 16
  32. 2021On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systemscited by 13
  33. 2022Log Barriers for Safe Black-box Optimization with Application to Safe Reinforcement Learningcited by 11
  34. 2019Non-Cooperative Inverse Reinforcement Learningcited by 7
  35. 2019Safe non-smooth black-box optimization with application to policy searchcited by 6
  36. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  37. 2019Policy Space Identification in Configurable Environmentscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 3; 2025: 1; 2026: 6.

10 papers.

  1. 2024ActSafe: Active Exploration with Safety Constraints for Reinforcement Learningcited by 23
  2. 2024Embedding Safety into RL: A New Take on Trust Region Methodscited by 10
  3. 2026Safe Exploration via Policy Priorscited by 6
  4. 2024A learning-based approach to stochastic optimal control under reach-avoid constraintcited by 3
  5. 2025Central Path Proximal Policy Optimizationcited by 3
  6. 2026Constrained Meta Reinforcement Learning with Provable Test-Time Safetycited by 1
  7. 2026Global Optimality for Constrained Exploration via Penalty Regularizationcited by 0
  8. 2026Safety Certification is Classificationcited by 0
  9. 2026Provably Safe Sim-to-Real Transfercited by 0
  10. 2026Computationally efficient safe exploration in reinforcement learningcited by 0