- 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
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 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 , every discarded state lies in Hence 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 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 , this gives the desired trajectory-safety guarantee.
Applicability to different terminal specifications. Section 3 expresses the certification objective through a general terminal payoff , 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 , introduce the target-hit flag and Including in the certificate state and setting expresses finite-horizon reachability and gives, for every online policy 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.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 over . At each restart, we initialize both truncated models with the last observed states. All three updates use the same candidate action, and the true and truncated stochastic models share the same disturbance . Over one step, the two deviations therefore take the exact forms and $ X_{t+1}^{(M)} - x_{t+1}^{(M)}=W_t.$
Truncation error. When , every discarded state lies in . The one-step truncation error therefore satisfies the deterministic bound for every compatible history.
Stochastic deviation. The one-step stochastic deviation is the additive Gaussian disturbance itself. Since is independent of the pre-action history and the candidate action, the exact conditional radius at coverage is $ r_{\mathrm{noise}}(\delta_2) =0.1\Phi^{-1},$ where is the standard normal CDF.
We enlarge each cell’s truncated successor enclosure by to obtain a successor set satisfying Equation (21). In Equation (22), enters only the coverage factor, and the backup maximizes over the eight values reported below. See Appendix C for details of the cell and successor set construction.
Numerical deviation bounds.
| 0–4 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0.0698 | 0.1743 | 0.2505 | 0.3097 | 0.3575 | 0.3974 | 0.4314 | 0.4609 |
| 10-4 | 10-3 | 0.005 | 0.01 | 0.03 | 0.07 | 0.15 | 0.30 | |
|---|---|---|---|---|---|---|---|---|
| 0.4265 | 0.3719 | 0.3290 | 0.3089 | 0.2744 | 0.2447 | 0.2145 | 0.1819 |
Initial value check. We report the initial certificate values and their check against in our response to Reviewer ajKP Q2. In brief, these values depend strongly on the reference policy, because 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 , it increases to 0.9410 (linear) and 0.4138 (nonlinear). The supplementary experiments in Q2 meet the condition for both systems, with .
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 extends outside , giving a zero lower backup for that action. The recursion therefore retains only the contribution with weight at each step, yielding the factor relative to the certificates for constant . Constant was safe in all 20,000 rollouts per model, with certificates of 0.9410 and 0.4138 under the original enclosure.
At , 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 , accounting exactly for the known term raised the initial certificates to 0.9700 and 0.5792.
Benefit of online filtering. With the deterministic reference , 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 check reduced mean squared intervention cost from 81 for constant to 65.67 for the linear filter with refined confidence levels, and to 75.32 and 75.68 for the two supplementary box filters.
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) denote the full history and s=(xt,…,xt−M+1) the retained window. Given history h and candidate action u, the FoD one-step update is Xt+1=x^(M)(t,s,u)+Rt(h)+Wt, where Rt(h)=−∑j=M+1t+1ψ(α,j)xt+1−j and x^(M)(t,s,u) is the deterministic truncated prediction initialized from s. Two compatible histories with the same retained window, safety flag, and candidate action can have different discarded-memory contributions Rt(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] with a>0, and Wt∼N(0,σ2) with σ>0, independently of the history and current action. The truncated model gives the safety probability ptrunc=2Φ(σa)−1, where Φ is the standard normal cumulative distribution function. For a compatible history with a nonzero discarded-memory shift ρ=Rt(h), the true conditional safety probability is ptrue(ρ)=Φ(σa−ρ)−Φ(σ−a−ρ)<ptrunc. Thus, ignoring discarded memory overestimates safety for that history. Our approach accounts for this contribution through a common lower bound covering all compatible histories.