{"id":"24970a66-9e29-4eca-b25a-d178b9b21039","arxiv_id":"2411.15622","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"An upper bound on the worst-case probability of hitting an unsafe state under Wasserstein-ambiguous transition kernels is computed via a convex-program robust Q-iteration for MDPs.","lead":"For a Markov decision process where the transition probabilities are known only up to an ambiguity set, the paper defines a worst-case robust safety function and shows it can be bounded by a robust Q-function computed with convex optimization. The result is meant to certify that a system reaches a goal before an unsafe state with high probability even when the model is imperfect.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The Wasserstein ambiguity set is built on an implicit metric |l-y| over arbitrary state labels; renumbering the MDP changes the certificate, so the method does not verify a property of the MDP unless a meaningful state metric is supplied.","rationale":"The core Bellman-style upper bound in Lemma 3 is valid for any fixed metric, and Lemma 6 matches the standard Wasserstein distributionally robust reformulation, so the mathematics is not obviously false. The load-bearing gap is definitional: the object being computed is only defined once a metric on X is chosen, and the paper neither supplies nor justifies one. In safety verification, the MDP is normally the object of interest; if the certificate changes under relabeling, the method is not verifying the MDP. The reader's conditional verdict remains appropriate: the paper needs to make the metric a first-class input with semantic justification, or prove that the safety bound is invariant under isometric relabelings and state that assumption. The numerical table also appears inconsistent with the stated nominal probabilities (for δ = 0, the stated P_{7,a} give J(7) = 0.5, not 0.35 as tabulated), but that is a validation error rather than the definitional problem selected here. This is a fixable modeling omission, not a sign that the underlying robust-Q construction is wrong.","tokens_in":10080,"tokens_out":15806,"duration_ms":156458,"concrete_test":"Apply a nontrivial relabeling to the numerical MDP, for example the permutation that reverses the state indices (1↔11, 2↔10, 3↔9, etc.), keeping the same transition probabilities and evaluation policy attached to the relabeled states. Run Algorithm 1 from Section III-B on the original and relabeled instances with the same δ and report the upper bounds J(x). If any J(x) changes, the certificate depends on the arbitrary label ordering. If the output is invariant under all permutations that preserve the transition graph, then the label metric is implicitly encoding geometric structure that must be made explicit; either way, this test forces the required metric assumption into the open.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section II, D^δ is defined per state-action as D^δ_{x,a} = {P̃ ∈ M(X) : W(P̃, P_{x,a}) ≤ δ}, with W computed using the cost |l-y| on the integer state labels. No metric on X is ever specified or included in the algorithm's input list: Algorithm 1 lists X, A, P, c(x,a,y), δ, π, and θ, but no metric. Consequently, renaming the states by any permutation changes the cost matrix, hence the set of admissible perturbed kernels, the fixed point of Lemma 6/Corollary 1, and the reported upper bound Σ_a π(a|x) Q^{δ,P}_π(x,a), even though the MDP dynamics and evaluation policy are unchanged. The numerical example illustrates the issue: states 8 and 9 are a goal state and a forbidden state with |8-9| = 1, so the ambiguity set permits moving probability mass directly between a target and a forbidden state at the smallest possible cost; this modeling choice is never justified. Unless the state space is explicitly endowed with a meaningful metric, or the metric is treated as a first-class modeling input with stated semantics, the central claim that the algorithm certifies robust p-safety of the given MDP is not well-defined.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributionally robust safety verification for finite Markov decision processes whose transition kernel is known only up to a Wasserstein-distance ambiguity set. It defines a robust safety function as the worst-case probability of reaching an unsafe state before a goal state, proves an upper bound on this function in terms of a distributionally robust Q-function (Lemma 3), derives a recursive Bellman-type equation (Lemma 4), and reformulates the robust Q-function as the solution of a finite convex program (Lemma 6 and Corollary 1). It then proposes a robust Q-iteration algorithm (Algorithm 1) and demonstrates the computed upper bounds on an 11-state MDP for increasing ambiguity radii. The central claim is that robust p-safety can be certified by computing the upper bound J(x)=∑_a π(a|x)Q^{δ,P}_π(x,a).","tokens_in":10309,"tokens_out":8524,"duration_ms":86427,"significance":"If the technical gaps are repaired, the paper offers a useful and computationally tractable certificate for robust probabilistic safety: the Wasserstein DRO reformulation in Lemma 6/Corollary 1 reduces an infinite-dimensional worst-case problem to a finite convex program, and the upper bound in Lemma 3 connects this program to the safety objective. The paper builds on standard results (Wasserstein duality, robust dynamic programming) rather than introducing a genuinely new mechanism, but the combination with p-safety is a reasonable contribution. On the negative side, the manuscript as written has three load-bearing problems: the Wasserstein cost is defined on arbitrary integer state labels without modeling justification, the robust Q-function is never defined on terminal states although the recursions and algorithm range over all states, and the proof of Lemma 6 contains a sign error and an unjustified minimax interchange. These are fixable, but they currently prevent the main claim from being accepted as stated. The paper does not provide code or machine-checked proofs; the numerical example is illustrative only.","major_comments":[{"comment":"The Wasserstein ambiguity set D^δ_{x,a} is defined using the cost |y−z| on the integer labels of the finite state set X, but no metric on X is specified as part of the MDP model or as an input to Algorithm 1. Since the labels are arbitrary, any permutation of the state space leaves the MDP dynamics and the evaluation policy unchanged but changes the cost matrix, the ambiguity set, and therefore the computed certificate. The paper's statement that the algorithm certifies robust p-safety of the MDP is consequently not well-defined unless the state metric is explicitly treated as a first-class modeling input with stated semantics. The authors should either supply a meaningful metric on X, explain what perturbation semantics the label distance encodes, and include that metric in Algorithm 1's input list, or state all results as relative to a chosen metric.","section":"Section II, Definition of D^δ and W(·,·); Algorithm 1"},{"comment":"The robust Q-function Q^{δ,P}_π(x,a) is defined only for (x,a)∈H×A in Definition 4, yet Lemma 6 states Eq. (2) for all (x,a)∈X×A and the max in Eq. (2) ranges over all l∈X, including goal and forbidden states. The recursive equation and the Q-iteration algorithm also initialize and update Q on terminal states without specifying a boundary value. Without a convention such as Q^{δ,P}_π(l,a)=0 for l∈E∪U, the equations in Lemma 6 and the iterations in Algorithm 1 are not well-posed. This is not a mere notational issue, because the terminal-state values enter the convex program and affect the computed upper bound.","section":"Definition 4, Lemma 6, and Algorithm 1"},{"comment":"The proof of the finite convex reformulation contains a sign error in the substitution that eliminates the inner supremum. The text says to choose λf(y) = −(c(x,a,y)+∑_a' Q^{δ,P}_π(y,a')π(a'|y)), but with this choice the term c(x,a,y)+∑_a'Q(... ) − λf(y) becomes 2(c+∑Q), not zero. The correct elimination requires λf(y)=c(x,a,y)+∑_a'Q(... ). In addition, the step from the constrained problem to Eq. (4) interchanges an infimum over λ≥0 with a supremum over f and over P̃ without a minimax argument, and the case λ=0 is not handled even though the stated infimum is over λ≥0. The resulting formula is the standard Wasserstein DRO reformulation and is likely correct, but the proof as written is invalid and must be repaired with a proper duality argument.","section":"Lemma 6 proof, Eq. (3)–(4)"}],"minor_comments":[{"comment":"The statement of Lemma 5 is internally inconsistent: it writes Q^{δ,P}_π(y,a) inside the expectation but then conditions on a′∼π(a′|y). It should read ∑_{a′∈A}Q^{δ,P}_π(y,a′)π(a′|y), or the notation should be corrected. The lemma also appears unused in the subsequent developments, so its role should be clarified.","section":"Lemma 5"},{"comment":"The convergence of the robust Q-iteration is asserted by reference to [14] but no contraction argument or stopping criterion analysis is given for the specific operator in Eq. (2). Since Algorithm 1 is the main computational deliverable, the authors should either prove convergence of the iteration or state precisely which conditions from [14] apply.","section":"Algorithm 1"},{"comment":"The numerical example reports the upper bounds J(x) for different δ but does not compare them against the exact robust safety function S^{δ,P}_π(x) or a sampling-based estimate. Without such a comparison, the tightness and thus the practical utility of the certificate cannot be assessed from the example.","section":"Section IV, Table I"},{"comment":"In the displayed dual form of the Wasserstein distance, the notation ||z1−z2|| appears in Eq. (3) after |z1−z2| was used in Eq. (1); the norm notation should be replaced by the absolute value for consistency. Minor typographical issues of this kind appear throughout the proof of Lemma 6.","section":"Eq. (1) and surrounding text"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely salvageable: the finite convex program in Lemma 6/Corollary 1 is a standard Wasserstein DRO reformulation, and the upper-bound idea is sound. The main obstacles are the unmodeled state metric, the missing terminal-state boundary values for Q, and the flawed proof of Lemma 6. I would encourage the editor to send the manuscript back for a major revision rather than reject it, provided the authors fix these issues and state the role of the metric explicitly."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper has a sensible idea—bounding a distributionally robust safety function by a robust Q-function and computing that via a Wasserstein-robust convex program—and the authors are upfront that this gives a conservative certificate. The extension of p-safety to kernel ambiguity is natural and the recursive Q-step, while borrowed from their own prior work, is applied correctly. The convex program in Lemma 6 is the standard Wasserstein DRO reformulation and, modulo proof detail, is probably right.\n\nThe soft spots are real. First, the Wasserstein distance is defined on the integer labels |l-y| with no stated metric on the state space; the ambiguity set changes under renumbering, so the certificate is not a property of the MDP alone. The metric needs to be a first-class modeling input with semantics. Second, the proof of Lemma 6 skips the step where the Lagrangian dual over the infinite constraint set (∀f) is justified; it may hold, but as written it is not rigorous. Also, Q is never defined at terminal states, while Eq. (2) ranges over all l∈X; the boundary condition should be stated explicitly. Third, and most seriously, the numerical table contradicts the theory at δ=0: with no ambiguity the robust safety function must equal the nominal safety function, but the reported J(4)=0.1 and J(7)=0.35 disagree with the correct values 0.35 and 0.5 computed from the stated MDP. That is not a small rounding error; it suggests either a bug in their Q-iteration, a mis-specified cost, or a different MDP than described. The absence of code or convergence details makes this hard to check.\n\nThe contribution is incremental, but that is not a flaw for a workshop-level paper. The core idea is plausible and the flaws are fixable. I would send it to review, with the expectation of a major revision focusing on the metric definition and a corrected reproducible numerical study. For researchers in robust MDPs and safety verification, this is a useful idea to know about, but the current version is not a reliable reference.","headline":"Plausible robust-safety upper bound, undermined by an arbitrary state-label metric and a δ=0 numerical table that doesn't match the theory.","tokens_in":10868,"tokens_out":5721,"would_cite":false,"duration_ms":46287,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For an MDP with only a nominal transition kernel, the worst-case probability of reaching an unsafe state is bounded above by a distributionally robust Q-function, and that Q-function is the solution of a finite convex program.","keywords":["distributionally robust optimization","safety verification","Markov decision process","Wasserstein ambiguity set","robust Q-function","robust value iteration","probabilistic safety"],"falsifier":"Permute the state labels of the numerical example, keeping the transition graph and probabilities identical, and rerun Algorithm 1 with the same $\\delta$. If the output $J(x)$ changes, the certificate depends on an arbitrary indexing choice. Alternatively, for a small state space, brute-force enumerate every transition kernel within $D^\\delta$ and compute the true worst-case hitting probability; if it exceeds $J(x)$ for any $\\delta$, the claimed upper bound is incorrect.","tokens_in":9848,"feed_emoji":"🛡️","tokens_out":7830,"duration_ms":62525,"temperature":0.7,"pith_summary":"This paper extends probabilistic safety verification to Markov decision processes whose transition kernel is not known exactly, only a nominal kernel and a Wasserstein ambiguity set around it. The authors define a robust safety function, the worst-case probability of hitting the unsafe set before the goal set, and prove an upper bound on it in terms of a distributionally robust Q-function. They then show this Q-function satisfies a recursive equation that is a finite convex program, so the upper bound can be computed by a model-based robust Q-iteration algorithm. A small numerical example demonstrates that the bound grows with the ambiguity radius $\\delta$, and that safety can be certified up to a certain $\\delta$.","feed_headline":"Worst-case safety under model drift becomes a convex program.","feed_subtitle":"A single Q-iteration pass bounds the worst-case risk of hitting unsafe states, for every kernel in a Wasserstein ball.","key_machinery":"The load-bearing object is the distributionally robust Q-function $Q_\\pi^{\\delta,P}(x,a)$, defined as the worst-case expected number of steps that hit the unsafe set before the goal, with the worst case taken over all transition kernels inside the Wasserstein ball $D^\\delta$. The key mechanism is the dual reformulation of the 1-Wasserstein distance, which converts the inner supremum over kernels into an infimum over a Lagrange multiplier $\\lambda$ plus auxiliary variables $h(y)$, yielding the finite convex program of Corollary 1: minimize $\\lambda \\delta + \\sum_y h(y) P_{x,a}(y)$ subject to $h(y) \\geq \\max_l ( -\\lambda |l-y| + c(x,a,l) + \\sum_{a'} Q_\\pi^{\\delta,P}(l,a') \\pi(a'|l) )$ for all $y$. Robust Q-iteration consists of sweeping through state-action pairs and updating each Q value by solving this program until the change falls below a threshold.","core_discovery":"The central claim is that robust p-safety can be certified without solving the infinite-dimensional worst-case problem over probability measures. For a fixed policy $\\pi$, the robust safety function $S_\\pi^{\\delta,P}(x)$ is upper-bounded by $\\sum_a \\pi(a|x) Q_\\pi^{\\delta,P}(x,a)$, where $Q_\\pi^{\\delta,P}$ is the distributionally robust Q-function. Using Kantorovich duality, the paper rewrites the Wasserstein constraint and obtains a finite convex program whose optimum is $Q_\\pi^{\\delta,P}(x,a)$ for each state-action pair. Iterating this convex program to convergence gives a value $J(x)$ that certifies robust p-safety when $J(x) \\leq p$ for all taboo states.","pith_inferences":["A consequence the paper does not state: the certificate depends on the metric $|l-y|$ between state labels, so unless the labels encode a meaningful distance, renumbering states changes the ambiguity set and can change the certified bound.","The bound in Lemma 3 may be loose because it moves the supremum inside the sum over actions; tightening this gap is a natural next step.","A testable extension: for a small MDP, enumerate all kernels inside $D^\\delta$ and compute the true worst-case hitting probability by brute force; comparing it with $J(x)$ would quantify the conservatism of the certificate."],"forward_implications":["For any policy $\\pi$ and nominal kernel, Algorithm 1 outputs an upper bound $J(x)$ on the worst-case unsafe-hit probability, so $J(x) \\leq p$ for all taboo states is a valid certificate of robust p-safety.","The certificate is monotone in the ambiguity radius: as $\\delta$ grows, the computed bound increases, and eventually the bound crosses the safety threshold $p$, meaning the model can no longer be certified.","Uncertainty in the transition kernel is handled entirely at the level of the nominal kernel and a single scalar radius, without requiring samples of the true kernel.","The per-state-action convex program has size linear in $|X|$, making it a tractable alternative to directly solving the infinite-dimensional stochastic program."],"supporting_citations":[{"why":"Defines the Wasserstein ambiguity set and provides the Kantorovich-duality reformulation that underlies the finite convex program.","marker":"[1]"},{"why":"Gives the dual representation of the Wasserstein distributionally robust program used in the derivation of Lemma 6.","marker":"[2]"},{"why":"Introduces the safety function for MDPs and its expected-cost recursive form, which the paper extends to the robust setting.","marker":"[12]"},{"why":"Establishes convergence of robust value iteration, cited to justify the robust Q-iteration algorithm.","marker":"[14]"},{"why":"Presents a convex optimization approach to Wasserstein distributionally robust MDPs, the closest predecessor the paper builds on.","marker":"[15]"},{"why":"Provides the recursive expression for the safety Q-function used in the proof of Lemma 4.","marker":"[17]"}],"fun_headline_variants":["Robust safety for MDPs via distributionally robust Q-iteration","Convex program certifies robust MDP safety","Worst-case MDP safety under model ambiguity","Distributionally robust Q-iteration for safe MDPs","One convex program bounds worst-case risk"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantee rests on the assumption that the integer labels of states, used in $|l-y|$ to define the Wasserstein distance, form a meaningful notion of distance; nothing in the MDP setup justifies this, so relabeling states changes the ambiguity set and hence the certificate.","fun_headline_variants_meta":{"raw":{"variants":["Robust safety for MDPs via distributionally robust Q-iteration","Convex program certifies robust MDP safety","Worst-case MDP safety under model ambiguity","Distributionally robust Q-iteration for safe MDPs","One convex program bounds worst-case risk"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000404,"raw_usage":{"total_tokens":2030,"prompt_tokens":795,"completion_tokens":1235,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":411,"completion_tokens_details":{"reasoning_tokens":1159}},"tokens_in":411,"tokens_out":1235,"duration_ms":8588,"temperature":1.0,"reasoning_tokens":1159,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:07:41.652344+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Permute the state labels of the numerical example, keeping the transition graph and probabilities identical, and rerun Algorithm 1 with the same $\\delta$. If the output $J(x)$ changes, the certificate depends on an arbitrary indexing choice. Alternatively, for a small state space, brute-force enumerate every transition kernel within $D^\\delta$ and compute the true worst-case hitting probability; if it exceeds $J(x)$ for any $\\delta$, the claimed upper bound is incorrect.","supporting_citations":[{"cited_title":"Data-driven distrib utionally robust optimization using the Wasserstein metric: Performance gu arantees and tractable reformulations,","cited_arxiv_id":null,"evidence_quote":"Defines the Wasserstein ambiguity set and provides the Kantorovich-duality reformulation that underlies the finite convex program."},{"cited_title":"Distributionally robust stocha stic optimiza- tion with Wasserstein distance,","cited_arxiv_id":null,"evidence_quote":"Gives the dual representation of the Wasserstein distributionally robust program used in the derivation of Lemma 6."},{"cited_title":"Probabilistic safe ty guarantees for Markov decision processes,","cited_arxiv_id":null,"evidence_quote":"Introduces the safety function for MDPs and its expected-cost recursive form, which the paper extends to the robust setting."},{"cited_title":"Robust dynamic programming,","cited_arxiv_id":null,"evidence_quote":"Establishes convergence of robust value iteration, cited to justify the robust Q-iteration algorithm."},{"cited_title":"A convex optimization approach to distributi onally robust Markov decision processes with Wasserstein distance,","cited_arxiv_id":null,"evidence_quote":"Presents a convex optimization approach to Wasserstein distributionally robust MDPs, the closest predecessor the paper builds on."},{"cited_title":"Safe Reinforcement Learning for Constrained Markov Decision Processes with Stochastic Stopping Time","cited_arxiv_id":"2403.15928","evidence_quote":"Provides the recursive expression for the safety Q-function used in the proof of Lemma 4."}],"review_version":1}