CS Paper Radar

Anytime-Valid Runtime Monitoring of Learned Barrier Certificates

Zhipeng Cao, Taoran Wu, Weiru Cui, Luke Ong, Bai Xue

eess.SY cs.AIcs.LGmath.OCmath.ST ·submitted 2026-10-20 06:46 UTC · v2
code/data

Abstract

Learned barrier certificates provide a principled mechanism for establishing safety of stochastic systems, but their validity may deteriorate during deployment when the underlying dynamics differ from those used for training. We propose an anytime-valid runtime monitor that audits a learned barrier certificate using observed closed-loop trajectories. The monitor is intended to detect loss of statistical support for the deployed barrier condition; it does not by itself guarantee detection before unsafe entry or safety of a subsequent intervention. Specifically, the conditional barrier-drift condition is formulated as an episode-wise sequential hypothesis test, and observed barrier increments are transformed into a nonnegative test supermartingale, yielding finite-sample false-alarm control under arbitrary stopping times. Inspired by finite-horizon safety verification, we further introduce a deterministic temporal shaping of the monitoring boundary, making the monitor more conservative early in a prescribed deployment horizon while preserving anytime-validity. The monitor is designed to detect statistical evidence that the safety certificate is no longer consistent with the observed dynamics, rather than to predict unsafe entry. To assess the monitor empirically, we evaluate empirical alarm behavior under valid and invalid certificates. Code and data are available at https://github.com/FormalCert-AI/runtime-barrier-monitor.

Comment
Update-v2: add stepwise falsification guarantee theorem, VLA experiments, and acknowledgment

Closest papers

Nearest neighbours by meaning across the whole index.

Runtime Monitoring of Supermartingale Certificates

cs.AI eess.SY ·2026-10-14 ·Mirco Giacobbe, Thomas A. Henzinger, Konstantin Kueffner, Emily Yu, Đorđe Žikelić
similarity 0.74
Abstract

Supermartingale certificates formally guarantee temporal properties of discrete and continuous-time stochastic dynamical systems. However, these guarantees rely on a mathematical model of the world, leaving a sim-to-real gap that can invalidate them for the deployed system. We formulate the runtime monitoring problem for supermartingale certificates, in which a monitor observes a single system trajectory and raises an alarm when there is sufficient statistical evidence that the supermartingale certificate has been violated during execution. We present an algorithm to automatically construct a monitor using betting-based sequential tests that bound the probability of ever raising a false alarm at a user-specified level. Within this betting framework, we formulate strategies that allow the monitor to exploit spatial regularity to improve detection power while preserving this statistical guarantee. We demonstrate the efficacy of our approach on supermartingale certificate benchmarks from the literature.

0.25

FoSeRL: Formal Sequential Robustness Certification for Reinforcement Learning Policies

cs.LG ·2026-10-03 ·Sara Taheri, Deep Kumar Ganguly, Jan Křetínský, Majid Zamani
similarity 0.64
Abstract

Even a few action perturbations can substantially degrade the performance of a deployed decision policy. Certifying the resulting return loss is challenging in stochastic environments, where returns vary even without an attack. We introduce FoSeRL, a framework for certifying deployed RL policies against precommitted, temporally sparse action attacks. The deployed policy is unchanged, with no smoothing or retraining. Certification requires a resettable simulator supporting shared randomness and independent one-step successor queries, but no analytical dynamics model. FoSeRL certifies that an attacked episode loses no more than a prescribed amount of return relative to the same episode unattacked, with at least a target probability and at a user-specified confidence level. Both runs share the initial state and randomness, so the measured loss reflects the attack, not the episode; carrying the running return gap as a state coordinate makes it the terminal value, reducing trajectory-level certification to terminal safety. Time-dependent barrier conditions on the augmented state bound the terminal failure probability: satisfied exactly, they certify every admissible precommitted attack; learned from sampled trajectories and verified on held-out data, they certify the same guarantee under a specified attack-episode setting. Across six stochastic continuous-control environments and three RL policy families (TD3, SAC, and PPO), FoSeRL certifies non-trivial cardinality--magnitude robustness frontiers, achieves substantially larger certified budgets than policy smoothing, and reveals marked robustness differences among policies with comparable nominal performance.

0.20

Anytime-Valid Certification of Robustness Margins for Safe Control via E-Values

eess.SY ·2026-10-16 ·Panagiotis S. Trakas, Omid Mirzaeedodangeh, Lars Lindemann
similarity 0.64
Abstract

