Research map / Learning theory and algorithms / Combinatorial and search optimization
Polynomial-Time Approximability of Constrained Reinforcement Learning
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 a polynomial-time (0,ε)-additive bicriteria approximation for tabular constrained MDPs with shortly recursive cost criteria (expectation, chance, almost-sure, anytime), via state-budget augmentation and dynamic rounding, extended to continuous states with (ε,ε) guarantees.
Problem
Finding optimal constrained policies in MDPs under general constraints (chance, almost-sure, expectation, anytime, and mixed types) is NP-hard; prior polynomial-time approximations covered only subsets of these settings.
Approach
Recast a history-dependent cost constraint as a per-step action constraint by augmenting states with artificial budgets and actions with future budgets, solve the resulting reduced MDP with a dynamic program over rounded partial costs, and round budgets to a polynomial-size grid to get bicriteria guarantees.
Key results
- Polynomial-time (0,ε)-additive bicriteria algorithm for tabular SR-criterion CMDPs with runtime O(H^{6m+1} S^{4m+2} A ||c_max - c_min||^{3m} / ε^{3m}).
- Extension to continuous-state CMDPs gives polynomial-time (ε,ε)-bicriteria for expectation, almost-sure and anytime-almost-sure constraints.
- On a knapsack-as-CMDP experiment, the function approximation method was fastest, the bicriteria method next, and the FPTAS slowest; the FPTAS always respected the budget.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply the proposed polynomial-time bicriteria algorithm to tabular SR-criterion CMDPs | Tabular CMDPs · Tabular SR-criterion CMDPs | reward gap: (0, ε) | Helped |
| apply the proposed algorithm after discretizing the state space | Continuous-state CMDPs · Continuous-state SR-criterion CMDPs | reward and constraint approximation: (ε, ε) | Helped |
| use function approximation instead of the bicriteria algorithm | Knapsack example · Knapsack example | running time | Helped |
| use the bicriteria algorithm instead of the FPTAS | Knapsack example · Knapsack example | running time | Helped |
| use the function approximation method rather than the bicriteria or FPTAS | Knapsack example · Knapsack example | constraint violation | Hurt |
| use the bicriteria algorithm rather than the FPTAS | Knapsack example · Knapsack example | constraint violation | Hurt |
| use function approximation, the bicriteria, or the FPTAS | Knapsack example · Knapsack example | value | No clear effect |
Surprising findings
- Function approximation approach had the worst constraint violation in the knapsack experiment, though still modest.
Limitations
- Guarantees are bicriteria (constraint violated by up to ε), not exact feasibility.
- Runtime is polynomial only under polynomially bounded costs and for constant number of constraints m; exponent grows with m.
- Continuous-state result requires Lipschitz assumptions and polynomial-size description.
Experimental setup
Benchmarks: knapsack instances (OpenAI gym environment)
Metrics: value weight/constraint violation running time
Baselines: textbook knapsack FPTAS
Builds on: anytime constrained MDP state augmentation knapsack problem FPTAS for constrained MDPs
Closest papers by meaning
- Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time (NeurIPS 2024 · similarity 0.93)
- Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation (NeurIPS 2025 · similarity 0.89)
- Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.89)
- Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability (NeurIPS 2025 · similarity 0.89)
- Achieving $\tilde{O}(1/\epsilon)$ Sample Complexity for Constrained Markov Decision Process (NeurIPS 2024 · similarity 0.88)
- Confident Natural Policy Gradient for Local Planning in $q_\pi$-realizable Constrained MDPs (NeurIPS 2024 · 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.