REVIEW 4 major objections 5 minor 39 references
Model-Free Stochastic Reachability Using Kernel Distribution Embeddings
T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper claims that the terminal-hitting reach-avoid probability can be computed from samples of the stochastic kernel alone, without ever knowing the system model.
desk verdict The algorithm is plausible and the experiments are honest, but the convergence proof assumes the value functions belong to the RKHS, and the indicator functions the recursion actually propagates do not. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the conditional distribution embedding $\mu(x,u) = \int \mathcal{K}_X(y,\cdot)\,Q(dy|x,u)$ in the RKHS $\mathcal{H}_X$. Its defining property is the inner-product identity $\langle \mu(x,u), f\rangle_{\mathcal{H}_X} = E_{y\sim Q(\cdot|x,u)}[f(y)]$, which converts every expectation in the reach-avoid recursion into an inner product. The empirical estimate from samples is the regularized least-squares solution $\hat{\mu}(x,u) = \eta\Phi^\top(G + \lambda M I)^{-1}\Psi \mathcal{K}_{X\times U}((x,u),\cdot)$, so evaluating the approximate value function is a matrix-vector product with coefficients $\beta(x,u)$. This is what carries the argument: the unknown stochastic kernel is never constructed explicitly.
What would settle it
Run Algorithm 1 with a Gaussian kernel on a one-step problem ($N=1$) where $V_0^\pi(x)$ is known exactly, such as a deterministic map with target set $T$ having a sharp boundary, so $V_0^\pi(x)=1_K(x)1_T(f(x))$. Evaluate $\hat{V}_0^\pi$ at points approaching the boundary from both sides as $M$ grows with $\lambda\to 0$ and $\lambda^3 M\to\infty$. Since the Gaussian RKHS contains only continuous functions, the inner-product identity (12) cannot hold for the indicator $f=1_T$, and the pointwise error will not converge to zero near the boundary.
Extended reading notes
Core claim
For a Markov control process with unknown stochastic kernel $Q$, the value function $V_k^\pi(x) = 1_K(x)\,E_{y \sim Q(\cdot|x,\pi_k(x))}[V_{k+1}^\pi(y)]$ can be replaced by $\hat{V}_k^\pi(x) = 1_K(x)\,\langle \hat{\mu}(x,\pi_k(x)), V_{k+1}^\pi\rangle_{\mathcal{H}_X}$, where $\hat{\mu}$ is a regularized empirical estimate of the conditional distribution embedding of $Q$ built from $M$ samples. The paper proves, under an RKHS membership assumption, that $|V_0^\pi(x) - \hat{V}_0^\pi(x)|$ converges in probability to $0$ and is bounded by $N\varepsilon$. Thus the dynamic programming recursion is computed by matrix operations using only data, and the same construction applies to the maximal reach-avoid policy through a supremum over controls.
Load-bearing premise
The proof assumes every value function propagated through the recursion lies in the reproducing kernel Hilbert space, but the recursion initializes and multiplies with indicator functions of target and safe sets, which are discontinuous and hence not contained in a Gaussian RKHS.
Editorial extensions
If this is right
- Reachability verification becomes model-free: only i.i.d. transition samples are needed, not the equations of the dynamics or the disturbance distribution.
- The recursive computation of reach-avoid probabilities becomes a sequence of matrix-vector products, so evaluating a pointwise estimate costs $O(M^2)$ with the inverse precomputed and scales linearly in state dimension through kernel evaluations.
- The error bound $|V_0^\pi - \hat{V}_0^\pi| \leq N\varepsilon$ grows linearly with the horizon, independent of the state dimension, which is why a 10,000-dimensional integrator example is feasible.
- Non-Gaussian disturbances, such as a beta distribution, are included with no modification because the method is distribution-free.
- A maximal reach-avoid policy can be approximated by taking the supremum over controls of the same kernel-based expression.
Reading between the lines
- The sample matrix $G$ depends only on the sampled state-action pairs, not on the dynamics, so the same kernel inverse could be reused across different policies or different target and safe sets.
- An online variant could update the embedding as new observations stream in, turning the method into an adaptive certification tool for human-in-the-loop or black-box systems.
- Because Gaussian kernels are smooth, the estimate will necessarily smooth over discontinuities of the true value function at the boundaries of the target and safe sets; local sample refinement near boundaries is a natural practical remedy, though the RKHS membership gap remains.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a model-free, sample-based method for the terminal-hitting stochastic reachability problem. The transition kernel is represented through a conditional distribution embedding in an RKHS, so that the expectation in the dynamic programming recursion becomes an inner product. Algorithm 1 computes approximate value functions from i.i.d. transition samples, and the paper claims convergence in probability (Proposition 2, Corollary 3). The method is demonstrated on a double integrator, a 10,000-dimensional integrator chain, and a Clohessy-Wiltshire-Hill rendezvous example, with code provided. The writing is clear and the numerical scope is ambitious, but the central theoretical guarantee is not established.
Significance. If the convergence claims were valid, the paper would offer a genuinely model-free alternative to grid-based or optimization-based stochastic reachability, with pointwise queries whose cost scales linearly in state dimension. The availability of reproducible code and the high-dimensional integrator example are concrete strengths. However, the main theorem relies on an unstated and false premise: that the propagated value functions belong to the Gaussian RKHS. Since the algorithm propagates indicator functions of the target and safe sets, the inner-product representation and the Cauchy-Schwarz bound used in the proof are not justified. The optimal-policy problem is also stated but not analyzed. These issues are load-bearing, so the paper cannot be accepted in its current form.
major comments (4)
- [Section III-A, Proposition 2 and Eq. (27)] The proof of Proposition 2 requires V_{k+1} to lie in the RKHS H_X: Eq. (26) writes the one-step error as an inner product in H_X, and Eq. (27) invokes Cauchy-Schwarz with the RKHS norm of V_{k+1}. However, the recursion initializes V_N^π = 1_T in Algorithm 1 and then sets V_k^π(x) = 1_K(x) times a conditional expectation, so the propagated objects are indicator functions or products of an indicator with a conditional expectation. For the Gaussian RBF kernel used throughout the paper, H_X consists of continuous functions; an indicator of a nonempty proper Borel set with nonempty boundary is discontinuous and is not an element of H_X. Hence the inner product in Eq. (21) is not a valid RKHS inner product at k = N-1, the norm ||V_{k+1}||_{H_X} in Eq. (27) is not finite, and the Cauchy-Schwarz step is unjustified. The paper never states or proves the required membership condition. This invalidates Proposition 2 and, through it, Corollary 3.
- [Corollary 3 proof] The induction in Corollary 3 is not justified. Proposition 2 bounds the error between the exact Bellman operator applied to the exact value function V_{k+1} and the estimator applied to the same V_{k+1}. In Algorithm 1, for k < N-1, the estimator is applied to the already approximated value function V_{k+1}, and the additional term involving V_{k+1} - V_{k+1} is not bounded. No contraction, Lipschitz, or stability property of the reachability operator is proved, so the claimed accumulated bound |V_0^π(x) - V_0^π(x)| ≤ Nε does not follow from the one-step bound.
- [Section III-B and Problem 2] Problem 2 asks for an approximation of the maximal reach-avoid policy that converges in probability, but Section III-B only defines the approximate optimal value functions and policy via the supremum. No convergence theorem, error bound, or consistency argument is given for the supremum or for the arg sup. The numerical experiments either use a fixed zero policy (integrator examples) or a precomputed safety controller (CWH example), so the optimal-policy contribution is neither proved nor demonstrated.
- [Section IV and Lemma 1] The numerical experiments use λ = 1 with M = 1024, whereas Lemma 1 and Proposition 2 require λ → 0 and λ^3 M → ∞. Thus the experiments are run outside the regime in which the stated convergence theorem applies; for fixed λ the estimator has a bias that need not vanish as M grows. The observed error decrease in Fig. 2 therefore cannot be attributed to the paper's convergence result, and the numerical section does not validate the theorem's hypotheses.
minor comments (5)
- [Section III-A] The heading 'A. Terminal-Hitting Time Problem' appears twice, once before Algorithm 1 and again immediately after it; this appears to be a formatting error.
- [Equation (14)] The norm in the regularized least-squares problem uses the space H_Υ, but H_Υ is never defined; please specify the vector-valued RKHS and its norm explicitly.
- [Introduction and Section IV-C] The introduction claims the method 'does not suffer from the curse of dimensionality,' but Section IV-C states that the number of samples needed increases with state dimensionality and can be prohibitive; these statements should be reconciled or qualified.
- [Section IV-B] The name 'Clohessey-Wiltshire-Hill' is a typo for 'Clohessy-Wiltshire-Hill'; it appears in the text and in Table I.
- [Algorithm 1] The approximate value functions V_k^π are claimed to map to [0,1], but the kernel estimator Y^T β(x,π_k(x)) is not guaranteed to lie in [0,1]; the paper should state whether a projection or clipping step is intended.
Circularity Check
No circularity found: kernel embedding estimator independently approximates the stochastic kernel; the RKHS indicator-function gap is a correctness issue, not a circular reduction.
full rationale
The derivation is self-contained with respect to circularity. Algorithm 1 computes the reach-avoid probability by substituting a kernel conditional mean embedding estimator \bar{\mu} for the true stochastic kernel \mu inside the standard dynamic programming recursion (Eqs. 3-4 and 21-23). The convergence argument (Proposition 2, Corollary 3) relies on Lemma 1, which is an external result ([18, Lemma 2.2]) on the convergence of conditional mean embeddings, not on a self-citation by the present authors. The kernel bandwidth and regularization parameter are not fitted to the reach-avoid probability being predicted; they are fixed hyperparameters (sigma=0.1, lambda=1) with a cross-validation suggestion. Nothing in the paper defines the target reach-avoid probability in terms of the estimator, and no parameter is fitted to a subset of the target data and then used to predict a statistically forced quantity. The same samples are reused for estimating the embedding and evaluating the value function, but this is standard empirical conditional mean embedding practice and is covered by the cited convergence lemma; it does not make the prediction equal to its input. The proof does contain a genuine omitted hypothesis: the Cauchy-Schwarz step in Eq. (27) requires V_{k+1} in H_X, and the value functions are initialized as indicator functions (Eq. 3), which are not in a Gaussian RKHS. However, this is a correctness/assumption gap, not circularity, because the claimed convergence does not reduce to the paper's own assumptions.
Assumptions & free parameters
free parameters (3)
- Kernel bandwidth σ =
0.1
- Regularization parameter λ =
1
- Normalizing constant η =
unspecified
assumptions (4)
- standard math Standard RKHS theory: reproducing property, Riesz representation, characteristic kernel embedding injectivity.
- domain assumption The stochastic kernel Q is Borel-measurable on compact Borel state and action spaces, and samples are drawn i.i.d. from Q.
- standard math Lemma 1 (sup-norm convergence of the conditional mean embedding) from [18] is imported without proof.
- ad hoc to paper Value functions V_k lie in the RKHS H_X.
Cite this review
Pith. "Pith review of Model-Free Stochastic Reachability Using Kernel Distribution Embeddings." pith.science (2026). https://pith.science/paper/TNUXRG3Q
@misc{pith2026190800697,
author = {Pith},
title = {Pith review of: Model-Free Stochastic Reachability Using Kernel Distribution Embeddings},
year = {2026},
howpublished = {\url{https://pith.science/paper/TNUXRG3Q}},
note = {Machine review of arXiv:1908.00697}
}
read the original abstract
We present a solution to the terminal-hitting stochastic reach-avoid problem for a Markov control process. This solution takes advantage of a nonparametric representation of the stochastic kernel as a conditional distribution embedding within a reproducing kernel Hilbert space (RKHS). Because the disturbance is modeled as a data-driven stochastic process, this representation avoids intractable integrals in the dynamic recursion of the reach-avoid problem since the expectations can be calculated as an inner product within the RKHS. We demonstrate this approach on a high-dimensional chain of integrators and on Clohessy-Wiltshire-Hill dynamics.
Figures
Reference graph
Works this paper leans on
-
[1]
V erification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem ,
S. Summers and J. Lygeros, “V erification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem ,” Automatica, vol. 46, no. 12, pp. 1951–1961, Dec. 2010
work page 1951
-
[2]
Probab ilistic reacha- bility and safety for controlled discrete time stochastic h ybrid systems,
A. Abate, M. Prandini, J. Lygeros, and S. Sastry, “Probab ilistic reacha- bility and safety for controlled discrete time stochastic h ybrid systems,” Automatica, vol. 44, no. 11, pp. 2724–2734, November 2008
work page 2008
-
[3]
Stochastic reachabil ity for control of spacecraft relative motion,
K. Lesser, M. Oishi, and R. Erwin, “Stochastic reachabil ity for control of spacecraft relative motion,” in IEEE Conf. Dec. & Ctrl. , Dec 2013, pp. 4705–4712
work page 2013
-
[4]
A. Vinod, V . Sivaramakrishnan, and M. Oishi, “Piecewise -affine approximation-based stochastic optimal control with Gaus sian joint chance constraints,” in Amer . Ctl. Conf., 2019
work page 2019
-
[5]
H. Sartipizadeh, A. Vinod, B. Acikmese, and M. Oishi, “V o ronoi partition-based scenario reduction for fast sampling-bas ed stochastic reachability computation of LTI systems,” Amer . Ctrl. Conf. , pp. 37– 44, 2018
work page 2018
-
[6]
Multiple pursuer-base d intercept via forward stochastic reachability,
A. Vinod, B. HomChaudhuri, C. Hintz, A. Parikh, S. Buerge r, M. Oishi, G. Brunson, S. Ahmad, and R. Fierro, “Multiple pursuer-base d intercept via forward stochastic reachability,” in Amer . Ctrl. Conf. , 2018, pp. 1559–1566
work page 2018
-
[7]
A. Vinod, S. Rice, Y . Mao, M. Oishi, and B. Ac ¸ıkmes ¸e, “St ochastic motion planning using successive convexification and proba bilistic oc- cupancy functions,” in IEEE Conf. Dec. & Ctrl. , 2018, pp. 4425–4432
work page 2018
-
[8]
Scalable underapproximative ver ification of stochastic LTI systems using convexity and compactness,
A. Vinod and M. Oishi, “Scalable underapproximative ver ification of stochastic LTI systems using convexity and compactness,” i n Hybrid Sys.: Comp. and Ctrl. , 2018, pp. 1–10
work page 2018
Show all 39 references
-
[9]
Scalable underapproximation for the stochastic reach-avoid problem for high dimensional LTI systems using Fourier transforms,
A. Vinod and M. Oishi, “Scalable underapproximation for the stochastic reach-avoid problem for high dimensional LTI systems using Fourier transforms,” IEEE Ctrl. Syst. Letters , vol. 1, no. 2, pp. 316–321, 2017
2017
-
[10]
Approximate dynamic programming for stochast ic reacha- bility,
N. Kariotoglou, S. Summers, T. Summers, M. Kamgarpour, and J. Lygeros, “Approximate dynamic programming for stochast ic reacha- bility,” in Euro. Ctrl. Conf. , 2013, pp. 584–589
2013
-
[11]
Policy search for the optimal control of Markov decision pr ocesses: A novel particle-based iterative scheme,
G. Manganini, M. Pirotta, M. Restelli, L. Piroddi, and M . Prandini, “Policy search for the optimal control of Markov decision pr ocesses: A novel particle-based iterative scheme,” IEEE Trans. on Cybern. , vol. 46, no. 11, pp. 2643–2655, 2015
2015
-
[12]
A time-dependent Hamilton- Jacobi formulation of reachable sets for continuous dynami c games,
I. Mitchell, A. Bayen, and C. Tomlin, “A time-dependent Hamilton- Jacobi formulation of reachable sets for continuous dynami c games,” IEEE Trans. Autom. Ctrl. , vol. 50, no. 7, pp. 947–957, 2005
2005
-
[13]
Reach-avoi d problems with time-varying dynamics, targets and constraints,
J. Fisac, M. Chen, C. Tomlin, and S. Sastry, “Reach-avoi d problems with time-varying dynamics, targets and constraints,” in Hybrid Syst.: Comput. and Ctrl. , 2015, pp. 11–20
2015
-
[14]
Bellman and S
R. Bellman and S. Dreyfus, Applied Dynamic Programming. Princeton University Press, 1962
1962
-
[15]
Sch¨ olkopf and A
B. Sch¨ olkopf and A. Smola, Learning with kernels: Support vector machines, regularization, optimization, and beyond . Cambridge, MA: MIT Press, 2002
2002
-
[16]
Shawe-Taylor and N
J. Shawe-Taylor and N. Cristianini, Kernel Methods for Pattern Analysis. New Y ork, NY: Cambridge University Press, 2004
2004
-
[17]
Theory of reproducing kernels,
N. Aronszajn, “Theory of reproducing kernels,” Trans. of the Amer . Math. Soc. , vol. 68, no. 3, pp. 337–404, 1950
1950
-
[18]
Modelling transition dynamics in MDPs with RKHS embedding s,
S. Gr¨ unew¨ alder, G. Lever, L. Baldassarre, M. Pontil, and A. Gretton, “Modelling transition dynamics in MDPs with RKHS embedding s,” in Int’l Conf. Mach. Learn. , 2012, pp. 535–542
2012
-
[19]
Kernel embedding s of con- ditional distributions: A unified kernel framework for nonp arametric inference in graphical models,
L. Song, K. Fukumizu, and A. Gretton, “Kernel embedding s of con- ditional distributions: A unified kernel framework for nonp arametric inference in graphical models,” IEEE Signal Process. Mag. , vol. 30, pp. 98–111, Jul. 2013
2013
-
[20]
A Hilb ert space embedding for distributions,
A. Smola, A. Gretton, L. Song, and B. Sch¨ olkopf, “A Hilb ert space embedding for distributions,” in Int’l Conf. Algorithmic Learn. Theory , 2007, pp. 13–31
2007
-
[21]
Modelling policies in mdps in reproducing kernel hilbert space,
G. Lever and R. Stafford, “Modelling policies in mdps in reproducing kernel hilbert space,” in Artif. Intell. and Stats. , 2015, pp. 590–598
2015
-
[22]
Hilbert space embeddings of POMDPs,
Y . Nishiyama, A. Boularias, A. Gretton, and K. Fukumizu , “Hilbert space embeddings of POMDPs,” in Uncertainty Artif. Intell. , 2012, pp. 644–653
2012
-
[23]
Hilbert sp ace em- beddings of conditional distributions with applications t o dynamical systems,
L. Song, J. Huang, A. Smola, and K. Fukumizu, “Hilbert sp ace em- beddings of conditional distributions with applications t o dynamical systems,” in Int’l Conf. Mach. Learn. , 2009, pp. 961–968
2009
-
[24]
Billingsley, Probability and Measure
P . Billingsley, Probability and Measure . John Wiley & Sons, 2012
2012
-
[25]
Chow and H
Y . Chow and H. Teicher, Probability Theory: Independence, Inter- changeability, Martingales. Springer, 2012
2012
-
[26]
Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming
M. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014
2014
-
[27]
Bertsekas and S
D. Bertsekas and S. Shreve, Stochastic optimal control: The discrete- time case . Athena Scientific Publ., 1996
1996
-
[28]
Steinwart and A
I. Steinwart and A. Christmann, Support vector machines . Springer, 2008
2008
-
[29]
Berlinet and C
A. Berlinet and C. Thomas-Agnan, Reproducing Kernel Hilbert Spaces in Probability and Statistics . Springer, 2011
2011
-
[30]
On learning vector-valued functions,
C. Micchelli and M. Pontil, “On learning vector-valued functions,” Neural Comput. , vol. 17, no. 1, pp. 177–204, 2005
2005
-
[31]
Conditional mean embeddings as regressors,
S. Gr¨ unew¨ alder, G. Lever, L. Baldassarre, S. Patterson, A. Gretton, and M. Pontil, “Conditional mean embeddings as regressors,” in Int’l Conf. Mach. Learn. , 2012, pp. 1823–1830
2012
-
[32]
Hilbert space embeddings and metrics on prob ability measures,
B. Sriperumbudur, A. Gretton, K. Fukumizu, B. Sch¨ olko pf, and G. Lanckriet, “Hilbert space embeddings and metrics on prob ability measures,” J. Mach. Learn. Res. , vol. 11, pp. 1517–1561, Aug. 2010
2010
-
[33]
A kernel method for the two-sample-problem,
A. Gretton, K. Borgwardt, M. Rasch, B. Sch¨ olkopf, and A . Smola, “A kernel method for the two-sample-problem,” in Adv. Neural Inf. Proc. Sys., 2007, pp. 513–520
2007
-
[34]
A kernel two-sample test,
A. Gretton, K. Borgwardt, M. Rasch, B. Sch¨ olkopf, and A . Smola, “A kernel two-sample test,” J. Mach. Learn. Res. , vol. 13, pp. 723–773, 2012
2012
-
[35]
Ker nel measures of conditional dependence,
K. Fukumizu, A. Gretton, X. Sun, and B. Sch¨ olkopf, “Ker nel measures of conditional dependence,” in Adv. Neural Inf. Proc. Sys. , 2008, pp. 489–496
2008
-
[36]
Affine controller synthesis for s tochastic reachability via difference of convex programming,
A. Vinod and M. Oishi, “Affine controller synthesis for s tochastic reachability via difference of convex programming,” in IEEE Conf. Dec. & Ctrl. (to appear) , 2019
2019
-
[37]
SReachTools: A Matl ab stochastic reachability toolbox,
A. Vinod, J. Gleason, and M. Oishi, “SReachTools: A Matl ab stochastic reachability toolbox,” in Hybrid Sys: Comp. & Ctrl. , 2019, pp. 33–38
2019
-
[38]
Random features for large-scal e kernel machines,
A. Rahimi and B. Recht, “Random features for large-scal e kernel machines,” in Adv. Neural Inf. Process. Syst. , 2008, pp. 1177–1184
2008
-
[39]
Fastfood–approximati ng kernel expan- sions in loglinear time,
Q. Le, T. Sarl´ os, and A. Smola, “Fastfood–approximati ng kernel expan- sions in loglinear time,” in Int’l Conf. Mach. Learn. , 2013
2013
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.