mlsanityData to 14 Oct 2026

Provably Efficient Safe Exploration via Primal-Dual Policy Optimization

arXiv 2003.00534 ↗First posted 1 Mar 2020cs.LG math.OC stat.MLcited by 134

Not on the map. Why?

Cited by 41 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

We study the Safe Reinforcement Learning (SRL) problem using the Constrained Markov Decision Process (CMDP) formulation in which an agent aims to maximize the expected total reward subject to a safety constraint on the expected total value of a utility function. We focus on an episodic setting with the function approximation where the Markov transition kernels have a linear structure but do not impose any additional assumptions on the sampling model. Designing SRL algorithms with provable computational and statistical efficiency is particularly challenging under this setting because of the need to incorporate both the safety constraint and the function approximation into the fundamental exploitation/exploration tradeoff. To this end, we present an underlineOptimistic underlinePrimal-underlineDual Proximal Policy underlineOPtimization (OPDOP) algorithm where the value function is estimated by combining the least-squares policy evaluation and an additional bonus term for safe exploration. We prove that the proposed algorithm achieves an tildeO(d H2.5√T) regret and an tildeO(d H2.5√T) constraint violation, where d is the dimension of the feature mapping, H is the horizon of each episode, and T is the total number of steps. These bounds hold when the reward/utility functions are fixed but the feedback after each episode is bandit. Our bounds depend on the capacity of the state-action space only through the dimension of the feature mapping and thus our results hold even when the number of states goes to infinity. To the best of our knowledge, we provide the first provably efficient online policy optimization algorithm for CMDP with safe exploration in the function approximation setting.

Key facts. Cited by 134 papers in the map (data through 14 Oct 2026). First posted on arXiv 1 Mar 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 23; 2022: 26; 2023: 32; 2024: 23; 2025: 13; 2026: 17.

134 papers.

Sort:

By area:

  1. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 181
  2. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  3. 2023Confronting Reward Model Overoptimization with Constrained RLHFcited by 96
  4. 2021Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergencecited by 84
  5. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  6. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
  7. 2022Penalized Proximal Policy Optimization for Safe Reinforcement Learningcited by 68
  8. 2022Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environmentscited by 60
  9. 2021Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Primal-Dual Approachcited by 50
  10. 2021Safe Reinforcement Learning Using Advantage-Based Interventioncited by 47
  11. 2024A Survey of Constraint Formulations in Safe Reinforcement Learningcited by 44
  12. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
38 more
  1. 2022Trustworthy Reinforcement Learning Against Intrinsic Vulnerabilities: Robustness, Safety, and Generalizabilitycited by 36
  2. 2021Safe Reinforcement Learning with Linear Function Approximationcited by 35
  3. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 35
  4. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 34
  5. 2022Provably Efficient Model-Free Constrained RL with Linear Function Approximationcited by 31
  6. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 30
  7. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  8. 2024Stepwise Alignment for Constrained Language Model Policy Optimizationcited by 30
  9. 2022Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraintscited by 29
  10. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 28
  11. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 27
  12. 2023Long-Term Fairness with Unknown Dynamicscited by 27
  13. 2022Safe Reinforcement Learning Using Black-Box Reachability Analysiscited by 26
  14. 2021Policy Optimization for Constrained MDPs with Provable Fast Global Convergencecited by 23
  15. 2022On Kernelized Multi-Armed Bandits with Constraintscited by 23
  16. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 22
  17. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  18. 2023Provably Efficient Model-Free Algorithms for Non-stationary CMDPscited by 21
  19. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 19
  20. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 19
  21. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  22. 2021Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processescited by 17
  23. 2022Safe Reinforcement Learning of Dynamic High-Dimensional Robotic Tasks: Navigation, Manipulation, Interactioncited by 17
  24. 2023A Near-Optimal Algorithm for Safe Reinforcement Learning Under Instantaneous Hard Constraintscited by 17
  25. 2022Robust Constrained Reinforcement Learningcited by 15
  26. 2023Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilitiescited by 15
  27. 2024Safe Reinforcement Learning on the Constraint Manifold: Theory and Applicationscited by 15
  28. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
  29. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  30. 2023Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learningcited by 14
  31. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 12
  32. 2022Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficientcited by 12
  33. 2024A CMDP-within-online framework for Meta-Safe Reinforcement Learningcited by 12
  34. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 11
  35. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterizationcited by 11
  36. 2021Safe Policy Optimization with Local Generalized Linear Function Approximationscited by 10
  37. 2022Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraintscited by 10
  38. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 10

50 most cited of 134 All 134 (JSON)