acceptodds
Under review as a conference paper at ICLR 2027

Safety Certificate for Stochastic Fractional-Order Dynamical Systems

Abstract

Certifying the safety of stochastic systems with long-range memory is challenging because future risk can depend on the entire state history. Existing safety certificates commonly assume Markovian dynamics, and their safety and persistent-feasibility guarantees do not carry over when infinite histories are unavailable to an online safety certificate. In this paper, we study how to quantify risk and ensure safety when only limited history information is available to the online certificate. First, we propose a Bellman-like backward recursion that constructs lower bounds on the value and action-value functions, and hence on long-term risk, using only a finite-memory representation. Second, we derive constraints on control actions that guarantee long-term safety while ensuring persistent feasibility. By combining offline-computed lower bounds with these action constraints, we obtain an efficient online safety certificate whose certified action set remains nonempty at every decision step. Then, we apply the framework to stochastic fractional-order dynamical systems, whose long-range memory makes existing Markov-based risk evaluation and safety certification techniques inapplicable. Finally, we use numerical simulations to demonstrate the effectiveness of the proposed framework and compare with existing techniques.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Safety certificate, Fractional-order dynamics

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_QsUQOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers the problem of safety certification of history-dependent stochastic systems. The proposed approach relies on an under-approximation of the Bellman operator with an M-memory approximation of the system. The effectivness of the approach is investigated on linear and nonlinear benchmarks

Critical strengths
  • The paper considers an important problem that has not received much attention in the past

  • The approach considered by the authors is sound and, to the best of my knowledge, Lemma1 and 2 and the resulting Theorems are novel and of potential interest.

Critical weaknesses
  • The literature review should better position the proposed backward recursion relative to existing dynamic-programming-based approaches to probabilistic safety verification and control, e.g., [L. Laurenti and M. Lahijanian, “A Unifying Perspective for Safety of Stochastic Systems: From Barrier Functions to Finite Abstractions,” IEEE Transactions on Automatic Control, doi: 10.1109/TAC.2025.3597569]. In particular, the authors should distinguish the established components of the recursion from their contributions to certification of history-dependent systems using finite memory.

  • The practical implementation of the probabilistic bounds in Lemmas 1 and 2 is insufficiently specified. Although the appendices provide expressions for the required constants, it remains unclear which numerical values, confidence parameters, and envelopes over compatible histories were used in the experiments. The authors should report the resulting deviation bounds and initial certificate values, explicitly checking the condition required for the prescribed safety guarantee. The conservatism of the individual bound components and the resulting certificate should also be evaluated numerically.

  • Both experiments report 500 safe trajectories out of 500 under the proposed controller. Additional settings with nontrivial safety probabilities would help assess the method’s effectiveness and the accuracy of its guarantees. The authors should report the certified probability lower bounds and the confidence parameters used to construct them alongside the empirical safety estimates and their confidence intervals. To assess conservatism, the certificate should also be compared with an estimate of the safety probability under the same reference policy.

  • The authors should explain how (M) is selected and discuss the limitations of the chosen memory representation relative to alternative history summaries.

  • The reported numerical implementation discretizes the retained state window, whose dimension is (nM). Consequently, a full-grid implementation scales exponentially with the memory length and this is a potential weakness of the resulting approach. Therefore, the experiments should investigate how varying (M) affects the tightness of the certified bounds, empirical safety, and computational cost. Reporting offline computation time, peak memory usage, and online decision time, together with sensitivity to grid resolution, would clarify the practical tradeoffs.

Questions for authors

Please, consider the Weaknesses identified above and, in particular, it is important to clarify the empirical conservativism of the various bounds and to extend and calrify the experimental analysis.

8 comments
AuthorsOpenReview ↗

Response to Weakness 1

We thank the reviewer for pointing us to the work of Laurenti and Lahijanian. We have revised Section 2 and added a remark after Section 4.3 to clarify the relationship between the two works and our contributions in problem formulation, methodology, and guarantees. Our central contribution is to establish valid certificates and online filtering guarantees for history-dependent stochastic systems whose finite-memory representations need not admit a Markov transition law, while accommodating different task specifications through a general terminal payoff. We also included a comparison with their method IMDP in Appendix D (Figures 7-10). Across all simulations, our method achieves higher empirical safety probabilities, lower control intervention costs, and shorter offline computation times than IMDP.

Connection to existing safety DP and our extension. Laurenti and Lahijanian unify stochastic barrier functions and finite abstractions as approximations of safety dynamic programming (DP), and analyze their correctness, conservatism, and convergence properties. Our Equations (5)–(7) share a similar backward-recursion structure with their safety DP: starting from a terminal condition, one-step updates propagate continuation values backward to the initial time. The lower-bound construction in Section 4.3 also shares the structure of their robust DP, propagating valid probability bounds through conservative updates over possible successor distributions.

The main distinction lies in the dynamical information underlying these updates. Their theory assumes a controlled Markov transition law: given the current state and action, the conditional distribution of the next state is independent of the earlier history. Although their policies may depend on history, the system dynamics retain this Markov structure.

Our work extends this backward-certification approach to history-dependent systems whose finite-memory representations need not admit a Markov transition law. The same retained window and action can correspond to different conditional successor distributions. We therefore perform the updates using conditional lower bounds that hold uniformly over all compatible full histories. This allows a similar DP structure to certify the original dynamics using limited historical information and to establish guarantees for an entire class of online filtering policies.

The central certification challenge with finite memory. Let h=(x0:t,u0:t−1)h=(x_{0:t},u_{0:t-1}) denote the full history and s=(xt,…,xt−M+1)s=(x_t,\ldots,x_{t-M+1}) the retained window. Given history hh and candidate action uu, the FoD one-step update is Xt+1=x^(M)(t,s,u)+Rt(h)+Wt,X_{t+1}=\hat{x}^{(M)}(t,s,u)+R_t(h)+W_t, where Rt(h)=−∑j=M+1t+1ψ(α,j)xt+1−jR_t(h) = -\sum_{j=M+1}^{t+1}\psi(\alpha,j)x_{t+1-j} and x^(M)(t,s,u)\hat{x}^{(M)}(t,s,u) is the deterministic truncated prediction initialized from ss. Two compatible histories with the same retained window, safety flag, and candidate action can have different discarded-memory contributions Rt(h)R_t(h), and hence different conditional successor distributions. Finite-memory certification must account for these differences to provide valid guarantees for the original system.

