Conformalized Data-Driven Reachability Analysis with PAC Guarantees
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.
Rosa: We're looking at the paper: "Conformalized Data-Driven Reachability Analysis with PAC Guarantees".
Dev: Here's the gist of the paper. Data-driven reachability analysis computes overapproximations of reachable sets directly from noisy data through a framework that provides Probably Approximately Correct (PAC) coverage guarantees via the Learn Then Test (LTT) calibration procedure.
Rosa: This framework is significant because it allows for safety certificates in cyber-physical systems without requiring explicit system models or known noise bounds.
Dev: Core Methodology and Guarantees The central contribution is the Conformalized Data-Driven Reachability (CDDR) framework, which formalizes data-driven reachability under unknown noise as a calibration problem and provides an (α, δ)-PAC coverage guarantee via LTT.
Rosa: This approach establishes a modelguarantee decoupling principle where the PAC guarantee holds independently of model accuracy.
Paper summary: Rosa: So we're looking at this paper called "Conformalized Data-Driven Reachability Analysis with PAC Guarantees". Basically the authors are trying to compute reachable sets directly from noisy data without needing any known bounds on the noise or system parameters like Lipschitz constants.
Dev: Right, so they propose this framework called Conformalized Data-Driven Reachability, or CDDR, which gives you a Probably Approximately Correct PAC coverage guarantee using a Learn Then Test calibration procedure. It claims this works even for systems where you don't know the process noise distributions.
Taro: I wonder how they handle the uncertainty when we're dealing with those unknown noise distributions? Does it just guess wrong or is there a principled way to manage that randomness?
Rosa: Well, the core idea is decoupling model accuracy from the PAC guarantee. They argue this makes you get a formal safety certificate for cyber-physical systems without having an explicit system model at all.
Dev: That decoupling principle is important because it means the PAC guarantee holds regardless of how accurate your fitted model actually turns out to be, which simplifies things for real-time control loops.
Taro: If the guarantee is independent of the model accuracy, that suggests we can trust the reachability prediction even if our local affine models are a bit off. But what about when the world misbehaves in ways not covered by those three settings they define?
Rosa: They developed this for three settings: linear timeinvariant systems without measurement noise, LTI systems with bounded measurement noise, and general nonlinear systems including dynamics that aren't Lipschitz continuous.
Dev: That covers a lot of ground. For the LTI case without measurement noise, they propagate reachable sets using a fitted model and some conformalized error zonotopes called ZCPk.
Taro: So for the nonlinear stuff, instead of fitting one big model, they fit a local affine model at each time step k around a nominal trajectory. That sounds computationally intensive when you're trying to run this in real-time.
Rosa: It is intensive but it handles non-Lipschitz dynamics, which is where traditional methods struggle because you can't assume smooth behavior everywhere. They use the data from a training set Dtr and partition it into a calibration set Dcal of size n, where n equals K minus Ktr.
Dev: And then they have this reachability set propagation rule that changes depending on whether you're in the LTI case without measurement noise or the LTI case with measurement noise, which involves Minkowski sums with those zonotopes Zv.
Taro: What about the results? Do these guarantees actually hold up when we test them against real-world failure modes, and what are the actual performance metrics they report?
Rosa: They have a theorem establishing an alpha delta PAC multi-step coverage guarantee under Assumption one which requires that calibration trajectories and the test trajectory are independently and identically distributed <ref:2603.12220#pg1>. Experiments on a five dimensional LTI system under Gaussian and heavy-tailed Student t noise show CDDR achieves valid coverage where deterministic methods simply don't provide formal guarantees.
Dev: And they also showed that you can control the geometry of the coverage by designing a score function, and specifically for anisotropic noise, using a normalized score function can reduce the reachable set volume by orders of magnitude while still keeping that PAC guarantee intact.
Taro: So it sounds like if we have directional noise where things are much noisier in one direction than another, this method can actually shrink the uncertainty region significantly without sacrificing the mathematical safety promise.
Rosa: Exactly. They found that an isotropic score function is a bit conservative when you have anisotropic noise, and they needed a calibration set size of three thousand one hundred five for the PAC guarantee in that case.
Dev: But then they introduced this normalized score function, which requires a calibration set of four hundred fifty nine to achieve comparable volume reduction to the isotropic baseline while not changing the required PAC guarantee at all.
Taro: That's interesting because it means we don't have to drastically increase our data collection just to get better directional precision; we can tune how we measure instead.
Rosa: They conclude that CDDR successfully gives a distribution-free and model-class-free PAC guarantee for LTI systems, both with and without measurement noise, as well as for non-Lipschitz nonlinear systems. They also noted that across random calibration splits, CDDR achieves zero failure rate, unlike the empirical max or marginal CP baselines they compared it against.
Dev: The implication here is that this framework offers a robust way to plan trajectories in unknown or noisy environments where traditional methods simply can't provide formal guarantees about reaching certain states.
Taro: So for someone who just listens to the show, what does this mean? It means we have a way to check if a planned path will stay within bounds even when the noise is weird and we don't know the noise distribution at all.
Rosa: It means moving towards safety certificates in complex systems without needing perfect mathematical models of every single component.
Dev: The paper "Conformalized Data-Driven Reachability Analysis with PAC Guarantees" shows how data can replace explicit system models to provide formal probabilistic guarantees on reachability.
Conclusion: Rosa: So, we’re wrapping up this look at "Conformalized Data-Driven Reachability Analysis with PAC Guarantees." Basically, these authors are showing how you can figure out where a system *can* go using just noisy data instead of needing a perfect blueprint of the system itself.
Dev: Right. They’ve put together this framework that uses something called Learn Then Test calibration to give you a formal guarantee—a PAC guarantee—about the reachability, even when you don't know what the noise distribution is.
Taro: It’s significant because it lets us get a safety certificate for those cyber-physical systems without having to build a complete model of how they work or knowing exactly how much noise there is.
Rosa: That's the big deal, I think. If you can do that, it means we can deploy things in the real world where you don't have perfect system models and you definitely don't know the exact noise bounds.
Dev: Exactly. The way they handle unknown noise distributions is a core part of this work; they treat it like a calibration problem instead of a known quantity.
Taro: And what they did for the nonlinear systems is pretty cool, too—they fit local models at every time step around the path you’re taking, which handles those tricky non-smooth dynamics.
Rosa: And the results are pretty strong; they show zero failure rate across random calibration splits when compared to some of the other methods they tested. It seems like this approach is very robust in terms of performance across different setups.
Dev: That robustness comes from how they handle those score functions, because you can tune them to control the trade-off between how much data you need and how accurate your reachability prediction gets.
Taro: So, it’s not just about getting *a* guarantee; it’s about controlling the geometry of that uncertainty region when things are noisy or directional.
Rosa: And they managed to do that without having to drastically increase the size of the calibration set for those more complex noise scenarios.
Dev: It moves us toward a world where we don't need perfect models, but we still get a formal, distribution-free statement about system safety based on what we actually observe.
Taro: So it’s about leveraging data to prove reachability bounds in really messy, non-ideal situations.
Rosa: It sets a new standard for how we approach uncertainty in motion planning and control when the underlying physics are hard to pin down.
Yanliang Huang, Zhen Zhang, Peng Xie, Zhuoqi Zeng, Amr Alanwar
Technical University of Munich · Hainan Bielefeld University of Applied Sciences
eess.SY, cs.SY
Submitted: 2026-03-12
Updated: 2026-11-06
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 95/100
The gist: Data-driven reachability analysis computes overapproximations of reachable sets directly from noisy data through a framework that provides Probably Approximately Correct (PAC) coverage guarantees via…
Key concepts
- Conformalized Data-Driven Reachability (CDDR)
- A framework that treats reachability under unknown noise as a calibration problem. It uses data to construct uncertainty sets and provides PAC guarantees, meaning the resulting safety bounds are correct with high probability, regardless of the true system model accuracy.
- Learn Then Test (LTT) Calibration
- A procedure used to calibrate the data-driven reachability analysis. It involves training on a calibration set and testing on a separate trajectory set to estimate uncertainty. This process ensures the PAC guarantee holds by decoupling model accuracy from the statistical confidence in the coverage.
- PAC Coverage Guarantee
- A formal mathematical guarantee stating that, with high probability (confidence level $eta$) and with sufficient accuracy ($ ext{error } heta$), a computed reachable set will contain the true set of possible states. This allows for robust safety verification even when system dynamics are complex or noisy.
- Modelguarantee Decoupling Principle
- A core idea stating that the PAC guarantee holds independently of how accurate the underlying system model is. The statistical calibration method (LTT) ensures that the uncertainty quantification provides a reliable safety bound, even if the assumed mathematical model has errors.
Terminology
Summary
Data-driven reachability analysis computes overapproximations of reachable sets directly from noisy data through a framework that provides Probably Approximately Correct (PAC) coverage guarantees via the Learn Then Test (LTT) calibration procedure. p. 0 This framework is significant because it allows for safety certificates in cyber-physical systems without requiring explicit system models or known noise bounds. p. 0
Core Methodology and Guarantees
The central contribution is the Conformalized Data-Driven Reachability (CDDR) framework, which formalizes data-driven reachability under unknown noise as a calibration problem and provides an (α, δ)-PAC coverage guarantee via LTT. This approach establishes a modelguarantee decoupling principle where the PAC guarantee holds independently of model accuracy. p. 0 The framework is developed for three settings: linear timeinvariant (LTI) systems with unknown process noise distributions, LTI systems with bounded measurement noise, and general nonlinear systems including non-Lipschitz dynamics. p. 0
System Modeling and Data Handling
The problem formulation considers three settings: (A) LTI without measurement noise where the state is directly observed, (B) LTI with measurement noise where the observation-input data is available, and (C) Nonlinear without measurement noise where the dynamics f may be non-Lipschitz. The available data consists of trajectories generated from an initial state in X0 under inputs in U and is partitioned into a training set Dtr and a calibration set Dcal. p. 2
Reachability Set Propagation
The reachable sets RCPk depend on the calibration data and vary across calibration draws. The propagation rules differ based on the system type. p. 0 For LTI systems without measurement noise, reachable sets are propagated using the fitted model M˜ and conformalized error zonotopes ZCPk. p. 2 In the LTI with measurement noise case, the recursion involves Minkowski sums with Zv to account for observation-state conversion. p. 2 For general nonlinear systems, CDDR fits a local affine model M′k at each time step k, linearized around a nominal trajectory. p. 2
Theoretical Validation and Performance
Theorem 1 establishes the (α, δ)-PAC multi-step coverage guarantee under Assumption 1, which requires that calibration trajectories and the test trajectory are i.i.d. Experiments confirm CDDR achieves 100% coverage with the PAC guarantee from Theorem 1. p. 4 Furthermore, score function design can control the geometry-coverage tradeoff; for anisotropic noise, a normalized score function reduces the reachable set volume by orders of magnitude while preserving the PAC guarantee. p. 0
Score Function Optimization
The performance evaluation shows that score variants impact efficiency and required calibration size. The isotropic score is conservative under anisotropic noise. p. 3 The per-dimension score requires a larger calibration set of nmin = 3105 for the PAC guarantee compared to the isotropic case. p. 5 The normalized score achieves a comparable volume reduction with nmin = 459, matching the isotropic baseline while requiring no modification to the PAC guarantee. p. 5
Conclusion and Future Directions
CDDR successfully provides a distribution-free and model-class-free PAC guarantee for LTI systems (with or without measurement noise) and non-Lipschitz nonlinear systems. The framework handles the unknown process noise distributions and the lack of known Lipschitz constants. p. 0 Future work includes adaptive calibration for nonstationary environments and extension to nonconvex reachable sets. p. 5 The paper concludes that CDDR achieves zero failure rate across random calibration splits, unlike marginal CP and empirical-max baselines. p. 5
References
[1] M. Althoff, G. p. 5 Frehse, and A. p. 5 Girard, “Set propagation techniques for reachability analysis,” Annual Review of Control, Robotics, and Autonomous Systems, vol. p. 5 4, no. 1, pp. 369–395, 2021
[2] A. Alanwar, A. p. 0 Koch, F. Allgower, and K. p. 5 H. Johansson, “Data-driven reachability analysis from noisy data,” IEEE Transactions on Automatic Control, vol. p. 5 68, no. 5, pp. 3054–3069, 2023
[3] V. Vovk, A. Gammerman, and G. p. 5 Shafer, Algorithmic Learning in a Random World
[4] A. N. Angelopoulos, S. p. 5 Bates, E. J. Candes, M. I Jordan, and L Lei “Learn then test: Calibrating predictive algorithms to achieve risk control,” The Annals of Applied Statistics, vol 19, no 2 pp 1641–1662
[5] L. Lindemann, M. p. 0 Cleaveland, G. p. 0 Shim, and G. p. 5 J Pappas “Safe planning in dynamic environments using conformal prediction,” IEEE Robotics and Automation Letters, vol 8 no 8 pp 5116–5123
[6] N. Hashemi, X. p. 0 Qin, L. Lindemann, L. p. 0 Deshmukh “Data-driven reachability analysis of stochastic dynamical systems with conformal inference,” in Proc of the 62nd IEEE Conference on Decision and Control (CDC), 2023 pp 3102–3109
[7] A. Dixit, L. Lindemann, S. p. 0 X Wei, M. Cleaveland, G J Pappas and J W Burdick “Adaptive conformal prediction for motion planning among dynamic agents,” in Proc of the 5th Annual Learning for Dynamics and Control Conference (L4DC). p. 5 PMLR, 2023 pp 300–314
[8] M. Cleaveland, I Lee, G J Pappas, and L Lindemann “Conformal prediction regions for time series using linear complementarity programming,” in Proc of the AAAI Conference on Artificial Intelligence, vol 38 no 19 2024 pp 20984–20992
[9] A. Devonport, F Yang, L El Ghaoui, and M Arcak “Data-driven reachability analysis with Christoffel functions,” in Proc IEEE Conf Decision and Control (CDC), 2021 pp 5067–5072
[10] L. Blackmore, M Ono, and B C Williams “Chance-constrained optimal path planning with obstacles,” IEEE Transactions on Robotics, vol 27 no 6 pp 1080–1094
[11] S. Summers and J Lygeros “Verification of discrete time stochastic hybrid systems: A stochastic reach-avoid decision problem,” Automatica, vol 46 no 12 pp 1951–1961
[12] Z. Liu, S Jafarpour, and Y Chen “Probabilistic reachability of discrete-time nonlinear stochastic systems,” arXiv preprint arXiv:2409. p. 509334, 2024
[13] E. Arsenault, Y Wang, and M P Chapman “Toward scalable risk analysis for stochastic systems using extreme value theory,” IEEE Control Systems Letters, vol 6 pp 3391–3396
[14] G C Calafiore and M C Campi “The scenario approach to robust control design,” IEEE Transactions on Automatic Control, vol 51 no 5 pp 742–753
[15] S Bates, A N Angelopoulos, L Lei, J Malik, and M I Jordan “Distribution-free risk-controlling prediction sets,” Journal of the ACM, vol 68 no 6 pp 1–34
[16] E Dietrich, R Devonport, S Tu, and M Arcak “Data-driven reachability with scenario optimization and the holdout method,” in Proc IEEE Conf Decision and Control (CDC), 2025 pp 3925–3931
[17] M. Althoff “An introduction to CORA 2015,” in Proc of the Workshop on Applied Verification for Continuous and Hybrid Systems (ARCH), 2015 pp 120–151
[18] W. Kuhn “Rigorously computed orbits of dynamical systems without the wrapping effect,” Computing, vol 61 no 1 pp 47–67, 1998
[19] A.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Data-driven reachability analysis will be applied to LTI systems with unknown process noise distributions to compute overapproximations of reachable sets directly from noisy data, bypassing the need for known noise bounds or system-specific structural parameters.
-
The system can safely verify safety in cyber-physical systems by constructing overapproximating reachable sets using the Conformalized Data-Driven Reachability (CDDR) framework, which provides Probably Approximately Correct (PAC) coverage guarantees through the Learn Then Test (LTT) calibration procedure.
-
For LTI systems with bounded measurement noise, the system can compute reachable sets where the recursion uses a Minkowski sum involving a known, bounded observation-state conversion zonotope Zv to account for measurement noise corruption of inputs.
-
In general nonlinear systems, the system can compute overapproximations of reachable sets by fitting local affine models at each time step around a nominal trajectory, allowing model accuracy and statistical coverage to be fully decoupled.
-
The improved system can utilize a normalized score function to reduce the reachable set volume by orders of magnitude under anisotropic noise while preserving the PAC guarantee, offering tighter safety certificates than isotropic methods.
Sources
Related papers
- Industrial Load Modeling and Optimization for Market-Based Interaction with Power Systems
- Exact and Approximate Convex Reformulation of Linear Stochastic Optimal Control with Chance Constraints
- Certified Set Convergence for Piecewise Affine Systems
- Symbolic Control for Stochastic Systems via Finite Parity Games
- Multiobjective optimization-based design and dispatch of islanded, hybrid microgrids for remote, off-grid communities in sub-Saharan Africa
- Physiology-informed layered sensing for intelligent human-exoskeleton interaction