mlsanityData to 7 Oct 2026

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

arXiv 2408.16286 ↗First posted 29 Aug 2024cs.LG math.OCcited by 10

Not on the map. Why?

Abstract (arXiv)

Designing a safe policy for uncertain environments is crucial in real-world control systems. However, this challenge remains inadequately addressed within the Markov decision process (MDP) framework. This paper presents the first algorithm guaranteed to identify a near-optimal policy in a robust constrained MDP (RCMDP), where an optimal policy minimizes cumulative cost while satisfying constraints in the worst-case scenario across a set of environments. We first prove that the conventional policy gradient approach to the Lagrangian max-min formulation can become trapped in suboptimal solutions. This occurs when its inner minimization encounters a sum of conflicting gradients from the objective and constraint functions. To address this, we leverage the epigraph form of the RCMDP problem, which resolves the conflict by selecting a single gradient from either the objective or the constraints. Building on the epigraph form, we propose a bisection search algorithm with a policy gradient subroutine and prove that it identifies an varepsilon-optimal policy in an RCMDP with tildeO(varepsilon-4) robust policy evaluations.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 51 of its 86 references that are in the map. First posted on arXiv 29 Aug 2024.

Builds on

51 of 86 references.

References · 51

  1. 2021Convex optimizationcited by 2,479
  2. 2017Constrained Policy Optimizationcited by 928
  3. 2018Reward Constrained Policy Optimizationcited by 397
  4. 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
  5. 2019Batch Policy Learning under Constraintscited by 242
  6. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
  7. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  8. 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
  9. 2020Exploration-Exploitation in Constrained MDPscited by 146
  10. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
  11. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
  12. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
38 more
  1. 2021Reward is enough for convex MDPscited by 82
  2. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  3. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  4. 2019Safe Policies for Reinforcement Learning via Primal-Dual Methodscited by 75
  5. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 67
  6. 2019Reinforcement Learning with Convex Constraintscited by 57
  7. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 49
  8. 2020Constrained Upper Confidence Reinforcement Learningcited by 46
  9. 2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 46
  10. 2021A Primal-Dual Approach to Constrained Markov Decision Processescited by 42
  11. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  12. 2021DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learningcited by 34
  13. 2021A Dual Approach to Constrained Markov Decision Processes with Entropy Regularizationcited by 33
  14. 2020Learning with Safety Constraints: Sample Complexity of Reinforcement Learning for Constrained MDPscited by 32
  15. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
  16. 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 29
  17. 2023Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPscited by 27
  18. 2023Solving Stabilize-Avoid Optimal Control via Epigraph Form and Deep Reinforcement Learningcited by 24
  19. 2020Robust Constrained-MDPs: Soft-Constrained Robust Policy Optimization under Model Uncertaintycited by 23
  20. 2024Truly No-Regret Learning in Constrained MDPscited by 23
  21. 2020Scalable First-Order Methods for Robust MDPscited by 22
  22. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 21
  23. 2022Efficient Policy Iteration for Robust Markov Decision Processes via Regularizationcited by 19
  24. 2023ReLOAD: Reinforcement Learning with Optimistic Ascent-Descent for Last-Iterate Convergence in Constrained MDPscited by 19
  25. 2021Faster Algorithm and Sharper Analysis for Constrained Markov Decision Processcited by 18
  26. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  27. 2020Robust Constrained Reinforcement Learning for Continuous Control with Model Misspecificationcited by 16
  28. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
  29. 2022Robust Constrained Reinforcement Learningcited by 14
  30. 2018Distributionally Robust Optimization for Sequential Decision Makingcited by 11
  31. 2023Robust Markov Decision Processes without Model Estimationcited by 11
  32. 2022On the convex formulations of robust Markov decision processescited by 8
  33. 2018Robust Nonparametric Regression under Huber's ε-contamination Modelcited by 6
  34. 2024Constrained Reinforcement Learning Under Model Mismatchcited by 6
  35. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  36. 2021Robust Entropy-regularized Markov Decision Processescited by 4
  37. 2024A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processescited by 4
  38. 2024Methods of Nonconvex Optimizationcited by 3

50 most cited of 51 All 51 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 6; 2026: 4.

10 papers.

  1. 2025SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfercited by 8
  2. 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
  3. 2026Safe Exploration via Policy Priorscited by 6
  4. 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
  5. 2025A Comprehensive Survey on Physical Risk Control in the Era of Foundation Model-enabled Roboticscited by 2
  6. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  7. 2025Provably Efficient Sample Complexity for Robust CMDPcited by 1
  8. 2026Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guaranteescited by 0
  9. 2026Robust Peak-cost Constrained Reinforcement Learningcited by 0
  10. 2026Distinguish or Homogenize: Last-Chance Policy Identification and Risk-Budgeted Recovery under Irreversible Resource Depletioncited by 0