A scalar one-step example illustrates how discarded memory affects the safety probability. Suppose the truncated prediction is zero, the safe set is [−a,a][-a,a] with a>0a>0, and Wt∼N(0,σ2)W_t\sim\mathcal N(0,\sigma^2) with σ>0\sigma>0, independently of the history and current action. The truncated model gives the safety probability ptrunc=2Φ(aσ)−1,p_{\mathrm{trunc}} = 2\Phi\left(\frac{a}{\sigma}\right)-1, where Φ\Phi is the standard normal cumulative distribution function. For a compatible history with a nonzero discarded-memory shift ρ=Rt(h)\rho=R_t(h), the true conditional safety probability is ptrue(ρ)=Φ(a−ρσ)−Φ(−a−ρσ)<ptrunc.p_{\mathrm{true}}(\rho)=\Phi\left(\frac{a-\rho}{\sigma}\right)-\Phi\left(\frac{-a-\rho}{\sigma}\right)<p_{\mathrm{trunc}}. Thus, ignoring discarded memory overestimates safety for that history. Our approach accounts for this contribution through a common lower bound covering all compatible histories.

AuthorsOpenReview ↗

Response to Weakness 1 (Continued)

Uniform lower bounds over compatible histories. Equation (4) states this certification requirement explicitly: for each candidate action, the lower bound must hold uniformly over all full histories mapped to the same certificate state. Under the recursive-update, measurability, and other conditions stated in the paper, Theorem 1 applies to a certificate state ζt\zeta_t that is neither Markov nor a sufficient statistic of the full history. These common conditional lower bounds provide the foundation for backward certification of history-dependent dynamics with finite memory.

For FoD trajectory safety, the safety flag provides a computable history bound. When Ct=1C_t=1, every discarded state lies in C=x∈Rn:∥∥x∥∥∞≤xmax⁡.\mathcal C=\\{x\in\mathbb{R}^n:\|\|x\|\|_\infty\le x_{\max}\\}. Hence ∥∥Rt(h)∥∥∞≤xmax⁡∑j=M+1t+1∣ψ(α,j)∣,\|\|R_t(h)\|\|_\infty\le x_{\max}\sum_{j=M+1}^{t+1}|\psi(\alpha,j)|, uniformly over all compatible histories. Combining this history bound with a conditional noise bound yields successor sets satisfying the conditional coverage requirement in Equation (21) for every compatible history, and hence one-step lower-bound operators satisfying Assumption 1.

From offline certification to online filtering guarantees. We further use these bounds to define the certified action set $ \{ u\in\mathcal A_t(\zeta): \underline Q_t^\pi(\zeta,u) \ge \underline V_t^\pi(\zeta) \}. $ This set remains nonempty under the conditions stated in the paper. Theorem 1 guarantees that every online policy μ\mu selecting certified actions at each step satisfies $ \mathbb E^\mu \left[ G(\zeta_T)\mid\zeta_0 \right] \ge \underline V_0^\pi(\zeta_0), $ together with persistent feasibility. Offline evaluation of a reference policy therefore provides a common guarantee for an entire class of online policies. The controller can pursue its own performance objective within the certified action set while preserving the initial certified lower bound. Whenever $ \underline V_0^\pi(\zeta_0)\ge\eta, $ the prescribed terminal expectation requirement is guaranteed. For G(ζT)=CTG(\zeta_T)=C_T, this gives the desired trajectory-safety guarantee.

Applicability to different terminal specifications. Section 3 expresses the certification objective through a general terminal payoff G(ζT)∈[0,1]G(\zeta_T)\in[0,1], allowing trajectory safety, finite-horizon reachability, and their joint requirements to be treated within the same backward-recursion and online-filtering framework. By incorporating the history information needed for the task into a recursively updated certificate state, Theorem 1 provides a unified guarantee under Assumption 1, even when that state does not admit a Markov transition law.

For example, for a target set D\mathcal D, introduce the target-hit flag B0=1{X0∈D}B_0=\mathbf 1_{\{X_0\in\mathcal D\}} and Bt+1=max⁡Bt,1{Xt+1∈D}.B_{t+1}= \max \\{ B_t,\mathbf 1_{\{X_{t+1}\in\mathcal D\}} \\}. Including BtB_t in the certificate state and setting G(ζT)=BTG(\zeta_T)=B_T expresses finite-horizon reachability and gives, for every online policy μ\mu selecting certified actions,

\left( \exists t\in\{0,\ldots,T\}: X_t\in\mathcal{D} \middle| \zeta_0 \right) \ge \underline V_0^\pi(\zeta_0).$$ Retaining both the safety flag $C_t$ and the target-hit flag $B_t$, and setting $G(\zeta_T)=C_TB_T$, expresses the joint requirement of reaching the target by the deadline while remaining safe throughout the horizon: $$\mathbb P^\mu \left( \\{ \forall t\in\{0,\ldots,T\}: X_t\in\mathcal C \\} \cap \\{ \exists t\in\{0,\ldots,T\}: X_t\in\mathcal D \\} \middle| \zeta_0 \right) \ge \underline V_0^\pi(\zeta_0).$$ Our contribution thus addresses both dynamics and task specifications: valid certification of history-dependent dynamics whose finite-memory representations need not admit a Markov transition law, and a unified terminal-payoff formulation accommodating multiple task requirements. The resulting guarantees hold for the entire class of online policies that respect the certified action constraints, allowing the controller to pursue its own performance objective while preserving the specified guarantee. **Comparison with IMDP.** We compare our method with IMDP while varying the fractional order $\alpha$ and time horizon $T$. Across all simulations, our method achieves higher empirical safety probabilities, lower intervention costs, and shorter offline computation times. Detailed results are provided in Appendix D and Figures 8–11.
AuthorsOpenReview ↗

