Research map / Reinforcement learning / MDPs and planning

Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form

ICLR 2025 · Reinforcement learning › MDPs and planning · approach: Robust MDP policy gradient · 0 citations (OpenAlex)

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 EpiRC-PGS, an epigraph-form bisection search with a projected policy gradient subroutine for finding near-optimal policies in tabular robust constrained MDPs; the paper's own main result is later flagged by an erratum as incorrect.

Problem

Identifying a near-optimal policy in a tabular robust constrained MDP (RCMDP), where cost is minimized and constraints must hold under worst-case transition kernels, given that Lagrangian policy gradient can get stuck at suboptimal stationary points.

Approach

Reformulate the RCMDP in epigraph form, so the inner problem is a max over a single worst-case objective-or-constraint cost (avoiding summed conflicting gradients), then solve it with projected policy gradient inside a bisection search over the objective threshold b0.

Key results

• Theoretical claim of O~(eps^-4) robust policy evaluations for eps-optimal policy identification; the paper's erratum states this main result is incorrect because the global optimality proof is false in general and RCMDPs are NP-hard even under (s,a)-rectangularity.
• Experiments with N=5 constraints over 10 seeds show the proposed method reaches feasible low-cost policies while LF and averaged LF fail feasibility in some settings.
• Erratum: the claimed global optimality of stationary points of the maximum violation function does not hold in general.

Measured effects reported in the paper

Surprising findings

• The paper's central claim of global optimality of stationary points was later found to be false, as the min-max interchange used in the proof does not hold in general.
• Even under (s,a)-rectangularity, finding an eps-optimal policy in RCMDPs is NP-hard, and general RMDPs may admit multiple local minima.

Limitations

• Double-loop structure is inefficient when the inner problem is costly; single-loop design left open
• Coverage assumption mu > 0 on initial distribution is required
• Iteration complexity may not be tight relative to RMDP natural policy gradient results

Experimental setup

Datasets: randomly generated tabular RCMDP environments (Dirichlet transitions, GARNET-like)

Benchmarks: random tabular RCMDP with finite uncertainty set KL-rectangular RCMDP CMDP with LP reference

Metrics: objective cost return constraint satisfaction feasibility

Baselines: Lagrangian formulation (LF) with policy gradient averaged Lagrangian policies (LF-pol-avg) averaged occupancy measures (LF-occ-avg) LP method for CMDP optimal value

Builds on: Lagrangian policy gradient for CMDPs robust MDP with rectangular uncertainty sets epigraph form of constrained optimization KL uncertainty set robust DP

Closest papers by meaning

• Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees (NeurIPS 2025 · similarity 0.91)
• A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.90)
• Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.89)
• Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.88)
• Near-Optimal Sample Complexity for Online Constrained MDPs (NeurIPS 2025 · similarity 0.88)
• Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs (AAAI 2025 · similarity 0.88)