Non-rectangular Robust MDPs with Normed  Uncertainty Sets
Authors: Navdeep Kumar
Adarsh Gupta
Maxence Mohamed ELFATIHI
Giorgia Ramponi
Kfir Yehuda Levy
Shie Mannor
Venue: NeurIPS 2025 poster ()
Keywords: Robust MDPs
Non-rectangular uncertainty sets
Robust Policy evaluation
Primary area: reinforcement_learning
TL;DR: We propose a efficient robust policy evaluation method for non-rectangular robust MDPs with uncertainty sets bounded by $L_p$ norms.

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 \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.

Non-Rectangular Robust MDPs with Normed Uncertainty Sets
Navdeep Kumar' Technion
Adarsh Gupta Finsynth.ai
Maxence Mohamed Elfatihi École Polytechnique
Giorgia Ramponi University of Zurich
Kfir Levy
Shie Mannor Technion
Technion
Abstract
Robust policy evaluation for non-rectangular uncertainty set is generally NP-hard, even in approximation, Consequently, existing approaches suffer from either expo- nential iteration complexity significant accuracy gaps. Interestingly, a powerful class of Lp-bounded uncertainty sets that avoid these complexity bar- riers due to their structural simplicity. We further show that this class can be decomposed into infinitely many sa-rectangular -ounnudded sets and leverage its structural properties derive novel dual formulation for Lp robust Markov Decision Processes (MDPs). This formulation reveals key insights into the adver- sary's 's strategy and leads to the first polynomial-tine robust policy evaluation algorithm for normeed non-rectangular robust MDPs.
identify
Introduction
Robust Markov Decision Processes (MDPs) effectively handle uncertainties in environmental pa- rameters, making them indispensable for high-stakes domains such as robotics, finance, healthcare, and autonomous driving, where failures have catastrophic consequences 24
12
30
25 [6].
They also outperform standard MDPs in terms generalization, ensuring robust performance across Consequently, extensive research has been conducted robust
diverse scenarios 37
38
26
15), primarily focusing on rectangular uncertainty sets that leverage the contractive robust Bellman operator. However, practical robust MDPs often feature non-rectangular uncertainty sets, where rectangular relaxations can result in overly suboptimal solutions [21l 8 36). Intuitively, non-rectangular uncertainty set could be thought of as an n-dimensional sphere of unit radius, and its rectangular relaxation is the smallest n--imennsoonal cube encapsulating the sphere. The ratio between the sphere and the encapsulating cube exponential in the dimension (O(2-))) (28).. This suggests that the rectangular relaxation of the non-rectangular uncertainty set, contains many additional environments. Moreover, most of the additional enviromments would lie near the corners representing big differences from the center many coordinates scenarios unlikely to occur in the real world, as aptly captured by the paper titled "Lightening doesn't 't strike twice, robust MDPs [22) These improbable, highly perturbed environments can lead significant gap between the solutions of non-rectangular robust MDPs and their rectangular relaxations.
MDPs
36
17
16
14
35 33 20
18
39
While non-rectangular robust MDPs capture much better interdependencies across the states, they lack the existence of contractive robust Bellman operators, which makes the problem very difficult solve with standard dynamic programming techniques [8] This makes non-rectangular robust
corrosponding author email navdeep. kumapp2ooama22
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

