{"id":"b11c44cf-9c27-4f80-beff-08b83b03e5c1","arxiv_id":"2502.09432","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"For non-rectangular Lp transition uncertainty, the worst-case return equals the nominal return minus a penalty that can be found by binary search on a fixed-point equation.","lead":"This paper studies Markov decision processes where the transition probabilities are uncertain inside a non-rectangular Lp ball, a setting previously thought to be too hard. It derives a dual formula and a binary search method for evaluating a policy's worst-case return, with experiments against brute-force sampling.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's linear convergence guarantee presupposes an exact F(λ) oracle; the paper supplies only an approximate spectral heuristic (Alg. 2, App. H.1) and even labels the bilinear oracle NP-hard, so the implemented method lacks the asserted guarantee.","rationale":"The reader's weakest_assumption identifies the same load-bearing gap: Algorithm 1's correctness requires an exact inner maximization, while Algorithm 2 is an approximate spectral heuristic. My reading confirms this and adds that the paper itself acknowledges the inner bilinear problem is NP-Hard (Appendix H), making it unlikely that an exact polynomial oracle exists unless a strong structural result is proven—which the paper does not provide. The dual formulation and the decomposition of Up into sa-rectangular sets are genuine contributions, and the reversed inequality in Lemma 3.5 appears to be a typo that does not affect the algorithm's update rule (the code sets λl when F>λ, which matches F>λ iff λ<λ*). However, the central algorithmic deliverable—robust policy evaluation with a convergence guarantee—does not follow for the implemented method. A conditional verdict is right: the paper should be publishable if the authors either supply a certified exact solver, replace the bisection with a method tolerant to inexact F, or state the result as heuristic with empirical validation only. My proposed test would settle whether the heuristic can silently fail on small instances, which is the minimal check for the concern to land.","tokens_in":25982,"tokens_out":7023,"duration_ms":58655,"concrete_test":"On a small MDP (e.g., S=3, A=2), run Algorithm 1 with F(λ) evaluated (a) by the spectral heuristic Algorithm 2 and (b) by a global optimizer (e.g., scipy differential_evolution with random restarts, or a fine grid over b∈B) at each bisection step. If the final λ* differs, or if the bisection direction differs on any step, then Algorithm 2 is not a valid implementation of the oracle assumed by Theorem 3.6. To make the failure explicit, construct A=E_λ H for a λ near the fixed point where the top eigenvector's positive part is suboptimal for max_{b≥0, ||b||_2≤1} ||Ab||_2; such matrices exist by the paper's own admission in Appendix H.1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.6 claims that Algorithm 1 computes J^pi_Up with linear convergence. This requires the bisection test F(λ)>λ to be correct at every step, which in turn requires exact evaluation of F(λ)=max_{b∈B}||E_λ b||_q (Lemma F.1). No exact polynomial-time algorithm for this inner maximization is provided. For p=2, Algorithm 2 is explicitly a heuristic: Appendix H.1 admits it 'may not always yield the exact solution, especially when multiple eigenvectors significantly contribute to the optimal x.' Moreover, Appendix H opens by calling the equivalent bilinear oracle max_{b,k} k^T A b 'NP-Hard'. If the heuristic underestimates or overestimates F(λ), the bisection direction in Algorithm 1 is flipped and the iterates need not converge to λ*. Thus Theorem 3.6's guarantee applies only to an oracle algorithm, not to the implemented Algorithm 1 combined with Algorithm 2. The reversed inequality in Lemma 3.5 (stating F(λ)>λ iff λ>λ*; Proposition D.7 and Lemma F.1 imply the opposite) is a separate internal inconsistency; Algorithm 1's update rule uses the correct direction, so the algorithm survives that typo, but the missing exact inner solver does not.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies robust policy evaluation for non-rectangular Lp-bounded transition kernel uncertainty sets. It shows that the non-rectangular set can be decomposed into a union of sa-rectangular Lp sets (Proposition 3.2), derives a min-max fractional expression for the robust return in terms of nominal quantities (Lemma 3.3), states a dual formulation (Theorem 3.4), and proposes a binary-search algorithm (Algorithm 1) that evaluates a function F(λ) at each step, claiming linear convergence (Theorem 3.6). For p = 2 the inner maximization is handled by a spectral heuristic (Algorithm 2). The paper also derives a policy gradient and combines it with the evaluation oracle into a policy improvement scheme.","tokens_in":26196,"tokens_out":8888,"duration_ms":108629,"significance":"The core decomposition (Proposition 3.2) is simple and correct, and the fractional expression in Lemma 3.3 is a clean, nominal-only characterization of the robust return that provides genuine insight into the adversary's rank-one perturbation. The paper ships code and presents experiments showing large speedups over random sampling baselines. If the algorithmic guarantees could be established, this would be a valuable first step for non-rectangular Lp RMDPs. However, the main algorithmic claim is currently not supported: the inner maximization defining F(λ) is not solved exactly, and the paper itself notes that the required bilinear oracle is NP-Hard. The claimed separation from the NP-hardness result of Wiesemann et al. is also under-substantiated. The dual theorem is stated without proof. These gaps place the central contributions at risk.","major_comments":[{"comment":"The linear convergence guarantee of Algorithm 1 presupposes an exact evaluation of F(λ)=max_{b∈B} ||E_λ b||_q at every bisection step. For p=2, the provided solver is Algorithm 2, and Appendix H.1 explicitly states that this approach 'may not always yield the exact solution, especially when multiple eigenvectors significantly contribute to the optimal x.' An inexact inner solve can reverse the comparison F(λ_n)>λ_n, so the bisection can move in the wrong direction; Theorem 3.6's O(2^{-n}) bound therefore does not hold for the implemented Algorithm 1 combined with Algorithm 2. This gap also propagates to Theorem 5.2, whose O(ε^{-8}) complexity calls Algorithm 1 as a subroutine. Please either provide an exact polynomial-time inner solver (or a certified approximation that provably preserves the bisection decision) and restate the guarantees accordingly, or present Algorithm 1+2 as a heuristic without the linear-convergence claim.","section":"§3.2, Theorem 3.6; Appendix H, H.1"},{"comment":"The stated equivalence 'F(λ)>λ if and only if λ>λ*' is reversed relative to the proof. In Lemma F.1, f(λ)=max_{b∈B} ||E_λ b||_q - λ = F(λ)-λ, and Proposition D.7 gives f(λ) ≥ 0 iff λ* ≥ λ. Hence F(λ) ≥ λ iff λ ≤ λ*, not λ > λ*. Algorithm 1's update rule in the main text uses the correct direction (raising λ_l when F>λ), so the algorithm is not affected by this error, but the lemma and the surrounding discussion must be corrected.","section":"§3.2, Lemma 3.5"},{"comment":"The argument that L1-bounded non-rectangular uncertainty is tractable because 'U1 is defined by a single global constraint (∥P−P̂∥1≤β)' is not valid: the L1 ball in the space of transition matrices is a polyhedral set with exponentially many facets, not a single-constraint polyhedron in the sense of the IP reduction in [9]. The claim that only knapsack-like integer programs can be reduced to U1 requires a formal proof; without it, the contribution that the NP-hardness result of [9] does not apply to Lp-bounded RMDPs is not established.","section":"§1 and Appendix D.2"},{"comment":"The dual formulation for J*_Up is stated without proof and no appendix contains its derivation. Since 'derive a novel dual formulation' is one of the stated contributions, the theorem needs a proof or a precise pointer to a proof; in particular, the definition of the set D = {D^π H^π | π∈Π} and the max-min exchange must be justified.","section":"Theorem 3.4"},{"comment":"The volume ratio claim is justified only by analogy between a sphere and an enclosing cube, but the sets in question are not full-dimensional spheres or products of cubes: each component of U^sa_2 is a ball inside the simplex affine subspace, and U2 is a ball inside the global affine subspace of stochastic matrices. The claimed exponential ratios O(c^{-SA}) and O(c^{-S}) are plausible but are not established by the proof as written.","section":"§2, Proposition 3.1"}],"minor_comments":[{"comment":"The relationship between the inner maximization max_{b∈B} ||E_λ b||_q and the bilinear problem max_{b,k} k^T A b, which Appendix H labels NP-Hard, should be stated precisely; the two problems are not obviously equivalent for general p.","section":"§3.2 / Appendix H"},{"comment":"The operator H^π is used without a formal definition; the phrase 'H^π R := R^π' is not sufficient to specify its action on all arguments, and the notation in Theorem 3.4 (e.g., D b for a matrix D and vector b) should be clarified.","section":"Theorem 3.4 / Lemma 3.3"},{"comment":"Algorithm 5 uses a stopping criterion f(λ)>ε, whereas Algorithm 1 uses F(λ)>λ as the bisection test; the two terminating conditions should be reconciled, and the relationship between f and F should be made explicit in the algorithm box or its caption.","section":"Appendix J.2, Algorithm 5"},{"comment":"The proof that the set B is convex is not rigorous: the 'minor arc' argument is a sketch at best. The convexity claim may be true (as the image of a convex set under a linear map), but it needs a proper proof or a citation.","section":"Appendix H.1, Proposition H.8"},{"comment":"There are numerous typos and word-level errors, e.g., 'insishts' (p.2), 'trie to tweak' (p.3), 'precious work' (p.4), 'diamension' (p.6), and 'theses uncertainty sets' (p.3). A careful proofreading pass is needed.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The central algorithmic guarantee is not supported as written, and the hardness-avoidance argument is cursory. I would advise asking the authors either to supply an exact inner solver (or a certified approximation that preserves the bisection direction) or to substantially weaken the algorithmic claims and present the spectral method as a heuristic. The paper's clean dual expression and decomposition remain interesting even if the convergence theorem is dropped, but the novelty as stated ('first efficient algorithm') is currently overstated. The experiments would also benefit from comparison against an exact solver on small instances and from reporting variability across seeds."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the good part. The decomposition of the non-rectangular Lp ball into sa-rectangular Lp balls is correct, and the fractional dual expression that follows from Sherman-Morrison is a real contribution. Expressing the robust return in nominal terms and writing a dual for robust MDPs for the first time is worth something. The volume argument in Proposition 3.1 is also a nice, honest motivation for why non-rectangular sets matter.\n\nNow the problem. The paper's central algorithmic claim—Theorem 3.6, linear convergence of binary search for J^π_Up—presupposes that the inner maximization defining F(λ) is solved exactly at every bisection step. The paper's p=2 solver, Algorithm 2, is a spectral heuristic. Appendix H.1 openly says it may not always yield the exact solution, and Appendix H calls the bilinear oracle NP-hard. That is not a minor technicality: if F(λ) is evaluated inexactly, the bisection test F(λ)>λ can flip, and the iterates need not converge to λ*. So the theorem's guarantee applies to an oracle algorithm, not to the implemented one. This is a load-bearing gap, not a cosmetic one.\n\nThere is also a smaller internal inconsistency: Lemma 3.5 states F(λ)>λ iff λ>λ*, but Proposition D.7 implies the opposite. The algorithm's update rule uses the correct direction, so the practical effect is nil, but the typo needs fixing.\n\nOne more hesitation: the experiments compare against random kernel sampling and scipy SLSQP, not against any ground truth. So \"significantly outperforms\" means only that the heuristic beats those baselines on the reported instances. The complexity claim O(S^3A^3 log ε^{-1}) inherits the same caveat as the inner solver.\n\nWho should read this: anyone working on robust MDPs with non-rectangular uncertainty. The conceptual advance is real and the paper opens a direction people thought NP-hard. But as it stands, the headline guarantee is not supported. The fix is visible: either supply an exact solver or a certified approximation for the inner maximization, or restate the theorem to hold under an approximation error bound and prove convergence with it.\n\nRecommendation: send it to review. The paper deserves a serious referee even in its current form; it just needs to be revised to align the claims with the algorithm, or the algorithm with the claims.","headline":"The union decomposition and dual expression are genuinely new, but the paper's signature algorithm loses its guarantee once you look at what actually computes F(λ).","tokens_in":26790,"tokens_out":4366,"would_cite":false,"duration_ms":84226,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"Robust policy evaluation for non-rectangular Lp-bounded transition uncertainty reduces to a fixed-point binary search, with the worst-case kernel being a rank-one perturbation of the nominal kernel.","keywords":["robust Markov decision processes","non-rectangular uncertainty","Lp norm uncertainty","robust policy evaluation","dual formulation","rank-one adversary","fixed-point binary search","robust policy gradient"],"falsifier":"Take a small random MDP, compute $F(\\lambda)$ exactly by global optimization at the bisection points, and compare it with Algorithm 2's value; if there is any $\\lambda$ where Algorithm 2 returns a value on the wrong side of the diagonal, such as $F_{\\text{approx}}(\\lambda) > \\lambda$ while $F_{\\text{exact}}(\\lambda) < \\lambda$, then Algorithm 1 selects the wrong half of the interval and the reported robust return differs from $J^\\pi - \\lambda^*$, falsifying the practical claim of linear-convergence evaluation for p=2.","tokens_in":25761,"feed_emoji":"🎲","tokens_out":8147,"duration_ms":71219,"temperature":0.7,"pith_summary":"The paper tries to establish that robust policy evaluation—finding the worst-case return of a fixed policy—is not inherently intractable for non-rectangular Markov decision processes when the transition uncertainty is bounded by an Lp ball around a nominal kernel. For this class, the worst-case kernel is a rank-one perturbation of the nominal kernel, and the robust return splits into the nominal return minus a penalty term that is a fixed point of a scalar function. That fixed point can be found by binary search with linear convergence, which the paper presents as the first efficient robust policy evaluation algorithm for non-rectangular kernel uncertainty. The paper also characterizes the adversary in closed form and derives a robust policy gradient method. If correct, this makes a class of coupled, less conservative uncertainty models computationally usable rather than merely expressive.","feed_headline":"Binary search cracks non-rectangular robust MDPs","feed_subtitle":"For Lp-bounded transitions, the worst kernel is rank-one, so policy evaluation becomes a fixed-point hunt.","key_machinery":"The load-bearing machinery is the decomposition $U_p = \\bigcup_{b\\in B} U^{sa}_p(b)$, which rewrites one coupled Lp ball as an infinite union of state-action-rectangular Lp balls sharing the nominal kernel. This makes the known rank-one form of the sa-rectangular adversary available piecewise, and the Sherman-Morrison formula turns the induced return into a bilinear fractional function of nominal occupancy and value terms. The binary search hinges on the scalar function $F(\\lambda) = \\max_{b\\in B} \\|E^\\pi_\\lambda b\\|_q$, whose crossing of the diagonal locates the robust penalty. The outer bisection is exact when $F$ is evaluated exactly, while the p=2 inner norm maximization is handled by the spectral Algorithm 2.","core_discovery":"The central claim is that for the non-rectangular Lp-bounded uncertainty set $U_p = \\{P : \\|P - \\hat{P}\\|_p \\le \\beta,\\ \\sum_{s'} P(s'|s,a) = 1\\}$, robust policy evaluation is tractable because $U_p$ decomposes into a continuum of sa-rectangular Lp sets sharing the same nominal kernel. On each such set the adversary's worst kernel has the form $P = \\hat{P} - b k^\\top$; applying the Sherman-Morrison formula gives $J^\\pi_{U_p} = J^\\pi - \\gamma \\max_{b,k} [\\langle k, v^\\pi_R\\rangle \\langle d^\\pi, b^\\pi\\rangle / (1 + \\gamma \\langle k, v^\\pi_b\\rangle)]$, all in nominal terms. Defining $F(\\lambda) = \\max_{b\\in B} \\|E^\\pi_\\lambda b\\|_q$, the penalty is the unique fixed point $\\lambda^*$ of $F$, with $F(\\lambda) > \\lambda$ iff $\\lambda > \\lambda^*$; hence Algorithm 1 converges linearly, $J_n - J^\\pi_{U_p} \\le O(2^{-n})$. The paper further argues that the known strong NP-hardness for non-rectangular RMDPs, proved for uncertainty sets cut by finitely many half-spaces, does not transfer to Lp balls, and it supplies an $O(S^3 A^3 \\log \\epsilon^{-1})$ p=2 spectral inner solver as the practical implementation.","pith_inferences":["Inference: The same union decomposition would extend to finite unions of Lp balls, which the paper names as future work, and would make any uncertainty set approximated by Lp balls evaluable; the practical bottleneck is the number of balls and the exactness of the inner norm solve.","Inference: A provable approximation guarantee for the inner maximization $\\max_{x\\ge 0, \\|x\\|_2\\le 1}\\|Ax\\|_2$ would convert Algorithm 1 into an approximation scheme with certified error; without one, the linear-convergence theorem should be read as conditional on exact inner solves.","Inference: The spectral heuristic's accuracy likely degrades when $A^\\top A$ has many comparable eigenvalues, because it selects from single-eigenvector positive parts; this is a testable prediction, namely that random matrices with near-degenerate leading eigenvalues should show larger gaps against a global solver.","Inference: If the fixed-point perspective transfers to other divergence-bounded uncertainty sets whose worst kernel has a closed form, non-rectangular robustness beyond Lp might also escape the half-space hardness barrier; the paper does not claim this."],"forward_implications":["For any policy, robust evaluation under an Lp-ball uncertainty set is performed by Algorithm 1 with error decaying like $O(2^{-n})$ per bisection step; with the p=2 spectral inner solver the cost is $O(S^3 A^3 \\log \\epsilon^{-1})$.","The adversary for non-rectangular Lp uncertainty is a rank-one perturbation $\\hat{P} - b k^\\top$ whose direction $k$ maximizes reward loss $\\langle k, v^\\pi_R\\rangle$ while minimizing long-term exposure to high-uncertainty states; this is the first description of the non-rectangular adversary in nominal terms.","Because the robust return is $J^\\pi - \\lambda^*$ and $\\lambda^*$ is computed from nominal quantities, robust policy gradient updates can be computed without a separate NP-hard worst-kernel oracle; the resulting double-loop algorithm converges to an $\\epsilon$-optimal robust policy in $O(\\epsilon^{-8})$ iterations.","Non-rectangular Lp sets avoid the exponential over-conservatism of rectangular enclosures: the volume ratio of the smallest enclosing rectangular set to the L2 ball is exponentially small in the state-action count, so Lp sets can reduce conservatism while remaining evaluable.","The dual min-max formulation $J^*_{U_p} = \\max_{D\\in\\mathcal{D}} \\min_{k,b} [\\mu^\\top D R - \\gamma \\mu^\\top D b\\, k^\\top D R/(1+\\gamma k^\\top D b)]$ is the first dual formulation for robust MDPs and gives a new tool for robust value- and policy-based methods."],"supporting_citations":[{"why":"Supplies the strong NP-hardness result for general non-rectangular RMDPs that the paper argues Lp-bounded sets avoid.","marker":"[9]"},{"why":"Establishes that the worst kernel for sa- and s-rectangular Lp RMDPs is a rank-one perturbation of the nominal kernel, the structural fact reused here.","marker":"[20]"},{"why":"Gives the closed-form robust return and generalized standard deviation for Lp rectangular sets that the decomposition builds on.","marker":"[19]"},{"why":"Provides the Sherman-Morrison inversion formula used to convert the rank-one perturbed return into a fractional expression in nominal quantities.","marker":"[34]"},{"why":"Guarantees global convergence of robust policy gradient given an oracle for robust evaluation, the oracle this paper's Algorithm 1 supplies.","marker":"[17]"},{"why":"Handles non-rectangular reward-robust MDPs only and highlights that kernel uncertainty under non-rectangular sets remained open.","marker":"[23]"},{"why":"Provides the volume-of-ball estimates used to show rectangular enclosures are exponentially more conservative than Lp balls.","marker":"[24]"}],"fun_headline_variants":["Lp balls tame non-rectangular robust MDPs","Rank-one worst kernel unlocks fast Lp RMDP evaluation","Fixed point cracks non-rectangular Lp robust MDPs","Dual formulation turns NP-hard RMDPs tractable for Lp sets","First algorithm solves non-rectangular Lp RMDPs fast"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Algorithm 1's binary search is only as correct as the inner maximization $F(\\lambda)$, and the proposed p=2 subroutine is a heuristic with no exactness or approximation guarantee, so if $F(\\lambda)$ is computed inexactly the bisection decision can flip and the linear-convergence theorem does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Lp balls tame non-rectangular robust MDPs","Rank-one worst kernel unlocks fast Lp RMDP evaluation","Fixed point cracks non-rectangular Lp robust MDPs","Dual formulation turns NP-hard RMDPs tractable for Lp sets","First algorithm solves non-rectangular Lp RMDPs fast"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001259,"raw_usage":{"total_tokens":5201,"prompt_tokens":1033,"completion_tokens":4168,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":649,"completion_tokens_details":{"reasoning_tokens":4092}},"tokens_in":649,"tokens_out":4168,"duration_ms":28775,"temperature":1.0,"reasoning_tokens":4092,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T21:29:31.654526+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small random MDP, compute $F(\\lambda)$ exactly by global optimization at the bisection points, and compare it with Algorithm 2's value; if there is any $\\lambda$ where Algorithm 2 returns a value on the wrong side of the diagonal, such as $F_{\\text{approx}}(\\lambda) > \\lambda$ while $F_{\\text{exact}}(\\lambda) < \\lambda$, then Algorithm 1 selects the wrong half of the interval and the reported robust return differs from $J^\\pi - \\lambda^*$, falsifying the practical claim of linear-convergence evaluation for p=2.","supporting_citations":[{"cited_title":"Robust markov decision processes","cited_arxiv_id":null,"evidence_quote":"Supplies the strong NP-hardness result for general non-rectangular RMDPs that the paper argues Lp-bounded sets avoid."},{"cited_title":"Pol- icy gradient for rectangular robust markov decision processes","cited_arxiv_id":null,"evidence_quote":"Establishes that the worst kernel for sa- and s-rectangular Lp RMDPs is a rank-one perturbation of the nominal kernel, the structural fact reused here."},{"cited_title":"Efficient value iteration for s-rectangular robust markov decision processes","cited_arxiv_id":null,"evidence_quote":"Gives the closed-form robust return and generalized standard deviation for Lp rectangular sets that the decomposition builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Sherman-Morrison inversion formula used to convert the rank-one perturbed return into a fractional expression in nominal quantities."},{"cited_title":"Policy gradient in robust mdps with global convergence guarantee, 2023","cited_arxiv_id":null,"evidence_quote":"Guarantees global convergence of robust policy gradient given an oracle for robust evaluation, the oracle this paper's Algorithm 1 supplies."},{"cited_title":"Solving non-rectangular reward-robust mdps via frequency regularization, 2023","cited_arxiv_id":null,"evidence_quote":"Handles non-rectangular reward-robust MDPs only and highlights that kernel uncertainty under non-rectangular sets remained open."},{"cited_title":"Smith and Mavina K","cited_arxiv_id":null,"evidence_quote":"Provides the volume-of-ball estimates used to show rectangular enclosures are exponentially more conservative than Lp balls."}],"review_version":1}