Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911620012179456 |
|---|---|
| author | Kitamura, Toshinori Kozuno, Tadashi Kumagai, Wataru Hoshino, Kenta Hosoe, Yohei Kasaura, Kazumi Hamaya, Masashi Parmas, Paavo Matsuo, Yutaka |
| author_facet | Kitamura, Toshinori Kozuno, Tadashi Kumagai, Wataru Hoshino, Kenta Hosoe, Yohei Kasaura, Kazumi Hamaya, Masashi Parmas, Paavo Matsuo, Yutaka |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_16286 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form Kitamura, Toshinori Kozuno, Tadashi Kumagai, Wataru Hoshino, Kenta Hosoe, Yohei Kasaura, Kazumi Hamaya, Masashi Parmas, Paavo Matsuo, Yutaka Machine Learning Optimization and Control 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. |
| title | Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2408.16286 |