Distributionally Robust Safety Verification for Markov Decision Processes

Abhijit Mazumdar; Rafal Wisniewski; Yuting Hou

REVIEW 3 major objections 4 minor 17 references

Distributionally Robust Safety Verification for Markov Decision Processes

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict Plausible robust-safety upper bound, undermined by an arbitrary state-label metric and a δ=0 numerical table that doesn't match the theory. read the letter →

arxiv 2411.15622 v2 pith:UK25IIVA submitted 2024-11-23 eess.SY cs.SY

Abhijit Mazumdar , Yuting Hou , Rafal Wisniewski This is my paper · ORCID

classification eess.SYcs.SY

keywords distributionallyrobustoptimizationsafetyverificationMarkovdecisionprocessWassersteinambiguitysetQ-functionvalueiterationprobabilistic

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

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

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

Referee Report

3 major / 4 minor

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

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 (3)

[Section II, Definition of D^δ and W(·,·); Algorithm 1] 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.
[Definition 4, Lemma 6, and Algorithm 1] 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.
[Lemma 6 proof, Eq. (3)–(4)] 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.

minor comments (4)

[Lemma 5] 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.
[Algorithm 1] 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 IV, Table I] 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.
[Eq. (1) and surrounding text] 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.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the robust safety upper bound follows from the definitions and standard Wasserstein duality; self-citations are not load-bearing.

full rationale

The derivation chain is not circular. The robust safety function is defined as a worst-case hitting probability (Definition 2); Lemmas 1 and 2 rewrite this using the standard cumulative-cost representation of hitting probabilities, and Lemma 3 obtains the upper bound by exchanging a finite sum over actions with a supremum. Lemma 4's recursion is the dynamic programming principle for the same cumulative cost; although it cites Lemma 2 of [17] (an overlapping-author preprint), the recursion is an immediate consequence of Definition 4 and is not used as an unverified uniqueness or ansatz. Lemma 6 and Corollary 1 derive a finite convex program via Kantorovich duality (external results [1], [2]) and a Lagrangian dual step; the program is a reformulation of the definition, not a fitted or renamed prediction. Algorithm 1 iterates this fixed-point equation and outputs the upper bound; no parameter is fitted to the output or to a subset of data. The only caveat is that the Wasserstein ambiguity set implicitly uses the metric |l-y| on integer state labels, so the certificate is relative to that metric; this is an unstated modeling input rather than a circular derivation, and it does not make the theorem's conclusion equal to its assumptions.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No parameters are fitted to data. The robustness radius delta is an input, not a fitted value. The load-bearing choices are the arbitrary state-label metric and the rectangularity of the ambiguity set, together with implicit zero boundary conditions at terminal states.

assumptions (5)

domain assumption Finite state and action spaces with stationary evaluation policy and time-invariant transition probabilities
Stated in Section II; the dynamic programming decomposition and Q-iteration rely on stationarity and finiteness.
domain assumption Ambiguity set is the product of per-state-action Wasserstein balls and the worst case can be chosen independently per transition
Used in Lemma 4 to write the robust Q-function recursively; rectangularity of the product ambiguity set is assumed without discussion.
standard math Strong duality and Kantorovich duality hold for the Wasserstein-constrained optimization over probability measures on a finite metric space
Used in Lemma 6 to pass from the infinite-dimensional supremum to the finite convex program; cited to [1].
ad hoc to paper The state space is metrized by absolute label difference |x-y|
The Wasserstein distance and the convex program depend on this arbitrary metric; no physical or graph distance is justified in Section II.
domain assumption Q-values at terminal states E and U are zero and the process stops on entry
Eq. (2) ranges over all l in X including terminal states, but Q is only defined for H times A; the zero boundary is implicit and never stated.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Distributionally Robust Safety Verification for Markov Decision Processes." pith.science (2026). https://pith.science/paper/UK25IIVA

@misc{pith2026241115622,
  author       = {Pith},
  title        = {Pith review of: Distributionally Robust Safety Verification for Markov Decision Processes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UK25IIVA}},
  note         = {Machine review of arXiv:2411.15622}
}

