Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes
This addresses the computational complexity challenge in non-rectangular robust MDPs for researchers and practitioners in reinforcement learning and robust optimization.
The paper tackles robust Markov decision processes with non-rectangular uncertainty sets, which capture interdependencies across states, by identifying a class of Lp-bounded uncertainty sets that avoid NP-hard complexity barriers and developing the first robust policy evaluation algorithms for such problems. Empirical results show the approach significantly outperforms brute-force methods.
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.