Robust control uses the error between a known model and the true system as a robustness margin. However, this error is usually unknown: conservative estimates restrict feasibility and performance, while underestimates can result in violations of the control property. We estimate this robustness margin from online data using e-values, a statistical tool for hypothesis testing, in the setting of discrete-time control barrier functions (CBFs). Here, we measure the robustness margin as the difference between the observed CBF and the model-based CBF prediction. We then design a robust CBF controller in three steps by: (1) selecting a set of candidate margins, (2) obtaining validity certificates for these candidates via sequential tests based on e-values, and (3) updating the CBF controller with the smallest certified candidate. The deployed tests accumulate evidence against the hypothesis that an exceedance risk, the probability of the robustness margin exceeding the candidate margin, remains at or above a pre-specified failure probability $α$. Our tests are anytime valid and thus enable the use of certified candidates in the CBF controller, guaranteeing that the probability that the exceedance risk of a certified margin exceeds $α$ is at most a user-chosen confidence $δ$. We validate our approach on navigation problems across different environments with visualizations in NVIDIA Isaac Sim.

0.20

DEPLOY-RL: Active Boundary Discovery and Conservative Certification for Deployable Reinforcement Learning in Safety-Critical Continuous Processes

cs.LG ·2026-10-30 ·Yeojin Jang, Minu Baek, Gihun Gil, Minsung Jung, Beomdo Park +6 more
top venuebenchmark similarity 0.61
Abstract · 8 pages; published in IJCAI-ECAI 2026, AI4Tech track. This version adds a publication notice

Reinforcement learning (RL) policies often outperform classical controllers in simulation, yet rarely reach production in safety-critical processes. The barrier is that there is no principled way to answer "Is this policy safe to deploy?" with statistical guarantees. We introduce DEPLOY-RL, a post-training certification framework built on one key insight: deployment certification requires discovering where failures occur (boundary discovery), not measuring how much everywhere (uniform reconstruction). Our contributions: (1) a contract-coupled acquisition function that concentrates sampling on certification-critical boundaries, achieving approximately 2x sample efficiency with a semi-empirical ambiguity reduction bound (domain-calibrated convergence guarantee); (2) conformal risk control providing finite-sample false-go guarantees (<= alpha) under explicit deployment contracts; (3) a three-way decision framework (Deploy/No-Deploy/Abstain) with fail-safe PID/MPC fallback. In simulations on papermaking (industrial digital twin) and Tennessee Eastman (public benchmark), DEPLOY-RL achieves 4.4% false-go rate (vs. 8.6% for the best baseline) while retaining 88.6% policy coverage, the only method achieving <5% false-go with >85% coverage among 14 baselines under our evaluation protocol.

0.35

When the Martingale Never Stops Firing: Anytime-Valid Gating on Real Forecast Streams

cs.LG stat.MEstat.ML ·2026-08-31 ·Weijia Han, Lisha Qu
similarity 0.61
Abstract · 4 pages, 2 figures

Machine learning systems are increasingly corrected while they run, and the decision of when to intervene is increasingly delegated to statistical monitors. Anytime-valid inference promises evidence that can be acted on at any moment, exactly the guarantee this setting needs, and it is moving from theory into deployed monitoring. Conformal test martingales are the change-detection instrument, and Ville's inequality caps their false-alarm probability on exchangeable data. The guarantee is conditional. A deployment inherits it only if the stream it monitors behaves exchangeably. The premise is hardest to satisfy where these monitors are most useful, on dependent data and inside loops where the monitor modifies the learner whose scores it reads. It is also rarely measured. We measure it in a pre-specified case study, where such a monitor gates the online updates of a Kalman adapter correcting frozen time-series foundation models on five forecasting streams. On exchangeable synthetic streams, the same implementation fires in at most 1 of 60 runs. On the real streams, at alpha = 0.05, 135 of 135 clean-stream runs fired. The construction does not explain the firing; the failure comes from the deployed score stream itself. Repeated fires hold the gate's drift response active, and the gated filter amplifies the very transient it was designed to prevent. The component worth keeping makes no validity claim. Huber-style gating of the filter's own updates cuts isolated-spike degradation by an order of magnitude with no dataset specific tuning. Anytime-valid methods proposed for dependent data should therefore be accompanied by null-calibration controls and mechanism traces.

0.25