read the original abstract

In this paper, we propose a distributionally robust safety verification method for Markov decision processes where only an ambiguous transition kernel is available instead of the precise transition kernel. We define the ambiguity set around the nominal distribution by considering a Wasserstein distance. To this end, we introduce a robust safety function to characterize probabilistic safety in the face of uncertain transition probability. First, we obtain an upper bound on the robust safety function in terms of a distributionally robust Q-function. Then, we present a convex program-based distributionally robust Q-iteration algorithm to compute the robust Q-function. By considering a numerical example, we demonstrate our theoretical results.

Figures

Figures reproduced from arXiv: 2411.15622 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Data-driven distrib utionally robust optimization using the Wasserstein metric: Performance gu arantees and tractable reformulations,

P . Mohajerin Esfahani and D. Kuhn, “Data-driven distrib utionally robust optimization using the Wasserstein metric: Performance gu arantees and tractable reformulations,” Mathematical Programming, vol. 171, no. 1, pp. 115–166, 2018

work page 2018
[2]

Distributionally robust stocha stic optimiza- tion with Wasserstein distance,

R. Gao and A. Kleywegt, “Distributionally robust stocha stic optimiza- tion with Wasserstein distance,” Mathematics of Operations Research , vol. 48, no. 2, pp. 603–655, 2023

work page 2023
[3]

Fast bellman upda tes for Wasserstein distributionally robust MDPs,

Z. Y u, L. Dai, S. Xu, S. Gao, and C. P . Ho, “Fast bellman upda tes for Wasserstein distributionally robust MDPs,” Advances in Neural Information Processing Systems , vol. 36, 2024

work page 2024
[4]

A moment -based distributionally robust optimization model for air trafﬁc ﬂow manage- ment,

B. Hao, K. Cai, Y .-P . Fang, A. Fadil, and D. Feng, “A moment -based distributionally robust optimization model for air trafﬁc ﬂow manage- ment,” in 2021 IEEE/AIAA 40th Digital Avionics Systems Conference (DASC). IEEE, 2021, pp. 1–7

work page 2021
[5]

Understan ding contrastive learning via distributionally robust optimiz ation,

J. Wu, J. Chen, J. Wu, W. Shi, X. Wang, and X. He, “Understan ding contrastive learning via distributionally robust optimiz ation,” Advances in Neural Information Processing Systems , vol. 36, 2024

work page 2024
[6]

A classiﬁcation of phi-diverg ences for data- driven stochastic optimization,

D. Love and G. Bayraksan, “A classiﬁcation of phi-diverg ences for data- driven stochastic optimization,” in IIE Annual Conference. Proceedings. Institute of Industrial and Systems Engineers (IISE), 2014 , p. 2780

work page 2014
[7]

p-safe analysis of stochastic hybrid processes,

R. Wisniewski, M. L. Bujorianu, and C. Sloth, “ p-safe analysis of stochastic hybrid processes,” IEEE Transactions on Automatic Control , vol. 65, no. 12, pp. 5220–5235, 2020

work page 2020
[8]

Safety of stochasti c systems: An analytic and computational approach,

R. Wisniewski and L.-M. Bujorianu, “Safety of stochasti c systems: An analytic and computational approach,” Automatica, vol. 133, p. 109839, 2021

work page 2021

Show all 17 references

[9]

St ochastic safety for random dynamical systems,

M. L. Bujorianu, R. Wisniewski, and E. Boulougouris, “St ochastic safety for random dynamical systems,” in 2021 American Control Conference (ACC). IEEE, 2021, pp. 1340–1345

2021
[10]

p-safety and stability,

——, “p-safety and stability,” IF AC-PapersOnLine, vol. 54, no. 9, pp. 665–670, 2021

2021
[11]

Stochastic safety for markov chains,

——, “Stochastic safety for markov chains,” IEEE Control Systems Letters, vol. 5, no. 2, pp. 427–432, 2020

2020
[12]

Probabilistic safe ty guarantees for Markov decision processes,

R. Wisniewski and M. L. Bujorianu, “Probabilistic safe ty guarantees for Markov decision processes,” IEEE Transactions on Automatic Control , 2023

