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

arXiv:2408.16286v5 Announce Type: replace Abstract: 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 arepsilon-optimal policy in an RCMDP with ilde{O}(arepsilon^{-4}) robust policy evaluations.

Related

• Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guarantees
• On the Fundamental Limitations of Dual Static CVaR Decompositions in Markov Decision Processes
• Near-Optimal Regret for the Safe Learning-based Control of the Constrained Linear Quadratic Regulator
• DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertainty

Source: arXiv cs.LG | 2026-04-27