Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929714155749376 |
|---|---|
| author | Kumar, Navdeep Gupta, Adarsh Elfatihi, Maxence Mohamed Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie |
| author_facet | Kumar, Navdeep Gupta, Adarsh Elfatihi, Maxence Mohamed Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie |
| contents | We study robust Markov decision processes (RMDPs) with non-rectangular uncertainty sets, which capture interdependencies across states unlike traditional rectangular models. While non-rectangular robust policy evaluation is generally NP-hard, even in approximation, we identify a powerful class of $L_p$-bounded uncertainty sets that avoid these complexity barriers due to their structural simplicity. We further show that this class can be decomposed into infinitely many \texttt{sa}-rectangular $L_p$-bounded sets and leverage its structural properties to derive a novel dual formulation for $L_p$ RMDPs. This formulation provides key insights into the adversary's strategy and enables the development of the first robust policy evaluation algorithms for non-rectangular RMDPs. Empirical results demonstrate that our approach significantly outperforms brute-force methods, establishing a promising foundation for future investigation into non-rectangular robust MDPs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_09432 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes Kumar, Navdeep Gupta, Adarsh Elfatihi, Maxence Mohamed Ramponi, Giorgia Levy, Kfir Yehuda Mannor, Shie Artificial Intelligence Machine Learning We study robust Markov decision processes (RMDPs) with non-rectangular uncertainty sets, which capture interdependencies across states unlike traditional rectangular models. While non-rectangular robust policy evaluation is generally NP-hard, even in approximation, we identify a powerful class of $L_p$-bounded uncertainty sets that avoid these complexity barriers due to their structural simplicity. We further show that this class can be decomposed into infinitely many \texttt{sa}-rectangular $L_p$-bounded sets and leverage its structural properties to derive a novel dual formulation for $L_p$ RMDPs. This formulation provides key insights into the adversary's strategy and enables the development of the first robust policy evaluation algorithms for non-rectangular RMDPs. Empirical results demonstrate that our approach significantly outperforms brute-force methods, establishing a promising foundation for future investigation into non-rectangular robust MDPs. |
| title | Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes |
| topic | Artificial Intelligence Machine Learning |
| url | https://arxiv.org/abs/2502.09432 |