Non-rectangular Robust MDPs with Normed Uncertainty Sets
Navdeep Kumar, Adarsh Gupta, Maxence Mohamed ELFATIHI, Giorgia Ramponi, Kfir Yehuda Levy, Shie Mannor
Abstract
Robust policy evaluation for non-rectangular uncertainty set is generally NP-hard, even in approximation. Consequently, existing approaches suffer from either exponential iteration complexity or significant accuracy gaps. Interestingly, 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$ robust Markov Decision Processes (MDPs). This formulation reveals key insights into the adversary’s strategy and leads to the \textbf{first polynomial-time robust policy evaluation algorithm} for $L_1$-normed non-rectangular robust MDPs.
BibTeX
@inproceedings{
kumar2025nonrectangular,
title={Non-rectangular Robust {MDP}s with Normed Uncertainty Sets},
author={Navdeep Kumar and Adarsh Gupta and Maxence Mohamed ELFATIHI and Giorgia Ramponi and Kfir Yehuda Levy and Shie Mannor},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=Xx0cJGXU7n}
}