Response to Weakness 2

We thank the reviewer. We have revised Section 6 and Appendix C to report the deviation bounds used in the experiments, explain how they hold uniformly over compatible histories, and check whether the resulting initial certificate values meet the prescribed safety threshold.

One-step implementation of Lemmas 1 and 2. Theorem 2 combines the truncation error and stochastic deviation bounds for a restart over a general horizon. In both experiments, we use the one-step special case, restarting at each decision time tt over [t,t+1][t,t+1]. At each restart, we initialize both truncated models with the last MM observed states. All three updates use the same candidate action, and the true and truncated stochastic models share the same disturbance WtW_t. Over one step, the two deviations therefore take the exact forms Xt+1−Xt+1(M)=−∑j=M+1t+1ψ(0.3,j)Xt+1−j,X_{t+1}-X_{t+1}^{(M)}=-\sum_{j=M+1}^{t+1}\psi(0.3,j)X_{t+1-j}, and $ X_{t+1}^{(M)} - x_{t+1}^{(M)}=W_t.$

Truncation error. When Ct=1C_t=1, every discarded state lies in [−3,3]5[-3,3]^5. The one-step truncation error therefore satisfies the deterministic bound ∥∥Xt+1−Xt+1(M)∥∥∞≤rtail(t)=3∑j=6t+1∣ψ(0.3,j)∣\|\|X_{t+1}-X_{t+1}^{(M)}\|\|_\infty \le r_{\rm tail}(t)=3\sum_{j=6}^{t+1}|\psi(0.3,j)| for every compatible history.

Stochastic deviation. The one-step stochastic deviation is the additive Gaussian disturbance itself. Since WtW_t is independent of the pre-action history and the candidate action, the exact conditional ℓ∞\ell_\infty radius at coverage 1−δ21-\delta_2 is $ r_{\mathrm{noise}}(\delta_2) =0.1\Phi^{-1}1+(1−δ2)1/52\frac{1+(1-\delta_2)^{1/5}}{2},$ where Φ\Phi is the standard normal CDF.

We enlarge each cell’s truncated successor enclosure by rtail(t)+rnoise(δ2)r_{\mathrm{tail}}(t)+r_{\mathrm{noise}}(\delta_2) to obtain a successor set satisfying Equation (21). In Equation (22), δ1=10−4\delta_1=10^{-4} enters only the coverage factor, and the backup maximizes over the eight δ2\delta_2 values reported below. See Appendix C for details of the cell and successor set construction.

Numerical deviation bounds.

tt0–45791113151719
rtailr_{\rm tail}00.06980.17430.25050.30970.35750.39740.43140.4609
δ\delta10-410-30.0050.010.030.070.150.30
rnoiser_{\rm noise}0.42650.37190.32900.30890.27440.24470.21450.1819

Initial value check. We report the initial certificate values and their check against η=0.95\eta=0.95 in our response to Reviewer ajKP Q2. In brief, these values depend strongly on the reference policy, because V‾0π(ζ0)\underline V_0^\pi(\zeta_0) lower bounds the safety probability of the reference policy itself. The original experiments do not meet the prescribed threshold, because the original reference policy is iteself unsafe in more than half of the rollouts. Their 500/500 safety result is therefore empirical rather than certified at the prescribed threshold. A safer reference policy raises the certificate substantially: with constant u=1u=1, it increases to 0.9410 (linear) and 0.4138 (nonlinear). The supplementary experiments in Q2 meet the condition for both systems, with V‾0π(ζ0)=0.9512>0.95\underline V_0^\pi(\zeta_0)=0.9512>0.95.

Numerical conservatism. In 20,000 rollouts per model, the original reference policy had empirical trajectory safety of 0.4822 (linear) and 0.3410 (nonlinear), versus initial certificates of 0.1144 and 0.0503. With the original cells, every successor enclosure for u=10u=10 extends outside C\mathcal C, giving a zero lower backup for that action. The recursion therefore retains only the u=1u=1 contribution with weight 0.90.9 at each step, yielding the factor 0.9200.9^{20} relative to the certificates for constant u=1u=1. Constant u=1u=1 was safe in all 20,000 rollouts per model, with certificates of 0.9410 and 0.4138 under the original enclosure.

At t=19t=19, the largest observed truncation errors were 0.2467 and 0.2545, compared with the uniform bound of 0.4609. For the executed actions on these histories, both the noise-only backups and those incorporating noise and truncation attained the largest available weight of 0.9998. Adding the retained-window cell enclosure reduced the means to 0.9899 and 0.7718. Over the full horizon with reference u=1u=1, accounting exactly for the known X0X_0 term raised the initial certificates to 0.9700 and 0.5792.

Benefit of online filtering. With the deterministic reference u=1u=1, that action remains certified at every step. The filter can therefore choose an action closer to the nominal input whenever the certified set permits it, while preserving the same trajectory-safety lower bound. On the matched 500-rollout experiments, the configurations that passed the 0.950.95 check reduced mean squared intervention cost from 81 for constant u=1u=1 to 65.67 for the linear filter with refined confidence levels, and to 75.32 and 75.68 for the two supplementary box filters.

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

This paper proposes a safety certification framework for stochastic systems with long-range memory, with particular emphasis on fractional-order dynamical systems. The approach constructs lower bounds on value and action-value functions through a Bellman-like backward recursion using finite-memory representations. These bounds are used to derive an online safety filter that guarantees probabilistic trajectory safety and persistent feasibility, subject to an initial certification condition. The framework accounts for discarded history through probabilistic truncation and stochastic deviation bounds. Numerical experiments on linear and nonlinear fractional-order systems demonstrate improved empirical safety and reduced online computation compared to several existing approaches.

