Non-rectangular Robust MDPs with Normed Uncertainty Sets

We thank the reviewer for recognizing the significance of moving beyond rectangular uncertainty sets. We're glad our use of the Sherman–Morrison formula and fixed-point formulation was found useful, as these were central to achieving both tractability and insight in our analysis.

We welcome the reviever feedback on the presentation that we fixed in the draft and it will reflect in the final version. We answer the major questions below.

Q1) Can the method be generalized to other types of uncertainty sets?

The current method is specifically designed for $L_p$ robust MDPs, relying critically on the rank-one perturbation structure of the worst-case kernel, which enables closed-form matrix inversion.

However, we believe that this approach could also be extended to KL-divergence-based uncertainty sets. As shown in [30], the worst-case kernel under KL divergence has an exponentiated closed form. If a closed-form or practical approximation for the associated matrix inverse can be derived, it would lead to both useful and insightful extensions of the method.

Q2) The paper only considers policy evaluation. Policy learning is still unclear.

Policy gradient methods for non-rectangular robust MDPs have been shown to converge to a globally optimal solution, with an iteration complexity of $O(\epsilon^{-4})$ [32]. However, this result assumes oracle access to the exact policy gradient, which in turn requires accurate policy evaluation.

In summary, once robust policy evaluation is performed, policy improvement via policy gradient can be carried out efficiently.

Q3) It is known that in the robust MDPs, history-dependent policies may achieve strictly higher rewards than stationary policies. However, how to evaluate a history-dependent policy is not discussed in this paper.

Yes, we apologize for this omission. However, robust policy evaluation has been proven to be strongly NP-hard even for stationary policies [35], making the extension to non-stationary policies considerably more complex and unwieldy. In other words, robust evaluation for non-stationary policies lies beyond the scope of this work. We will include this point as a limitation in the final version.

We thank the reviewer for their positive feedback.

We’re glad the reviewer finds the proposed uncertainty set meaningful for tractable robust MDP formulations. We also appreciate the recognition of the soundness of our theoretical results and the clarity of our literature review and problem setup.

Q1) I agree that in general develop theory and algorithms of non-rectangular uncertainty sets are important topics, but the explanation provided in this paper is not very convincing to me. The point argued here, as well as the idea of the $L_p$ bounded uncertainty sets, is that across different state action pairs only certain of the transition probabilities could deviate much from the nominal model. This is more like a domain specific prior and might not always hold. Probably a better way to argue this is to provide more concrete mathematical examples of certain application domains to show that this is the case.

There are several natural ways where $L_p$ bounded uncertainty sets arise. For example, if the model is the combination of a nominal model + noise, and if the noise has $L_P$ shape this naturally leads to an $L_p$ shape, cf. [21].

Q2) The theory and the algorithms proposed in this work are relatively direct provided with existing results on rectangular uncertainty sets.

Yes, the reviewer is correct in observing that our work builds upon prior research on rectangular robust MDPs. Nonetheless, we believe that the contributions and insights presented in this work remain significant and stand on their own merit.

Q3) How small should the uncertainty set radius $\beta$ be to make sure that the non-rectangular set contains valid probability kernels? The paper only emphasizes that such a key parameter should be small, but how small should it be? It would be better to incorporate some quantitative characterization.

As the uncertainty radius increases, the worst-case transition kernel $P^*$ may no longer admit a rank-one perturbation form of the nominal kernel. In such cases, the candidate output from our algorithm, $P_0 - bk^\top$, may fall outside the probability simplex and thus may not represent a valid transition kernel. To address this, we project $P_0 - bk^\top$ onto the simplex to obtain a valid transition kernel $P'$.

Furthermore, while the projected kernel $P'$ may not maintain the rank-one structure, we expect it to be close to the true worst-case kernel $P^*$. To support this, we conducted a new experiment comparing our method with random sampling across various uncertainty radii.

Experimental Setup