MDPs a crucial yet challenging area of study, with only a limited body of work existing on the topic
36 21 g
The key challenge for non-rectangular robust MDPs is robust policy evaluation That is, given oracle access to the robust gradient (robust policy evaluation ), the robust policy gradient method can efficiently achieve an e-close globally optimal policy with an iteration complexity of O(e [33] However, the robust policy evaluation for general convex non-rectangular uncertainty sets is strongly NP-hard, even for approximations [36. Despite this hardness, 21 first proposed two methods for non-rectan non-rectangular robust policy evaluation for general convex uncertainty sets: One with exponential iteration complexity in the state-action space, and another that approximates the solution but with a possible very high accuracy gap in the worst case (see Table D. These pioneering approaches remain computationally prohibitive or overly imprecise, consistent with the NP-hardness result.
Interestingly, the NP-hardness result in [6 applies specifically kernel uncertainty sets with certain polyhedral structures (see Appendix for details). For T.p -bounded uncertainty sets, [8 showed that robust policy evaluation can be done efficiently, though this limited reward uncertainty, a much simpler case compared to kernel uncertainties, This raises a critical open question: Are there useful classes of kernel uncertainty sets that avoid this NP-Hardness barrier? And we show that L normed non-rectangular uncertainty sets are efficiently solvable in polynomial time.
We identify specific class of non rectangular uncertainty sets, bounded by an Lp- ball around a nominal kernel, and demonstrate that it effectively circumvents the NP-hardness result of [36.. Moreover, show that robust policy evaluation for this non-rectangular T,p- -bounded uncertainty set is equivalent to robust policy evaluation over an infinite collection of sa-rectangular T.p -bounded uncertainty sets. While robust policy evaluation for each sa-rectangular set is computationally tractable [20] 18), managing this infinite collection poses significant challenges. To overcome this, we leverage the property that the worst kernel for each sa-rectangular uncertainty set is rank-one perturbation of the nominal kernel [8]. This insight enables us to express the robust policy evaluation problem (or robust return) in novel dual form, providing a clearer understanding of the adversary's behavior. Furthermore, this dual formulation facilitates the development of a binary search method for robust policy evaluation, achieving an iteration complexity of O(log e e!) ") for approximating the
robust return up to e tolerance.
In summary, robust MDPs are critical for handling uncertainties in high-stakes domains, yet existing methods are largely confined to rectangular uncertainty sets, limiting real-world applicability. Non- rectangular uncertainty sets, though more realistic, often face NP-hard challenges in robust policy evaluation. This work identifies a promising class of non-rectangular Lp -bounded kernel uncertainty sets, demonstrating that they cireumvent existing NP-hardness results and enable efficient robust policy evaluation. By connecting robust evaluation for these sets to an infinite collection of sa- rectangular uncertainty sets and leveraging their structure, we propose a computationally efficient binary search method with logarithmic iteration complexity. This approach not only advances the understanding of non-rectangular robust MDPs but also opens the door to future investigation into broader classes of non-rectangular uncertainty sets in robust MDPs
2 Preliminary
A robust Markov Decision Process (RMDP) can be described as tuple (8, A. R,U), where S is the state space, A is the action space, is an initial distribution over states S, 7 is a discount factor in [0, 1), R is a reward function mapping S x A R. and 1/ set of transition kernel P that maps S x AA to As [66 25 A policy क S - AA is a decision rule that maps state space to a probability distribution over action space. Let II (AA)s denote set of all possible policies. Further, {{ [s, a) denotes the probability of taking action a in state s by policy x. and the probability of transition to state s' from state under action a respectively. In addition, we denote and (T)(s) = =. (((,))((ss a) as short-hands. The return of policy π, is defined as Jp = {1,, Fp) = (R" d where up == D R is value function, d7 y T occupation measure and D = (I - pP=) is occupancy matrix [27] As a shorthand, we denote and the usage shall be clear from the context. For an uncertainty set 24, the robust return J for a policy n, and the optimal robust return Jú are defined as:
(* Σ. T(a s) P(s'|s,
the state-action occupation measure as d' a) = (x) (T)))) (a|s)
Jū = Jr, and Ju = max Jú Pel
2

---

Table 1: Related Work on Robust Policy Evaluation for Kon-Rectangular Uncertainty Sets.
Method
Uncertainty Set
Iteration Com-
Accuracy
Irreducibility Assumption of 22
NP-Harness Result of [6
plexity
8
Reward Lp Normed
Ollgg
No
No
Algorithm 3.1 of 21
General Kernel Set
( log 1)
No
Yes
Algorithm 3.2 of [1
General
O(c-2)
6a + 8p)
Yes
Yes
Kernel Set
Ours
Kernel L1
log(E-!)
No
No
Normed
The constants dd. &p can be as large as O A) A), 0(25) and O(Sv respectively.
respectively. The objective is determine an optimal robust policy ny that achieves the optimal robust performance Juz Unfortunately, even robust policy evaluation (i.e., finding the worst-cass transition kernel Pt E arg minpeu JP) strongly NP-hard for general (non-rectangular) convex uncertainty sets [36]. This makes solving non-rectangular robust MDPs a highly challenging problem.
To make the problem tractable, common approach is use s-rectangular uncertainty sets, U X X where the uncertainty is modeled independently across states (36). These sets decompose state-wise, capturing correlated uncertainties within each state while ignoring inter-dependencies across states. A further simplification is the sa-rectangular uncertainty set, U where uncertainties
are assumed to be independent across both states and actions. Formally, 4 (x..)e5xx
where Ps.a a are independent component sets for each state-action pair [16 25 34 35
A I.p bounded uncertainty sets, U5th and Ug. which are centered around a nominal transition kernel P are defined as 2 = (PI (s') = 1, P| Peulp p S B.a), and UØ = {P E. Pea('')
[P, P. lpp < {.); J. where radius vector 3 is assumed small enough to ensure all kernels within the uncertainty sets are valid [14 7 20 [8] Interestingly, for L, bounded uncertainty set, adversarial (worst) kemels rank perturbation of the nominal kernel that is used later in the paper (18)
Dual Formulation. The primal formulation of an MDP is defined as:
max(μ, v), with its dual: "EV
max (d, R),
RED
where V = fo v= RT TT P E 11 represents the set of value functions. The dual formulation
relies on the state-action occupancy measure d, where d E D C R|S|X|A| satisties the non-negativity constraint (d 0) and the flow conservation constraint: Σ. d(s,a) Ev d(s', (os'a'')P a() s',a') = (s);; Vs S. The feasible set D forms a convex polytope [ whereas the set of value functions, V. is polytope that is generally non-convex [6]. This dual formulation offers several advantages, including efficient handling constraints and the ability to solve the problem using linear programming techniques.
For robust MDPs, the geometry of robust value functions is significantly more intricate compared to standard MDPs [32] While the dual formulation for standard MDPs is well-established, this work is the first to derive dual formulation for this specific class of non-rectangular robust MDPs, providing critical insights and laying the foundation for the development of robust policy evaluation methods.
3 Method
In this section, we introduce boundedd non-rectangular uncertainty set, and demonstrate that its rectangular relaxation may yicld highly sub-optimal solutions. Then, establish that this
3

---

uncertainty set avoids the NP-Hardness results established in [36.. Subsequently, we show that the robust evaluation for this uncertainty set is equivalent to robust evaluation over infinite collection of sa-rectangular robust MDPs. This equivalence leads to novel dual formulation and, ultimately, a binary search method for robust policy evaluation. We begin with defining non-rectangular Tp- bounded uncertainty set as:
Up - {P|1PP 1P- SB SB, 1,(d
where P is the nominal kernel, 3 is uncertainty radius, and |P (P((ss)))))).
P(s'|s, a)))) The simplex constraint ensures that the transition kernel satisfies the unity- sum-rows property, as discussed in [20] Following previous works 7 20 18), we assume the radius/ (3 is sufficiently small to ensure all the kernels within the uncertainty sets are valid transition kernels. As discussed in 20), this assumption can be lifted by imposing boundary constraints (0 < P(s]s, a) < 1) at the expense of additional complexity and without yielding significant additional insights. Throughout the paper, we use d" v², _ D as shorthand for d up and
D., respectively, w.r.t. nominal kernel P.
Why non-rectangular RMDPs. Note that the non-rectangular uncertainty sets allow noise one state be coupled with noise in other states. Before delving into solving them, first discuss their importance. Why are uncertainty sets modeled with non-rectangular sets Up (e.g., I2-balls) better than rectangular ones?
In Figure we illustrate this by capturing the uncertainty set using non-rectangular Un (circle/sphere) balls and rectangular (square/cube) balls. The blue dots represent possible environments, with the origin being the nominal environment. Points farther away from the origin indicate larger perturbations. Specifically, points near the corners of the square/cube represent environments with large perturbations in nearly all dimensions or coordinates simultaneously. The likelihood of such simultaneous perturbations is very low, and this issue becomes dimensions. This phenomenon is well discussed in the paper Lightning Doesn's I Strike Twice: Coupled RMDPs(22 22
pronounced in higher
Uncertainty Points
1 Bal
piRectangitarls Rall
Reprasantation
Rapresantation
10
0.
0.0
-15
1.5
1.0
-1.0
0.
00
-3.0
-15
1.0
-1.
Figure 1: Modeling Uncertainty with Non-Rectangular and Rectangular L2-Balls.
Moreover, as shown in the result below, most of the volume of a high-dimensional cube lies near its corners outside the embedded sphere. This implies that rectangular robust MDPs are overly conservative, as their uncertainty sets focus on environments near the corners momners-correpponiii to highly unlikely extreme perturbations.

---

Proposition 3.1. Let U and Ui denote the smallest sa-rectangular and s-rectangular sets, respec- rively. that contain Uz. Then:
vol(U1g OcTooA) and
vol(U1) Oc,r²), vol
vol(U
where vol(X) denotes the volume of the X, S = | |A| and Coy Csa are constants.
The result follows from comparing the n-dimensional sphere's volume C,T" (Cn, + enclosing cube's volume 2n'" (side 2r), resulting in ratio of ((2-").
0) 28 to the
In summary, real-world uncertainty sets are often non-rectangular and highly coupled. Their rectan- gular relaxations (the smallest rectangular uncertainty sets encapsulating the original non-rectangular sets) introduce exponentially more additional environments, many of which correspond to highly perturbed kernels that improbable in practice. As result, relaxed rectangular robust MDPs can produce overly conservative and suboptimal solutions compared to their non-rection contrrettagglar counterparts.
Complexity. While non-rectangular robust MDPs better capture real-world uncertainty sets, robust policy evaluation (even approximation) has been proven NP-hard for general uncertainty sets defined as intersections of finite hyperplanes [36] Specifically, (36 reduces an Integer Program (IP) with m constraints robust MDPs where the uncertainty set consists of intersections of half-spaces (m--lneer constraints). This polyhedral structure is fundamental to the hardness proof, consequently, does not extend to our uncertainty sets Un for p > 1. For the case of Ui, the IP reduction does apply, but since Ui is defined by single global constraint (I) P1 1 < 8), this implies that the corresponding IP has only one simple constraint which is efficiently solvable. A detailed discussion can be found in Appendix B.2
Intuitively, the NP-Hardness result primarily applies to polyhedral uncertainty sets with numerous vertices. This leaves room for the possibility that many uncertainty sets defined by a small number distances, might fall outside the scope of this hardness and
of global constraints, such as could potentially be tractable. However, we leave this intriguing question for future exploration: is NP-Hardness merely the tip of the iceberg?
The above discussion highlights the potential tractability of Lp-robust MDPs, prompting to address the challenge of solving them. A key insight is that the non non-rectan uncertainty set Up can be expressed as a union sa-rectangular sets (4) with varying radius vectors b, as formalized in the result below. Each sa-rectangular set be efficiently solved individually, paving the way for a more manageable approach to the overall problem.
Divide and Conquer.
Covering an L, ball with centered rectangles
0.75
-0.28
-1.00
-0.50
-0.25
0.50
(a) Illustration of Proposition sphere be written as infinite union of dimensional inscribing cubes.
3.2
N-dimensional
(b) Projections of set D along principal components, for S 3, A = with 10 millions samples, strongly suggesting non-convexity.
Figure
5

---

For the first time, the above result expresses the robust return in terms of the nominal return J and penalty term involving only nominal values (dt 2x n², and ug)). Notably, the denominator term 1 1+ vf)) ) is strictly positive (see appendix for details). In the subsequent subsections, we delve Proposition 3.2. [Decomposition] The non-rectangular uncertainty set Up can be expressed as:
Up
U (b)) BEB
where B = {b E R |bb|p S B), and uz (P [P( 8,a) P( 8,a)1p S
b(s, a), V(s, a)}; is sa-rectangular uncertainty set with radius vector b.
The proof of the above result intuitively generalizes the idea that circle (or n-dimensional sphere) be covered by inscribed square (or n-dimensional rectangles) touching its boundaries and continuum of its rotated versions, as shown in Figure 2(a) This offers a significant simplification to
the problem hand, as it implies that rentanccan policy evaluation (difficult) can be decomposed into sa-rectangular uncertainty sets (easier) as:
Jú
= min min Jp. BEB (E)
In essence, we have simplified complex problem into an infinite number of more manageable ones. However, the task remains incomplete. Although a closed-form expression exists for Jüg J E., d (s, (1) where q the Hölder conjugate of p (i.e., p and Op is the generalized standard deviation (GSTD) defined as op(r) = min ||v - w1 lp 20). this approach still computationally impractical. The core challenge lies in solving maxteB E0,a (s, a which remains a formidable task. To circumvent this, we leverage the dual formalism, which elaborated in the next section.
1
1)
3.1 Dual Formulation of Robust MDPs
Here, we present a dual formulation for robust MDPs specifically for Lp boundede uncertainty sets. While this formulation is inherently more intricate than the classical dual formulation for standard MDPs 27 it forms the foundation for all subsequent results in this work.
Now, leveraging results from 18], know that the worst-case kernel for sa-rectangular uncertainty sets, PT (b) P bk T_ can be expressed rank-one perturbation of the nominal kernel, where K. = {k || S 1, 1 T 0}. Consequently, the adversary can restrict their focus to rank-one perturbations, enabling us to reformulate the robust return as:
Jú
min min J bEB KEK
min min μ D7 bEB KEK
where the last equality stems from Jp = μ DDRR. Further, leveraging Lemma 4.4 from 18 or directly applying the Moerman-Morrison formula 4 (see Proposition D.I. the robust return can be expressed as:
k RT
Jü
min [ TT - -p - DE beB,eEK
1+ Dob=
where bū := E. T (als)).a.. The following result introduces a more concise and interpretable form of this robust return expression.
Lemma 3.3. [Penalized Robust Return] The robust return can be expressed as:
(d
Jú
=
max bEB,KEK:
1+r(k,y
where ug
D" represents the value function with uncertainty radius the reward vector:
deeper into evaluating this penalty term and analyzing the nature of the optimal (k, b) for given policy revealing the adversary. Finally, by maximizing the robust return Jú over policies, we dual formulation, stated below.

---

Theorem 3,4 (Dual Formulation). The optimal robust return is the solution to
[ --p² Db DR
Jú max min DED KER
1+ yk* Db
where D D D" x ET }. D -1- and Ha R x + R.S is a policy averaging
linear operator defined as H R := = R
The dual formulations for the sa-rectangular and s-rectangular cases differ notably in their definitions of B. In the sa-rectangular case, B = { whereas in the s-rectangular case, B = {6 E RSxA ||bs lpp S {.). These distinctions are elaborated the appendix. The result above frames the dual of robust MDPs as min-max problem, offering valuable and insightful perspectives. However, as Figure 2(b) suggests (with further details in the appendix), the set DD may be non-convex, which complicates the problem. Despite this, we believe that the dual formulation holds potential for future work, providing deeper insights and enabling the development of improved algorithms. In this work, we keep our focus on the robust policy evaluation while policy improvement is addressed via existing robust policy gradient method with proven guarantees (33 discussed further Appendix C
3.2 Robust Policy Evaluation
Now, we directly attempt to evaluate the penalty term in Lemma 3.3 which leads to a binary search- based robust policy evaluation algorithm. The key idea is to identity bisection function:
F(A)
max k EX,, BEB,KEK
where E-:= D"R D AD= Hº Note that Ex is constructed using quantities that are computationally straightforward, and H RSSA - IRS represents the policy-averaging linear operator, defined by (H" Rs(s) == Σ. R(s,s)
Proposition 3.5. For 1, F can be evaluated in closed form
F(A) 8 max sES,aEA
T(als)|ld" (s)p" XD*
where
|a<|ep max; my min; 2i and D = -I-7Pa)-1
2
Proof. The proof referred to Proposition G.4
Note that the above result requires computation of v" dd , D which can be approximated iteratively with time complexity O(S² log e or exactly via matrix inversion with time complexity O A Lemma 3.6 (Robust Policy Evaluation). Let X be fixed point of the function F(A), then the robust return can be expressed as:
Jū, -
And X* can be efficiently computed using binary search Algorithm 1 as F(A) >>
Y>K
Proof. The proof can be found in Appendix (see Lemma
The result enables direct computation of the robust return by iteratively refining À until convergence, leveraging the monotonicity properties of F(A). Further, the bisection property of F established in the result, directly implies the linear convergence rate of Algorithm [ stated result below.
Algorithm Binary Search for Robust Policy Evaluation
Initialize: Upper limit A, T- lower limit A
1: while not converged: n = n. + do
2: Bisection value: A. (>z + Xu)/2
3: Bisection: X = >, if ((A,) > Ans else > = An-
4: Update robust return: Jn JJ. where P = proj(P, - -b
(b, k) arg max & E and proj is simplex projection operator.
5: end while

---

Theorem 3.7. Algorithm 7 converges linearly, i.e.,
Jn - Júp S 02
We conclude that robust evaluation can be performed efficiently with linear iteration complexity. However, each iteration involves solving the subproblem maX,es ||Ar]|g as part of Algorithm which can solved in closed form shown in Proposition 3.5 For 2, we provide spectral heuristic
for its approximation the appendix, however for other p + 1, 2, can be hard.
Revealing the Adversary
We provide first insights into the structure of the worst-case kernel in non-rectangular robust MDPs, addressing unexplored area in the literature. The following result reveals that, similar to rectangular uncertainty sets [18], the worst-case transition kernel a rank-one perturbation of the nominal kernel, but with more complex structure.
Theorem 4.1 (Worst-Case Kernel). For policy and uncertainty set Up, the worst-case transition kernel is:
1ú bk
where (k, b) solves:
J (k, x
KE 1 7 (k, vg))
The above result follows directly from Lemma
3.3 It highlights the adversary's strategic use of k, b, and their interaction with the value functions 2i and Dr. revealing a more nuanced structure compared to the rectangular case. The adversary's objectives in selecting the worst-case kernel are twofold:
Maximizing Trajectory Uncertainty (Jğ): The adversary seeks increase the agent's vis- its to high-uncertainty states, enhancing its ability to steer the agent toward vantaaans outcomes.
Optimizing the Perturbation Direction (k): The adversary selects k maximize k u thereby pushing the agent into low-reward trajectories, while simultancously minimizing k ug ensure the agent remains exposed to eigh-uncertainty states.
These insights provide a deeper understanding of the adversary's behavior and offer practical guidance for designing more resilient robust algorithms to counteract such strategies effectively.
Message to Practitioners
The adversary focuses solely rank-one perturbations of the nominal kernel, iteratively boosting its influence by pushing the agent into highhuncertaitty states, then leveraging that influence steer the agent toward low-reward trajectories, ultimately driving the agent the lowest possible return.
Experiments: Robust Policy Evaluation with L1 Normed Uncertainty Set
We conduct numerical comparison of our Algorithm aand CPI (Algorithm 3.2 from 21 reproduced as Algorithm 2 in the appendix) for robust policy evaluation. The experiments are performed using randomly generated nominal kernel P. reward function Rt, and policy An uncertainty set 24 is constructed using the nominal kernel with a fixed uncertainty radius 3.
Figure 14 demonstrates the convergence behavior of both methods, presenting results based on the number of iterations (left panel) and computation time (right panel). The left panel shows the robust return achieved iteration, while the right panel depicts the robust return a function of wall-clock time. Note that the x-axes of the figure have a logarithmic scale in order to clearly capture the slow convergence of the CPI method.

---

Robust
-0.150
-0.175
-0.200
Robust Return
-0225
4.43
-0250
144
-0 100
-0.325
Uncoraatty Kalio lay suidt
39
Algortthm (Ours)
10
10
10
20"3
10a
Uncertainty Radius # (Log Scale)
Figure 3: Robust Return for (Uncertainty Radius, S=12 and A=8, 7=0.9 and convergence tolerance of 10 Robust Return of Random Kernel is minimum of 500 millions kernels samples for each B
Our Algorithm I We apply our Binary Search Algorithm to perform robust policy
evaluation with the given nominal kernel P and uncertainty radius B3. Each iteration of the algorithm involves computing F()), using close form solution provided in Proposition 3.5 Our algorithm converges very quickly requiring only few iterations.
Algorithm 3.2 of [21]. We run Algorithm with precomputed values of dm and A", The step sizes are chosen to either a small constant or dynamically adjusted, as described in the algorithm. Note that Line 3 of the algorithm involves solving arg min (z, P). This constrained optimization is solved using a numerical method ceiipy.miimiize. This gradient based method improves very slowly and converges very far from the true robust return as the uncertainty set U4 is very non-rectangular.
Brute Force Benchmark. To approximate the true robust return, we generate a large number of random samples {P, i S n} from U4 and estimate the empirical minimum, min; J as a proxy for the robust return. Note this method requires exponential number of samples reasonably cover the entire uncertainty set. Hence the values obtained in Figure 14] are an approximate upper bound on the true robust return.
The results in Figure 14 reflect a general trend observed across a wide range of experiments conducted with space sizes ranging from S = 5 to S 190 and uncertainty radius {0.005, 0.01, 0.05). Our proposed algorithm consistently demonstrates superior performance, converging in significantly fewer iterations and less computation time while the computational demands of the CPI algorithm grow substantially with larger state spaces. Hence, our method exhibits more favorable scaling properties, making practical for high-dimensional problems.
The codes, detailed explanations, and additional experiments are available at httph::t/////ctt httt::://anonmouu 4open. www.eecceinneonnnnc.ncc srsiennce///norrreettaauulaaar ar -mdd-- 77B8| System details for the experiments as follows: Operating System: macOS Sequoia (Version 15.4.1), Chip: Apple M2, Cores: 8 (4 performance and 4 efficiency), Memory: 16 GB (LPDDRS).
Discussion
We studied robust Markov decision processes (RMDPs) with non-rectangular bo--bodnded uncer- tainty sets, balancing expressiveness and tractability. We showed that these uncertainty sets can be decomposed into infinitely many sa-rectangular sets, reducing robust policy evaluation min-max fractional optimization problem (dual form). This novel dual formulation provides key insights

---

Complesity nitrrcions
Complesity (i
-012
-0.2
100
12
042
dipader 3 (Den))
duardiin (ior price scaud biters 0014
Furnariinn souts 010
Figure 4: Comparison of Algorithm D (Ours) and the CPI Algorithm for B (Uncertainty Radius) = y = 0.9, and convergence tolerance of 10
0.05, S 10, A = 8
into the adversary and leads to the development of an efficient robust policy evaluation algorithm. Particularly, we provided first polynomial time policy evaluation for non-rectangular I, normed uncertainty set. These findings further pave the way for scalable and efficient robust reinforcement learning algorithms.
have considered small enough uncertainty radius to ensure positivity of the kernel. As discussed in [20], imposing this additional positivity constraints (or dealing with nominal kernel with complicate the analysis without yielding significant additional insights. However, we leave a thorough investigation of this topic for future work.
Limitations. Similar to 7
20 18
transition probability some states would significantly
Optimal robust policies for non-rectangular uncertainty sets may history dependent [36], but we focus stationary policies since even their evaluation is NP-hard [3). Extending to non-stationary cases is left for future work.
Future Work. Our results naturally extend to uncertainty sets that can be expressed finite union of Lp balls. Furthermore, any uncertainty set can be approximated using a finite number of Lp balls, with smaller balls providing better approximation. However, the number of balls required for an accurate approximation may grow prohibitively large. While this work is limited to Lp norms, may be possible to generalize our approach to other types of uncertainty sets. A key challenge in such an extension would be identifying the structure of the worst-case kernel and developing corresponding matrix inversion techniques.
Particularly, the case of KL-divergence- based uncertainty sets, the structure of worst-case transition kernel is known (31 takes an exponentiated form rather than a rank-one form. It may be possible to derive an analogue of the therman-Morrisor formula, or a practically useful approximation, for this case.
Acknowledgments and Disclosure of Funding
This research was partially supported by Israel PBC- VATAT, by the Technion Artificial Intelligent Hub (Tech.Al) and by the Israel Science Foundation (grant No. 447/20).
Additionally, part of this work was supported by the Israel Science Foundation (grant No. 3019/24).
References
[1] M. A. Abdullah, H. Ren, H. B. Ammar, Milenkovic, R. Luo, M. Zhang, and J. Wang. Wasserstein robust reinforcement learning, 2019.
[2] E. Altman. Constrained Markov Decision Processes. Chapman and Hall, 1999.
[3] A. Bagnell, A. Y. Ng, and J. Schneider. Solving uncertain markov decision processes.
Technical report, Carnegie Mellon University, 2001.
10

---

[4] M. S. Bartlett. An Inverse Matrix Adjustment Arising in Discriminant Analysis. The Annals of Mathematical Statistics, 22(1):107 111, 1951.
[5] Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, March 2004.
[6] R. Dadashi, A. A. Taiga, N. L. Roux, D. Schuurmans, and M. G. Bellemare. The value function polytope in reinforcement learning, 2019.
[7] E. Derman, M. Geist, and S. Mannor. Twice regularized mdps and the equivalence between robustness and regularization, 2021.
[8] U. Gadot, E. Derman, N. Kumar, M. M. Elfatihi, K. Levy, and S. Mannor. Solving non- rectangular reward-robust mdps via frequency regularization, 2023.
[9] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-C JIPCComlettenes: (Series of Books in the Mathematical Sciences). W. H. Freeman, first edition edition, 1979.
[10] V. Goyal and J. Grand-Clément. Robust markov decision process: Beyond rectangularity, 2018.
[11] J. Grand-Clément, N. Si, and S. Wang. Tractable robust markov decision processes, 2024.
[12] G. A. Hanasusanto and D. Kuhn. Robust data-driven dynamic programming. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[13] J. M. Hendrickx and A. Olshevsky, Matrix p-norms are np-hard to approximate if 'neq 1,2,iin CoRR, abs/0908. 1397, 2009.
[14] C. P. Ho, M. Petrik, and W. Wiesemann. Partial policy iteration for 11-robust markov decision processes, 2020.
[15] C. P. Ho, M. Petrik, and W. Wiesemann. Robust SiphiS-divergence MDPs. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances in Neural Information Processing Systems, 2022.
[16] G. N. Iyengar. Robust dynamic programming. Mathematics of Operations Research, (0(2):257-280 May 2005.
[17] D. L.. Kaufman and J. Schaefer. Robust modified policy iteration. INFORMS J. Comput., 25:396-410, 2013.
[18] N. Kumar, E. Derman, M. Geist, K. Y. Levy, and Mannor. Policy gradient for rectangu- lar robust markov decision processes. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[19] N. Kumar, K. Wang, K. Levy, and Mannor. Policy gradient for reinforcement learning with general utilities, 2023.
[20] N. Kumar, K. Wang, K. Y. Levy, and S. Mannor. Efficient value iteration for s-rectangular robust markov decision processes. In Forty-first International Conference on Machine Learning. 2024.
[21] M. Li, D. Kuhn, and T. Sutter. Policy gradient algorithms for robust mdps with non-rectangular uncertainty sets, 2024.
[22] S. Mannor, O. Mebel, and H. Xu. Lightnnng does not strike twice: Robust mdps with coupled uncertainty. CoRR, abs/1206.466 2012.
[23] S. Mannor, O. Mebel, and H. Xu. Robust mdps with k-rectangular uncertainty. Math. Oper. Res., ((84):14444155 1509, nov 2016.
[24] S. Mannor, D. Simester, P. Sun, and J. N. Tsitsiklis. Bias and variance in value function estimation. In Proceedings of the Tiesty-First International Conference on Machine Learning, ICML '04, page 72, New York, NY, USA, 2004. Association for Computing Machinery.
11

---

[25] A. Nilim and L. E. Ghaoui Robust control of markov decision processes with uncertain transition matrices. Oper. R 53:780-798, 2005.
[26] C. Packer, K. Gao, J. Kos, P. Krähenbühl, V. Koltun, and D. Song. Assessing generalization in deep reinforcement learning, 2018.
[27] M. L. Puterman. Markov decision processes: Discrete stochastic dynamic programming. In Wiley Series in Probability and Statistics, 1994.
[28] D. J. Smith and M. K. Vamanamurthy. How small is a unit ball? Mathematics Magazine,
62(2):101-107, 1989.
[29] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018
[30] A. Tamar, S. Mannor, and H. Xu. Scaling up robust mdps using function approximation. In Proceedings of the 31th International Conference on Machine Learning, ICML 2014, Beijing, China, 21-26 June 2014, volume 32 of JMLR Workshop and Conference Proceedings, pages 181-189. JMLR.org. 2014.
[31] K. Wang, U. Gadot, N. Kumar, K. Levy, and S. Mannor. Robust reinforcement learning via adversarial kernel approximation, 2023.
[32] K. Wang, N. Kumar, K. Zhou, B. Hooi, Feng, and S. Mannor. The geometry of robust value functions. In K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, editors, Proceedings the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 22727-22751. PMLR, 17-23 Jul 2022.
[33] Q. Wang, C. P. Ho, and M. Petrik. Policy gradient in robust mdps with global convergence guarantee, 2023.
[34] Y. Wang and S. Zou. Online robust reinforcement learning with model uncertainty, 2021.
[35] Y. Wang and S. Zou. Policy gradient method for robust reinforcement learning, 2022.
[36] W. Wiesemann, D. Kuhn, and B. Rustem. Robust markov decision processes. Mathematics of Operations Research, 38(1):153-183, 2013.
[37] H. Xu and S. Mannor. Robustness and generalization, 2010.
[38] C. Zhao, O. Sigaud, F. Stulp, and T. M. Hospedales. Investigating generalisation in continuous deep reinforcement learning, 2019.
[39] R. Zhou, T. Liu, M. Cheng, D. Kalathil, P. Kumar, and C. Tian. Natural actor-critic for robust reinforcement learning with function approximation. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility. transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes]. [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
12

---

The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", it is perfectly acceptable to answer "[No] prooidddd proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). ). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
The paper is theoretical in nature, the claims are reflected in abstract and introduction.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer:
[Yes]
Justification:
Discussed in the last section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-specification asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
13

---

The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Proof in appendix and assumption in the main text.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Paper is theoretical in nature, toyish experiments are just for the sake of completeness.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
14

---

While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c)
If the contribution is new model (e.g., , a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
Codes are publicly available.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
mublic/guidest (aglli/cuuldas//ddeeuuuiisssssss SoodeeSubmsssionool1155.
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https cttt:ps.cc.uublic/// htwbbl/icgggidee//ooooooo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: No training no tests sets.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
15

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: Not applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Provided in the main text.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't It make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The paper is theoretical in nature, hence not relevant.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
16

---

If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper is theoretical in nature, hence not relevant.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploymentt of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper is theoretical in nature, hence not relevant.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
17

---

Answer: [NA]
Justification:
The paper is theoretical in nature, hence not relevant.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's ' creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper is theoretical in nature, hence not relevant.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper theoretical in nature, hence not relevant.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
18

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper is theoretical in nature, hence not relevant.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality the research, declaration is not required.
Answer: [NA]
Justification: The paper is theoretical in nature, hence not relevant. LLM is used for only writing and editing only english text.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to LLM policy hbtpps////errrpocco/////ooooeroo for what should or should not be described.
Notations and Definitions
For set S, |S| denotes its cardinality. (u, 1) = E.ess u())u(s) denotes the dot product between functions u, S + R. ||:| (E))(s)))) denotes the g-th power of Lp norm of function v. and we use ||ы|| ||l p and ||||| ||0|2 shorthand. For Rla, 2 0, Vc, Ecec G. 1} the probability simplex over C. var(-) variance function, defined var(u) (v()(((s) F. where Exegr(s) m(x) is the mean of function S Rd. 0, denotes all zero vector and all ones vector/function respectively of appropriate dimension/domain. 1(a b) ;= if 6. 0 otherwise. is the indicator function. For vectors u, 1(u 2 v) is component wise indicator vector, i.c. 1(u 2 (x) = 1uu(x) 2 v(x)). B = {(a b) 6, E B} is the Cartesian product between set A and B.
C. Ac == {a +
[S]
A Related Work
Rectangular Robust MDPs. In the literature, the sa-rectangular uncertainty is very old assumption
[66 255] (36] introduced s-rectangular uncertainty sets and proved its tractability, addition the intractability of the general non-rectangular uncertainty sets. The most advantageous aspect of the s-rectangularity, is the existence contractive robust Bellman operators. This gave rise to many robust value based methods [14]
33 Further, for many specific uncertainty sets, robust Bellman operators are equivalent to regularized non-robust operators, making the robust value iteration as
efficient non-robust MDPs 7 34
20
There exists many policy gradient based methods for robust
19

---

Table 2: Useful Notations
Notation
Definition
Remark
P. g
1 + +
Holder's conjugates
p
dp
Standard deviation w.r.t Lp norm
0", ,". .VP,
- 71-pp-)-11 RR
Value function
D5, D
(1 - --pp)-1
Occupancy matrix
d", ...p
1ºa (I - -P-a-
Occupancy measure
u U, U2
Uncertainty sets
MDPs, relying upon contractive robust Bellman operators for the robust policy evaluation 35 18
Further, [9 31 try refine the process, and directly get samples from the adversarial model via pessimistic sampling There exist other notions of rectangularity such as k-rectangularity [23] and t-rectangularity [10] which sparsely studied. However, [11 shows, the theses uncertainty sets either equivalent to s-rectangularity or non-tractable.
Non-Rectange Ron-Rectang Reward Robust MDPs. Policy evaluation for robust MDPs with non-rectangular uncertainty set is proven to be a Strongly-NP-Harn problem [36], in general. For a very specific case,
where uncertainty is limited only to reward uncertainty bounded with Lp norm, [8] proposed robust
policy evaluation via frequency (occupation measure) regularization, and derived the policy gradient for policy improvement.
Approximate Policy Evaluation for Non-Rectangular Kernel RMDPs. 21 provides the following two policy evaluation methods for robust MDPs for general uncertainty sets.
Langevian dynamics based Algorithm 3.1 of 21 This Langevian dynamics based Markov
Chain Monte Carlo method solves the robust policy evaluation problem to global optimality with arbitrary small accuracy The iteration complexity of the algorithm is O log ) which exponential in the dimension of the uncertainty set q. The algorithm well suited only for small dimensional uncertainty. For general case the dimension g S2 A can be very large, this makes the algorithm very computationally inefficient as expected from the hardness result from [2].
CPI sytle Algorithm 3.2 of 21 (presented in Algorithm This CPI based algorithm computes the robust policy with iteration complexity of O with an accuracy 62 + 6p), where 5ą is mismatch-coefficcn
and 8p is measure of non-rectangularity of the uncertainty set. However, the mismatch coefficient may not exist without an irreducibility assumption (Assumption in (21),, moreover even under Assumption 1, the constant 6 = ((23) can be exponentially large for ladder MDPs which have large diameter (more details provided below). In addition, the von-rectangularityy constant 8p can be as large as O (V Hence, a large d20p T-y makes the bound meaningless, as the sub-optimality is upper bounded by I To summarize, this approach is efficient only for small diameter MDPs and almost rectangular uncertianty sets.
Our Method: We provide robust policy evaluation method for L2-robust MDPs with an iteration complexity of Olog !) and with an accuracy e. This is possible as we showed that the NP-hardness result of [2] doesn't apply to this case.
We don't require the irreducibility Assumption of [2I] which can be very limiting. Further, the Lp robust MDPs may have very large tolerance ōzōP hence the Algorithm 3.2 from 21 is not applicable.
Difficult MDPs for Algorithm 3.2 of [21]
20

---

MDP with high mismatch coefficients: Consider an MDP with only one action and state-space {s, I <is f S}. Let s1 be the starting state, Let the kernel be defined Pa(S (1+1,8) (4) 2, (2(s(ss)) =
Now let the uncertainty set be P {P& E [0.4,0.6), Note that for this case, log( 2 (
log( (Po.4 O(S).
High non-reetangularity coefficient This is inspired from the fact that
max | bEB,
max a, b max b
where B B(, 1) is unit ball around origin, and B, [-1, 1) is the smallest rectangular cube containing B. Then choosing
(n)" l", we have maXbeB, a, >= /ni and maXieg < a, b >= 1. This implies 2 /n 11 From definition in page 11 of [21], we have
óp
max PEP;
< VV,
mIX < VV,
PEP
where Py is the smallest s-rectangular uncertainty containing P. Here, P E RSAXS this suggests öp can be of the order of (S)A).
The discussion is summarize in the Table 1
Algorithm 2 CPI Algorithm 3,2 of [21] for Robust Policy Evaluation
Input:
Nominal kernel P, policy æ, Uncertainty u.
while not converged: n = n + do
2:
Define f(P) = 1 E (0 where A7(s, a, 8') : P(s')s,a)u7(()) - (()"),)))))))
3: Compute P E arg minpeu f(P).
4: Update the estimated worst kernel: Pa+1 = (1 - an) + anp
where an
(1-7)²
f(P))
47
5: end while
Return:
Robust return JP
Robust Policy Gradient Methods. The absence of contractive robust Bellman operators renders the development of value-based methods for robust MDPs particularly challenging. Consequently, policy gradient methods naturally emerge as viable alternative. The update rule given by:
-k-1
Proj PEn
Tk
17k
V
x
where JpC J S c and learning rate уІ
O
This approach guarantees convergence to V
global solution within O(E iterations
33
However, this update rule depends on oracle access to the robust gradient, which is highly challenging to obtain because robust policy evaluation is an NP-hard problem.
B On the Non-Rectangular Uncertainty Sets
B.1 Why non-rectangular RMPDs
Proposition B.1. Let Let Un be the smallest sa-rectangular set and s-rectangular set containing
U2 then
vol(U2)) O(c-SA) and vol = (c, vol(Ug)
vol((1a))
where vol(X) is volume of the set X and c., Csa are constants.
21

---

Proof. Volume of n-dimension sphere of radius is car" where 15
8ST
28
And to cover an
n-dimension sphere of radius r, we need a cube radius 2r whose volume (2r) R. Hence the first result vol(((,)
vol(1 = ((2 immediately follows.
Now, the volume of the set of X = x, where X, is an A-dimension sphere of radius then the volume of is (car)s. And the volume an SA dimensional sphere c5 where Hence the ratio of their volume is O((c)))), implying the other result. O
lim Cn + 0 288
B.2 Complexity
Reduction of Integer Program Robust MDP
0/1 Integer Program (IP): For g. Z", S F,F mX
3r E 10, 8.l. Fx Sx and s
is a NP-Hard problem 19. [36] which reduces into the following robust MDP.
Robust MDP:
1. State Space s {b3, 19. 6f | -, .,... nn {eo, T}, where is terminal state.
2. Singleton Action Space: A= {a].
3. Uncertainty set: U = (P& & [0, F5 g)
4. Discount factor E [0, 1); Uniform initial state distribution μ..
5. Big reward M 7AA Σ where << helps in rounding. 2
6. Transitions and rewards illustrated in Figure
Es:
Esc
Si
Ea/nt mey
I 1--ii
1:0
Gei
Sni
Sim E/nc
Set
1- SLt
Figure MDP Pg. and R(Figure of (6
Robust policy evaluation proven to be NP-hard for general uncertainty sets defined as intersections of finite hyperplanes [36]. Specifically, robust MDPs with uncertainty set Uhard == [P&|FE < g. e [0, 1]m}} where Pe specially designed kernel with ladder structure with only action (effectively no decision) and terminal state [36).
Note that PC g imposes m-linear constraints Uhard while allow only one global constraint on Up. Observe that U1 [P& T < 9. [0, 1]m) is the nearest uncertainty to Uhard as both have polyhedral structure. This restricts the class of the IP programms have number of constraints m 1 and the row of F to be all ones. In other words, only IP programmes that can be reduced to 24 are of the following form: For for,cE Z". S..EE
E Z.
Br E (0, s.t. 1 and c
Solution:
Case g then no.
Case 2) If g 0, 2 0 then yes and 0,5 then yes.
22

---

If > 0 then compute the sum of g smallest coordinates of and this sum is less/equal than Ç then answer is yes, otherwise no.
Further, for IP to be reducable to robust MDPs, the diameter of the uncertainty (max p' eUhara || P 1'111 25) has be large for the practical settings. Loosly speaking, robust MDPs with a Up uncertainty have one global constraint and small radius 3, which corresponds to Knapsack Problem with small budget (IP with one constraint and small g) which are much easier solve 9..
We can thus conclude that the hardness result of 36 doesn't 't apply our uncertainty case.
B.3 Decomposition
Proposition B.2. Non-rectangular uncertainty Up can be written as an infinite union of sa- rectangular sets Upa as
Up BEB
where B = 16 E |1b| S B}. Note that all of them share the nominal kernel P.
Proof. By definition, we have
Up = (PI P
Plpp 3, Σ p(s =
(3)
8¹
= (PI Σ
1PP0 N0 Psal b S BP, Σ P(s' (,0)) =
(4)
8,0
= {P]
S 8 PPaa Poa 1b bla P = =1}
(5)
8,0
(P] Σ
sa < 8 |Pa Pea 1B S Usay EP(((os = 1}
8,4
[P Poe - Peal < Ur P(d'ss,0)) =0 =
Σ,,o b% SBp,
(1)))
(8)
bEB
C Additional Results: Robust Policy Improvement
In the previous section, we identified that the worst-case kernel can be expressed rank-one perturbation of the nominal kemel. Leveraging this structure, we developed a method to efficiently evaluate the robust policy. This method also computes the perturbation (5k and, consequently, the worst-case kernel.
Using the computed worst kernel, can directly evaluate the gradient with respect to the policy. This enables policy improvement through gradient ascent, as detailed [33]:
ma+1 proj n. 1/s V
where P., is the worst-case kernel estimate for the policy Tk. This method guarantees global convergence with an iteration complexity of O(e-1) 33].
Alternatively, the policy gradient can be derived for the approximate perturbation, shown in the result below.
Policy Gradient Theorem Once the worst kernel for policy is computed using Algorithm I the policy gradient can be used to update the policy. Alternatively, the following policy gradient theorem provides a direct way to compute the gradient:
23

---

Lemma C.1 (Approximate Policy Gradient Theorem). Given transition kernel P = P 33k return is expressed as:
3k the
1k Jp: Jū #1 (kk uz))
and the gradient given by:
J.JØ = d3 QR 7 k u d= nk 0
Jz (k: 1 " >k oz
o (* D Uu + + 13: 23
Q3
u2)) Q3.
Proof.
The expression for the return follows directly from the inverse matrix theorem, shown in 18. The gradient is then derived using the policy gradient theorem [29 in the format used in [1)]
kT D R 2. = QR Y 7 D=
11 D
di
Q7
7 + yk D B
d Q7
+ + 1 D k D R
k
о Q3:
(1 + 7k D )
k u
Jz D
J3 (N: (TTT))() (** D
= d QR 9 + k 8
d" Q3
QR 72
(1+ n 17)2 Q
1 7k o/
The main advantage of this policy gradient formulation is that terms like Jg. vg. Q along with the nominal terms JR. R QR. can be efficiently computed using Bellman operators and bootstrapping techniques.
Interpretation of Gradient Terms The approximate policy gradient reveals the interplay of various components in robust MDPs:
The first term, d' o Qh, represents the nominal policy gradient, emphasizing actions with high rewards.
kJvj rp dm Q7. discourages policies that place significant weight on
The second term, TT high-uncertainty Q-values, scaled by the vulnerability to adversarial actions.
The last two terms, while more complex to interpret, further reflect the intricate dynamics of robust MDPs.
Robust Policy Gradient Algorithm The robust policy gradient algorithm (Algorithml 3 converges to an e-optimal policy within -teiittrtooonn
Theorem C.2. The robust policy gradient method from 33 achieves global convergence within O(e-t) iterations for the policy gradient step. Algorithum computes the worst-case kernel in O iterations at step n. The total iteration complexity for global optimality is O(e
Algorithm 3 Jemplos a double-loop structure: the inner loop (Algorithm) D computes the worst-case kernel for fixed policy, while the outer loop updates the policy using the derived gradient. An actor-critic style alternative, where the kernel and policy are updated simultaneously, left for future work.
Algorithm 3 Robust Policy Gradient Algorithm
I: while not converged: n + 1 do
2: Compute the worst-case kernel P P _K for policy using Algorithm i with tolerance
<= n
3: Compute the policy gradient G using Lemma C.I G,
4: Update policy: л +- proj
5: end while
24

---

Extension to KL Entropy Uncertainty Sets. For the KL uncertainty case, the worst kernel is given by ugg. (T - y A where A is diagonal matrix [31] If we can invert this matrix, then its possible to build upon it. We leave this for future work.
D Helper Results
Proposition D.1 (Sherman-Morison Formula [4))) IfA E Rux* invertible matrix, and E RR,
then the matrix A + wo= invertible and only if + v" A + 0:
A "v A' A-1
(A + uv²) A-
2 A-tu
Proposition D.2.
0g(v) ::nn= w1 11
k $1,17=0
min
||
Proof. Follows directly from Lemma J.1 of 20
Proposition D.3. For any vector |a>|| 1, we have
2 V2
where EV is positive quadrant.
Proof. For any vector ||a||| 1, we have
| + || 1|= 2
And Projay (x) x4 and Projæy (-x) r- the follows.
Proposition D.4. For | and kod 0, we have
1 1+nk² (1 71--P)--66 2 0,
for all |bblp S 3,62 0.
Proof. This true from the Sherman-Morrison formula as J P-eeT is finite, hence the denominator must be strictly greater than zero.
E Dual Formulation
Lemma E.1 (Sa-rectangular Duality). For the sa-rectangular uncertainty set = Uzz0 (3) with radius vector 3 E T xAA the robust return can be written as the following optimization problem,
1r7 D D BO D7 R
J J 7
max ITT
1 1+>k7 D 3
where 85- = En (als))a..
Proof. From 18 we know that the worst kernel pa (g) for the uncertainty set (450(3) is a rank one-perturbation of P. In other words,
P (3) = P + 3k
25

---

for some & R satisfying || = 1 and 17 = O. This implies that it is enough to look for rank-one perturbations of the nominal kernel P in order find the robust return. That is,
Fipz = min JP
P (3)
min P= P=P+0k" -
J7.
(looking only at rank one perturbations)
min
4 D
P=P+0k" 1111=
min
11 -7pp)-11 RR
P=P+ 11kll,,111,111111111
(1 TP= + + I
=
min 1
|
1 B D R
J
max |||||
1,11
1+ 1 D
Lemma E.2 (S-rectangular Duality), For = Ug, the robust return can be written as the following optimization problem,
, 3r8 ) (k,
1 yk? DF BT J= -7 Se.11.1 $1,
min
where D = (1- d= = 1¹" D and vr =DRR..
Proof.
Jug(3)
[PP,-(P), ST J
min
= min
min
JB
Σ. 8 S8 PP (P).ull Bou. ITP P.n
= min
J (B)
Σ. 8 <05
D
min
J -
max
Σ. Sh 500
1111
1 gKI Ba
3T D R 1 kkt D 8m
J
max 80 1
The above result formulates the robust return in terms of nominal values only for the first time. This implies the robust objective can rewritten dual form as
DR
Júg
max min DED kEK
1 DRT 7H4² D6
D6
1 RkT D6
where D (1-1--P)) II) K (k R ||ballp I 3.).
| 1,
0}, and B = {b R
Comparing the penalty term from the previous results in 20 18 the dual formulation can be written
as
1T DR
Jig max max min DED KER
[ up D3
1 +T D D
where 35 -1TTall0
Surprisingly, the optimization here looks as if it is optimized for the same value of 3 = maxy, 8P, 5.P E. (a)ss)B.. B.llTelly for all values of feasible k. This suggest that the ad- versary payoff is maximized by maximizing the expected uncertainty in the trajectories.
26

---

Lemma E.3 (Non-rectangular Duality). Foru = Up the robust return can be written as the following optimization problem
(k: VTT) 1 (k,, 0z)
Jü = min where D = dx 122 D and Tr D Rd.
Proof. Now,
((p(() ||P -II- 1 Pm
min
Jp
110 see || (P)a-())alll P Jp
min
min
min
Jug=(9)
||8 Dee
D R"
J - | 55
min
1 k=
1 D Ba
p D D 1+ D=
max | 100p_5_111)
The above result formulates the robust return in terms of nominal values only, for the first time. Comparing with the existing result, we get very interesting relation:
T U
Tg (
max ||||| 11 +
(10)
++kk" 03
where UI (1 (11--P
The LHS is a robust quantity (variance of the robust return) which is express in the terms of purely nominal quantities. This is the simplest of all such relations. We believe that the above relation can help in theoretical derivations and experiment design but not exactly sure how yet.
E.1 Intuition on the Adversary
sa-rectangular case. We know that the a (v represents the penalty for robustness, expressed as:
Jk = J - (dd" )3,
Understanding how a(1)) arises provides insight into the behavior of the adversary described in 10). Furthermore, if P === P BK.T. then:
kT
= (d"
U
7ke oz
Here, k represents the direction in which the adversary discourages perturbations in the kernel. The optimal direction & chosen by the adversary maximizes the objective in (1O).
s-rectangular uncertainty sets. Now, we turn our attention to the coupled uncertainty case.
Lemma E.4. For l = Ug. the robust return can be formulated as the following optimization problem:
(d 8 (k,
J J -7 |1 Se. | 11. 1..51,111 (1, 1 7k D=
min
where D (1 (1-7pp)-1 d= nrt D.. and '. D R
27

---

Proof. The proof follows similarly to the sa-rectangular case and is detailed in the appendix. The key additional step involves decomposing the s-rectangular uncertainty set Un into a union of sa-rectangular uncertainty sets a
By comparing the penalty term from previous results
20 we obtain:
(d) (T²
Σ (s) E. 8 S |
max
LITk 1 1 7k" D 8
This relation is interesting as it connects the robust term on the left-hand side (LHS) with the non-robust terms on the right-hand side (RHS).
Interestingly, the optimization here suggests that the adversary maximizes the expected uncertaitty in trajectories, as the same value of $5 max She S0g En (als)) B,1|Tsll, appears for all feasible k.
F Robust Policy Evaluation
g(3) F(A) = maxxec ( (g(a)) Ah(x)) ), we have
Proposition F.1 For X = max Ec h(x)
F(X*) = 0 and f()) 2 0 + X 2 A.
Proof.
If F(A) then
Er s.t. g(z) - Ah(x) 20
Er s.t. g(0)
2 X,
(as ((sh(()) > 0 for all x))
h(x)
g(z)
max 2EC h(r)
2 X.
If F(A) < 0 then
9(x) - Ah(x) 50.
VEEC
g(x)
X,
(as h(r)(()) > 0)
h(x)
(x)
max
SA
2EC h(x)
If F(A) 0 then X max
g(z) h())
implied from the above two items.
Lemma F2. The robust return can be expressed as
Jū = J X3
where the penalty X" is a fixed point of F())- Furthermore, X* can be found via binary search as F(A) > if and only if X > X3, where F(A) maxte ||E E 7
=1" R D AD" H", and R".
Proof. We want evaluate the following
A DD D 1 7kt Da
max BEB,REK
f(x) This is of the form max, g(z) if and only if X" A, where
Then according to Proposition E.I
we have f(x*) 0 and f()) > 0
28

---

f(A) = max BEBRAEK
T7 b
1(1 + t D*b"))
max BEB.KE
DTD A,
11
max NEB
TT
C² X,
(from Proposition G.6
S
11
max
C >
(Holder's inequality)
where A D" :n (A5 AD= ) H
G Evaluation of max x Ey
In Algorithm D
we need to solve
RT Eb
max 2p S. <k, 13,1>=0
sub-routine which is 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. As we see later, for L bounded uncertainty set, provided provably efficient robust-policy evaluation method that provides the solution in the close form. For p = 2, we provided heuristic algorithm that works well in practice and also generalizes well beyond theoretically applicable uncertainty radius B. However, we believe it is possible provable solve this sub-problem via standard methods as second-order cone optimization quadratic programming, but we are not aware of the exact positive nor negative result about this case. For p co, non-rectangular uncertainty set degenerates to sa- sa-rectangular one, which already efficiently solvable. And for other p, we are not sure if the efficient solution exists.
G.1 For p 1
For uncertainty case Ui bounded by Lball. We have the close-form solution to our sub-problem. Lemma G.1.
A Eb
max E(i, Mlspp
where |a<laap max,, min: ds is span-norm.
Proof.
max IMISSI 0
T Eb
&TEb
max 11,60
max
kT
Eb
(11)
11
S 12
max
Eb lep.
(from Preposition G.2
(12)
max E(, 1lap:
(from Preposition G.3
(13)
Notably, the optimizers ks,", b* are given
(*(1) = 1(i it),
where i" = arg max, |[ and
(imaz) (immn) 5"
where imaz = arg maxx((Eb)(i) and imin = arg min, (Fbb) (1).
29

---

Proposition G.2.
1 (1 (k, = ||
max
where |00|aa mux, di ming ai
2
Proof. Let E R", then we have
max (1
Σ ka
max |kll (1,(1,
Σ
lss +
Σ
(14)
i
max
kya +
Σ
(15)
Lanyo R== Liee <0 1
max; T2 min4 24
(16)
2
Proposition G.3.
max 1,
Bbllep max [E,, 1)lssps
where |arlssp
min,
Proof.
max
Ebllep
max
E(,, E(,jibblleep.
(matrix multiplication)
(17)
11
$ max
by (())())))
Cl sp satisfies triangle incquality)
(18)
11
max/| [( slpp
(maximization over b).
(19)
Further, max, || ((, eppp is achievable by taking to one-hot vector at index that maximizes max;| E(,, 1) Hence, we get the desired result.
Proposition G.4. For 1, F can be evaluated in closed form as
F(A) = 7 (a)s (s)o" - >D" (:))))p
where || MAX, P.-min
Proof. From Lemma G.1
we have F(A) = max | [ (8, ())))))ssp And from definition, we have
E = 7 D" D xD H" Further,
(D'R' (s, - H (s',
(20)
-()(())()))) (((())((())))a())))
(21)
(22)
Further,
(D*H*) ) (8, = - (1.
(23)
Finally, using |0]|ssp = maxijj 2.-I, we get the desired result.
30

---

G.2 For p =
For p 2. we proposed heuristic spectral Algorithm 2, solve the above sub-problem. And as the Figure 6, Figure and Table 3 shows the superiority of its performance over numerical methods (scipy). Further, we showed the previous response that this method yields much better performance than random search even when uncertainty radius 3 is big-enough.
For other p ş 1, problem without positivity and mean-zero constraints,
not sure if the above sub-problem is efficiently sovable not. As similar
Ap- =
max ||
6 Ak
max | A0AAll P11
is very well studied problems, and several negative results are known in the literature for p + 1,2, oo 13
Proposition G.5. /Orthogonality Jquivalence]Let K. -K | S 1,1 0}, and W
(KT -5) |Al|2 11. Then we have,
K= W.
Proof. Now let l: E K. then (T 11 T E W. Now the other direction, let E W. then (h:T (I 11
3 ) 1) by construction and [ - Il s ||k||2 s 1, this implies
kT 11
-)) E
The above result implies that
k- Ab
ET Ab
max S1,
max K
max BllSS
AT Ab,
(as K.
W from above Proposition G.5
11T
max M111211
T
)b,
(def. of W).
S
Further, have equivalence of optimizers
11T A Ab = (b",
11T
arg 1I
}k²) 1
arg max
k (T
S A
|| $8
Proposition G.6. The solving of
11
max | 0.1b
RT Ab, is equivalent to
max [k]]=_1||bbssp
1 TT
S Ab.
las
Proof. Directly follows from the proposition above.
G.3 Eigenvalue Approach (Spectral Methods)
This section focus on deriving a spectral method for solving the optimization problem:
max ||
|| |x]l2,
where A E _2xx, Compute ATA A. We perform cigenvalue decomposition of ATA A:
A A VAVT. where diag(A1, (2, ,,)...,,,))),) An) (eigenvalues) and V = [U1, U2 Un] (eigenvectors). Further, WLOG
A1 2 ..,,, and
||u+,
Vi,
| |I
where ust max(u; 0), oi = min(v, 0) denotes positive and negative parts respectively.
31

---

Zero Order Solution:
fo ||Au1ll: 1|-
First order solution:
f1 max| Autll:
Second order solution:
(Lu; + (1 - f)
f2 max max I|A se(0,1]
[ttu; + (1 )) 11-
Third order solution:
114 (ru, + su, + tux) [(ru; + su, + tuk)
fo max
max
Upper bounds on max |11
Zero order upper bound: X
First
order
upper
bound:
Ex Aeci,
where
(og Uz)
(0 (o,, u,)
1
j=1 (2 u,)2
if
(e= (e, u,)²
1,
i-1 Ej=ı (u,,,,)
2,)2 1. 1.
otherwise
Lemma G.7 (Zero Order Approximation). The highest projected eigenvector u half-good solution, i.e.,
"7
is at least
|0
A1 2
|
|| |
11
Further, if A is rank-one then it is exact, i.e.,
||uull
max 11,2
||Ax||2.
Proof. We have |ilj
from Proposition
D.3 Let (vi)=
Eiore, where o; (u, vz)
V2
[+))+
we have
T AT Au Au
Eani) Σ Aariyy > orvi)
oork Σ
(as 2 are orthogonal)
= =bro? + Σ Noo
iff
2 2110 + Σ Ano
(as d2 2 As.
1
= =1rr? An - (1-
(as Σ
o. 1)
1
> (A1 + An),
(as 2
2
v2
Rest follows.
Proposition G.8 (First Order is Better than the First).
A
| 1| 2 max Noo,e 2
where j E arg max, Aety, u,) and σ; = (er, us) >
1
v2
32

---

Proof. Let uj
(1/)+
Ei o. Us, where of {ug, vi), we have
[(,))+
uz AT Auj Eo of Axveof of))
Σm(o!)
(as oj are orthogonal),
2 {)(o{))
max A:(o;)
(by definition of j).
Rest follows.
Proposition G.9. Second order solution J2 = maxi, max || equal maxiallaS1, A when A is rank two.
(1-+0--)))))
[1-20,]1 || is exactly
This approach is computationally efficient but may not always yield the exact solution, especially when multiple eigenvectors significantly contribute to the optimal x.
The intuition behind this approach is that the matrix A A can be decomposed into its cigenvalues and cigenvectors, representing the principal directions of the transformation applied by A. The eigenvector corresponding to the largest eigenvalue provides the direction of maximum scaling for A. However, since the solution is constrained to the nonnegative orthant (x: 2 0), we adjust the eigenvectors by only considering their positive parts. The method identifies an approximate solution u by selecting and normalizing the positive part of the eigenvector that contributes the most the objective function.
Algorithm 4 Second Order Spectral Approximation for max | ||
1: Normalize the positive part:
U4
| 11
2: Compute scores for all eigenvectors:
Score; = Accus, u.).
3: Select j = arg max, Score,,
4: Output: Approximate solution u, uut /llut [|2 and approximate maximum value || 122-
Notes
This approach is effective when the largest eigenvalue $1 dominates the others. It approxi- mates the solution by leveraging the spectral properties of A A.
The result might not be exact if multiple eigenvalues contribute significantly, as the approach considers only the contribution of individual eigenvectors.
G.4 Experimental Verification
This section describes three different methods for solving the optimization problem:
max
||
||
where E Ruxa, The methods are compared in terms of their computational efficiency and the quality of their solutions.
33

---

G.4.1 Brute Force Random Search
The brute force method randomly samples vectors r E IK" from the nonnegative orthant, normalizes them to satisfy ||>||| = 1, and evaluates | for each sampled vector. The steps are as follows:
1. Generate N random vectors 2; 2 0, i I....
2. Normalize each vector to unit norm: I; +- z:/l =z
3. Compute |A; || for each vector and select the maximum value.
This method is simple to implement but computationally expensive, as it evaluates for a large number of randomly generated vectors. See figure 6
Brute Force Random Kernel Penalty Time
Optimal Velue Random Kernol
0.08
Penslty ( J0,1 (Bigger is Better)
0.06
0.04
100
200
300
500
600
Time (sacl
Figure 6: Random Kernel Guess takes exponentially long time to converge. While Algorithm 1 only
took 0.14 find the optimal value.
G.4.2 Numerical Optimization (Seipy Minimize)
This approach uses numerical optimization to directly solve the problem:
max 2
||Az||2-
The optimization problem is formulated as:
min x
||x1|2,, subject to ||~||| S 1 and x 2
Steps include:
1. Define the objective function -I| 12-
2. Impose constraints: ||/||| < 1 and 2 0.
3. Solve the problem using scipy opt.opiiimii omtimize.... wtt.:ptt.....iiiiiiiei.p.ee minimize, with an initial guess
This method provides the exact solution computationally more expensive than the spectral method.
G.5 Comparison Metries
The three methods are compared based on:
Optimality:
The maximum value ||Ax||2 achieved by each method.
Time Efficiency: The computational time required by each method.
34

---

G.6 Results and Observations
The following plots compare the performance of the three methods:
Optimality Plot:
Shows that the maximum value obtained with scipy.minimize is slightly better than our spectral method, while random search performs poorly.
Time Efficiency Plot: Illustrates the that scipy. scales much poorly with dimension, while our spectral method is way faster than both methods.
Optimality
Random Search
Spectral Method
Scipy.minimize
20
Values obtained
25
50
75
100
125
150
175
200
State Space Cardinaltiy
Figure 7: Comparison optimality across methods.
Time
2.5
Random Search
an Nardth
Spectral Method
Scipy.minimize
2.0
Time taken
1.5
1.0
0.5
25
200
State Space Cardinaltiy
Figure 8: Comparison of computational time across methods
35

---

Optimal values attained
Time taken
π
Random
Spectral
minimize
Random
Spectral
minimize
10
4.10
4.45
4.46
0.12
0.0007
0.005
20
5.14
6.71
6,82
0.19
0.0003
0.01
50
9.23
11.59
11.93
0.25
0.0007
0.03
100
11.95
16.44
17.19
0.31
0.001
0.28
200
15.74
22.1
23.68
0.44
0.004
2.1
300
19.32
28.58
29.73
0.57
0.012
8.19
500
24.46
36.56
38.47
0.83
0.209
43,49
1000
33.91
51.64
54.25
1.38
0.171
313.6
Table 3: Attained Values and Time Taken.
G.6.1 Parameters of Experiments
The experiments were conducted evaluate the performance of three methods- brute force random search, eigenvalue heuristic, and numerical optimization solving the problem:
max
State Space Cardinality and Random matrix Generation
State Space Cardinality (n): The dimension of the problem, denoted by n. represents the state space cardinality. In the experiments, n varied from to 300 to analyze the scalability of the methods.
Matrix Generation: The matrix A E R=x= was generated random matrix with entries sampled from a standard normal distribution:
Aij N/O, 1), 1..=1..... .,..,,
The same random seed (seed 42) was used across all runs to ensure reproducibility.
10000 random vectors were generated for Brute Search Method.
Process of matrix Evaluation The goal of the experiments to maximize ||Ax||2 under the constraints ||>||e S 1 and 2 0. The matrix A is evaluated by:
1. Generating random vectors x E R for the brute force method.
2. Computing the spectral decomposition of A A for the eigenvalue heuristic.
3. Defining and solving constrained optimization problem for the numerical optimization method.
The results, including the optimal values and computational times, are recorded for each method.
Evaluation Metrics
The performance of the methods was assessed using the following metrics:
Optimality: The maximum value ||Ar|| obtained by each method.
Computational Efficiency: The time taken by each method to compute the result.
Scalability: The behavior of the methods as n increases.
This systematic evaluation ensures fair comparison of the three approaches across varying problem sizes.
Hardware and Software Specifications ware and software setup:
The experiments were conducted on the following hard-
Model Name: MacBook Pro (2023 model).
Model Identifier: Mac14.7.
36

---

Chip: Apple M2 with 8 cores (4 performance and 4 efficiency cores).
Memory: 16 GB Unified Memory.
Operating System: macOS Ventura.
Programming Language: Python 3.9.
Libraries Used:
numpy for numerical computations.
scipy for numerical optimization.
matplotlib for generating plots.
time for recording computational times.
The experiments were designed to ensure reproducibility by fixing the random seed (seed 42). Computational times and results are specific to the above hardware configuration and may vary on different systems.
H
Convexity D
H.1 MDP Configuration
define an MDP with the following parameters:
State space size: S 3
Action space size: A =
Discount factor: 7 = 0.9
Random kernel P. random reward R, seed 42.
Compute the set D (D* [x] with 10 millions random policies x
H.2 Dimensionality Reduction via PCA
Given the high-dimensional nature of the D 4 representations, we apply Principal Component Analysis (PCA) extract meaningful structure.
We retain the top 10 components to capture the dominant variations in the dataset.
The explained variance ratio is visualized to assess how much information each component retains.
2D projections of the first few principal components are generated for visualization.
H.3 Random Linear Projections
To further explore the geometry of the occupancy measure set, we apply random linear projections of the high sich-iimensional data:
2D Random Projections: The data is projected onto randomly chosen 2D subspaces.
37

---

A
Figure 9: 2D PCA projections of the first 5 components.
A
Gramial
Figure 10: 2D Random Projections of the Data.
I Experimental Evaluation: Single MDP Comparison
To assess the performance of our proposed binary search algorithm for robust policy evaluation under L2-norm bounded uncertainty, we conduct a series of experiments comparing it against existing methods on fixed Markov Decision Process (MDP) instances. The primary objective is to evaluate convergence speed, accuracy relative an estimated worst-case value, and consistency across different problem configurations. More details of these experiments along with others can
38

---

be found in the appendix. and codes are available at https: hoppon science/r Kernel-Robuse Babbust-R--B744 B
I.1 Experimental Setup
Algorithms Compared We evaluate the following algorithms:
Our Method:
The binary search algorithm presented in this work, which leverages spectral method for computing the key bisection function F()).
2. CPI (Crank-Wolfe)) The Conservative Policy Iteration algorithm adapted from 21 for general robust policy evaluation.
SA-Rectangular L2 VI: Robust Value Iteration for (s.a)-rectangular L2 uncertainty, common baseline representing a structured relaxation.
4. S-Rectangular L2 VI: Robust Value Iteration for (s)-rectangular L2 uncertainty, another structured relaxation.
Benchmark Generation For each MDP instance and policy, we establish empirical benchmark for the worst-case robust value. This is achieved by sampling 1,000 transition kernels from the L2 ball of radius 3 centered the nominal kernel Prominat Each sampled kernel is projected ensure remains a valid stochastic matrix and stays within the L2 ball. The policy я is evaluated for each sampled kernel, and the minimum value obtained across these samples, Vimin reference robust value.
benchmark. serves
MDP and Policy Configuration Experiments are conducted on randomly generated MDPs. For each trial, nominal transition kernel, a reward function, and a uniform initial state distribution are generated. A fixed, randomly generated stochastic policy is then used for robust policy evaluation by all algorithms.
Experimental Configurations Two main sets of single MDP comparisons are performed:
1. Varying State Space (S): S E {10,50, 50, 100, 200, with actions A 10 and uncertainty radius 3 = 0.01.
2. Varying Uncertainty Radius (3): B {0.005, 0.01, 0.05, 0.1}. with state space $ 100 and actions A 10.
The discount factor is = 0.9. Algorithms are run until convergence (tolerance of 10 10-6) or a maximum iteration limit (100).
I.2 Results and Discussion
present the convergence behavior of the evaluated algorithms on representative MDP instances for the varying state space and varying uncertainty radius configurations, respectively, Each subplot shows the estimated robust value versus algorithm iterations. The horizontal dashed line indicates Vimia benchmark An algorithm's final point marked with star (+) if its estimated robust value converges to within 10-6 of Vminn benehmark
Figures 1T and 12
Observations
Convergence Speed and Accuracy Our Method: Across all tested configurations, Our Method consistently demonstrates superior performance. It generally converges in fewer iterations and achieves a final robust value remarkably close to V Vonnchaark as frequently indicated by the star marker. This suggests efficient and accurate identification of the robust penalty X
The CPI algorithm typically converges but often settles value slightly higher (less pessimistic) than Vainn subproblem, the version tested, explores extreme points the set of all stochastic kernels, which may not always precisely align with the worst-case kernel strictly within the La ball.
CPI Performance:
Vonnhbarkk While providing robust estimate, its
39

---

Figure 11: Convergence of robust policy evaluation algorithms for varying state space sizes (S).
Algorithms whose final value is within 10 of the benchmark are marked with star (+)
Figure 12: Convergence robust policy evaluation algorithms for varying uncertainty radius (8).
Algorithms whose final value is within 10-6 of the benchmark are marked with star (+)
40

---

Both sa-rectangular and s-rectangular Lg VI methods consis- tently converge to robust values significantly lower than those found by Our Method, CPI, and Vinia benchharkk This highlights the conservatism inherent in rectangular relaxations when dealing with non-rectangular uncertainty.
Rectangular Relaxations:
Consistency Across Setups: The advantages of Our Method in terms of faster and more curate convergence are maintained robustly across different state space sizes and uncertainty radius.
41

---

1.3 Performance with large uncertainty radius.
Our theory limited only small enough radius, however we show that our algorithm works with bigger radius well. Experimental Setup
Environment: Fixed state space S = 12, action space A = 8, discount factor 0.9. The nominal kernel Po and reward function were generated randomly.
Random Sampling: For each uncertainty radius B, we sampled over 500 million kernels from the uncertainty set and computed the empirical minimum return.
Algorithm 1 (Ours): For each 3, our algorithm produced the worst-case rank-one pertur- bation 6k We then projected Po bb onto the simplex obtain a valid kernel P" and reported the return JT. as the worst-case estimate.
Time Taken:
Our algorithm typically takes 2-4 seconds, while random sampling of 500+ million kemnlss takes 400 minutes for each [3.
Nominal Return: The nominal return
-0.1414.
Table 4: Robust Return with different uncertainty raiduses.
9
10-4
10-3
0.002
0.01
0.05
0.1
0.5
1.0
2.0
Algorithm 1 (Ours)
-0.141
-0.142
-0.143
-0.150
-0.186
-0,231
-0.588
-1.026
-1.851
Random Sampling
-0.141
-0.142
-0.142
-0.145
-0.159
-0.176
-0.315
-0.467
-0.779
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 method works much faster than random sampling.
Conclusion
Our method performs exactly 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.
Experiments: Robust Policy Evaluation with L2 norm
We conduct numerical comparison of our Algorithm aad CPI (Algorithm 3.2 from 21 reproduced
as Algorithm 2 in the appendix) for robust policy evaluation. The experiments are performed using randomly generated nominal kernel P, reward function Rt, and policy An uncertainty set Ul2 is constructed using the nominal kernel with a fixed uncertainty radius 3.
Algorithm 5 Spectral method for computing max |
1: Compute eigenvector and eigenvalues X; of A A
2: WLOG let || ||2 2 I|u, || where of mmx (v;, 0), v.
min(v; 0)
Compute best score: arg max, \p ||o 1z
4: Output: Approximate maximum value B
v
10 11
42

---

Robust
-0.25
-0.50
0.75
Robust Return
-100
1125
-1.50
124
16-1 Uhoctiante Kalio lon bu
Algortthm (Ours)
Random
10
10
10"2
10
10a
Uncertalnty Radius (log Scale)
Figure Robust Return for (Uncertainty Radius, $=12 and A=8, 7=0.9 and convergence tolerance of 10 Robust Return of Random Kernel is minimum of 500 millions kernels samples for each B
Figure demonstrates the convergence behavior of both methods, presenting results based on the number of iterations (left panel) and computation time (right panel). The left panel shows the robust return achieved per iteration, while the right panel depicts robust return function of wall-clock time. Note that the x-axes of the figure have a logarithmic scale in order to clearly capture the slow convergence of the CPI method.
Our Algorithm I We apply our Binary Search Algorithm ! to perform robust policy evaluation with the given nominal kernel P and uncertainty radius f3. Each iteration of the algorithm involves computing F(A), for which our Spectral Algorithm 5 employed. Our algorithm converges very quickly requiring only a few iterations.
Algorithm 3.2 of [21]. We run Algorithm 2 with precomputed values of dt and A The step sizes are chosen to be either a small constant or dynamically adjusted, as described in the algorithm. Note that Line of the algorithm involves solving arg min (z, P). This constrained optimization is solved using numerical method (scipy. siipy.minimize). This gradient based method improves very slowly and converges very far from the true robust return as the uncertainty set Ud2 is very non-rectangular.
Brute Force Benchmark. To approximate the true robust return, we generate a large n) from U2 and estimate the empirical minimum, min; J proxy for the robust return. Note this method requires exponential number of samples reasonably cover the entire uncertainty set. Hence the values obtained in Figure [4] are an approximate upper bound on the true robust return.
number of random samples (P,
The results in Figure I4 reflect a general trend observed across a wide range of experiments conducted with space sizes ranging from S = 5 to S 190 and uncertainty radius {0.005, 0.01, 0.05). Our proposed algorithm consistently demonstrates superior performance, converging in significantly fewer iterations and less computation time while the computational demands of the CPI algorithm grow substantially with larger state spaces. Hence, our method exhibits more favorable scaling properties, making practical for high-dimensional problems.
The codes, detailed explanations, and additional experiments are available at //an:mouus 4open. www.sscceeeeen.....////. www.areelaat--eaeeeeeee rmdd- 77B8 System details for the experiments as follows: Operating System: macOS Sequoia ( (Version 15.4.1), Chip: Apple M2, Cores: (4 performance and 4 efficiency), Memory: 16 GB (LPDDR5).
43

---

Camplcelly dttrrll
Camplocty [inel
10.03
-0.00
00083
-0.00
-0023
-0323
Al witees
Sumar Naker 011E
Wik Stat 20-500
Bang
Log
Figure 14: Comparison of Algorithm | Ours) and the CPI Algorithm for B (Uncertainty Radius) 0.05, S = 10, A = 8, 0.9, and convergence tolerance of 10-1
44


Reviews:
[{"review_id": "wUkTY9v5AM", "reviewer": "Reviewer_oaPp", "summary": "The paper shows that robust policy evaluation for non‑rectangular transition uncertainty defined by an $L_p$ ball is polynomial‑time tractable, in contrast to the known NP‑hardness for general nonrectangular sets . By (i) decomposing the ball into an infinite union of sa‑rectangular sets, (ii) proving the worst‑case kernel is a rank‑one perturbation, and (iii) deriving a dual fixed‑point that can be solved by binary search, the authors obtain an $O(log 1/\\epsilon)$ algorithm. Experiments on small-scale random MDPs confirm large speed‑ups over the CPI baseline of prior art [20] Li et al. 2024.", "questions": "- 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.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The paper is the first to give a provably polynomial-time evaluator for a coupled transition-uncertainty set, namely an Lp ball. This closes a long-standing gap between expressive non-rectangular models and the rectangular relaxations used since Iyengar 2005, and it sidesteps the NP-hardness barrier of Wiesemann et al. 2013 by exploiting norm structure rather than polyhedral structure.\n\n- A dual reformulation reduces the min–max over kernels to a one-dimensional fixed point. Coupled with a Sherman–Morrison update, this yields transparent rank-one worst-case kernels, linear convergence of the bisection loop, and an $O(log 1/\\epsilon)$ iteration bound—all easy to verify and intuitively linked to the geometry of the Lp ball.\n\n- The evaluator drops the irreducibility and large-diameter assumptions that hampered earlier CPI-style methods, making it applicable to sparse or disconnected MDPs. The authors release full proofs and runnable code; timing studies up to 190 states show speed-ups of orders of magnitude that agree with the theoretical complexity.\n\nWeaknesses\n\n- 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.\n\n- 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.", "was_revised": true, "final_justification": "The paper studies an important problem with non-trivial arguments that exploits the impossibility result to its core.", "rebuttal": "We thank the reviewer for the detailed and encouraging feedback.\n\nWe’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.\n\n***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.***\n> 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.\n\n> 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.\n\n\n\n***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.***\n> 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.\n\n> 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.\n\n> 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.\n\n***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.***\n> 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.\n\n> 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'$.\n\n> 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.\n\n> 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.\n\n### Experimental Setup\n\n- **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.\n- **Random Sampling**: For each uncertainty radius $\\beta$, we sampled over 500 million kernels from the uncertainty set and computed the empirical minimum return.\n- **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.\n- **Time Taken**: Our algorithm typically takes $2-4$ seconds  while random sampling of 500+ million random sampling takes 400 minutes for each $\\beta$.\n- **Nominal Return**: The nominal return was $-0.1414$.\n\n### Results\n\n| **$\\beta$**             | **0.0001** | **0.0005** | **0.001** | **0.002** | **0.01** | **0.05** | **0.1**  | **0.5**  | **1.0**   | **2.0**   |\n|-------------------------|:----------:|:----------:|:---------:|:---------:|:--------:|:--------:|:--------:|:--------:|:---------:|:---------:|\n| **Algorithm 1 (Ours)**  | -0.1415    | -0.1419    | -0.1423   | -0.1432   | -0.1504  | -0.1864  | -0.2312  | -0.5878  | -1.0259   | -1.8509   |\n| **Random Sampling**     | -0.1415    | -0.1416    | -0.1418   | -0.1421   | -0.1449  | -0.1589  | -0.1757  | -0.3149  | -0.4671   | -0.7788   |\n\n### Observation\n\nAs 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.\n\n### Conclusion\n\nOur 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.\n\n***System***: aws ec2 instance: c7a.32xlarge\nvCPUs: 128\nMemory: 256 GiB\nNetwork Bandwidth: Up to 50 Gbps\nProcessor: 4th generation AMD EPYC\nClock Speed: Up to 3.7 GHz"}, {"review_id": "NVkGq8XE8K", "reviewer": "Reviewer_5k8B", "summary": "This paper discusses a subclass of non-rectangular Robust Markov Decision Processes (RMDPs) for which the NP-hardness result of the policy evaluation problem [1] does not hold. This subclass is RMDPs with L_p ball uncertainty sets around a nominal kernel.\nThey first argue that assuming s- or s,a-rectangularity can lead to high conservativeness in cases where the uncertainty set is actually non-rectangular. Next, they show that for the RMDP subclass with L_p ball uncertainty sets with p>1, the NP-hardness result does not hold, since this result relies on a polyhedral structure in the uncertainty set of the RMDP.\nAfter showing that the NP-hardness result does not hold, they show that L_p balls with p>1 are equivalent to the union of an infinite number of s,a-rectangular sets. They use this observation to construct a new dual formulation for the policy evaluation problem, which they show can be solved efficiently with a binary-search based algorithm.\nThey compare their algorithm for the L_2 ball to the Conservative Policy Iteration (CPI) algorithm of [2]. These experiments show that their dedicated algorithm outperforms the CPI algorithm.\n\n\n[1] Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov decision processes. Math. Oper. Res., 38(1):153–183 (2013).\n\n[2] Mengmeng Li, Daniel Kuhn, and Tobias Sutter. Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Sets. CoRR abs/2305.19004 (2023).", "questions": "- 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?\n- 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?\n- Q3) What happens to the algorithm when considering p != 2?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The main strengths of this paper are the insight that the NP-hardness result of [1] does not necessarily apply to L_p ball uncertainty sets and the notion that there might be more uncertainty sets with this property. This work therefore exposes an interesting direction for future research.\n\n- Additionally, although I do not have the background to understand all the details, the discussion of the dual formulation seems technically solid.\n\n- Finally, the binary search algorithm proposed in this paper strongly outperforms the CPI algorithm in the experiment that is discussed in the main paper.\n\n\n## Weaknesses \n\nMy main concerns with the paper are two simplifications that are not clearly justified in the main paper. First of all, the work only considers memoryless randomized agent policies, while the cited work of Wieseman [1] states that optimal agent policies in non-rectangular RMDPs require both randomization and memory. Although one of the main points of this paper is that the NP-hardness result from [1] does not translate to their setting, I do not see any arguments as to why this simpler policy type is appropriate now.\nSecondly, Algorithm 2 is only discussed for L_2 ball uncertainty sets (so p=2), and no explanation is given on how a different value for p would change the algorithm or influence the complexity results. The experiments are also done only for L_2 balls.\n\nFurthermore, the experiments and discussion thereof are limited. The authors state that they have conducted multiple experiments, but only present the results of a single experiment in the main paper, claiming that the other experiments show the same trend. The results of the rest of the experiments are not in the appendix, and the anonymous GitHub repository that contains the \"additional experiments\" according to the paper only contains the code to run the additional experiments yourself.\nAdditionally, the paper does not compare their algorithm against any rectangular methods, while part of this paper is dedicated to discussing the overconservativeness of assuming rectangularity for a non-rectangular uncertainty set. Such a comparison would be valuable and expected.\n\nMoreover, Proposition 3.1 is unclear to me. The negative exponents in the complexity of the volume ratios would imply that the complexity becomes smaller as S and A become larger. This also doesn't correspond to the complexity given in line 149, which has a positive exponent, although a version with the negative exponent is written in line 23.\nAnother note on Proposition 3.1 is that it is based on s- and s,a- rectangular sets that enclose the L_2 ball. However, the L_2 ball is also an approximation of the uncertainty set according to the pictures in Figure 1. It might therefore be possible that the s- or s,a- rectangular sets that encase the uncertainty do not need to encase the entire L_2 ball. This is not discussed in the paper.\n\nFinally, the related work is discussed in limited detail. In particular, the authors summarize the existing research on RMDPs in just a single sentence with 18 citations that are not further explained, and then immediately move on to the non-rectangular RMDPs. There is a bit more discussion in the appendix, but this should be part of the main paper.\n\n## Minor remarks\n- line 20: \"non-rectangular uncertainty set could be thought of as ...\" plural vs singular.\n- line 35: \"given oracle access to the robust gradient ...\" word (\"a\") missing, I think.\n- line 75: \"..., and U set of transition kernel P ...\" word (\"a\") missing and singular should be plural (\"kernels\"), I think.\n- line 96: \"A L_p-bounded uncertainty sets ...\" plural vs singular.\n- Figure 1: The left image is labeled 3D, but this should be 2D.\n- The Notes and Definitions section after the NeurIPS checklist does not seem a proper part of the appendix. There is no letter in front.\n- Figure 2: Caption missing.\n- References to the proofs/content in the appendix are missing. (line 177, lines 291-296)\n- The answer to the NeurIPS checklist question 9 is missing, but from the justification, it is clear that this should be a [NA]\n- The bibliography is inconsistent. It is not possible to quickly see whether the cited papers have been published somewhere and where.", "was_revised": true, "final_justification": "I believe the paper has some merit, and I was happy to read the authors intend to discuss the limitation to policy evaluation of stationary policies in the revised version of the paper, and I believe that the evaluation of stationary policies is a valuable and interesting starting point.\nAlthough I still think that the evaluation of the algorithm and the discussion of p!=2 are limited, I believe the theoretical contribution is sufficiently interesting to raise my score to a borderline accept, in particular with the perspective of future research in the non-rectangular RMDP direction.", "rebuttal": "We thank the reviewer for their thoughtful and encouraging feedback.\n\nWe’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.\n\n***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?***\n> Yes, the reviewer is correct in noting that the optimal robust policy for non-rectangular robust MDPs can, in general, be non-stationary.\n\n> 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**.\n\n> 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.\n\n> 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.\n\n***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?***\n> 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.\n\n***Q3) What happens to the algorithm when considering p != 2?***\n> 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.\n\n***Q4) Other minor comments.***\n> 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."}, {"review_id": "OT8mEaOIlR", "reviewer": "Reviewer_p4ao", "summary": "This technical paper studies the problem of robust policy evaluation (RPE) in robust Markov decision processes (RMDPs) with *non-rectangular* uncertainty sets, for which existing results suffer from either exponential iteration complexity or coarse approximation bounds. This paper identifies a class of $L_p$-bounded uncertainty sets that can break such difficulties. Dual representation and a resulting efficient RPE algorithm with iteration complexity $\\log(1/\\epsilon)$ are developed.", "questions": "1. 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. \n2. 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.", "limitations": "Please see the **Questions** part.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:** \n1. The newly proposed uncertainty set is meaningful in terms of a providing a computationally tractable formulation of non-rectangular uncertainty sets for RMDPs.\n2. Most of the theoretical results are sound and well developed. The literatures are sufficiently reviewed and the problem setups are clearly introduced.\n\n**Weakness:**\n1. 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.\n2. The theory and the algorithms proposed in this work are relatively direct provided with existing results on rectangular uncertainty sets.", "was_revised": true, "final_justification": "The reviewer is still concerned with the motivations of the proposed uncertainty set, the novelty of the analysis, as well as the characterization of the convergence rate of the algorithm. The overall goal of the paper has nice merits, but the reviewer believes it is better to go through further revision before acceptance. Therefore, I am maintaining my original score.", "rebuttal": "We thank the reviewer for their positive feedback.\n\nWe’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.\n\n***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.***\n> 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].\n\n***Q2) The theory and the algorithms proposed in this work are relatively direct provided with existing results on rectangular uncertainty sets.***\n>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.\n\n***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.***\n\n> 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'$.\n\n> 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.\n\n### Experimental Setup\n\n- **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.\n- **Random Sampling**: For each uncertainty radius $\\beta$, we sampled over 500 million kernels from the uncertainty set and computed the empirical minimum return.\n- **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.\n- **Time Taken**: Our algorithm typically takes $2-4$ seconds  while random sampling of 500+ million random sampling takes 400 minutes for each $\\beta$.\n- **Nominal Return**: The nominal return was $-0.1414$.\n\n### Results\n\n| **$\\beta$**             | **0.0001** | **0.0005** | **0.001** | **0.002** | **0.01** | **0.05** | **0.1**  | **0.5**  | **1.0**   | **2.0**   |\n|-------------------------|:----------:|:----------:|:---------:|:---------:|:--------:|:--------:|:--------:|:--------:|:---------:|:---------:|\n| **Algorithm 1 (Ours)**  | -0.1415    | -0.1419    | -0.1423   | -0.1432   | -0.1504  | -0.1864  | -0.2312  | -0.5878  | -1.0259   | -1.8509   |\n| **Random Sampling**     | -0.1415    | -0.1416    | -0.1418   | -0.1421   | -0.1449  | -0.1589  | -0.1757  | -0.3149  | -0.4671   | -0.7788   |\n\n### Observation\n\nAs 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.\n\n### Conclusion\n\nOur 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.\n\n\n***System***: aws ec2 instance: c7a.32xlarge\nvCPUs: 128\nMemory: 256 GiB\nNetwork Bandwidth: Up to 50 Gbps\nProcessor: 4th generation AMD EPYC\nClock Speed: Up to 3.7 GHz \n\n***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.***\n> 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."}, {"review_id": "gcAz4stwjE", "reviewer": "Reviewer_vgZb", "summary": "The paper studies policy evaluation problems of non-rectangular robust MDPs with normed uncertainty sets. The key technical ingredient is the use of the Sherman-Morrison formula to reformulate the objectives and derive the fixed point equation $F(\\lambda)$. Because of them, the proposed bisection algorithm can achieve $\\log(\\epsilon^{-1})$ convergence rate.", "questions": "Can the method be generalized to other types of uncertainty sets? e.g. $ \\{P:\\sum_{s,a} D(P_{s,a},\\hat{P}_{s,a})\\leq \\delta\\} $, where $D$ could be some divergences or Wasserstein distance.", "limitations": "The paper only considers policy evaluation. Policy learning is still unclear.\n\nIt 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.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Most of the existing literature on robust MDPs focuses on the rectangular uncertainty sets because of their tractability. However, non-rectangular robust MDPs may be less conservative. Therefore, I believe the contributions of this paper is siginificant, which addresses computational challenges of policy evaluations of robust MDPs with a special class of uncertainty sets.\nIn particular, the use of the Sherman-Morrison formula and the derivation the fixed point equation $F(\\lambda)$ is smart and useful.\n\nHowever, I believe the presentation of the paper can be further improved:\n\n* The notation is heavy and not always used carefully. For example, $D^\\pi$ is introduced on line 82 without a subscript, and $D^\\pi_P$ is never formally defined.\n* On line 121, the expression should be written using double bars, i.e., $\\left( \\sum_{s,a,s'} |P(s'|s,a) - \\hat{P}(s'|s,a)|^p \\right)^{1/p}$.\n* The policy-averaging linear operator $H^\\pi$ first appears on line 212 but is not defined until line 227.\n\nThe authors may also consider citing Section 6.9 in [1] for the dual formulation introduced on line 101.\n\n[1] Puterman, Martin L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.", "was_revised": true, "final_justification": "The paper is solid. But it has a limited scope. Therefore, I maintain my score as borderline accept.", "rebuttal": "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.\n\nWe 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.\n\n***Q1) Can the method be generalized to other types of uncertainty sets?***\n> 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.\n\n> 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.\n\n\n\n***Q2) The paper only considers policy evaluation. Policy learning is still unclear.***\n\n> 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.\n\n> In summary, once robust policy evaluation is performed, policy improvement via policy gradient can be carried out efficiently.\n\n\n***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.***\n>  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."}]

Author rebuttal:

Meta-review: This paper studies robust policy evaluation under non-rectangular uncertainty sets, which is generally NP-hard, and introduces a special class of \ell_p-bounded sets that avoid these complexity barriers. By decomposing them into infinitely many sa-rectangular sets, the authors derive a novel dual formulation and an efficient algorithm for robust policy evaluation in these settings.

I believe that the paper makes a strong theoretical contribution by providing the first polynomial-time algorithm for a certain coupled transition uncertainty sets. The dual reformulation and efficient algorithm are elegant, broadly applicable, and supported by proofs and significant empirical speed-ups. While the results have some limitation (e.g., requiring a small uncertainty radius), I agree with the authors that they serve as an important step in the right direction and encourage further exploration in this area. Reviewer p4ao (who gave the lowest rating 3) expressed concerned with the motivations of the proposed uncertainty set, the novelty of the analysis, as well as the characterization of the convergence rate of the algorithm, but the authors provided convincing rebuttal to these points (especially the motivations and the convergence rate). Therefore, even if Reviewer p4ao did not follow up on the discussion nor change their score, I still recommend accept.
Decision: Accept (poster)