2023
[13]

On a space of tota lly addi- tive functions,

L. V . Kantorovich and S. Rubinshtein, “On a space of tota lly addi- tive functions,” V estnik of the St. Petersburg University: Mathematics , vol. 13, no. 7, pp. 52–59, 1958

1958
[14]

Robust dynamic programming,

G. N. Iyengar, “Robust dynamic programming,” Mathematics of Oper- ations Research, vol. 30, no. 2, pp. 257–280, 2005

2005
[15]

A convex optimization approach to distributi onally robust Markov decision processes with Wasserstein distance,

I. Y ang, “A convex optimization approach to distributi onally robust Markov decision processes with Wasserstein distance,” IEEE control systems letters , vol. 1, no. 1, pp. 164–169, 2017

2017
[16]

A dynamic game approach to distributionally robus t safety speciﬁcations for stochastic systems,

——, “A dynamic game approach to distributionally robus t safety speciﬁcations for stochastic systems,” Automatica, vol. 94, pp. 94–101, 2018

2018
[17]

Safe r einforcement learning for constrained Markov decision processes with st ochastic stopping time,

A. Mazumdar, R. Wisniewski, and M. L. Bujorianu, “Safe r einforcement learning for constrained Markov decision processes with st ochastic stopping time,” arXiv preprint arXiv:2403.15928 , 2024

2024 arXiv

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Data-driven distrib utionally robust optimization using the Wasserstein metric: Performance gu arantees and tractable reformulations,

P . Mohajerin Esfahani and D. Kuhn, “Data-driven distrib utionally robust optimization using the Wasserstein metric: Performance gu arantees and tractable reformulations,” Mathematical Programming, vol. 171, no. 1, pp. 115–166, 2018

work page 2018

[2] [2]

Distributionally robust stocha stic optimiza- tion with Wasserstein distance,

R. Gao and A. Kleywegt, “Distributionally robust stocha stic optimiza- tion with Wasserstein distance,” Mathematics of Operations Research , vol. 48, no. 2, pp. 603–655, 2023

work page 2023

[3] [3]

Fast bellman upda tes for Wasserstein distributionally robust MDPs,

Z. Y u, L. Dai, S. Xu, S. Gao, and C. P . Ho, “Fast bellman upda tes for Wasserstein distributionally robust MDPs,” Advances in Neural Information Processing Systems , vol. 36, 2024

work page 2024

[4] [4]

A moment -based distributionally robust optimization model for air trafﬁc ﬂow manage- ment,

B. Hao, K. Cai, Y .-P . Fang, A. Fadil, and D. Feng, “A moment -based distributionally robust optimization model for air trafﬁc ﬂow manage- ment,” in 2021 IEEE/AIAA 40th Digital Avionics Systems Conference (DASC). IEEE, 2021, pp. 1–7

work page 2021

[5] [5]

Understan ding contrastive learning via distributionally robust optimiz ation,

J. Wu, J. Chen, J. Wu, W. Shi, X. Wang, and X. He, “Understan ding contrastive learning via distributionally robust optimiz ation,” Advances in Neural Information Processing Systems , vol. 36, 2024

work page 2024

[6] [6]

A classiﬁcation of phi-diverg ences for data- driven stochastic optimization,

D. Love and G. Bayraksan, “A classiﬁcation of phi-diverg ences for data- driven stochastic optimization,” in IIE Annual Conference. Proceedings. Institute of Industrial and Systems Engineers (IISE), 2014 , p. 2780

work page 2014

[7] [7]

p-safe analysis of stochastic hybrid processes,

R. Wisniewski, M. L. Bujorianu, and C. Sloth, “ p-safe analysis of stochastic hybrid processes,” IEEE Transactions on Automatic Control , vol. 65, no. 12, pp. 5220–5235, 2020

work page 2020

[8] [8]

Safety of stochasti c systems: An analytic and computational approach,

R. Wisniewski and L.-M. Bujorianu, “Safety of stochasti c systems: An analytic and computational approach,” Automatica, vol. 133, p. 109839, 2021

work page 2021