• Environment: Fixed state space $S = 12$, action space $A = 8$, discount factor $\gamma = 0.9$. The nominal kernel $P_0$ and reward function $R$ were generated randomly.
• Random Sampling: For each uncertainty radius $\beta$, we sampled over 500 million kernels from the uncertainty set and computed the empirical minimum return.
• Algorithm 1 (Ours): For each $\beta$, our algorithm produced the worst-case rank-one perturbation $bk^\top$. We then projected $P_0 - bk^\top$ onto the simplex to obtain a valid kernel $P'$, and reported the return $J^\pi_{P'}$ as the worst-case estimate.
• Time Taken: Our algorithm typically takes $2-4$ seconds while random sampling of 500+ million random sampling takes 400 minutes for each $\beta$.
• Nominal Return: The nominal return was $-0.1414$.

Results

Observation

As seen from the table, our algorithm consistently identifies worst-case kernels yielding significantly lower (i.e., more conservative) returns compared to the empirical minimum over 500 million random samples—even for large uncertainty radii. And our method is much faster than random sampling by order of magnitudes.

Conclusion

Our method performs exactly as expected for small uncertainty sets, with theoretical guarantees. For larger uncertainty radii—where theory no longer applies directly—our algorithm still significantly outperforms random sampling in estimating worst-case returns. We believe this demonstrates the robustness and practical utility of our approach beyond the theoretically guaranteed regime.

System: aws ec2 instance: c7a.32xlarge vCPUs: 128 Memory: 256 GiB Network Bandwidth: Up to 50 Gbps Processor: 4th generation AMD EPYC Clock Speed: Up to 3.7 GHz

Q4) Also, how does the convergence speed of Algorithm 1 depend on the uncertainty set size $\beta$? This is of interest because one would like to see how the proposed algorithm behaves as the size of the uncertainty set changes.

The theoretical convergence rate of Algorithm 1 is independent of the uncertainty radius $\beta$. Its empirical performance in terms of accuracy, as $\beta$ increases, is presented in the table above.

We thank the reviewer for their thoughtful and encouraging feedback.

We’re glad the reviewer found the insight—that NP-hardness need not apply to $L_p$ ball uncertainty—interesting, and we appreciate the recognition of its potential to open new research directions. We also thank the reviewer for their positive comments on the dual formulation and the empirical strength of our binary search algorithm.

Q1) What is the justification for considering memoryless randomized policies, while [1] states that for non-rectangular uncertainty sets both memory and randomization are needed?

Yes, the reviewer is correct in noting that the optimal robust policy for non-rectangular robust MDPs can, in general, be non-stationary.

However, it is important to highlight that even robust policy evaluation for stationary policies in non-rectangular robust MDPs is known to be strongly NP-hard.

Given the current state of the art, handling non-stationary policies appears significantly more complex and unwieldy, whereas focusing on stationary policies already presents substantial challenges.

Therefore, we believe that restricting attention to stationary policies is a natural and meaningful starting point. Extending the analysis to non-stationary robust policies remains an important and interesting direction for future work.

Q2) Where do the negative exponents come from in proposition 3.1 and on line 23? How does this correspond to the positive exponent in line 149?

We thank the reviewer for pointing this out. The correction has been made in line 149, where the exponent is now appropriately written as negative.

Q3) What happens to the algorithm when considering p != 2?

Our result and algorithm hold for all $p \geq 1$. However, for the specific case of $p = 2$, we can efficiently evaluate $F(\lambda)$ using a fast spectral method (Algorithm 2). For other values of $p$, one may need to rely on numerical methods, which could be comparatively slower.

Q4) Other minor comments.

We sincerely thank the reviewer for the invaluable time and effort dedicated to reviewing our paper. We appreciate the constructive comments, most of which we have already addressed and will be reflected in the final version.

We thank the reviewer for the detailed and encouraging feedback.

We’re glad the reviewer appreciates our robust policy evaluation method for coupled transition-uncertainty sets, and the significance of closing the gap between expressive non-rectangular models and tractable rectangular analysis. We’re especially encouraged that the clarity of our dual reformulation, the rank-one kernel structure, and the practical improvements over CPI methods came through clearly. We answer below the questions.

Q1) Validation is limited to random kernels with preset policies; there is no demonstration on a benchmark control task (grid-world, cart-pole, MuJoCo, etc.) where a robust policy derived from the evaluator outperforms rectangular or nominal baselines. Consequently the practical benefit, beyond runtime, remains speculative.