Critical strengths

The paper addresses an important problem in safety-critical control, namely providing probabilistic safety guarantees for stochastic systems with long-range memory under limited historical information. The proposed backward recursion and certified action constraints provide a principled framework for handling non-Markovian dynamics while maintaining persistent feasibility.

The theoretical development is reasonably comprehensive, including explicit treatment of memory truncation and stochastic disturbances. The experiments demonstrate encouraging improvements in empirical safety and online computation, particularly when compared with baseline methods restricted to the same memory window.

Critical weaknesses

The connection between the theoretical guarantees and their numerical implementation requires further clarification. The safety guarantee relies on certified one-step lower bounds that hold uniformly over all full histories compatible with the retained information. Section 5.4 acknowledges that this requires suitable upper envelopes of the history-dependent deviation bounds. However, it is unclear how these bounds are constructed in practice, particularly after discretization. Furthermore, the experiments report empirical safety probabilities but do not provide the computed initial certificate values needed to establish that the required probability threshold is formally satisfied.

The computational scalability and experimental validation remain limited. The experiments consider only two closely related five-dimensional systems over a horizon of 20 steps. Although the online computation times are promising, the cost of constructing the certificate offline is not reported. This is particularly important because the retained history has dimension 25, making direct discretization potentially expensive. Moreover, the evaluation does not investigate how the certificate quality and computational requirements change with memory length, fractional order, or horizon. These limitations make it difficult to assess the practicality of the proposed framework beyond the considered examples.

Questions for authors

How are the certified conditional lower bounds constructed after discretizing the finite-memory state? In particular, how is validity preserved uniformly over all full histories compatible with a discretized certificate state?

Can the authors report the computed initial certificate values and confirm whether they satisfy the prescribed safety threshold of 0.95? This would help distinguish the formal guarantees from the empirical safety probabilities reported in Section 6.

Can the authors clarify the offline computational cost and memory requirements? Appendix C states that each coordinate of the 25-dimensional retained history is discretized into three intervals, which would result in approximately (3^{25}) grid cells under direct discretization. How is this computation made tractable, and does the implementation preserve the theoretical guarantees?

8 comments
AuthorsOpenReview ↗

Response to Question 1

Thank you very much for the time in evaluating our manuscript and for the question. Section 5.4 states that the successor sets must be valid for all full histories compatible with a certificate state, but the manuscript omitted the construction used for the discretized state in Section 6 due to space limitations. We clarify it here and have added this discussion to the revised manuscript in Appendix C.

Discretized certificate state. For each retained state Xt−kX_{t-k}, k=0,…,M−1k=0,\dots,M-1, we record the bins (three uniform bins on [-x_\max, x_\max]) containing min⁡iXt−k,i\min_i X_{t-k,i} and max⁡iXt−k,i\max_i X_{t-k,i}, together with the safety flag CtC_t. All coordinates of Xt−kX_{t-k} therefore lie in a recorded interval [ℓk,uk][\ell_k,u_k], where ℓk\ell_k is the lower edge of the min-bin and uku_k is the upper edge of the max-bin. This state can be updated recursively by prepending the bins of Xt+1X_{t+1} and dropping the oldest pair, and G=CTG=C_T, so it is a certificate state in the sense of Section 3.1. Theorem 1 does not require it to be Markovian or sufficient. It only requires Assumption 1 to hold for every full history mapped to the same state. Each discretized state thus represents a set of full histories: the retained states vary within the recorded intervals, and when Ct=1C_t = 1, every compatible discarded state lies in the safe set.

Successor sets remain valid for every compatible history. Fix such a state with Ct=1C_t = 1 and an action uu. (i) We bound the deterministic prediction x^(M)(t,s,u)\hat{x}^{(M)}(t,s,u) over all retained states in the recorded intervals by interval arithmetic. The linear part is bounded by splitting A+αIA+ \alpha I into positive and negative parts; the older lags enter with nonnegative weights −ψ(α,j)-\psi(\alpha, j), and tanhtanh is monotone in the nonlinear model. (ii) When Ct=1C_t = 1, every discarded state coordinate lies in [-x_\max, x_\max], so the discarded contribution to each next state coordinate is bounded in absolute value by dt=xmax⁡∑j=M+1t+1∣ψ(α,j)∣.d_t=x_{\max}\sum_{j=M+1}^{t+1}|\psi(\alpha,j)|. (iii) Since WtW_t is independent of the history, a Gaussian radius r(δ2)r(\delta_2) satisfies P(∥Wt∥∞≤r(δ2))≥1−δ2P(\|W_t\|_\infty\le r(\delta_2))\ge 1-\delta_2. After expanding the intervals from (i) by dt+r(δ2)d_t + r(\delta_2), the next state lies in them with conditional probability at least 1−δ21-\delta_2, for every compatible full history. The coordinate intervals give bounds on the minimum and maximum of the next state. We include every discretized successor consistent with those bounds, shift the retained interval indices, and update the safety flag. For every compatible full history, this successor set has conditional coverage at least 1−δ21-\delta_2, which implies Eq. (21) with δ1=0\delta_1 = 0.

Common lower bound. Let ζt\zeta_t denote the discretized certificate state. For any function vv taking values in [0,1][0,1] on the discretized successor states, let mvm_v be its minimum over the enclosed successors Rt(ζ,u;δ1,δ2)R_t(\zeta, u; \delta_1, \delta_2) for a fixed confidence pair. We use mv=0m_v = 0 if the enclosure can include an unsafe state. By Eq. (21) and nonnegativity,

E[v(ζt+1)∣Yt=h,Ut=u]≥(1−δ1−δ2)mv\mathbb E[v(\zeta_{t+1})\mid Y_t=h,U_t=u] \ge (1-\delta_1-\delta_2)m_v

