# Symbolic Abstractions From Data: A PAC Learning Approach

arXiv: https://arxiv.org/abs/2104.13901 · HTML: https://mlsanity.com/paper/2104.13901/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 26 references that are in the map.
- First posted on arXiv 28 Apr 2021.

## Builds on (most cited first, 10 of 10)

- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [A General Safety Framework for Learning-Based Control in Uncertain Robotic Systems](https://mlsanity.com/paper/1705.01292/) (2017)
- [Formulas for Data-driven Control: Stabilization, Optimality and Robustness](https://mlsanity.com/paper/1903.06842/) (2019)
- [Data-Enabled Predictive Control: In the Shallows of the DeePC](https://mlsanity.com/paper/1811.05890/) (2018)
- [Data-Driven Model Predictive Control with Stability and Robustness Guarantees](https://mlsanity.com/paper/1906.04679/) (2019)
- [Formal Controller Synthesis for Continuous-Space MDPs via Model-Free Reinforcement Learning](https://mlsanity.com/paper/2003.00712/) (2020)
- [DRYVR:Data-driven verification and compositional reasoning for automotive systems](https://mlsanity.com/paper/1702.06902/) (2017)
- [Data-Driven Reachable Set Computation using Adaptive Gaussian Process Classification and Monte Carlo Methods](https://mlsanity.com/paper/1910.02500/) (2019)
- [Bayesian Safe Learning and Control with Sum-of-Squares Analysis and Polynomial Kernels](https://mlsanity.com/paper/2004.00662/) (2020)
- [Compositional Abstraction-based Synthesis for Interconnected Systems: An Approximate Composition Approach](https://mlsanity.com/paper/2002.02014/) (2020)

## Built on by (most cited first, 6 of 6)

- [Data-driven abstractions via adaptive refinements and a Kantorovich metric [extended version]](https://mlsanity.com/paper/2303.17618/) (2023)
- [Neural Abstraction-Based Controller Synthesis and Deployment](https://mlsanity.com/paper/2307.03783/) (2023)
- [GenCtrl -- A Formal Controllability Toolkit for Generative Models](https://mlsanity.com/paper/2601.05637/) (2026)
- [Data-driven Abstractions with Probabilistic Guarantees for Linear PETC Systems](https://mlsanity.com/paper/2203.05522/) (2022)
- [Transfer Learning for Control Systems via Neural Simulation Relations](https://mlsanity.com/paper/2412.01783/) (2024)
- [S3: A Smooth Simulation Surrogate for Optimizing Discrete Abstractions of Dynamical Systems](https://mlsanity.com/paper/2608.15920/) (2026)

## Abstract (arXiv)

Symbolic control techniques aim to satisfy complex logic specifications. A critical step in these techniques is the construction of a symbolic (discrete) abstraction, a finite-state system whose behaviour mimics that of a given continuous-state system. The methods used to compute symbolic abstractions, however, require knowledge of an accurate closed-form model. To generalize them to systems with unknown dynamics, we present a new data-driven approach that does not require closed-form dynamics, instead relying only the ability to evaluate successors of each state under given inputs. To provide guarantees for the learned abstraction, we use the Probably Approximately Correct (PAC) statistical framework. We first introduce a PAC-style behavioural relationship and an appropriate refinement procedure. We then show how the symbolic abstraction can be constructed to satisfy this new behavioural relationship. Moreover, we provide PAC bounds that dictate the number of data required to guarantee a prescribed level of accuracy and confidence. Finally, we present an illustrative example.