DARSY: A Tool for Data-Driven Abstraction and Policy Synthesis for Stochastic Systems with Unknown Dynamics

Thom Badings, Ibon Gracia, Mahdi Nazeri, Morteza Lahijanian, Alessandro AbatearXiv 2026 · arXiv

TL;DR

DARSY is an open-source Python tool that synthesizes control policies with formal "Probably Approximately Correct" (PAC) guarantees for stochastic systems with unknown dynamics. By combining data-driven abstractions (Interval MDPs) with robust dynamic programming, it allows researchers to bridge the gap between black-box simulators and formal verification.

What Problem Does This Paper Address?

Formal policy synthesis aims to create control strategies that guarantee a system will satisfy a specific requirement—like a robot reaching a goal while avoiding obstacles—with a high probability. Traditionally, this requires a "white-box" mathematical model of the system's dynamics and noise.

However, real-world systems (like drones or complex chemical processes) are often too messy to model exactly. We might only have access to a simulator or historical data. While reinforcement learning can handle these "black-box" scenarios, it rarely provides the rigorous safety guarantees required for critical applications. DARSY addresses this by creating a bridge: it uses data samples to build a formal abstraction that accounts for uncertainty, providing certified lower bounds on the probability of success even when the underlying equations are unknown.

Methods

DARSY transforms a continuous, unknown stochastic system into a finite, discrete abstraction called an Interval Markov Decision Process (IMDP).

  1. Data-Driven Abstraction: Instead of exact transition probabilities, DARSY calculates intervals (lower and upper bounds) for transitions between states. It uses a known Lipschitz constant (a measure of how "smooth" the dynamics are) and statistical techniques (Clopper-Pearson intervals) to ensure these bounds are sound with a user-defined confidence level ($\beta$).
  2. Two-Layer IMDP (2IMDP): A key innovation is the support for 2IMDPs. By grouping states into "blocks" and bounding transitions at both the state and block levels, DARSY can produce much tighter probability bounds than standard IMDPs, especially in data-sparse regions.
  3. Two-Phase Sampling: To keep the abstraction efficient, DARSY uses a clever two-phase approach. The first batch of samples identifies "candidate" successor states, and the second batch estimates the probabilities. This prevents the model from becoming an overly conservative "dense" graph where every state can transition to every other state.
  4. Formal Specifications: Users define tasks using syntactically co-safe Linear Temporal Logic (scLTL). DARSY uses the Spot library to convert these logic formulas into Deterministic Finite Automata (DFA).
  5. Robust Synthesis: The tool performs robust dynamic programming on the product of the abstraction and the DFA to find the optimal policy and the certified PAC lower bound on the satisfaction probability.
Figure 1: Based on sampled transitions (shown in blue) from a discrete-time stochastic system, DARSY computes a policy together with PAC bounds on the probability that the system satisfies a given scLTL specification (shown as automaton).

Datasets

The authors evaluated DARSY on 13 benchmarks derived from 10 different stochastic systems, ranging from 1 to 4 dimensions:

  • Linear Systems: Temp1D through Temp4D (room temperature control) and DoubleInt (double integrator).
  • Nonlinear Systems: MountainCar (classic RL benchmark), Pendulum (with both triangular and Gaussian noise), and Dubins Car (2D and 3D versions).
  • Noise Types: The benchmarks include additive and multiplicative noise with various distributions (Gaussian, Truncated Gaussian, and Triangular).

Key Insights and Ideas

  • The Power of Lipschitz Continuity: You don't need to know the equations if you know how much they can "wiggle." The Lipschitz constant allows DARSY to extrapolate from a single data point to a whole region of the state space safely.
  • Sparsity is Safety: Standard data-driven methods often result in "dense" abstractions where every transition is possible (with low probability). This leads to extreme conservatism. DARSY’s two-phase sampling (illustrated below) keeps the model sparse, which paradoxically leads to higher (better) certified lower bounds.
  • JAX Integration: By implementing the core algorithms in JAX, the authors enable just-in-time (JIT) compilation and vectorized computation, making the tool fast enough to handle abstractions with hundreds of thousands of states and millions of transitions.
Figure 3: Two-phase sampling for a state-action pair (𝑠,𝑢). (a) The successors of a first batch of samples from 𝑅𝑠, each inflated to a box using the Lipschitz constant, define a bound- ing box (dashed). The regions that intersect this bounding box are the candidate successors S𝑠,𝑢(in blue). (b) An inde- pendent second batch yields the probability intervals for all 𝑠′ ∈S𝑠,𝑢. The boxes that leave 𝑅𝑠,𝑢(red) count towards the probability of transitioning to the sink state 𝑠★.

Key Results

  • Tight Guarantees: In the "Pendulum-G" benchmark, the 2IMDP abstraction improved the certified lower bound ($\lambda$) from 0.622 (standard IMDP) to 0.743 using 100k samples.
  • Sample Efficiency: The tool demonstrates a clear "sweet spot" for sampling. While more samples always improve the bound, the gains eventually become marginal compared to the increased abstraction time.
  • Scalability: DARSY successfully handled the Temp4D system, creating an abstraction with over 20,000 states and 430 million transitions.
  • Non-Uniform Grids: To ensure the abstraction is "label-preserving" (i.e., every point in a grid cell has the same label like "goal" or "unsafe"), DARSY automatically refines user-requested grids into non-uniform partitions.
Example of a non-uniform state partition generated to align with goal and unsafe regions.

Limitations and Future Work

  • The Lipschitz Requirement: DARSY requires a Lipschitz constant. While these can be estimated from data or expert knowledge, an incorrect constant breaks the formal soundness of the tool.
  • Curse of Dimensionality: Like all abstraction-based methods, the number of states grows exponentially with the system's dimension. The current tool is effective up to 4 or 5 dimensions.
  • Future Directions: The authors plan to extend DARSY to "gray-box" settings where some partial knowledge of the dynamics is available. They also aim to leverage GPU acceleration via JAX to scale to even higher-dimensional systems and finer grid resolutions.

Summary updated

Abstract

This paper presents DARSY: a software tool for abstraction-based verification and policy synthesis in discrete-time stochastic control systems with unknown dynamics and noise distributions. DARSY requires only a simulator of the system and a Lipschitz bound on its dynamics, and needs no knowledge of dynamics or noise distributions. The tool is fully automated and constructs a finite interval Markov decision process (IMDP) abstraction from sampled transitions, whose probability intervals are obtained via statistical techniques and Lipschitz reasoning. Robust dynamic programming on this IMDP then yields a policy together with a lower bound on the probability that the unknown system satisfies a desired specification. This lower bound holds with a user-specified confidence; that is, it is probably approximately correct (PAC). The tool is implemented in Python and supports general Lipschitz-continuous system dynamics and specifications expressed in syntactically co-safe LTL (scLTL), which includes reach-avoid and finite-horizon safety specifications as special cases. Beyond standard IMDPs, DARSY implements a two-layer IMDP (2IMDP) abstraction that also bounds the probability of transitioning to aggregated state blocks, yielding smaller abstraction errors than IMDP abstractions and, as a result, tighter satisfaction guarantees. We demonstrate DARSY's broad applicability across a variety of benchmarks and specifications.
BibTeX
@misc{badings2026darsy,
  author = {Thom Badings and Ibon Gracia and Mahdi Nazeri and Morteza Lahijanian and Alessandro Abate},
  title = {{DARSY: A Tool for Data-Driven Abstraction and Policy Synthesis for Stochastic Systems with Unknown Dynamics}},
  year = {2026},
  eprint = {2611.25654},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25654},
}
Figure