for every full history hh represented by the current discretized state. The expectation is over the next disturbance WtW_t, with hh and uu fixed. The successor set and mvm_v are shared by all such histories, so maximizing over the confidence pairs gives a lower operator satisfying Assumption 1. Applying this operator to v=V‾t+1πv = \underline{V}_{t+1}^\pi gives the action-value update in Eq. (22). For Ct=0C_t = 0, the lower operator is zero.

Preservation of theoretical guarantees under discretization. Importantly, our discretization does not approximate the transition dynamics at representative grid points. Instead, each discretized certificate state represents an entire set of compatible full histories, and the successor enclosure conservatively accounts for all such histories. Consequently, the computed lower-bound operator satisfies Assumption 1 uniformly over the histories represented by each discretized state. Furthermore, the implemented range-minimum queries return the exact minimum over all enclosed successor cells, introducing no additional approximation in the Bellman recursion. Therefore, Theorem 1 applies directly to the discretized implementation, preserving the theoretical trajectory-safety guarantee and persistent feasibility, subject to the initial-value certification condition.

AuthorsOpenReview ↗

Response to Question 2

The original initial certificates did not meet the prescribed safety threshold because the shared reference policy used for baseline comparison itself had a safety probability below that threshold. We added supplementary experiments with a safer reference policy and tighter history bounds, obtaining initial certificates that satisfy the threshold and establish the prescribed trajectory-safety guarantee. These results are reported in Appendix C.

The computed initial certificate values for the original Section 6 experiments are 0.114 for the linear system and 0.050 for the nonlinear system. By Eq. (9), these are lower bounds on the trajectory-safety probabilities of the respective filters. Both are below 0.95, so the initial-value condition in Corollary 1 is not met. The 500/500 safe trajectories reported in Section 6 are empirical frequencies and are not certified at 0.95.

The reference policy has a substantial effect on these values. By the same argument as in Theorem 1, V‾0π\underline{V}_0^\pi lower-bounds the safety probability of the reference policy itself, and Theorem 1 guarantees that the filter attains at least this certified level. For comparison with MCLS, the original experiments used the shared reference policy that selects u=1u=1 with probability 0.9 and u=10u=10 with probability 0.1. This policy is itself unsafe. Its Monte Carlo safety probability is about 0.48 (linear) and 0.34 (nonlinear), so no valid lower bound for it can reach 0.95. Holding the original lower bound construction fixed and changing only the reference policy to deterministic u=1u=1 raises the initial values to 0.941 and 0.414. The remaining gap comes from bounding every discarded state by x_\max, which the supplementary construction below tightens.

Supplementary experiments. We use the same systems, safe set, horizon T=20T=20, memory length M=5M=5, and 500 disturbance sequences. Starting from x0x_0, we propagate intervals through the full-history dynamics under u=1u=1 and the noise event Wt∈[−0.35,0.35]5W_t \in [-0.35,0.35]^5. This gives time-dependent boxes It⊂CI_t\subset\mathcal C. We add the absorbing flag Ft+1=Ft 1{Xt+1∈It+1}F_{t+1}=F_t\,\mathbf 1\{X_{t+1}\in I_{t+1}\}, so the certificate state becomes ζt=(qt,Ct,Ft)\zeta_t = (q_t,C_t,F_t), where qtq_t is the discretized cell of Sˉt(M)\bar{S}_t^{(M)} . Its update remains recursive and the terminal payoff remains CTC_T, so Theorem 1 applies. When Ft=1F_t=1, the boxes bound every compatible discarded history and tighten the coordinate bounds on the retained states. An action passes the containment test if its resulting successor enclosure lies in It+1I_{t+1}.

The disturbance event has conditional probability at least 1−δ2=0.99751-\delta_2=0.9975 for every compatible full history. The recursion uses p=1−δ1−δ2=0.997499p=1-\delta_1-\delta_2=0.997499, with δ1=10−6\delta_1=10^{-6}. By construction, u=1u=1 passes the containment test whenever Ft=1F_t=1. The backward recursion yields V‾tπ=CtFtpT−t\underline{V}_t^\pi=C_tF_tp^{T-t} for t<Tt<T, with terminal payoff CTC_T. Since C0=F0=1C_0=F_0=1, both supplementary filters have V‾0π=p20≥0.95\underline{V}_0^\pi=p^{20} \ge 0.95. Theorem 1 therefore establishes the prescribed trajectory safety guarantee for these filters.

On the same 500 disturbance sequences, the supplementary filters kept 498/500 linear and 500/500 nonlinear trajectories safe. The mean squared deviations of the applied actions from the nominal action were 75.32 and 75.68 for the supplementary experiments and 62.16 and 66.15 for the original experiment, respectively. We have included this discussion in Appendix C.

AuthorsOpenReview ↗

Response to Question 3

Thank you for your question. We clarified that offline construction remains exponential in the retained memory length, while recursive min–max summaries and precomputed range minimum queries make the reported experiments tractable. Appendix D now reports measured build times, table storage, and peak memory, alongside a comparison with existing baselines. The implementation preserves the theoretical guarantees: conservative successor enclosures cover every compatible full history, and exact range minimum queries preserve the certified trajectory safety lower bound and persistent feasibility. We have included this discussion in Appendix D.

Exponential growth and comparison with other baselines. We agree that the offline construction grows exponentially, but this cost is shared by methods that certify a multi-step safety probability offline, whether by dynamic programming on a finite abstraction, which yields value or Q-functions as in our method, or by synthesizing a barrier certificate. Laurenti and Lahijanian [1] note that IMDP abstractions solve a number of linear programs proportional to the horizon and to the number of partition states, which is exponential in the state dimension, and that sum-of-squares and neural network barrier certificates also scale exponentially with it. The baselines in Section 6 avoid this offline cost because none of them computes such a bound offline. Each enforces a condition online, step by step, and gives up the multi-step guarantee, its tightness, or its certification:

(i) PrSBC solves one quadratic program per step under a one-step chance constraint. A trajectory level guarantee follows only under an independence assumption.

