{"id":"fe18e70e-5976-4960-a963-5f2f36891b9c","arxiv_id":"2412.10185","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Robust MDPs can be solved generically with implicit value iteration that provides anytime precision guarantees for many uncertainty sets, including L2 balls.","lead":"This paper presents a value-iteration framework for robust Markov decision processes that covers a broad family of uncertainty sets and objectives, and that maintains provable precision bounds during computation. The framework avoids explicitly building the underlying stochastic game, and its prototype solves models with over a million states in under a minute.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reader's pmin concern is not load-bearing (compactness gives pmin>0 under constant support); the real flaw is Lemma 1's Lp update: the printed sign computes a minimizer, and the optimality argument works only for p=2, so generic L2/Lp support is unproven.","rationale":"I agree with the reader that the current preprint has a serious proof flaw, but not the one singled out as weakest. The pmin issue is resolved by compactness, so that part of the rejection rationale should be withdrawn. The sign error in Lemma 1 is real and verifiable, and the general-Lp argument is even weaker than a sign typo: it only works for p=2. This is load-bearing because the framework's novelty is handling L2/Lp balls without constructing the induced SG; if the implicit update is wrong, the reliability guarantee for those models fails. I would not reject the entire line of work: Theorem 4's structure may survive once Lemma 1 is corrected, and the artifact can be checked against the corrected formula. Hence I move the verdict from REJECT to CONDITIONAL, pending the concrete test and a rewrite of the Lp case.","tokens_in":38976,"tokens_out":13191,"duration_ms":149507,"concrete_test":"Run a one-state-action check: S={s1,s2}, P*=(0.5,0.5), U={P: ||P−P*||_2 ≤ 0.1, P(s1)+P(s2)=1}, rewards L=(1,0). Evaluate the Lemma 1 formula as printed; it yields P(s1)=0.5−0.1/√2 and value ≈0.429, whereas brute-force or an LP over U gives the true maximum at P(s1)=0.5+0.1/√2 with value ≈0.571. If the printed formula returns the smaller value, the sign error is confirmed. Repeat with p=4 and the sign corrected: compare the closed-form point against a numerical optimizer of ΣP(s)L(s) over the L4 ball; if they disagree, the general-Lp optimality claim in Lemma 1 is false as stated.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The reader's weakest-assumption claim does not hold. For a closed constant-support RMDP, each uncertainty set is a closed subset of the finite simplex and every distribution in it has the same support S0; the continuous map P ↦ min_{s∈S0} P(s) is positive on the set and therefore attains a positive minimum on the compact set. So pmin > 0 is entailed by the stated assumptions; no hidden assumption is introduced in Lemma 2.\n\nThe genuinely load-bearing gap is in Lemma 1 (Appendix D), Lp-ball case, which is the basis for the advertised handling of L2 and general Lp uncertainty sets. For maximization the proof sets x = L_i − (‖L_i‖_1/k)·1 and claims the optimum is P_opt = P* − ζ x/‖x‖_p^w. Since x is positive on above-average-reward states and negative on below-average states, subtracting ζx moves probability from high-reward states to low-reward states: it constructs a minimizer. The correct sign for maximization is plus. The proof's further claim that the surface normal is parallel to P_opt − P* is valid only for p=2; for general Lp the normal is componentwise sign(P−P*)|P−P*|^{p−1}. Thus the closed-form polynomial update and its optimality are not proved for general Lp, and the L2 formula as printed is sign-reversed. Because the abstract and experiments advertise L2/Lp sets as a central novelty, this directly undermines the genericity and reliability claims for those sets; the code may be correct if it uses the opposite sign, but the manuscript as written does not support the claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a framework for solving robust Markov decision processes (RMDPs) that is generic over uncertainty sets (polytopes, intervals, Lp balls) and objectives (total reward, long-run average reward, stochastic shortest path), reliable through anytime algorithms with stopping criteria, and efficient by performing value iteration implicitly on the RMDP rather than by explicitly constructing the induced stochastic game. The main results are a formal reduction from RMDPs to stochastic games (Theorem 1), existence of memoryless deterministic optimal policies under closed constant-support uncertainty (Theorem 2), convergence of robust value iteration (Theorem 3), polynomial-time implicit Bellman updates for several uncertainty representations (Lemma 1), and anytime algorithms for constant-support and, in part, non-constant-support RMDPs (Theorems 4 and 5). The paper also reports a prototype implementation, artefacts, and experiments on benchmarks with up to a million states. One reviewer concern about a missing lower bound pmin>0 is not supported: for closed constant-support sets, the map P ↦ min_{s in the support} P(s) is positive and continuous on a compact subset of the simplex, so a positive minimum exists without an additional axiom.","tokens_in":39324,"tokens_out":6623,"duration_ms":75166,"significance":"If the results hold, the framework would be a substantial advance: it unifies several previously separate RMDP settings, provides the first practical anytime guarantees for undiscounted and average-reward robust objectives, and demonstrates scalability through an implicit implementation. The strengths of the submission include a concrete artefact with code and models, comparison against several existing tools, and a clear theoretical reduction to stochastic games that is used throughout. However, the central technical lemma for Lp-ball uncertainty sets, which is advertised as a key novelty (including L2 balls), contains a sign error and an optimality argument that only works for p=2. Since the paper's genericity and experimental claims for L2/Lp uncertainty rest on this lemma, the significance is conditional on a corrected and complete proof. The remaining framework, especially for polytopic and constant-support interval uncertainty, remains plausible and potentially valuable.","major_comments":[{"comment":"The proof defines P_opt(s,a) = P*(s,a) - ζ x / ||x||^w_p with x = L_i - (||L_i||_1/k)·1 and claims that this point maximizes the linear objective. Since x is positive on above-average-reward states and negative on below-average-reward states, subtracting ζx moves probability mass away from high-reward states and toward low-reward states; this constructs a minimizer, not a maximizer. The containment calculation then writes P_opt - P* = ζ x / ||x||^w_p, which contradicts the definition immediately above it. For maximization the sign must be plus. As printed, Lemma 1 does not prove the implicit L2 update, and the experiments in Section 6 that advertise L2 uncertainty sets rely on this formula.","section":"Appendix D, Lemma 1, Lp-ball case"},{"comment":"Even after correcting the sign, the optimality argument is only valid for p=2. At a boundary point P of an Lp ball, the outward normal is componentwise sign(P-P*)·|P-P*|^{p-1}, which is parallel to P-P* only for p=2. For general integer p, the KKT conditions require solving for a Lagrange multiplier, and the paper provides neither a closed form nor a polynomial-time numerical procedure for that multiplier. Consequently, the claim that the implicit update can be evaluated in polynomial time for every p ∈ N ∪ {∞} is not established; the proof as written supports only L1, L∞, and L2 with corrected sign. Since the abstract, introduction, and experiments present general Lp balls as a central feature, this is load-bearing for the paper's genericity and reliability claims.","section":"Appendix D, Lemma 1, general Lp optimality"},{"comment":"The termination proof breaks off mid-sentence. After the contraction argument, the text states that there is some n for which |U_n(s) - L_n(s)| and then continues with the incomplete fragment 'as U_i(s) ≥ L_i(s) (see Correctness paragraph) this implies U_n(s) − L_n(s),' without completing the epsilon-bound argument or specifying how n is chosen. Because termination for every ε > 0 is part of Definition 4, the printed proof of Theorem 4 is incomplete. This is readily fixable, but it should be written out explicitly.","section":"Appendix E, proof of Theorem 4, termination paragraph"}],"minor_comments":[{"comment":"The while condition 'U(s_i) - L(s_i) > ε' uses an undefined identifier s_i; it should quantify over all states, e.g. 'max_{s ∈ S'} (U(s) - L(s)) > ε'.","section":"Algorithm 2, line 4"},{"comment":"The equality LG_i(s) = 2·L_{i/2}(s) is only meaningful for even i and has the index off by one; it should be LG_{2j}(s) = 2·L_j(s). The limit conclusion is unaffected, but the indexing should be corrected.","section":"Appendix D, proof of Theorem 3, LRA part"},{"comment":"The column header 'Solving Time' in Table 3 does not state units; the text should explicitly repeat that times are in seconds, as is done for Tables 1 and 2.","section":"Section 6, Table 3"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle to acceptance is the Lp-ball update in Lemma 1: the sign error makes the printed theorem false for maximization, and the general-p optimality argument is not valid. This is fixable by correcting the sign, restricting the claim to p=2 (or supplying a proper KKT analysis for general p), and re-running or re-validating the L2 experiments. The rest of the framework, especially the polytopic and interval cases, appears sound in structure, so I see this as a major-revision issue rather than a rejection, provided the authors address the proof gap directly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The reader's take is half right. The concern about pmin in Lemma 2 is a red herring: under the Constant-Support Assumption plus closedness, each uncertainty set is a compact subset of the simplex, and the map P ↦ min_{s∈S0} P(s) is continuous and positive on it, so a uniform positive minimum is entailed. No hidden assumption there.\n\nThe genuinely load-bearing flaw is in Lemma 1's Lp-ball update. The printed formula sets x = L_i − mean(L_i) and claims P_opt = P* − ζx/‖x‖_p^w for maximization. Since x is positive on above-average-reward states and negative on below-average ones, subtracting ζx moves probability away from good states: that constructs a minimizer, not a maximizer. The sign should be plus. And even with the sign fixed, the argument only works for p=2, where the simplex constraint projects the gradient to zero-sum direction c − mean(c). For general p, the optimality condition is componentwise sign(P−P*)|P−P*|^{p−1} proportional to L_i, which the printed update does not satisfy. So the advertised handling of L2 and general Lp uncertainty sets is not proven. The code might be correct (the experiments suggest it works), but the manuscript as written does not support the genericity claim for those sets.\n\nThat said, the paper is not a waste of time. The anytime BVI framework for closed constant-support RMDPs with TR and LRA objectives is a real step forward: it resolves an explicitly open stopping-criterion question, avoids explicit SG construction, and the experiments on million-state models are impressive and backed by a public artifact. The SG reduction for TR is a useful formalization. If the Lp update is corrected — and it likely can be, at least for p=2 — the paper would be solid.\n\nWho is this for? The robust-MDP and probabilistic verification community. The paper deserves a serious referee: the core algorithmic idea is valuable and the flaw is localized in one proof, not a fundamental conceptual collapse. I would not accept the current version as-is, but I would send it to review rather than desk-reject.","headline":"The pmin worry is a red herring; the real flaw is the sign-reversed Lp update proof in Lemma 1, but the anytime-VI framework is valuable and deserves a rigorous review.","tokens_in":39855,"tokens_out":3925,"would_cite":true,"duration_ms":38762,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A framework solves robust Markov decision processes with anytime precision guarantees, without constructing the induced stochastic game.","keywords":["robust Markov decision processes","stochastic games","value iteration","anytime algorithm","stopping criterion","long-run average reward","total reward","implicit updates"],"falsifier":"Run Algorithm 2 on a closed constant-support RMDP whose uncertainty set is, for example, {$P : 0 \\le P(s_1) \\le 1,\\ P(s_2)=1-P(s_1)$}, so probabilities approach zero while support stays constant; if for some $\\varepsilon$ the gap between upper and lower bounds never drops below $\\varepsilon$, the anytime claim fails for that instance.","tokens_in":38769,"feed_emoji":"🎲","tokens_out":3829,"duration_ms":42264,"temperature":0.7,"pith_summary":"The paper aims to make robust Markov decision processes (RMDPs) practically solvable while retaining formal correctness guarantees, even when transition probabilities are only known to lie in general uncertainty sets. It claims that RMDPs can be solved through a reduction to stochastic games without ever materializing the game, so non-polytopic sets such as L2-balls become tractable. The central proof target is an anytime value-iteration algorithm that maintains lower and upper bounds on the true value and provably closes the gap for total-reward, stochastic-shortest-path, and long-run-average objectives. If correct, this closes the stopping-criterion gap left by earlier robust value iteration and makes reliable RMDP solving scale to models with a million states.","feed_headline":"Robust MDP solver gives precision guarantees at any time","feed_subtitle":"Implicit stochastic-game updates solve million-state robust Markov decision processes in under a minute.","key_machinery":"The Constant-Support Assumption—that all distributions in one uncertainty set share the same set of possible successors—together with closedness of the uncertainty sets. This combination guarantees continuity of value functions with respect to the environment policy, which yields memoryless deterministic optimal policies and allows end components to be collapsed so that Bellman updates have a unique fixpoint and upper bounds converge. The second key mechanism is the implicit Bellman update: instead of enumerating the possibly uncountably infinite actions of the induced stochastic game, the algorithm optimizes a linear function over the uncertainty set in polynomial time for the supported representations.","core_discovery":"The paper establishes that, for every closed constant-support RMDP with a total-reward objective and any precision epsilon > 0, its Algorithm 2 is an anytime algorithm: it keeps sound lower and upper bounds whose difference converges to zero, and it works implicitly, without constructing the induced stochastic game. The long-run-average variant is likewise anytime. The paper generalizes the RMDP-to-SG connection to arbitrary uncertainty sets and to total-reward and stochastic-shortest-path objectives, proves that robust Bellman updates converge in the limit, and gives polynomial-time implicit update formulas for polytopes in H- or V-representation and for Lp-norm balls. It also proves that in closed constant-support RMDPs optimal policies exist and are memoryless deterministic, and it reports experimental evidence of solving RMDPs with over a million states in under a minute.","pith_inferences":["A reader relying on the anytime guarantee should verify that all transition probabilities in their uncertainty sets are bounded away from zero, because the termination proof uses such a positive minimum probability; the paper's theorem statement does not spell out this condition.","The implicit-update technique likely transfers beyond the listed objectives to discounted rewards and to optimistic or best-case environment semantics, since the paper notes those cases reduce to the same machinery.","For distance-based uncertainty sets such as KL-divergence or Wasserstein balls, the Constant-Support Assumption holds for sufficiently small radii, suggesting a practical route from this framework to distributionally robust reinforcement learning with guarantees."],"forward_implications":["Explicit construction of the induced stochastic game becomes unnecessary, removing the exponential space blowup that limited earlier polytopic approaches.","Uncertainty sets such as L2-balls, which state-of-the-art tools could not handle, become solvable with formal precision guarantees.","RMDPs with total reward, stochastic shortest path, and long-run average reward objectives all fall under one implicit value-iteration framework with a sound stopping criterion.","The reported runtimes suggest that reliable RMDP solving can scale to large verification benchmarks with millions of states and actions."],"supporting_citations":[{"why":"Introduces RMDPs and the robust dynamic programming / stochastic-game connection that the paper extends to arbitrary uncertainty sets and new objectives.","marker":"Nilim and Ghaoui 2005"},{"why":"Provides the independent RMDP formulation and robust value iteration whose implicit-update idea the paper generalizes.","marker":"Iyengar 2005"},{"why":"Formalizes the polytopic RMDP-to-SG reduction for long-run average reward; its explicit construction is the baseline the paper makes implicit.","marker":"Chatterjee et al. 2024"},{"why":"Gives robust value iteration for average reward and explicitly leaves a stopping criterion open, the gap the paper's anytime algorithm fills.","marker":"Grand-Clément, Petrik, and Vieille 2023"},{"why":"Supplies the stochastic-game value iteration framework with stopping criteria that the paper adapts to RMDPs.","marker":"Kretínský, Meggendorfer, and Weininger 2023a"},{"why":"Proves convergence of value iteration for stochastic games with total reward, used to establish robust VI convergence.","marker":"Chen et al. 2013"},{"why":"Provides the large benchmark MDPs that the prototype scales to a million states.","marker":"Hartmanns et al. 2019"}],"fun_headline_variants":["Million-state robust MDPs solved in under a minute","Anytime precision for robust MDPs without SG construction","Generic robust MDP solver: anytime guarantees, million states","Solve robust MDPs implicitly: reliable, efficient, anytime"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The anytime guarantee's contraction argument needs all transition probabilities in every uncertainty set to be bounded away from zero, and the Constant-Support Assumption alone does not ensure that for every closed set.","fun_headline_variants_meta":{"raw":{"variants":["Million-state robust MDPs solved in under a minute","Anytime precision for robust MDPs without SG construction","Generic robust MDP solver: anytime guarantees, million states","Solve robust MDPs implicitly: reliable, efficient, anytime"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000247,"raw_usage":{"total_tokens":1524,"prompt_tokens":910,"completion_tokens":614,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":526,"completion_tokens_details":{"reasoning_tokens":544}},"tokens_in":526,"tokens_out":614,"duration_ms":6362,"temperature":1.0,"reasoning_tokens":544,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:15:40.647229+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 2 on a closed constant-support RMDP whose uncertainty set is, for example, {$P : 0 \\le P(s_1) \\le 1,\\ P(s_2)=1-P(s_1)$}, so probabilities approach zero while support stays constant; if for some $\\varepsilon$ the gap between upper and lower bounds never drops below $\\varepsilon$, the anytime claim fails for that instance.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the large benchmark MDPs that the prototype scales to a million states."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces RMDPs and the robust dynamic programming / stochastic-game connection that the paper extends to arbitrary uncertainty sets and new objectives."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the independent RMDP formulation and robust value iteration whose implicit-update idea the paper generalizes."},{"cited_title":"K.; Karrabi, M.; Novotn \\' y , P.; and Zikelic, D","cited_arxiv_id":null,"evidence_quote":"Formalizes the polytopic RMDP-to-SG reduction for long-run average reward; its explicit construction is the baseline the paper makes implicit."},{"cited_title":"Z.; Parker, D.; and Simaitis, A","cited_arxiv_id":null,"evidence_quote":"Proves convergence of value iteration for stochastic games with total reward, used to establish robust VI convergence."}],"review_version":1}