Polynomial-Time Approximability of Constrained Reinforcement Learning
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
We study the computational complexity of approximating general constrained Markov decision processes. Our primary contribution is the design of a polynomial time (0,ε)-additive bicriteria approximation algorithm for finding optimal constrained policies across a broad class of recursively computable constraints, including almost-sure, chance, expectation, and their anytime variants. Matching lower bounds imply our approximation guarantees are optimal so long as P neq NP. The generality of our approach results in answers to several long-standing open complexity questions in the constrained reinforcement learning literature. Specifically, we are the first to prove polynomial-time approximability for the following settings: policies under chance constraints, deterministic policies under multiple expectation constraints, policies under non-homogeneous constraints (i.e., constraints of different types), and policies under constraints for continuous-state processes.
Key facts. Cited by 1 paper 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 20 of its 39 references that are in the map. First posted on arXiv 11 Feb 2025.
Builds on
20 of 39 references.
Closest ancestors · 1
Same direction, newest first
Other references · 19
- 2017Safe Reinforcement Learning via Shieldingcited by 449
- 2017Safe Model-based Reinforcement Learning with Stability Guaranteescited by 366
- 2018A Lyapunov-based Approach to Safe Reinforcement Learningcited by 297
- 2019End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Taskscited by 289
- 2022A Review of Safe Reinforcement Learning: Methods, Theory and Applicationscited by 181
- 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 151
- 2022Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environmentscited by 60
- 2023State-wise Safe Reinforcement Learning: A Surveycited by 55
- 2022Near-Optimal Sample Complexity Bounds for Constrained MDPscited by 37
- 2020Safe Reinforcement Learning via Projection on a Safe Set: How to Achieve Optimality?cited by 34
- 2020Constrained episodic reinforcement learning in concave-convex and knapsack settingscited by 34
- 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
7 more
- 2018Deep Reinforcement Learning for Resource Management in Network Slicingcited by 27
- 2018Resource Constrained Deep Reinforcement Learningcited by 24
- 2022Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithmcited by 20
- 2021Reinforcement Learning with Almost Sure Constraintscited by 11
- 2020Provably Safe PAC-MDP Exploration Using Analogiescited by 9
- 2021Explicit Explore, Exploit, or Escape (E4): near-optimal safety-constrained reinforcement learning in polynomial timecited by 6
- 2023Anytime-Constrained Reinforcement Learningcited by 6
Built on by
Citing papers per year: 2026: 1.
1 paper.
Similar, not cited
Close in wording, no citation either way
- 2026Mathematical methods of reinforcement learning
- 2025Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
- 2025Computational Hardness of Reinforcement Learning with Partial qπ-Realizability
- 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation
- 2024Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Time
- 2025Provably Efficient Sample Complexity for Robust CMDP
- 2026Near-Optimal Sample Complexity for Online Constrained MDPs
- 2026Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality