acceptodds
Under review as a conference paper at ICLR 2027

Data-Driven Safety Verification of POMDPs: Showing Learnability of Safety Certificates via Spectral Learning of Weighted Automata

Abstract

We develop a data-driven method for finite-horizon safety verification of a partially observable Markov decision process (POMDP) with unknown transition and observation kernels under a fixed finite-state controller. The method uses only observation data and covers two sampling regimes: multiple independent trajectories generated from a common initial distribution, and a single trajectory whose closed-loop latent process is stationary and geometrically mixing. We represent an observation-based safety specification by a deterministic finite automaton (DFA). Exploiting the weighted finite automaton (WFA) realization of the observation-word probability function of the closed-loop POMDP, we estimate empirical Hankel matrices and apply the Ho-Kalman algorithm to obtain a WFA estimate, which is used as a proxy for the unknown POMDP. More precisely, we estimate the probability with which the learned WFA generates words which satisfy the specification. This estimated probability, in turn, can be used to provide a PAC (Probably Approximately Correct) bound on the probability with which the words generated by the unknown POMDP satisfy the specification. This then allows us to provide PAC bounds on safety certificates for the original POMDP, showing that safety certificates of POMDPs are PAC learnable.

Primary area:
learning theory
Keywords:
Partially observable Markov decision processes, Safety verification, Weighted automata, Spectral learning, PAC guarantees

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_pDmfOpenReview ↗
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
  1. 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.
  2. 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?
  3. 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.
  4. 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
  1. How are the Hankel rank and basis selected in practice?
  2. Can the error radius be computed from observed data and stated prior information while preserving the PAC guarantee?
  3. How are unknown mixing parameters handled, and is there an implementable stopping rule?
  4. What additional assumptions would connect observation-level certification to physical-state safety?
2 comments

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\mathcal U,\mathcal 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|\alpha|=|\beta|=n, where nn 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×nn\times 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α,β)\sigma_n(H_{\alpha,\beta}). In practical computation, we use a computable lower bound on σn(Hα,β)\sigma_n(H_{\alpha,\beta}) obtained as follows.

By Weyl’s inequality, ∣σn(H^α,β)−σn(Hα,β)∣≤σmax⁡(H^α,β−Hα,β)=∥H^α,β−Hα,β∥2≤∥H^α,β−Hα,β∥F|\sigma_n(\widehat H_{\alpha,\beta})-\sigma_n(H_{\alpha,\beta})|\le \sigma_{\max}(\widehat H_{\alpha,\beta}-H_{\alpha,\beta})=\Vert\widehat H_{\alpha,\beta}-H_{\alpha,\beta}\Vert_2\le\Vert\widehat H_{\alpha,\beta}-H_{\alpha,\beta}\Vert_F. With probability at least 1−δ1-\delta, ∥H^α,β−Hα,β∥F≤K∗(δ,N)\Vert\widehat H_{\alpha,\beta}-H_{\alpha,\beta}\Vert_F\le K_*(\delta,N). Hence, with probability at least 1−δ1-\delta, σn(H^α,β)−K∗(δ,N)≤σn(Hα,β)≤σn(H^α,β)+K∗(δ,N)\sigma_n(\widehat H_{\alpha,\beta})-K_*(\delta,N)\le \sigma_n(H_{\alpha,\beta})\le \sigma_n(\widehat H_{\alpha,\beta})+K_*(\delta,N). Since σn(Hα,β)\sigma_n(H_{\alpha,\beta}) appears in the denominators, we use its lower bound σn(H^α,β)−K∗(δ,N)\sigma_n(\widehat H_{\alpha,\beta})-K_*(\delta,N) which is computable. Note that, for fixed δ\delta, K∗(δ,N)K_*(\delta,N) can be very small as NN 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 NN 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\mathcal{L}_{\mathrm{safe}}, 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.

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.

Reviewer_GUj4OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary
  1. Paper Summary* The paper considers finite-horizon safety verification of a POMDP with unknown transition and observation kernels, operating with a fixed, known finite-state controller (FSC). Safety is specified by a DFA over observation words, and the quantity of interest is p_T, the probability that the first T observations are accepted. Using only observation data, either N i.i.d. trajectories or a single stationary, geometrically mixing trajectory, the authors recover a weighted finite automaton (WFA) with the standard spectral (Ho-Kalman) construction, take the Kronecker product of the learned WFA with the DFA, and read off an estimate of p_T. Existing bounds are propagated and the DFA product to an error bound for fixed T (Theorem 3.5). Thresholding the estimate yields a safety certificate, from which the authors conclude that safety certificates of POMDPs are PAC learnable (Theorem 3.1). Validation consists of a two-state, two-observation example with horizon T = 3.

Minor comments:

Line 235: delta-mesurable map not defined

Inconsistencies with strict and non strict inequalities. e.g. Definition 2.4 requires strict P(Gamma = 1) < delta and P(Gamma = 0) < delta but Corollaries 3.6 and 3.7 only establish <= delta.

Typos: Line 222: "denotes its observation" Line 428: "defined" Line 485: "did not use"

Critical strengths

The construction is correct and constructive. The DFA-WFA product gives an explicit, computable estimator. However, the paper has major issues (see Weaknesses).

Critical weaknesses

Each of the 3 listed contributions (lines 114-117) is not new or not interesting. 1. The POMDP as a WFA has been done already in Balle & Maillard (2017). 2. As the authors state thenselves, the bounds are directly taken from literature. 3. For PAC learnability, I think Hoeffding's inequality can give the same guarantee without learning any model and would use less trajectories (i assume) than 1.3x10^14 for example (line 841).

The experiments are trivial and not up to ICLR's standards.

Questions for authors

None

1 comment

We thank the reviewer for the constructive comments and pointing out these errors. We have corrected them. The corresponding revisions are highlighted in blue in the revised manuscript.

We would like to reformulate our contributions as follows:

  1. We derive the error bound between minimal WFA representation and estimated WFA for i.i.d. sampling regime and single-trajectory sampling regime based on Hankel error bounds.
  2. We show that the learned WFA-DFA product captures the information needed to estimate safety probabilities at horizon TT without running the DFA separately on each sequence.
  3. We show that safety certificates are PAC learnable for specification automata with common upper bounds on their size and number of accepting states.

In the following, we address the concerns raised in the review.

-- We use the correspondence between a controlled POMDP under a fixed FSC and its WFA representation for safety verification. The novelty of our work is not the representation itself, but the finite-sample error analysis for the WFA realization and safety probability by using both i.i.d. and single-trajectory sampling regime. Based on this error bound, we obtain high-probability safety certificate.

-- The cited concentration bound controls only the estimation error of the Hankel matrix. It does not give the error bound between minimal WFA representation and the estimated WFA. Our work shows how this error propagates through the minimal WFA, its Kronecker product with the specification DFA, and the finite-horizon safety probability. In turn, this error propogation helps us to yield a safety certificate. For i.i.d. sampling regime, our method allows the length of sampled trajectories to be shorter than the verification horizon. For the single-trajectory sampling case, to the best of our knowledge, there is no previous work on error bound of WFA estimation.

-- We add numerical examples to show the comparison between our method and Hoeffding inequality method in Appendix E.3 of the revised manuscript. Although the Hoeffding inequality needs fewer data points, the advantage of our method compared to Hoeffding inequality can be characterized as follows:

  • Under the i.i.d. sampling regime, the direct Hoeffding inequality requires each sampled trajectory to contain at least TT observations. It is therefore unavailable when the dataset contains only trajectories of length less than TT. In contrast, the WFA can be learned from the shorter words required to estimate the Hankel and shifted Hankel matrices. Once learned, it can be propagated to evaluate the safety probability over a longer fixed horizon. This is significant since our method lowers the risk of the system running into unsafe status as the sequences get longer during data collection.

  • Under the single-trajectory sampling regime, the direct Hoeffding inequality evaluates the safety indicator 1Os+1:s+T∈Lsafe\mathbf{1}_{\\{\mathbf{O}_{s+1:s+T}\in\mathcal{L}_{\mathrm{safe}}\\}}, s=0,…,N−1s=0,\ldots,N-1 for NN length-TT observation windows. Each window is processed from the initial state of the specification automaton and requires up to TT transitions in the DFA. Hence, there are N⋅TN\cdot T transition steps to compute the safety indicator in total. In our method, once the WFA is learned, the safety probability can be estimated by propagating the WFA-DFA product to TT, without restarting the DFA and processing each length-TT window separately. Our method needs O(Nn2)O(Nn^2) steps to compute H^α,β\widehat H_{\alpha,\beta} and H^α,o,β\widehat H_{\alpha,o,\beta}, and there is no need to know the specification DFA when computing H^α,β\widehat H_{\alpha,\beta} and H^α,o,β\widehat H_{\alpha,o,\beta}.

  • Our method gives a universal error bound for all the specification automata with common upper bounds on their size and number of accepting states. That is, the high probability guarantee from our method is actually

    $ \mathbb{P}\left( \begin{gathered} \forall\ \mathrm{DFA\ of\ size\ at\ most}\ D_s\ \mathrm{and\ number\ of\ accepting\ states\ at\ most}\ |F|,\
    |\widehat{\mathbf{p}}_T-p_T|\leq\varepsilon_T(\delta,N) \end{gathered} \right)\geq 1-\delta. $ While Hoeffding inequality gives $ \forall\ \mathrm{specification\ automaton},\quad \mathbb{P}\left( |\widehat{\mathbf{p}}_T-p_T| \leq C\sqrt{\frac{\ln\frac{1}{\delta}}{N}} \right)\geq 1-\delta, $ for some constant CC. This difference means that, with a high probability, our estimation accuracy guarantee holds for all specification automata within the prescribed size simultaneously. While the standard Hoeffding bound provides a high-probability guarantee for each fixed DFA, and it only works when the DFA is chosen independently of data. In contrast, our method allows the DFA to be selected or refined based on the observed data while giving the same 1−δ1-\delta guarantee, as long as the DFA remains within the prescribed class.

Reviewer_LDCtOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper presents a data-driven approach to learning safety certificates for finite-horizon POMDPs under a fixed finite-state controller, which induces a finite hidden Markov process. It constructs a weighted finite automaton representing the probabilities of observation words and combines it with a DFA specifying safe behavior. It considers two settings: transient finite-horizon safety using multiple independent runs from a common initial distribution, and stationary finite-horizon safety using a single trajectory under stationarity and geometric-mixing assumptions. The main result bounds the error in the estimated safety probability in terms of the amount of available observation data, and uses this bound to provide PAC guarantees for safety certification when the true safety probability is sufficiently above the required threshold.

Critical strengths
  • Safety verification of unknown POMDPs is an important problem for safe learning.
  • Using learned weighted automata to verify observation-based specifications is an interesting approach.
  • The finite-sample analysis covers both independent trajectories and a single dependent trajectory. The formal development is non-trivial and appears sound at a high level.
Critical weaknesses
  • I found the presentation technically dense. A running example illustrating the construction of the learned WFA, its product with the specification DFA, and the resulting safety certificate would improve its readability.
  • The key novelty of the PAC-learnability result is not clear to me. For a fixed horizon, the satisfaction probability is just a sum of observation-word probabilities. Existing guarantees for the joint observation-sequence distribution (e.g., Hsu, Kakade, and Zhang, 2012) would therefore give bounds on satisfaction probabilities under their respective assumptions. The single-trajectory analysis also builds on the Hankel concentration results of Balle and Maillard (2017). I understand that deriving an explicit verification bound requires technical work, but I would like to understand what additional insight or capability this extension provides.
  • The guarantees hold for a fixed horizon, and the error bound can grow exponentially with that horizon. This makes it unclear how useful the guarantees are for infinite or discounted horizons.
  • The evaluation appears limited to an illustrative example in Appendix E. I would like to see more experiments showing how the approach scales, how conservative the bounds are, and when it offers an advantage over direct statistical model checking.
Questions for authors
  1. How do your assumptions and guarantees compare with those of Hsu et al. (2012) and Balle and Maillard (2017)? What is the main new technical challenge in extending these learning guarantees to the satisfaction-probability bound?
  2. What is the main advantage of learning the WFA for verification? For example, can observations from short runs give useful safety guarantees over much longer runs despite the dependence of the bound on the horizon?
  3. Could you experimentally compare with direct statistical model checking, showing how sample requirements, runtime, and certification success change as the horizon and model size increase? I would also like to see an example where the training trajectories are shorter than the verification horizon.
2 comments

We thank the reviewer for the thoughtful comments and suggestions.

We understand the concern of the reviewer about the presentation. We would be happy to add more intuitive explanations behind mathematical definitions in the final version.

The novelty of our work does not lie in deriving an error bound between the exact and estimated Hankel matrices. Our novelty lies in 1) We use the correspondence between controlled POMDP and WFA realizations to generate safety certificates.1) We establish the error analysis between exact and estimated WFA representation of controlled POMDPs. 2) We allow the length of sampling trajectories shorter than the verification horizon under i.i.d. sampling regime.

We also extend our approach to infinite-horizon safety pλ:=∑T=0∞λTpTp_{\lambda}:=\sum_{T=0}^\infty\lambda^Tp_T, for λ∈(0,1)\lambda\in(0,1). Under an appropriate stability assumption, the error remains finite and does not grow with TT. We are happy to include this extension in the revised paper.

Answers:

-- We cite Theorem 6.2.1 of Balle (2013) and Theorem 3 of Balle and Maillard (2017). These results establish error bounds for Hankel matrix estimation, while our work uses these bounds to generate safety certificates. Comparing with Hsu et al., they require the number of observations to be no less than the number of states and ensure that the WFA obtained from the HMM is minimal. Our formulation does not require these restriction. Regarding guarantees, they provide error bounds for observation-sequence probabilities. We derive parameter estimation error bounds between the learned WFA and the exact WFA realization, and then propagate these bounds to the error bound of safety probabilities for output sequences. Balle and Maillard explicitly specify prefix and suffix sets and assumed that the corresponding Hankel submatrix has rank same as the rank of the infinite Hankel matrix. Our method follows this standard formulation, and for simplicity we assume that ∣α∣=∣β∣=n|\alpha|=|\beta|=n. We can also consider larger prefix and suffix sets and select rows and columns from the larger Hankel matrix to seek a larger smallest singular value. Moreover, they assume geometric mixing under the single-trajectory sampling regime. Our paper adopts the same mixing assumption and assumes that sampling starts from the stationary distribution. Regarding guarantees, they provide a concentration bound for Hankel matrix estimation under the single-trajectory sampling regime. Our paper further provides accuracy guarantees for the learned WFA parameters and safety probabilities.

The main technical challenge is to control how the Hankel estimation error propagates through the spectral WFA realization, the WFA-DFA product, and its evolution over TT steps, thereby obtaining an error bound for the safety probability. How to use this error bound to obtain a valid high-probability guaranteed safety certificate is another technical challenge.

-- Advantages of learning WFA:

  • The learned WFA is reusable. Once learned, the same WFA can be combined with different DFAs and propagated to different fixed horizons to obtain safety probability estimates and corresponding certificates. Moreover, we obtain a universal accuracy guarantee P(∀ DFA of size at most Ds, number of accepting states at most ∣F∣, ∣p^T−pT∣≤εT(δ,N))≥1−δ\mathbb{P}(\forall\ \mathrm{DFA \ of \ size\ at\ most}\ D_s,\ \mathrm{number\ of\ accepting\ states\ at\ most}\ |F|,\ |\widehat{\mathbf{p}}_T-p_T|\leq\varepsilon_T(\delta,N))\geq 1-\delta. While statistical model checking methods such as Hoeffding inequality gives ∀ specification automaton,P(∣p^T−pT∣≤Cln⁡1δN)≥1−δ.\forall\ \mathrm{specification\ automaton}, \mathbb{P}\left(|\widehat{\mathbf{p}}_T-p_T|\leq C\sqrt{\frac{\ln\frac{1}{\delta}}{N}}\right)\geq 1-\delta. This difference means that our estimation accuracy guarantee holds for all DFAs within the prescribed size simultaneously. While the latter provides a guarantee for each fixed DFA, and it only works when the DFA is chosen independently of data. In contrast, our method allows the DFA to be selected or refined based on the observed data while giving the same guarantee, as long as the DFA remains within the prescribed class.
  • Shorter trajectories are enough for longer time horizon under i.i.d. sampling regime. In the i.i.d. case, each trajectory need only be sufficiently long to estimate the required Hankel entries. There is no need to collect complete trajectories of length TT, including unsafe sequences of that length. Shorter runs can reduce exposure to catastrophic events during data collection if the Hankel basis is well-chosen.
  • Under the single-trajectory sampling regime, WFA allows us to charactrize safety probability by observation windows with length less than TT. This avoids explicitly estimating the full joint distribution over OT\mathcal O^T.

-- The reviewer did not specify a particular statistical model-checking method. However, in our response to Reviewer GUj4, we used an approach based on Hoeffding inequality to directly estimate the safety probability. Please see the response to Reviewer GUj4.

Dear authors: Thank you for clarifying the advantages of the WFA approach and for adding the comparison with the Hoeffding inequality in Appendix E.3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.