Formal Abstractions using Interval Markov Decision Processes

This direction is split into other directions: interval-based transition modeling. Its last version stays readable and citable here.

Version 1 of 168 papers81 conceptsfrozen 2026-10-04

In classical control theory and reinforcement learning, we often model the world as a Markov Decision Process (MDP). We assume that if a robot takes an action in a certain state, there is a fixed, known probability of landing in the next state. However, this assumption is a fragile foundation for safety-critical systems. In the real world, we rarely know these probabilities exactly. Whether due to finite data samples, sensor noise, or the inherent loss of precision when simplifying a continuous world into discrete states, our "point estimates" of probability are almost certainly wrong.

To address this, researchers have developed a framework that replaces single-point probabilities with Interval Markov Decision Processes (IMDPs). By representing transitions as ranges—intervals with a lower and upper bound—we can build controllers that are "correct-by-construction," providing rigorous safety guarantees even when the underlying system dynamics are uncertain or unknown.

The Problem with Point Estimates

When we discretize a continuous dynamical system into a finite set of states, we introduce "abstraction error." A single discrete cell in our model might represent a vast region of physical space. As Adrien Banse, Alessandro Abate, and colleagues note in Data-driven memory-dependent abstractions of dynamical systems, the exact transition probability depends on where inside that cell the system starts. Picking a single number to represent this transition is an oversimplification that can lead to dangerously optimistic safety claims.

Furthermore, when we learn models from data, we face epistemic uncertainty—the uncertainty stemming from a lack of knowledge. As argued in Probabilities Are Not Enough by Thom Badings and Alessandro Abate, treating estimated probabilities as absolute truths ignores the risk that our finite dataset might not represent the true distribution of the environment.

From Points to Intervals

The core intuition of the IMDP framework is to embrace this uncertainty rather than ignore it. Instead of saying the probability of a transition is $0.8$, we say it lies within the interval $[0.75, 0.85]$.

This shift transforms the problem from a standard optimization task into a robust game. When we synthesize a control policy, we assume an "adversary" will choose the worst possible probability distribution from within our defined intervals. If we can find a policy that satisfies our safety requirements even against this adversary, we have a robust guarantee. Kim G. Larsen and Axel Legay highlight in Quantitative Modal Transition Systems that this interval-based approach ensures models remain mathematically closed under composition, which is vital for verifying complex, multi-component systems.

Building Abstractions from Data

How do we determine these intervals if the system is unknown? Modern research utilizes two primary paths:

  1. Statistical Concentration Inequalities: By observing trajectories, researchers like Zhi Zhang and Sadegh Soudjani use tools like Hoeffding’s inequality to calculate bounds that contain the true transition probability with a high degree of confidence (Formal Verification of Unknown Stochastic Systems via Non-parametric Estimation).
  2. The Scenario Approach: In Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noise, Thom S. Badings and Nils Jansen demonstrate how to use a finite number of noise samples to define intervals. This "distribution-free" method allows for Probably Approximately Correct (PAC) guarantees, meaning the safety bounds hold even if the noise is non-Gaussian or follows a mysterious distribution.

Scaling to Complex Systems

A major hurdle for formal methods is the "curse of dimensionality." Discretizing a high-dimensional state space leads to an exponential explosion of states. Recent work has focused on making IMDPs practical for real-world robotics:

Why It Works: The Intuition of Robustness

The reason IMDP abstractions work is that they provide a safety buffer. By planning against the lower bounds of success probabilities and the upper bounds of risk, an agent (like a UAV or a robot explorer) ensures that its plan is viable for the worst-case scenario within its knowledge gaps.

As Brendan Juba and Roni Stern highlight in their work on Safe Action Models, this allows an agent to be "Probably Approximately Complete." It may not find the absolute optimal path that a perfect model would, but it is guaranteed to find a path that is safe, provided a safe path exists within the bounds of its observations. In safety-critical autonomy, being robustly safe is far more valuable than being optimally risky.

Papers in this version

Showing 60 of 68 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_formal_abstractions_using_interval_marko_deb1f930,
  title = {Formal Abstractions using Interval Markov Decision Processes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/formal-abstractions-using-interval-markov-decision-processes/rdr_deb1f930193745e0a06e18c2025020f9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_formal_abstractions_using_interval_marko_deb1f930_v1,
  title = {Formal Abstractions using Interval Markov Decision Processes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/formal-abstractions-using-interval-markov-decision-processes/rdr_deb1f930193745e0a06e18c2025020f9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}