Non-rectangular Robust MDPs with Normed Uncertainty Sets

Shie Mannor (Technion) · Navdeep Kumar (Technion - Israel Institute of Technology, Technion - Israel Institute of Technology) · Adarsh Gupta (Finsyth AI) · Maxence Mohamed ELFATIHI (École Polytechnique) · Giorgia Ramponi (Department of Informatics, University of Zurich, University of Zurich) · Kfir Y. Levy (Technion)

$l_1$-normed mdps$l_p$-bounded uncertainty setsaccuracy gapsadversary’s strategyapproximation dual formulation iteration complexitynon-rectangular uncertainty setnp-hard policy evaluation polynomial-time algorithmrobust markov decision processesrobust policy evaluation algorithmsa-rectangular setsstructural simplicity

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.