Author name cluster

Adarsh Gupta

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

NeurIPS Conference 2025 Conference Paper

Non-rectangular Robust MDPs with Normed Uncertainty Sets

Navdeep Kumar
Adarsh Gupta
Maxence Mohamed Elfatihi
Giorgia Ramponi
Kfir Y. Levy
Shie Mannor

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.

PDF Details

EWRL Workshop 2025 Workshop Paper

Non-rectangular Robust MDPs with Normed Uncertainty Sets

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

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 Lp-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 Lp-bounded sets and leverage its structural properties to derive a novel dual formulation for Lp robust Markov Decision Processes (MDPs). This formulation provides key insights into the adversary’s strategy and enables the development of an efficient robust policy evaluation algorithm for these Lp normed non-rectangular robust MDPs.

PDF