We agree that evaluating the empirical performance of a robust algorithm—motivated by our theoretical analysis of non-rectangular uncertainty—on moderately complex domains or real-world problems would be valuable for developing practical methods. However, this extension would require substantial additional work to be practically useful and is beyond the scope of the current paper.

The primary goal of this work is to initiate study into non-rectangular robust MDPs, a class often considered intractable. We hope that our results will serve as a foundation for future research in this direction, ultimately contributing to real-world applications.

Q2) The guarantees rely on the uncertainty radius being small enough that every perturbed row stays in the simplex. They do not cover KL-divergence, Wasserstein balls, or large uncertainty radius where new transitions appear—settings that are common in distributionally-robust RL and may break the rank-one structure the theory exploits.

Yes, the reviewer is correct in noting that our analysis critically relies on the rank-one structure of the perturbation, which holds only when the uncertainty radius is sufficiently small. This rank-one structure may indeed not be preserved in more general settings, such as those described by the reviewer.

However, in the case of KL-divergence–based uncertainty sets, the structure of the worst-case transition kernel is known [30]—it takes an exponentiated form rather than a rank-one form. It may be possible to derive an analogue of the Sherman-Morrison formula, or a practically useful approximation, for this case.

The broader point is that our work serves as a step in the right direction, highlighting the possibility that practical algorithms for non-rectangular robust MDPs may indeed exist. We hope this encourages further exploration in this promising area.

Q3) Your method requires the radius to be small enough that all perturbed rows remain valid probability vectors. In realistic safety‑critical settings, large shocks or zero‑probability transitions can occur. Could you quantify how performance or guarantees degrade as the radius grows, and comment on whether this limitation is less severe than the approximation gap in [20]? You described Li et al. 2024 as “meaningless” because its approximation bound is loose in certain worst‑case instances; then the methods described in the paper should be held to the same standard.

First, we sincerely apologize if our wording gave the impression that we were describing the work of Li et al. (2024) as “meaningless.” That was not our intention, and we will revise the phrasing accordingly. What we meant to convey is that the worst-case accuracy bound in their work can, in some settings, exceed the maximum possible sub-optimality—rendering the bound vacuous in those cases.

Regarding the robustness radius: as the uncertainty radius increases, the worst-case transition kernel $P^*$ may no longer admit a rank-one perturbation form of the nominal kernel. In such cases, the candidate output from our algorithm, $P_0 - bk^\top$, may fall outside the probability simplex and thus may not represent a valid transition kernel. To address this, we project $P_0 - bk^\top$ onto the simplex to obtain a valid transition kernel $P'$.

The robust return then becomes $J^\pi_{P'}$. Crucially, even in the worst-case projection scenario, the sub-optimality gap $J^\pi_{P'} - J^\pi_{P^*}$ is upper bounded by $\frac{2}{1 - \gamma}$, meaning the result remains meaningful. We will include this clarification in the final version.

Furthermore, while the projected kernel $P'$ may not maintain the rank-one structure, we expect it to be close to the true worst-case kernel $P^*$. To support this, we conducted a new experiment comparing our method with random sampling across various uncertainty radii.

Experimental Setup

• Environment: Fixed state space $S = 12$, action space $A = 8$, discount factor $\gamma = 0.9$. The nominal kernel $P_0$ and reward function $R$ were generated randomly.
• Random Sampling: For each uncertainty radius $\beta$, we sampled over 500 million kernels from the uncertainty set and computed the empirical minimum return.
• Algorithm 1 (Ours): For each $\beta$, our algorithm produced the worst-case rank-one perturbation $bk^\top$. We then projected $P_0 - bk^\top$ onto the simplex to obtain a valid kernel $P'$, and reported the return $J^\pi_{P'}$ as the worst-case estimate.
• Time Taken: Our algorithm typically takes $2-4$ seconds while random sampling of 500+ million random sampling takes 400 minutes for each $\beta$.
• Nominal Return: The nominal return was $-0.1414$.

Results

Observation

As seen from the table, our algorithm consistently identifies worst-case kernels yielding significantly lower (i.e., more conservative) returns compared to the empirical minimum over 500 million random samples—even for large uncertainty radii. Furthermore, our methods works much faster than random sampling.

Conclusion

