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 $\varepsilon$-optimal policy in an RCMDP with $\tilde{\mathcal{O}}(\varepsilon^{-4})$ robust policy evaluations.
| Comments: | This manuscript contains a technical error; the main result does not hold (see also arXiv:2604.21177 for a formal invalidation) |
| Subjects: | Machine Learning (cs.LG); Optimization and Control (math.OC) |
| Cite as: | arXiv:2408.16286 [cs.LG] |
| (or arXiv:2408.16286v5 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2408.16286 arXiv-issued DOI via DataCite |
From: Toshinori Kitamura [view email]
[v1]
Thu, 29 Aug 2024 06:37:16 UTC (331 KB)
[v2]
Mon, 2 Sep 2024 10:56:20 UTC (296 KB)
[v3]
Mon, 10 Feb 2025 04:45:21 UTC (630 KB)
[v4]
Sun, 6 Apr 2025 00:39:54 UTC (381 KB)
[v5]
Fri, 24 Apr 2026 03:11:36 UTC (395 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。