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:
- 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).
- 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:
- Neural Network Dynamics: Sheree-Ann Adams and Luca Laurenti have shown that even "black-box" neural network models can be converted into IMDPs using convex relaxation, allowing for formal control synthesis of deep learning-based controllers (Formal Control Synthesis for Stochastic Neural Network Dynamic Models).
- Continuous Action Spaces: Traditional IMDPs often require discretizing actions (e.g., "turn left 5 degrees"). Giannis Delimpaltadakis and Morteza Lahijanian introduced Continuous-Action IMDPs (caIMDPs), which solve the max-min optimization problem directly over continuous ranges, improving both accuracy and speed (Interval Markov Decision Processes with Continuous Action-Spaces).
- Tighter Bounds: To reduce the conservatism of intervals, Ibon Gracia and Morteza Lahijanian proposed Multi-Interval MDPs, which bound transitions to clusters of states, capturing more precise information about the system's flow (Beyond Interval MDPs: Tight and Efficient Abstractions of Stochastic Systems).
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.