Our method performs exactly as expected for small uncertainty sets, with theoretical guarantees. For larger uncertainty radii—where theory no longer applies directly—our algorithm still significantly outperforms random sampling in estimating worst-case returns. We believe this demonstrates the robustness and practical utility of our approach beyond the theoretically guaranteed regime.

System: aws ec2 instance: c7a.32xlarge vCPUs: 128 Memory: 256 GiB Network Bandwidth: Up to 50 Gbps Processor: 4th generation AMD EPYC Clock Speed: Up to 3.7 GHz

Although I find the paper's idea and the duality arguments nice, the substep of norm maximization still remains NP-hard, and the paper does not seem to provide a provable algorithm for solving it. Could you further elaborate on this if I am missing something here? We are glad that the reviewer finds the paper's idea and duality argument nice. And the the reviewer is correct in noticing that we need to solve $z := \max_{\lVert b\rVert_p\leq1, \lVert k\rVert_p\leq1, b\succeq 0, <k,1>=0}b^\top A k$ as sub-routine in Algorithm 1. And as mentioned in Line 984 that it is a bi-linear optimization. And bilinear optimization is NP-Hard in general. But we have a special form, which might be solvable for many cases, as illustrate below.

For $p=1$: For uncertainty case $\mathcal{U}1$ bounded by $L_1$-ball. We have the close-form solution to our sub-problem. That is, $z:=\max_{\lVert b\rVert_1\leq1, \lVert b\rVert_1\leq1, b\succeq 0, <k,1>=0}b^\top A k = \max_{\lVert b\rVert_1\leq1, b\succeq 0}\max_{ \lVert k\rVert_1\leq1, <k,1>=0}b^\top A k= \max_{\lVert b\rVert_1\leq1, b\succeq 0}\lVert b^\top A \rVert_{sp},$ where $\lVert x \rVert_{sp} = \frac{\max_{x_i}-\min_{i}x_i}{2}$ is span-norm. Now, we have to maximize the above span-norm over the simplex ($\lVert b\rVert_1\leq1, b\succeq 0$), and we can easily show that $z = \max_{i}\lVert A(i,\cdot)\rVert_{sp}.$ We will add this discussion in detail in the final version. To summarize, non-rectangular robust MDP with $L_1$ bounded ball can be efficiently be solved in polynomial time.

For $p=\infty$, non-rectangular uncertainty set degenerates to sa-rectangular one, which is already efficiently solvable [19].

For $p=2$, we proposed a heuristic spectral Algorithm 2, to solve the above sub-problem. And Figure 6, Figure 7 and Table 3 shows the superiority of its performance over numerical method such as scipy. Further, we showed in the previous response that this method also yields much better performance than random search even when uncertainty radius $\beta$ is big-enough.

For other $p\neq 1,2$, we are not sure if the above sub-problem is efficiently sovable or not. As a similar problem without positivity and mean-zero constraints, $A_{p\to q} := \max_{\lVert b\rVert_p\leq1, \lVert k\rVert_p\leq1}b^\top A k = \max_{\lVert b\rVert_p\leq1}\lVert b^\top A \rVert_q,$ is very well studied known as Matrix p-norms. And there are several negative and constant approximation results are known in the literature for Matrix p-norm problem for $p\neq 1,2,\infty$ [Hendrickx and Olshevsky].

To summarize, for $L_1$ bounded uncertainty set are efficient and solutions can be obtained in the close form. And for $p=\infty$, it is equvialent to sa-rectangular case which is easy. For $p=2$, we provided heuristic algorithm that works well in practice and also generalizes well beyond theoretically applicable uncertainty radius $\beta$. However, we believe that for $p=2$, it is possible to provably solve this sub-problem via standard methods as second-order cone optimization or quadratic programming, but we are not aware of the exact positive nor negative result. And for other $p$, we are not sure if the efficient solution exists.

We thank the reviwer again for this thoughful question. We will gladly add this discussion in the final version.

[Hendrickx and Olshevsky] @article{DBLP:journals/corr/abs-0908-1397, author = {Julien M. Hendrickx and Alexander Olshevsky},title = {Matrix P-norms are NP-hard to approximate if p {\textbackslash}neq1,2{\textbackslash}infty},journal = {CoRR},volume = {abs/0908.1397},year = {2009}}