Learning Control Policies for Stochastic Systems with Reach-Avoid Guarantees
Dorde Zikelic, Mathias Lechner, Thomas A. Henzinger, Krishnendu Chatterjee
Abstract
We study the problem of learning controllers for discretetime non-linear stochastic dynamical systems with formal reach-avoid guarantees. This work presents the first method for providing formal reach-avoid guarantees, which combine and generalize stability and safety guarantees, with a tolerable probability threshold p ∈ [0, 1] over the infinite time horizon in general Lipschitz continuous systems. Our method leverages advances in machine learning literature and it represents formal certificates as neural networks. In particular, we learn a certificate in the form of a reach-avoid supermartingale (RASM), a novel notion that we introduce in this work. Our RASMs provide reachability and avoidance guarantees by imposing constraints on what can be viewed as a stochastic extension of level sets of Lyapunov functions for deterministic systems. Our approach solves several important problems -it can be used to learn a control policy from scratch, to verify a reach-avoid specification for a fixed control policy, or to fine-tune a pre-trained policy if it does not satisfy the reachavoid specification. We validate our approach on 3 stochastic non-linear reinforcement learning tasks.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
13 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Quantitative Supermartingale Certificates cites Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs
- Quantitative Supermartingale Certificates cites Learning Probabilistic Termination Proofs
- Quantitative Supermartingale Certificates cites Stability Verification in Stochastic Control Systems via Neural Network Supermartingales
- Quantitative Supermartingale Certificates cites Neural Model Checking
- Quantitative Supermartingale Certificates cites Compositional Policy Learning in Stochastic Control Systems with Formal Guarantees
- Quantitative Supermartingale Certificates cites Sound and Complete Witnesses for Template-Based Verification of LTL Properties on Polynomial Programs
- Stability Verification in Stochastic Control Systems via Neural Network Supermartingales cites Learning Probabilistic Termination Proofs
- Stability Verification in Stochastic Control Systems via Neural Network Supermartingales cites Almost Surely Stable Deep Dynamics
- Neural Model Checking cites Learning Safe Multi-agent Control with Decentralized Neural Barrier Certificates
- Neural Model Checking cites Learning Probabilistic Termination Proofs
- Neural Model Checking cites Stability Verification in Stochastic Control Systems via Neural Network Supermartingales
- Neural Model Checking cites Compositional Policy Learning in Stochastic Control Systems with Formal Guarantees
- Let a Neural Network be Your Invariant cites Learning Safe Multi-agent Control with Decentralized Neural Barrier Certificates
- Let a Neural Network be Your Invariant cites Learning Probabilistic Termination Proofs
- Let a Neural Network be Your Invariant cites Quantitative Supermartingale Certificates
- Let a Neural Network be Your Invariant cites Stability Verification in Stochastic Control Systems via Neural Network Supermartingales
- Let a Neural Network be Your Invariant cites Neural Model Checking
- Let a Neural Network be Your Invariant cites Compositional Policy Learning in Stochastic Control Systems with Formal Guarantees
- Compositional Policy Learning in Stochastic Control Systems with Formal Guarantees cites Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic Programs
- Compositional Policy Learning in Stochastic Control Systems with Formal Guarantees cites Stability Verification in Stochastic Control Systems via Neural Network Supermartingales
Cited by top-tier papers13
- Compositional Policy Learning in Stochastic Control Systems with Formal GuaranteesDorde Zikelic, Mathias Lechner, Abhinav Verma, Krishnendu Chatterjee et al.NeurIPS 2023 · 31 citations
- Neural Model CheckingMirco Giacobbe, Daniel Kroening, Abhinandan Pal, Michael TautschnigNeurIPS 2024 · 17 citations
- Sound and Complete Witnesses for Template-Based Verification of LTL Properties on Polynomial ProgramsKrishnendu Chatterjee, Amir Kafshdar Goharshady, Ehsan Kafshdar Goharshady, Mehrdad Karrabi et al.FM 2024 · 11 citations
- Quantitative Supermartingale CertificatesAlessandro Abate, Mirco Giacobbe, Diptarko RoyCAV 2025 · 7 citations
- Let a Neural Network be Your InvariantMirco Giacobbe, Daniel Kroening, Abhinandan Pal, Michael TautschnigNeurIPS 2025 · 6 citations
Builds on6
- Learning Safe Multi-agent Control with Decentralized Neural Barrier CertificatesZengyi Qin, Kaiqing Zhang, Yuxiao Chen, Jingkai Chen et al.ICLR 2021 · 164 citations
- Stability Verification in Stochastic Control Systems via Neural Network SupermartingalesMathias Lechner, Dorde Zikelic, Krishnendu Chatterjee, Thomas A. HenzingerAAAI 2022 · 45 citations
- Sound and Complete Certificates for Quantitative Termination Analysis of Probabilistic ProgramsKrishnendu Chatterjee, Amir Kafshdar Goharshady, Tobias Meggendorfer, Dorde ZikelicCAV 2022 · 30 citations
- Almost Surely Stable Deep DynamicsNathan P. Lawrence, Philip D. Loewen, Michael G. Forbes, Johan U. Backström et al.NeurIPS 2020 · 28 citations
- Learning Probabilistic Termination ProofsAlessandro Abate, Mirco Giacobbe, Diptarko RoyCAV 2021 · 26 citations
Related papers
- Policy Verification in Stochastic Dynamical Systems Using Logarithmic Neural CertificatesThom Badings, Wietze Koops, Sebastian Junges, Nils JansenCAV 2025 · 1 citation
- Stochastic Minimum-Cost Reach-Avoid Reinforcement LearningJingduo Pan, Taoran Wu, Yiling Xue, Bai XueICML 2026
- Stochastic Omega-Regular Verification and Control with SupermartingalesAlessandro Abate, Mirco Giacobbe, Diptarko RoyCAV 2024 · 13 citations
- Supermartingale Certificates for Quantitative Omega-Regular Verification and ControlThomas A. Henzinger, Kaushik Mallik, Pouya Sadeghi, Dorde ZikelicCAV 2025 · 6 citations
- Verified Safe Reinforcement Learning for Neural Network Dynamic ModelsJunlin Wu, Huan Zhang, Yevgeniy VorobeychikNeurIPS 2024 · 13 citations
