mlsanityData to 14 Oct 2026

Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time

arXiv 2405.14183 ↗First posted 23 May 2024cs.LG cs.DScited by 5

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We present a novel algorithm that efficiently computes near-optimal deterministic policies for constrained reinforcement learning (CRL) problems. Our approach combines three key ideas: (1) value-demand augmentation, (2) action-space approximate dynamic programming, and (3) time-space rounding. Our algorithm constitutes a fully polynomial-time approximation scheme (FPTAS) for any time-space recursive (TSR) cost criteria. A TSR criteria requires the cost of a policy to be computable recursively over both time and (state) space, which includes classical expectation, almost sure, and anytime constraints. Our work answers three open questions spanning two long-standing lines of research: polynomial-time approximability is possible for 1) anytime-constrained policies, 2) almost-sure-constrained policies, and 3) deterministic expectation-constrained policies.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 22 of its 57 references that are in the map. First posted on arXiv 23 May 2024.

Builds on

22 of 57 references.

References · 22

  1. 2017Safe Reinforcement Learning via Shieldingcited by 449
  2. 2017Safe Model-based Reinforcement Learning with Stability Guaranteescited by 366
  3. 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 297
  4. 2019End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Taskscited by 289
  5. 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 181
  6. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 151
  7. 2022Safe Reinforcement Learning by Imagining the Near Futurecited by 67
  8. 2022Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environmentscited by 60
  9. 2023State-wise Safe Reinforcement Learning: A Surveycited by 55
  10. 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
  11. 2020Safe Reinforcement Learning via Projection on a Safe Set: How to Achieve Optimality?cited by 34
  12. 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 34
10 more
  1. 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
  2. 2018Deep Reinforcement Learning for Resource Management in Network Slicingcited by 27
  3. 2018Resource Constrained Deep Reinforcement Learningcited by 24
  4. 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 20
  5. 2021Reinforcement Learning with Almost Sure Constraintscited by 11
  6. 2020Provably Safe PAC-MDP Exploration Using Analogiescited by 9
  7. 2021Explicit Explore, Exploit, or Escape (E4): near-optimal safety-constrained reinforcement learning in polynomial timecited by 6
  8. 2023Anytime-Constrained Reinforcement Learningcited by 6
  9. 2018Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional actions and scalar statescited by 1
  10. 2022Correlated Stochastic Knapsack with a Submodular Objectivecited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 2; 2026: 1.

5 papers.

  1. 2024Anytime-Constrained Equilibria in Polynomial Timecited by 1
  2. 2025Polynomial-Time Approximability of Constrained Reinforcement Learningcited by 1
  3. 2024Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPscited by 0
  4. 2025Trustworthy and Explainable Deep Reinforcement Learning for Safe and Energy-Efficient Process Control: A Use Case in Industrial Compressed Air Systemscited by 0
  5. 2026Learning Infinite-Horizon Average-Reward CMDPs via State Augmentationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Learning Deterministic Policies with Policy Gradients in Constrained Markov Decision Processes
  2. 2023Reinforcement Learning with General Utilities: Simpler Variance Reduction and Large State-Action Space
  3. 2025Deterministic Policy Gradient for Reinforcement Learning with Continuous Time and State
  4. 2026Mathematical methods of reinforcement learning
  5. 2026Frozen Policy Iteration: Computationally Efficient RL under Linear Qπ Realizability for Deterministic Dynamics
  6. 2024Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning
  7. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
  8. 2024A General Control-Theoretic Approach for Reinforcement Learning: Theory and Algorithms