Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees

Georgios Pantazis; Michelle S. Chong

math.OCApr 14, 2026

Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees

Authors: Georgios Pantazis, Michelle S. Chong

Organizations: Dynamics and Control (D&C) section at the Department of Mechanical Engineering, Eindhoven University of Technology, the Netherlands.

Abstract

We study finite horizon reachable set estimation for unknown discrete-time dynamical systems using only sampled state trajectories. Rather than treating scenario optimization as a black-box tool, we show how it can be tailored to reachable set estimation, where one must learn a family of sets based on whole trajectories, while preserving probabilistic guarantees on future trajectory inclusion for the entire horizon. To this end, we formulate a relaxed scenario program with slack variables that yields a tunable trade-off between reachable set size and out-of-sample trajectory inclusion over the horizon, thereby reducing sensitivity to outliers. Leveraging the recent results in adversarially robust scenario optimization, we then extend this formulation to account for bounded adversarial perturbations of the observed trajectories and derive a posteriori probabilistic guarantees on future trajectory inclusion. When probability distribution shifts in the Wasserstein distance occur, we obtain an explicit bound on how gracefully the theoretical probabilistic guarantees degrade. For different geometries, i.e., $p$ -norm balls, ellipsoids, and zonotopes, we derive tractable convex reformulations and corroborate our theoretical results in simulation.

Figures & tables

Panel of Figure 1 — Fig. 1 : Adversarially robust data-driven estimation of reachable sets for different geometries, i.e., zonotopes, ellipsoids and Euclidean balls. We consider $T=25$ and illustrate three timestamps at $k\in\{5,10,20\}$ . We learn each set using $N=1000$ different state trajectories, perturbed by the set $\Delta$ , thus giving rise to the red cross points which denote adversarial samples. We consider a penalty parameter $\rho\in\{0.5,1,2,5\}$ and illustrate the geometric shapes for these values. Note that as $\rho$ increases, the set increases as well. This is because the relaxation variables of $\hat{P}_{N,\rho,A}$ are penalized more to satisfy the observed state trajectories. As such, $\rho$ acts as a tuning parameter trading set size for inclusion of future state trajectories.

Fig. 2 : Adversarial theoretical trajectory violation level (dashed lines) vs its empirical counterpart (solid lines) for different geometric shapes. As the number of samples $N$ increases, the theoretical and empirical probabilities improve significantly. Note that zonotopes require a higher number of sampled trajectories to provide the same guarantees with ellipsoids and balls, though at the benefit of tighter zonotopic regions.

Fig. 3 : Out-of-distribution theoretical trajectory violation level (dashed lines) and out-of-distribution empirical trajectory violation level for reachable sets of different geometries.

Fig. 4 : Relative cumulative reachable set size over time for each geometry. Interestingly, as $\rho$ increases, all shapes exhibit similar relative increase in cumulative size.

Distribution Shift Robustness

Distribution shift robustness studies how to keep machine-learning predictions reliable when deployment data differ from training data.

See all 280 papers

On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity
Jul 21, 2026Jixian Liu, Ihab Tabbara, Hussein Sibai +1Reachability Analysis Sample Complexity
Department of Electrical and Computer Engineering, Johns Hopkins University · Department of Computer Science, Washington University in St. Louis
Temporal Difference Learning of Probabilistic Reach-Avoid Value Functions
Oct 20, 2026Elias Fontanari, Pietro Noah Crestaz, Matteo Saveriano +1Reachability Analysis
Industrial Engineering Department, University of Trento, Trento, Italy. · LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France.
Solving Parameter-Robust Avoid Problems with Unknown Feasibility using Reinforcement Learning
Feb 17, 2026Oswin So, Eric Yang Yu, Songyuan Zhang +3Safe RL Reachability Analysis
Department of Aeronautics and Astronautics, MIT · MIT Lincoln Laboratory

Jul 21, 2026J/K move · Enter open · S save

On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity

Jixian Liu, Ihab Tabbara, Hussein Sibai, Enrique Mallada

Department of Electrical and Computer Engineering, Johns Hopkins University · Department of Computer Science, Washington University in St. Louis

Reachability Analysis Sample Complexity

Open paper AskPDF arXiv

Reachability analysis is central to safety-critical control, robotics, and neural network verification, but classical computational methods, such as Hamilton--Jacobi reachability and set propagation, scale poorly with state dimension. Sampling-based methods have emerged as a promising alternative, often providing finite-sample guarantees that bound the probability-mass left uncovered. However, an explicit account of how the geometry of the initial set, the dynamics, and the sampling law affect the accuracy of the estimator is not fully available in the literature. We study this by casting sampling-based reachable-set recovery as geometric support estimation over a family of problems specified by an initial set, its dynamics, and a sampling law. First, we identify two regularity properties, positive reach of the initial set's complement and Lipschitz continuity of the dynamics, that together make recovery well-posed: a probability-mass coverage guarantee can be upgraded to accuracy

r

in Hausdorff distance. Second, we bound the resulting sample complexity: recovery is achievable with

\tilde{\mathcal{O}}\big((e^{3LT}/r)^n\big)

samples, exponential in both the state dimension and the time horizon. Third, we show that neither can be removed: an minimax lower bound of

Ω\big((e^{LT}/r)^n\big)

holds for every estimator, so the exponential dependence on dimension and the degradation over the horizon are both intrinsic, not artifacts of a particular method. Experiments on nonlinear systems confirm that adversarial sampling improves constants but not the scaling.

Abstract

Distribution Shift Robustness

Explore similar work

On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity

Temporal Difference Learning of Probabilistic Reach-Avoid Value Functions

Solving Parameter-Robust Avoid Problems with Unknown Feasibility using Reinforcement Learning