(ii) JED solves one optimization per step to enforce a discrete-time barrier condition for a given barrier function. Its finite horizon bound follows from a martingale inequality and needs no offline computation, but it loosens as the horizon grows (their Thm. 5), and martingale-based barrier bounds have no guarantee of converging to the true safety probability [1].

(iii) MCLS computes the long-term safety probability offline over the state space. Since the state of a fractional-order system is its growing history, we estimate this probability online by Monte Carlo at the current history (4,096 rollouts per action, 1.11 ms and 49.46 ms per decision for the linear and nonlinear systems). This avoids the offline cost but yields a statistical estimate, not a certified bound.

In contrast, our method certifies safety over a finite horizon for dynamics with infinite memory using a finite certificate state comprising a memory length MM and a safety flag. Crucially, our bounds hold uniformly over all full histories consistent with this certificate state, without requiring the state to be Markovian. The safety flag enables a uniform bound on the contribution of the discarded history, preserving the validity of the certificate under truncation. The QQ bounds are computed once offline, and online certificate evaluation requires only table lookups. Any policy selecting actions from the certified sets preserves the initial safety guarantee. We also prove persistent feasibility: the certified action sets remain nonempty at every step (Theorem 1).

A direct grid over the 25 physical coordinates would contain 325 cells. Its double-precision QQ table alone would require about 1.20 PiB for T=20T=20 and 10 actions. Our implementation summarizes each retained state by its minimum and maximum coordinates. With M=5M=5 and three intervals per scalar, the resulting grid has 310=59,0493^{10}=59,049 allocated cells. Of these, 65=7,7766^5=7,776 satisfy the minimum maximum ordering at every lag. The implementation masks the remaining cells and handles Ct=0C_t=0 separately.

In the backward recursion, shifting the retained window fixes the older indices of each successor. Only the indices of the new minimum and maximum vary. We precompute minima over rectangular ranges of these two indices, so each successor minimum requires four table lookups once its index ranges are known. At fixed grid resolution, the main recursion costs O(T[n2+N(M+∣U∣(n+K))])O\left(T[n^2+N(M+|\mathcal U|(n+K))]\right), where NN is the allocated cell count and KK is the number of confidence pairs.

[1] Luca Laurenti and Morteza Lahijanian. “A Unifying Perspective for Safety of Stochastic Systems: From Barrier Functions to Finite Abstractions.” IEEE Transactions on Automatic Control, vol. 71, no. 2, pp. 769–779, 2026.

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

The paper reformulates the problem of designing policies that satisfy certain requirements by recursively constructing lower bounds on value and action-value functions, and then restricting action selection to those whose lower action values are at least as large as the corresponding lower value. This ensures that the expected terminal payoff is bounded below by the initial value, and if the initial lower value is large enough, then the design requirement is satisfied. The proposed framework relies on the ability to construct a useful lower-bound operator, although it is unclear how difficult this may be in practice. The authors also apply their framework to stochastic fractional-order dynamical systems, establishing similar guarantees. Their experimental results are competitive with, and in some cases outperform, existing methods.

Critical strengths

The paper provides a useful reformulation of the safety certification problem by reducing it to constructing suitable lower-bound operators and ensuring that the initial lower value satisfies the desired threshold. The resulting framework provides theoretical guarantees of safety and persistent feasibility, and the experimental results demonstrate its potential practical benefits. This reformulation could offer a new perspective that can motivate further research in the area.

Critical weaknesses
  1. Although the authors provide constructions of lower-bound operators in Section 4.3, it is unclear how difficult it is to obtain sufficiently tight bounds in practice. In particular, constructing an operator that satisfies Assumption 1 does not necessarily guarantee that the resulting certificate will be useful. Moreover, it is unclear how difficult it is to verify Assumption 1 for a proposed operator.

  2. Even with a valid operator, if the initial lower value is not sufficiently large, the method may not be able to certify the desired safety requirement. This can again make it more difficult to certify safety in practice.

Questions for authors
  1. Could the authors elaborate on what determines the magnitude of the initial lower value function and how difficult it is to construct a lower-bound operator satisfying Assumption 1? I suggest including a discussion of the method's limitations in the main body of the paper rather than only in the appendix.

  2. Could the authors report the initial certified lower values obtained in their experiments?

Minor comments:

  1. In Assumption 1 and in Section 4.3, two visually similar symbols resembling v are used to represent different objects, making them difficult to distinguish. Using more distinct notation would improve readability.

  2. The experimental results could be visualized more clearly. In particular, the curves in Figure 1 are difficult to distinguish from one another.

8 comments
AuthorsOpenReview ↗

Constructing and verifying Assumption 1

We thank the reviewer for the clear summary of our framework and for recognizing its theoretical guarantees and practical potential. We would like to further emphasize the theoretical contribution underlying these guarantees: our framework establishes certification for history dependent systems using finite memory certificate states that need not be Markovian or sufficient statistics of the full history. By constructing conditional lower bounds that hold uniformly over all compatible full histories, we establish a terminal expectation guarantee and persistent feasibility for every online policy selecting certified actions. For fractional-order systems, the safety flag provides a uniform bound on the discarded-memory contribution, giving a concrete way to verify this requirement. Below, we explain the operator constructions and their verification, distinguish limitations in attainable safety from certificate conservatism, and present numerical improvements and computational requirements.

Constructing and verifying Assumption 1. Section 4.3 provides two constructive forms for verifying Assumption 1: ambiguity-set operators and successor-set operators, with explicit sufficient conditions. Together, they cover a broad range of common uncertainty descriptions, including uncertain parameters, bounded model and approximation errors, and conditional moment or concentration information. For the ambiguity-set construction, the lower bound operator is obtained by minimizing the expected continuation value over the candidate conditional successor laws in Pt(ζ,u)\mathfrak P_t(\zeta,u): inf⁡P∈Pt(ζ,u)∫v(z),P(dz).\inf_{P\in\mathfrak P_t(\zeta,u)} \int v(z),P(dz). Since every compatible conditional law belongs to the ambiguity set, this infimum gives a uniform lower bound on the corresponding conditional expectation. For a successor-set operator, verification consists of establishing a conditional coverage probability of at least (1-\delta) for a successor enclosure, uniformly over compatible histories. Nonnegativity then gives

