{"id":"0820187c-b30e-4903-aff7-d10623f5bfbd","arxiv_id":"1908.00697","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A data-only method computes finite-horizon reach-avoid probabilities by embedding conditional distributions in a reproducing kernel Hilbert space and evaluating the dynamic programming recursion as inner products.","lead":"This paper computes the probability that a controlled system reaches a target while staying safe, using only observed samples of the system's behavior. It maps random future states into a kernel function space, turning difficult integration into matrix arithmetic for model-free verification of black-box or human-in-the-loop systems.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Convergence proof invalid: value functions are discontinuous indicators, not in the Gaussian RKHS, so the Cauchy–Schwarz bound (27) is undefined at the first backward step.","rationale":"The reader's weakest assumption identifies exactly the load-bearing flaw: the true value functions are indicators, which are not in the Gaussian RKHS, so the Hilbert-space inner-product representation and the Cauchy–Schwarz error bound in Proposition 2 are not valid for the recursion's initial step. This is an internal inconsistency in the proof, not merely a disagreement with consensus: the proof quantifies over functions in H_X while the algorithm propagates discontinuous functions. The numerical demonstration cannot compensate because the chosen λ = 1 violates the paper's own convergence condition λ → 0, λ^3 M → ∞. Independent support exists — the paper provides code and a reproducible two-dimensional validation — but independent code validates the algorithm's practical behavior, not the claimed in-probability guarantee. A corrected analysis might have to use different tools, e.g., direct L2 or uniform error bounds for kernel ridge regression of discontinuous functions, or smoothing of the terminal indicator, but such an analysis is not in the paper. The central theoretical contribution therefore rests on an unproven and generally false premise, and the REJECT verdict is appropriate.","tokens_in":10807,"tokens_out":4061,"duration_ms":42352,"concrete_test":"Isolate the first backward step: set N = 1, X = [−2,2], T = [0,1], Gaussian kernel with σ = 0.1. Check whether 1_T belongs to the Gaussian RKHS. Since the RKHS of a continuous kernel contains only continuous functions and 1_T is discontinuous at the boundary, ||1_T||_{H_X} is infinite; equivalently, estimate 1_T by kernel ridge regression from M samples and compute the squared RKHS norm (e.g., α^T G α) with λ = 1/M^2; it diverges as M grows. If the norm diverges, Eq. (27) cannot yield a finite error bound at k = N−1, so Proposition 2 and Corollary 3 fail for the terminal indicator.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that Algorithm 1 yields V_0 approximating the reach-avoid probability with convergence in probability. The proof of Proposition 2 bounds the one-step error E_k(x) by 1_K(x) ||V_{k+1}||_{H_X} ||μ(x,π_k(x)) − μ̂(x,π_k(x))||_{H_X} (Eq. 27), which requires V_{k+1} ∈ H_X. But the recursion initializes V_N = 1_T and multiplies by 1_K, so the propagated objects are indicators and products of indicators with conditional expectations. For the Gaussian RBF kernel used throughout the paper, H_X consists only of continuous functions; an indicator of a nonempty proper Borel set is discontinuous on the boundary, so 1_T ∉ H_X and ||1_T||_{H_X} is infinite. Consequently Eq. (21), written as 1_K(x)⟨μ(x,π_k(x)), V_{k+1}⟩_{H_X}, is not a valid inner product evaluation at k = N−1, and the Cauchy–Schwarz step in Eq. (27) is not justified. Corollary 3 inherits this failure, so the claimed Nε bound has no foundation. The paper never states or proves the required membership condition. A secondary but reinforcing issue: the experiments use λ = 1, whereas Lemma 1 requires λ → 0 and λ^3 M → ∞, so even for continuous value functions the numerical configuration does not satisfy the stated convergence hypotheses. The algorithmic idea may be salvageable through a different analysis, but the paper's stated convergence guarantee is unsupported for the functions the algorithm actually propagates.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11115,"tokens_out":6668,"duration_ms":71193,"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":[{"comment":"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.","section":"Section III-A, Proposition 2 and Eq. (27)"},{"comment":"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":"Corollary 3 proof"},{"comment":"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":"Section III-B and Problem 2"},{"comment":"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.","section":"Section IV and Lemma 1"}],"minor_comments":[{"comment":"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.","section":"Section III-A"},{"comment":"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.","section":"Equation (14)"},{"comment":"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":"Introduction and Section IV-C"},{"comment":"The name 'Clohessey-Wiltshire-Hill' is a typo for 'Clohessy-Wiltshire-Hill'; it appears in the text and in Table I.","section":"Section IV-B"},{"comment":"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.","section":"Algorithm 1"}],"recommendation":"reject","confidential_remarks":"The core convergence result is invalid as written because the propagated indicator functions do not belong to the Gaussian RKHS. A substantial rewrite with a different analytical strategy, such as explicit smoothing of the value functions and a full error-propagation analysis, would be needed before the claims could be supported. I would not oppose a future resubmission of a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about arXiv:1908.00697. The kernel-embedding recursion for terminal-hitting reachability is a reasonable idea, and the authors ship code and a clean double-integrator validation. But the advertised convergence guarantee does not go through for the functions the algorithm actually propagates.\n\nWhat's new: prior RKHS embedding work covered MDPs with additive costs and POMDPs; this paper tailors conditional mean embeddings to finite-horizon multiplicative-cost reach-avoid, with an indicator factor at each step. The high-dimensional integrator demo (10,000 states) and the CWH rendezvous example are legitimate stress tests, and the runtimes are honestly reported. The paper also does a fair job of explaining the matrix operations and pointing to the Grunewalder et al. lineage.\n\nThe soft spot is load-bearing. Proposition 2 bounds the one-step error via Cauchy-Schwarz as 1_K(x) ||V_{k+1}||_{H_X} ||μ - μ̂||. That requires V_{k+1} to be an element of the Gaussian RKHS. The recursion starts with V_N = 1_T and multiplies by 1_K, so every propagated value function is an indicator or a product of an indicator with a conditional expectation. Indicators of nonempty proper Borel sets are discontinuous on the boundary, and a Gaussian RBF RKHS contains only continuous functions. So ||1_T||_{H_X} is not finite, and the inner product representation (12) is not valid at k=N-1. Corollary 3 inherits the problem. The paper never states or proves the needed membership condition. A secondary issue: the experiments fix λ=1, while Lemma 1 and Proposition 2 assume λ→0 and λ^3 M→∞. So even for continuous value functions, the numerical configuration is outside the stated hypotheses. That said, the flaw is in the proof, not necessarily in the algorithm. The estimator may well converge; the paper just doesn't show it. I'd also note a small in-sample reuse of samples for both building the embedding and evaluating V_{k+1}, which is minor compared to the RKHS issue.\n\nWho should read it: people working on data-driven verification or safe autonomy who want a practical, implementable baseline and are willing to distrust the stated error bound. It deserves a serious referee; the idea is worth engaging and the gap might be fixable with a different analysis (e.g., bounding the error via smooth approximations or using a different kernel class, or handling the indicator directly). I would not reject it out of hand, but I also wouldn't accept it in this form.","headline":"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.","tokens_in":11664,"tokens_out":2288,"would_cite":false,"duration_ms":23472,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["93E20","62G08","60J05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["stochastic reachability","kernel distribution embedding","reproducing kernel Hilbert space","reach-avoid problem","Markov control process","model-free verification","dynamic programming","nonparametric estimation"],"falsifier":"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.","tokens_in":10573,"feed_emoji":"🎯","tokens_out":7970,"duration_ms":73557,"temperature":0.7,"pith_summary":"The paper addresses the terminal-hitting reach-avoid problem: the probability that a stochastic control system reaches a target set at the final time while staying inside a safe set. It claims this probability can be computed from independent samples of the system's transitions, with no knowledge of the transition kernel. The key move is to embed the unknown kernel in a reproducing kernel Hilbert space, so the expectation in the backward dynamic programming recursion becomes an inner product. The resulting algorithm is claimed to converge in probability to the true value, with an error bound of at most $N\\varepsilon$ after $N$ steps, and pointwise queries whose cost scales linearly with state dimension. If true, this makes stochastic reachability verification model-free and applicable to high-dimensional, non-Gaussian systems.","feed_headline":"Compute reachability from data alone, no model needed","feed_subtitle":"Kernel embeddings turn the reach-avoid recursion into matrix operations that scale to high dimensions.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Adapts the RKHS model of transition dynamics in MDPs to the multiplicative-cost finite-horizon reach-avoid dynamic program.","marker":"[18]"},{"why":"Supplies the kernel distribution embedding construction and sample-based estimates used to build $\\hat{\\mu}$.","marker":"[20]"},{"why":"Provides the vector-valued RKHS regularized least-squares solution that gives the closed form of the embedding estimate.","marker":"[30]"},{"why":"Establishes that characteristic kernels make the embedding injective, supporting the pseudometric convergence argument.","marker":"[35]"},{"why":"Defines the terminal-hitting reach-avoid probability and its backward dynamic programming recursion that the algorithm approximates.","marker":"[1]"},{"why":"Supplies the reproducing kernel Hilbert space background for embedding probability measures.","marker":"[29]"}],"fun_headline_variants":["Kernel embeddings cut the model out of reachability analysis","Reach-avoid without a model: kernel embeddings do the math","Data-only reachability via kernel distribution embeddings","From samples to safety: kernel reachability that scales","No model, just data: solving reach-avoid with kernels"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Kernel embeddings cut the model out of reachability analysis","Reach-avoid without a model: kernel embeddings do the math","Data-only reachability via kernel distribution embeddings","From samples to safety: kernel reachability that scales","No model, just data: solving reach-avoid with kernels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000232,"raw_usage":{"total_tokens":1432,"prompt_tokens":827,"completion_tokens":605,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":443,"completion_tokens_details":{"reasoning_tokens":525}},"tokens_in":443,"tokens_out":605,"duration_ms":6017,"temperature":1.0,"reasoning_tokens":525,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:38:04.334552+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Modelling transition dynamics in MDPs with RKHS embedding s,","cited_arxiv_id":null,"evidence_quote":"Adapts the RKHS model of transition dynamics in MDPs to the multiplicative-cost finite-horizon reach-avoid dynamic program."},{"cited_title":"A Hilb ert space embedding for distributions,","cited_arxiv_id":null,"evidence_quote":"Supplies the kernel distribution embedding construction and sample-based estimates used to build $\\hat{\\mu}$."},{"cited_title":"On learning vector-valued functions,","cited_arxiv_id":null,"evidence_quote":"Provides the vector-valued RKHS regularized least-squares solution that gives the closed form of the embedding estimate."},{"cited_title":"Ker nel measures of conditional dependence,","cited_arxiv_id":null,"evidence_quote":"Establishes that characteristic kernels make the embedding injective, supporting the pseudometric convergence argument."},{"cited_title":"V erification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem ,","cited_arxiv_id":null,"evidence_quote":"Defines the terminal-hitting reach-avoid probability and its backward dynamic programming recursion that the algorithm approximates."},{"cited_title":"Berlinet and C","cited_arxiv_id":null,"evidence_quote":"Supplies the reproducing kernel Hilbert space background for embedding probability measures."}],"review_version":1}