Reach-Avoid Certificates for Contact-based Stochastic Hybrid Systems

eess.SY cs.ROmath.PR ·2026-10-12 ·Tianyi Xia, Ryan K. Cosner
theory similarity 0.61
Abstract

This work studies certified reach-avoid control of stochastic hybrid systems in which a stochastic differential equation governs continuous flow and a controlled stochastic kernel governs guard-triggered resets. The input appears only in the reset kernel, where it determines the post-jump distribution. Certificates for such systems have so far assumed spontaneous or controller-chosen jump times, a finite horizon, or discrete-time dynamics; we certify, over the infinite horizon, that the target is reached before the unsafe set with at least a prescribed probability. First, we introduce reach-avoid contact certificates, whose flow and jump conditions are imposed only on a sublevel corridor, and prove that any such certificate with a compatible reset policy meets the specification; a pointwise safety filter extends this guarantee from verification to control by constraining arbitrary nominal controllers. Next, we prove that executions are non-Zeno and bound the expected settling time and reset count. We frame certificate search as a linear program over any twice-differentiable dictionary followed by independent verification. We illustrate our approach via comparisons where the certified region is a subset covering 93.6\% of the ground truth and where our certificate-based safety filter reaches the goal while reducing collisions from 68 to zero across 200 episodes of a dribbling ball problem.

0.26

Attack-Aware Intrusion Risk Monitoring for Aerial Surveillance via Probabilistic Signal Temporal Logic

eess.SY cs.LO ·2026-11-03 ·Xinhao Yan, Kenji Kashima, Bo Chen, Hailong Huang
theory similarity 0.60
Abstract · 10 pages, 8 figures

This paper considers online intrusion-risk assessment and graded warning for unmanned aerial vehicles under bounded measurement attacks. To address this problem, we develop a monitoring framework that combines trusted state estimation, attack-aware risk assessment, and probabilistic signal temporal logic (PrSTL). Trusted observations support recursive state estimation, while potentially attacked observations inform integrity testing and intrusion-risk assessment. The key contribution is a confidence-set construction that combines normalized innovation statistics with physical attack bounds to characterize admissible measurement biases. The resulting family of bias-corrected Gaussian posteriors yields an upper bound on the probability of occupying a no-fly zone or its surrounding safety margin. Confidence guarantees and finite-cover numerical certificates quantify the reliability of this risk envelope, which is evaluated with or without an integrity alarm. The PrSTL monitor analyzes the resulting risk sequence to distinguish ordered, persistent, and repeated risk and produces graded warnings with explicit robustness margins and supporting windows. We validate the monitor in flight experiments with a Crazyflie quadrotor tracked by a Vicon motion capture system. Controlled comparisons quantify the contributions of individual monitoring components. Prescribed risk profiles verify the temporal semantics and illustrate how distinct risk patterns produce different warning levels.

0.20

Anytime-Valid Monitoring of Robust Stochastic Models

cs.LO ·2026-10-19 ·Martin Kurečka, Roman Andriushchenko, Milan Češka, Nicola Paoletti, Petr Novotný
theory similarity 0.60
Abstract

Formal methods provide a principal approach to obtaining safety guarantees for autonomous agents. Their key bottleneck is their reliance on a formal model (e.g., a Markov decision process) describing the agent-environment interaction. Learning or crafting the model is an error-prone process, which undermines the guarantees offered by formal methods. Robust models account for modelling uncertainty, but may still fail to capture the true environment. This issue can be addressed through \emph{runtime model monitoring}, which aims to raise an alarm when a likely model-environment discrepancy is detected, while keeping the probability of false alarm bounded. Existing approaches impose various assumptions and do not clearly explain the rationale behind their design choices, leaving the broader design space for these monitors somewhat opaque. In this paper, we formalise the design space of monitors for robust stochastic models through the lens of \emph{parameterised sequential betting} algorithms, highlighting the importance of \emph{observation feature} design (choosing what information about the history the monitor uses) and \emph{bet design} (how rich a family of betting rules the monitor can represent). We show that our framework generalizes the existing approaches, and we use its formalization to propose a new \emph{mixture of linear monitors (ML)} design. We prove that these ML monitors achieve an asymptotically optimal detection time within the class of linear monitors, making them a principled choice for our monitoring problem. Our experiments confirm that ML monitors significantly reduce detection times compared to existing monitors and can effectively exploit more complex observation features.

0.27