Non-rectangular Robust MDPs with Normed Uncertainty Sets

Navdeep Kumar, Adarsh Gupta, Maxence Mohamed ELFATIHI, Giorgia Ramponi, Kfir Yehuda Levy, Shie Mannor

Technion· Finsynth.ai· École Polytechnique· University of Zurich

Robust MDPs Non-rectangular uncertainty sets Robust Policy evaluation

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 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 first polynomial-time robust policy evaluation algorithm for

L_{1}

-normed non-rectangular robust MDPs.