- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper combines spectral learning of weighted finite automata (WFA) with automata-based verification to establish finite-sample PAC guarantees for finite-horizon safety of POMDPs under a fixed controller. The approach is mathematically interesting, and the perturbation analysis appears plausible under the stated assumptions. However, the manuscript is dense, it is not easy to follow, and the gap between its theoretical guarantees and practical implementation remains unclear.
I lean toward rejection in the current form. The main concerns are the unclear implementability of the certificate and the extremely conservative sample requirements. A computable confidence bound and clearer specification of the required prior information would substantially strengthen the work.
Critical strengths
The authors derive finite-sample estimation-error bounds and PAC safety-certification guarantees for both i.i.d. trajectories and a single stationary, geometrically mixing trajectory.
Critical weaknesses
- Basis selection: Assumption 3.3 requires a full-rank Hankel block with the unknown minimal rank. The paper does not explain how to select the rank and basis from noisy data while preserving the PAC guarantee.
- Computability of error bounds: The error radius depends on population-level quantities, including the smallest singular value of the true Hankel block. The single-trajectory bound also depends on mixing parameters. How can practitioners compute a valid certificate when these quantities are unknown?
- Sample complexity: The reported sufficient thresholds are approximately (1.3\times10^{14}) i.i.d. trajectories and (8.71\times10^{18}) single-trajectory sampling windows for the illustrated (T=3) example. These conservative bounds raise serious concerns about practical utility.
- Scope of safety: The guarantee concerns observation-language probabilities, not necessarily hidden-state safety or worst-case exclusion of hazardous behaviors. This distinction should be made explicit.
Questions for authors
- How are the Hankel rank and basis selected in practice?
- Can the error radius be computed from observed data and stated prior information while preserving the PAC guarantee?
- How are unknown mixing parameters handled, and is there an implementable stopping rule?
- What additional assumptions would connect observation-level certification to physical-state safety?
2 comments
Thanks for the response. The responses indeed clarify the theoretical contribution and acknowledge several limitations. However, the central gap between the stated PAC guarantees and a practically implementable certification procedure remains. These clarifications do not change my overall assessment. I continue to view the theoretical results as interesting, but consider the unresolved implementation issues and the conservatism of the current guarantees significant limitations of the work.
We thank the reviewer for the useful comments and suggestions.
We acknowledge that the sufficient sample sizes obtained from our bounds can be very large, which limits their immediate practical applicability. Such conservatism is not unique to our setting and has also motivated research on non-vacuous PAC-Bayes bounds (e.g. Dziugaite and Roy (2017)). However, establishing theoretical PAC bounds remains valuable as it: (1) establishes PAC learnability of safety certificates, providing a theoretical foundation for data-driven safety verification. (2) characterizes how the estimation accuracy depends on the confidence level, sample size, Hankel conditioning, and mixing properties. (3) provides a quantitative starting point for developing tighter, problem-specific guarantees. The sample sizes derived from our analysis are sufficient for the theoretical guarantees, rather than proven necessary requirements for accurate estimation. Refining the concentration and error-propagation analysis, and exploiting additional system structure to reduce conservatism, are important directions for future work.
Answers:
-- Computing the Hankel rank and selecting a complete Hankel basis are system identification problems within realization theory, which are separate from the safety verification error analysis studied in our work. These problems have their roots in classical realization theory of the 1960s, and there is no universal procedure for recovering the exact rank from finite, noisy data without additional assumptions. In the cited spectral learning result, Balle and Maillard explicitly specified prefix and suffix sets U,V and assumed that the relevant Hankel block has the same rank as the full Hankel matrix. Our method follows this formulation and for simplicity assumes that ∣α∣=∣β∣=n, where n is the rank of the full Hankel matrix. We can also consider larger candidate prefix and suffix sets. In this case, we can select an n×n submatrix from a larger Hankel block with the aim of increasing the smallest singular value. In practice, one constructs a sufficiently large empirical Hankel block, applies SVD to estimate its effective rank, and selects prefix and suffix subsets. However, estimation errors in the singular values must also be taken into account when determining the rank, which requires additional analysis.
-- In the theoretical analysis, the unknown quantity is σn(Hα,β). In practical computation, we use a computable lower bound on σn(Hα,β) obtained as follows.
By Weyl’s inequality, ∣σn(Hα,β)−σn(Hα,β)∣≤σmax(Hα,β−Hα,β)=∥Hα,β−Hα,β∥2≤∥Hα,β−Hα,β∥F. With probability at least 1−δ, ∥Hα,β−Hα,β∥F≤K∗(δ,N). Hence, with probability at least 1−δ, σn(Hα,β)−K∗(δ,N)≤σn(Hα,β)≤σn(Hα,β)+K∗(δ,N). Since σn(Hα,β) appears in the denominators, we use its lower bound σn(Hα,β)−K∗(δ,N) which is computable. Note that, for fixed δ, K∗(δ,N) can be very small as N increases.
-- Our single trajectory error bound assume that a prior bound on the mixing parameters are available. Exact parameter values are not necessary, since conservative bounds satisfying the mixing assumption are sufficient. We use these bounds as inputs to compute the error bounds and they are not estimated by our algorithm. Estimating mixing parameters from observation-level data is a separate research topic. The stopping time depends on the number N of the observation windows required to yield a valid safety certificate, and this number determines the time steps of how long a single trajectory should run. In more detail, it is relevant to the desired accuracy of the safety probability estimate and the confidence level of the certificate.
-- If partial knowledge of the environment is available, it can be included in the definition of safety language Lsafe, and hence in the definition of specification DFA. In a POMDP, the observation kernel specifies the probabilistic relationship between observations and underlying states. Belief states represent the conditional distribution of the underlying states given the history of action-observation sequence, and can support probabilistic guarantees for state-level safety when the required model is available. However, observation-level safety guarantees do not translate into state-level safety guarantees automatically without additional assumptions. Establishing this connection within our data-driven framework is beyond the scope of present work and remains a direction for future research.