Research map / Reinforcement learning / MDPs and planning
Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees
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.
Proposes RNPG, a robust natural policy gradient method for robust constrained MDPs that minimizes a max of scaled objective and constraint violations, avoiding binary search and achieving O(eps^-2) iteration complexity with feasibility.
Problem
Learning a policy that maximizes robust reward while satisfying robust constraints under model mismatch between a simulator (nominal model) and the real environment, where strong duality fails and binary search over epigraph parameters is costly with slow O(eps^-4) iteration complexity.
Approach
Reformulates the RCMDP as minimizing max{J_c0/lambda, max_n (J_cn - b_n + xi)}, so the update focuses on constraint violation when infeasible and on reward otherwise; uses KL-regularized natural policy gradient with a robust policy evaluator, removing binary search over the objective threshold.
Key results
- RNPG achieves a feasible policy on Constrained Riverswim where EPIRC-PGS does not, while attaining higher reward on Garnet.
- Wall-clock time for RNPG is about 2-5x lower than EPIRC-PGS across gamma values (e.g., CRS 48.6s vs 190.5s at gamma=0.9 in the table).
- Theory gives O(eps^-2) iteration complexity with feasibility under strict feasibility assumption, improving on O(eps^-4) of EPIRC-PGS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RNPG instead of EPIRC-PGS | RCMDP policy optimization · CRS | wall-clock time: at least 4x faster for γ=0.9; 6x faster for γ=0.995 | Helped |
| Use RNPG instead of EPIRC-PGS | RCMDP policy optimization · Garnet | wall-clock time: 3x speedup for γ=0.9; at least 5x speedup for γ=0.995 | Helped |
| Use RNPG instead of EPIRC-PGS | RCMDP policy optimization · CRS | feasibility | Helped |
| Replace KL regularization with ℓ2 regularization (RPPG) (ablation) | RNPG policy updates · Garnet | reward | Hurt |
| Replace KL regularization with ℓ2 regularization (RPPG) (ablation) | RNPG policy updates · CRS | constraint violations | Mixed |
| Increase λ | RNPG · CRS | value function | Hurt |
| Increase λ | RNPG · CRS | cumulative cost | Helped |
Surprising findings
- RPPG with l2 regularization also outperforms EPIRC-PGS in speed and reward, indicating binary search removal is the main computational gain.
Limitations
- Requires strict feasibility assumption and knowledge of the feasibility parameter xi for the O(eps^-2) guarantee; without it the rate degrades to O(eps^-4).
- Theory assumes (s,a)-rectangular KL-type uncertainty set and a support-condition assumption (beta) on the nominal model.
- Function approximation (RCAC) lacks iteration complexity guarantees.
Experimental setup
Datasets: Garnet Constrained Riverswim
Benchmarks: Garnet(15,20) Constrained Riverswim Modified Frozenlake CRS Garbage collector Cartpole
Metrics: expected reward constraint violation wall-clock time
Baselines: EPIRC-PGS RPPG robust CRPO
Builds on: EPIRC-PGS CRPO unconstrained robust natural policy gradient KL-divergence robust MDP evaluation
Closest papers by meaning
- Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form (ICLR 2025 · similarity 0.91)
- Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.90)
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.90)
- Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.90)
- Time-Constrained Robust MDPs (NeurIPS 2024 · similarity 0.90)
- Confident Natural Policy Gradient for Local Planning in $q_\pi$-realizable Constrained MDPs (NeurIPS 2024 · similarity 0.90)
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.