E![v(ζt+1)∣Yt=h,Ut=u]≥(1−δ)inf⁡z∈Rt(ζ,u;δ)v(z).\mathbb E!\left[v(\zeta_{t+1})\mid Y_t=h,U_t=u\right] \ge (1-\delta) \inf_{z\in\mathcal R_t(\zeta,u;\delta)}v(z).

This reduces verification to a one-step enclosure calculation with certified conditional coverage. Bounded errors enlarge the enclosure by their error sets, while conditional concentration bounds provide disturbance sets at the selected coverage level. The algorithm evaluates the supplied confidence choices and retains the largest valid lower bound.

Discarded information is essential to consider in the FoD problem studied in this paper. Two full histories with the same retained window and action can induce different successor distributions. When the safety flag equals one, the bounded safe set constrains all discarded states and hence their contribution to the successor. Combining this bound with the noise model yields either an ambiguity set of conditional successor laws or a successor enclosure with certified coverage.

For example, in the five-dimensional Gaussian setting in Appendix C, the discarded-memory radius at t=19t=19 is approximately 0.46090.4609, and the noise radius at conditional coverage 0.990.99 is approximately 0.30890.3089. Expanding the retained-window prediction enclosure by their sum, approximately 0.76980.7698, gives a valid physical successor enclosure uniformly over compatible histories. Applying the recursive certificate-state update then establishes the required coverage for the next certificate state.

AuthorsOpenReview ↗

Tightness and Usefulness of Safety Certificates

We thank the reviewer for the questions regarding the tightness and practical usefulness of our safety certificates. Below, we clarify the distinction between these two concepts and present theoretical arguments and numerical evidence showing when the certificates provide meaningful safety guarantees and how their tightness can be improved.

Certificate tightness and usefulness are related but distinct concepts. Tightness measures how closely a certified lower bound approximates the true safety probability, whereas usefulness concerns whether the certificate can establish the prescribed safety requirement and enable safe online control. A certificate need not be tight to be useful: even a conservative lower bound can provide meaningful safety guarantees, particularly when existing methods cannot reliably certify safety under limited history information. Our framework guarantees long-term safety and persistent feasibility whenever the initial certificate exceeds the prescribed threshold, regardless of whether the bound is tight.

The proposed framework is particularly useful for systems with long-range memory and limited online information. Unlike existing Markov-based safety certification methods, which may lose their guarantees when applied to truncated histories, our method explicitly accounts for discarded history through certified lower bounds. It therefore provides safety guarantees while requiring only a finite-memory representation for online certification. Moreover, the certified action set remains nonempty at every decision step, and any online policy selecting certified actions preserves the initial safety guarantee. These properties distinguish the practical usefulness of our framework from the numerical tightness of a particular certificate construction.

Conservatism can arise from fundamental limitations of the problem rather than the proposed certification framework. In stochastic systems with long-range memory, limited history information and disturbances introduce uncertainty about future trajectories. Appendix E demonstrates that such information restrictions can impose an intrinsic limit on achievable safety: a full-history controller achieves a safety probability of at least 0.992, whereas every controller restricted to the current state M=1M=1 achieves at most 0.548. This gap persists even with exact model knowledge and computation. Thus, improving numerical accuracy alone cannot overcome limitations imposed by insufficient information. At the same time, additional conservatism may arise from the particular lower-bound construction and can be reduced without changing the proposed framework.

Certificate usefulness can be improved through better reference policies and tighter lower bounds. In our numerical experiments, the original reference policy selects u=1u=1 with probability 0.9 and u=10u=10 with probability 0.1, yielding initial certificates of 0.1144 and 0.0503 for the linear and nonlinear systems, respectively. Replacing it with the deterministic reference u=1u=1, while keeping the enclosure construction fixed, increases the certificates to 0.9410 and 0.4138. This reference policy remained safe in all simulated rollouts for each system. Further tightening the enclosures by treating the known initial-state contribution exactly increases the certificates to 0.9700 and 0.5792, respectively. In particular, the linear certificate exceeds the prescribed safety threshold of 0.95. These results demonstrate that the modular framework can exploit improved reference policies and more accurate lower-bound constructions without modifying its underlying safety conditions.

Increasing memory capacity and reducing uncertainty provide additional routes to stronger certificates. Retaining more history reduces uncertainty about discarded states and can improve the certified lower bounds. In Appendix D, increasing the memory window from M=1M=1 to M=5M=5 improves the certificates by approximately 2.8–5.2 percentage points. Appendix C further demonstrates that incorporating time-dependent state boxes and a recursively updated history flag yields certificates of approximately 0.951 for both systems, exceeding the prescribed threshold. More accurate sensing and actuation can also reduce state-estimation uncertainty and effective disturbances, potentially yielding tighter successor enclosures and stronger certificates when these improvements are reflected in valid uncertainty bounds. Finally, optimizing confidence parameters balances probabilistic coverage against enclosure size, while more accurate certified computations can reduce numerical conservatism. All such refinements preserve the theoretical guarantees provided that the lower-bound validity conditions remain satisfied.

AuthorsOpenReview ↗

Computational Requirements and Practical Considerations

We thank the reviewer for the questions regarding computational requirements and practical scalability. Below, we explain how compact certificate representations and offline precomputation enable efficient online certification, and discuss the computational challenges shared with existing safety certification methods.

Computational tractability through compact certificate representations. Although the retained state history has dimension nMnM, our implementation avoids directly discretizing this high-dimensional space. Instead, it uses a compact representation based on the minimum and maximum state coordinates at each retained time step, reducing the discretized representation to 2M2M entries. With bb bins per entry, the resulting table contains at most b2Mb^{2M} cells, rather than bnMb^{nM}. This substantially reduces the computational burden, particularly for high-dimensional systems. In the reported five-dimensional experiments with M=5M=5, the median offline construction times over three runs were 7.74s for the linear system and 8.23s for the nonlinear system, with 99.56 MiB of stored tables. These measurements were obtained on a two-core Linux virtual machine running on an AMD Ryzen 7 9800X3D host.

