# Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time

arXiv: https://arxiv.org/abs/2405.14183 · HTML: https://mlsanity.com/paper/2405.14183/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 22 of 22)

- [Safe Reinforcement Learning via Shielding](https://mlsanity.com/paper/1708.08611/) (2017)
- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [End-to-End Safe Reinforcement Learning through Barrier Functions for Safety-Critical Continuous Control Tasks](https://mlsanity.com/paper/1903.08792/) (2019)
- [A Review of Safe Reinforcement Learning: Methods, Theory and Applications](https://mlsanity.com/paper/2205.10330/) (2022)
- [Constrained Reinforcement Learning Has Zero Duality Gap](https://mlsanity.com/paper/1910.13393/) (2019)
- [Safe Reinforcement Learning by Imagining the Near Future](https://mlsanity.com/paper/2202.07789/) (2022)
- [Enforcing Hard Constraints with Soft Barriers: Safe Reinforcement Learning in Unknown Stochastic Environments](https://mlsanity.com/paper/2209.15090/) (2022)
- [State-wise Safe Reinforcement Learning: A Survey](https://mlsanity.com/paper/2302.03122/) (2023)
- [Near-Optimal Sample Complexity Bounds for Constrained MDPs](https://mlsanity.com/paper/2206.06270/) (2022)
- [Safe Reinforcement Learning via Projection on a Safe Set: How to Achieve Optimality?](https://mlsanity.com/paper/2004.00915/) (2020)
- [Constrained episodic reinforcement learning in concave-convex and knapsack settings](https://mlsanity.com/paper/2006.05051/) (2020)
- [Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPs](https://mlsanity.com/paper/2008.00311/) (2020)
- [Deep Reinforcement Learning for Resource Management in Network Slicing](https://mlsanity.com/paper/1805.06591/) (2018)
- [Resource Constrained Deep Reinforcement Learning](https://mlsanity.com/paper/1812.00600/) (2018)
- [Achieving Zero Constraint Violation for Constrained Reinforcement Learning via Conservative Natural Policy Gradient Primal-Dual Algorithm](https://mlsanity.com/paper/2206.05850/) (2022)
- [Reinforcement Learning with Almost Sure Constraints](https://mlsanity.com/paper/2112.05198/) (2021)
- [Provably Safe PAC-MDP Exploration Using Analogies](https://mlsanity.com/paper/2007.03574/) (2020)
- [Explicit Explore, Exploit, or Escape (E4): near-optimal safety-constrained reinforcement learning in polynomial time](https://mlsanity.com/paper/2111.07395/) (2021)
- [Anytime-Constrained Reinforcement Learning](https://mlsanity.com/paper/2311.05511/) (2023)
- [Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional actions and scalar states](https://mlsanity.com/paper/1811.11680/) (2018)
- [Correlated Stochastic Knapsack with a Submodular Objective](https://mlsanity.com/paper/2207.01551/) (2022)

## Built on by (most cited first, 5 of 5)

- [Anytime-Constrained Equilibria in Polynomial Time](https://mlsanity.com/paper/2410.23637/) (2024)
- [Polynomial-Time Approximability of Constrained Reinforcement Learning](https://mlsanity.com/paper/2502.07764/) (2025)
- [Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs](https://mlsanity.com/paper/2408.10015/) (2024)
- [Trustworthy and Explainable Deep Reinforcement Learning for Safe and Energy-Efficient Process Control: A Use Case in Industrial Compressed Air Systems](https://mlsanity.com/paper/2512.18317/) (2025)
- [Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation](https://mlsanity.com/paper/2609.39093/) (2026)

## 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.