Research map / Reinforcement learning / Policy gradient and actor-critic
Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives an FPTAS for computing near-optimal deterministic policies in tabular constrained MDPs under any time-space recursive cost criterion (expectation, almost-sure, anytime), via value-demand augmentation and approximate DP over the action space with time-space rounding.
Problem
Computing near-optimal deterministic policies for constrained RL is NP-hard for common constraints (expectation, almost sure, anytime); polynomial-time approximability was open for anytime, almost-sure, and deterministic expectation constraints.
Approach
Augment states with value demands and actions with future value demands to break cyclic dependencies, cast the problem as a covering MDP, approximate the knapsack-like Bellman update by recursive dynamic programming over states, and round value demands over both time and state space to get provable guarantees.
Key results
- Additive FPTAS with runtime O(H^7 S^5 A r_max^3 / epsilon^3) returning policies with value at least V* - epsilon or certifying infeasibility.
- Relative FPTAS for non-negative rewards with runtime O(H^7 S^5 A log(r_max/(r_min p_min))^3 / epsilon^3).
- Resolves open questions on polynomial-time approximability for anytime, almost-sure, and deterministic expectation-constrained policies.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the additive FPTAS with polynomial-bounded rewards | Deterministic CRL with TSR criteria · TSR-constrained cMDPs with polynomial-bounded r_max | additive value guarantee: V^*_M - \epsilon | Helped |
| Use the relative FPTAS with non-negative rewards | Deterministic CRL with TSR criteria · TSR-constrained cMDPs with non-negative rewards | relative value guarantee: V^*_M(1 - \epsilon) | Helped |
Surprising findings
- Chance constraints and combinations of more than one of the example constraints are provably inapproximable, so the TSR class is a boundary of tractability.
Limitations
- Worst-case polynomial bound has high degree (H^7 S^5), so not asymptotically optimal and likely impractical.
- Requires reward assumptions (polynomially bounded rewards or non-negative rewards); unbounded rewards capture knapsack.
- Cannot handle multiple simultaneous constraints or chance constraints; applies only to TSR criteria.
Experimental setup
Builds on: knapsack approximation backward induction stochastic dynamic programming FPTAS
Closest papers by meaning
- Polynomial-Time Approximability of Constrained Reinforcement Learning (ICML 2025 · similarity 0.93)
- Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning (NeurIPS 2024 · similarity 0.89)
- Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs (AAAI 2025 · similarity 0.88)
- Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity (ICML 2025 · similarity 0.88)
- Reward Penalties on Augmented States for Solving Richly Constrained RL Effectively (AAAI 2024 · similarity 0.88)
- Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.