Low online computational overhead. The computationally intensive successor-enclosure construction and backward recursion are performed offline. Online certification requires only updating the compact certificate state, retrieving precomputed values, and checking the certified-action inequality. In a separate timing sweep for the linear system with M=1,…,5M=1,\ldots,5, median online decision times ranged from 0.034 to 0.047 ms over approximately 6,000 decisions per setting. These results demonstrate that the proposed method can support efficient real-time safety filtering despite the computational cost of offline certification.

Scalability limitations shared with existing safety certification methods. The main computational tradeoff is between the amount of history retained for certification and the offline resources required to construct the certificate. Although our compact representation avoids exponential growth in the number of discretized cells with respect to the physical state dimension nn, the table size still grows exponentially with memory length MM. Importantly, this limitation is not specific to our proposed framework but is a well-known challenge in numerical safety certification. In particular, grid-based value-function and safety dynamic programming methods generally suffer from the curse of dimensionality, as the number of discretization cells grows exponentially with the dimension of the represented state. Laurenti and Lahijanian [1] identify this computational challenge in their unified analysis of stochastic barrier functions and finite-abstraction methods, highlighting the tradeoff between certificate accuracy and computational cost. Similar scalability challenges arise in data-driven safety certification when dense state-space coverage or high-dimensional function approximation is required, although methods exploiting additional system structure can mitigate them. Thus, the exponential scaling of our grid-based implementation is consistent with the computational limitations of existing numerical safety certification approaches, rather than an additional burden introduced by our treatment of long-range memory. Furthermore, our framework reduces the effective discretization dimension through compact history representations and separates offline certificate construction from online control. More efficient representations and certified approximation techniques can further reduce computational costs while preserving the theoretical safety guarantees.

[1] Luca Laurenti and Morteza Lahijanian. “A Unifying Perspective for Safety of Stochastic Systems: From Barrier Functions to Finite Abstractions.” IEEE Transactions on Automatic Control, vol. 71, no. 2, pp. 769–779, 2026.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common response to all reviewers

We sincerely thank all reviewers for their time, careful reading, thoughtful comments, and constructive suggestions. We are encouraged by their recognition of the importance of safety certification for systems with long-range memory, the novelty of our approach, and the mathematical soundness of our theoretical contributions. In response, we have made the following updates to the manuscript:

  • Related work: Expanded safety DP discussion and clarified our contributions relative to these approaches.
  • Theory: Clarified uniform lower bounds, verification, and guarantees under discretization.
  • Experiments: Added a safety DP baseline and varied horizons, fractional orders, and memory lengths to assess safety, intervention cost, and computation.
  • Evaluation: Reported deviation bounds and initial certificates, assessing conservatism and usefulness.

All changes in the revised manuscript are marked in blue. Below, we summarize our responses to the main concerns shared by multiple reviewers.

Relation to existing methods. We have revised Section 2 and added a remark after Section 4.3 to clarify our contributions relative to existing safety DP. Our framework shares its backward-recursion structure while extending certification to history dependent stochastic systems whose finite memory representations need not admit a Markov transition law. The key is to construct conditional lower bounds that remain valid across all full histories compatible with the retained information, enabling certification of the original dynamics despite discarded memory. These certificates provide a common guarantee for an entire class of online filtering policies: under the stated conditions, controllers can pursue their own performance objectives while preserving the certified lower bound and persistent feasibility. A general terminal payoff formulation further accommodates trajectory safety, finite horizon reachability, and their joint requirements within the same framework. We have also added comparisons with IMDP (Laurenti and Lahijanian) in Appendix D (Figures 7–10). Across all simulations, our method achieves higher empirical safety probabilities, lower intervention costs, and shorter offline computation times than the IMDP.

Tightness and practical usefulness. We have clarified that certificate tightness and usefulness are distinct: a conservative lower bound remains useful if it meets the prescribed safety threshold, thereby guaranteeing trajectory safety and persistent feasibility under the stated conditions. To address conservatism, we identify its main sources and demonstrate how improved reference policies, tighter successor enclosures, and additional retained history strengthen the certificates within the same framework. For example, improving the reference policy and enclosure construction raises the linear system’s initial certificate from 0.1144 to 0.9700, exceeding the prescribed threshold of 0.95. Appendix C further demonstrates certificates above 0.95 for both linear and nonlinear systems using refined history information. We also distinguish conservatism in the certificate construction from fundamental limitations imposed by restricted information: Appendix E shows that limited history can reduce achievable safety even with exact model knowledge and computation. Regarding practical usefulness, our framework explicitly accounts for discarded history and enables online controllers to pursue their performance objectives while preserving the initial certified guarantee. Complementing these certification results, our method achieves higher empirical safety probabilities than all baselines across all experiments, with the lowest intervention costs and shortest online computation times in most settings. These empirical benefits demonstrate practical value without implying that the certified bounds are necessarily tight.

Computational cost and scalability. We have expanded Appendices C and D to clarify computational requirements and distinguish offline construction from online execution. Our offline construction grows exponentially with memory length. As discussed by Laurenti and Lahijanian, exponential scaling with state dimension also arises in existing offline certification approaches, including finite-abstraction methods such as IMDP, sum-of-squares barrier certificates, and neural-network barrier certificates. Our computational cost thus reflects a challenge shared by multiple approaches to certifying multi-step safety probabilities. We further clarify why PrSBC, JED, and MCLS avoid this offline burden: they rely on one-step chance constraints, conservative martingale bounds, or online Monte Carlo estimates, respectively, with corresponding differences in trajectory-level guarantees, tightness, or certification. Our method computes certified bounds once offline and supports inexpensive online evaluation through table lookups.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.