When designing autonomous systems—such as unmanned aerial vehicles, medical devices, or robotic explorers—we rely on mathematical models to predict how actions change the state of the world. Traditionally, these systems are modeled as Markov Decision Processes (MDPs), where transitions between states are governed by precise point probabilities. For instance, a robot executing a "move forward" action might have an exact $0.80$ probability of success and a $0.20$ probability of slipping.
However, this assumption of perfect precision is a dangerous fiction. In practice, transition probabilities are almost never known exactly. They are either estimated from finite, noisy data streams, or calculated via coarse approximations of continuous physical space. If a control policy is optimized against a single point estimate that happens to be slightly wrong, its real-world performance can degrade catastrophically.
To build truly safe autonomy, we must separate what is randomly fluctuating from what is fundamentally unknown. This distinction leads to Interval Markov Decision Processes (IMDPs), a framework that models transition probabilities as ranges rather than fixed scalars.
The Two Flavors of Uncertainty
To understand why interval-based modeling works, we must distinguish between two types of uncertainty:
- Aleatoric Uncertainty (Stochasticity): The inherent randomness of the universe. Even if you perfectly understand a die, you cannot predict the next roll. In an MDP, this is captured by the fact that transitions are probabilistic.
- Epistemic Uncertainty (Ignorance): The lack of knowledge about the system itself. This arises because we have finite data, imperfect sensors, or simplified models.
Standard MDPs compress both types of uncertainty into a single point estimate. As Olivier Buffet et al. demonstrated in Robust Planning with (L)RTDP, ignoring epistemic uncertainty makes planning fragile. If our data suggests a transition probability is $0.7$, but the true value is $0.5$, an agent relying on that point estimate might confidently choose a path that leads to failure.
An IMDP replaces the single scalar probability with an interval: $[\underline{P}, \overline{P}]$. If a robot's chance of slipping is bounded between $0.1$ and $0.3$, the IMDP explicitly preserves this entire range. This simple shift allows formal verification tools to reason over a family of possible worlds simultaneously.
Playing Against an Adversarial Nature
How do you compute an optimal plan when the exact transition probabilities are moving targets? The core mechanism relies on a game-theoretic formulation: Robust Dynamic Programming.
When evaluating a policy within an IMDP, we treat the epistemic uncertainty as an adversarial opponent, often called "Nature." Instead of calculating a standard expected value, the planning algorithm performs a min-max optimization.
- If the agent wants to maximize the probability of reaching a safe goal state, it assumes Nature will choose the lowest possible transition probability ($\underline{P}$) within the allowed interval toward that goal.
- If the agent wants to minimize the risk of entering a hazardous state, it assumes Nature will choose the highest possible transition probability ($\overline{P}$) into danger.
Standard MDP Transition:
[State S] --- Action A (P = 0.7) ---> [Safe State]
Interval MDP Transition (Worst-Case Analysis):
[State S] --- Action A (P ∈ [0.5, 0.8]) ---> [Safe State]
↑
Nature chooses the pessimistic lower bound (0.5)
By finding a policy that satisfies safety specifications under the worst possible distribution allowed by the intervals, the resulting controller is guaranteed to be safe in the real world. As explored by Marnix Suilen et al. in Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet, structuring these uncertainty sets as intervals allows algorithms to solve this min-max optimization efficiently, avoiding the computational bottlenecks of more complex geometric uncertainty sets.
Turning Data into Rigorous Bounds
For an IMDP to provide real-world safety guarantees, its intervals must be mathematically sound. If the true physical probability falls outside the interval $[\underline{P}, \overline{P}]$, the safety guarantees evaporate.
When dynamics are learned entirely from data, researchers use statistical concentration inequalities (such as Hoeffding's inequality) or the "scenario approach" to construct these intervals. This creates a Probably Approximately Correct (PAC) guarantee.
In Probabilities Are Not Enough: Formal Controller Synthesis for Stochastic Dynamical Models with Epistemic Uncertainty, Thom Badings et al. showed how to map raw noise samples directly to valid IMDP transition intervals. Instead of guessing a noise distribution (like assuming it is Gaussian), the data samples dictate the width of the intervals. The more data the system collects, the narrower the intervals become, allowing the agent to safely shed its conservatism and act more efficiently.
When the underlying physics are completely hidden, non-parametric learning methods can step in. For example, J.D. Jackson, in Safety Verification of Unknown Dynamical Systems via Gaussian Process Regression, demonstrated that Gaussian Processes can learn unknown system behaviors from noisy trajectories, translating the GP's variance directly into the upper and lower bounds of an IMDP. Similarly, Sheree-Ann Adams et al. applied convex relaxation techniques to abstract complex, black-box stochastic neural networks into verified IMDP models in Formal Control Synthesis for Stochastic Neural Network Dynamic Models.
Turning Discretization Error into an Asset
The utility of interval modeling extends beyond data collection; it also solves a fundamental computational bottleneck in formal verification known as the state-explosion problem.
Physical systems operate in continuous space (e.g., exact coordinates, velocities, temperatures). To verify them using discrete model checkers, the continuous space must be chopped up into a finite grid of cells. Transitioning from one cell to another is inherently imprecise because a robot could start at the far left edge of a cell or the far right edge, leading to different downstream outcomes.
Traditionally, researchers tried to make this discretization error vanishingly small by creating an incredibly fine grid. This causes the number of states to explode exponentially.
Interval modeling offers an elegant escape hatch. Instead of fighting discretization error, we can embrace it as a form of transition uncertainty. In Efficiency through Uncertainty: Scalable Formal Synthesis for Stochastic Hybrid Systems, Nathalie Cauchi et al. demonstrated that by treating the spatial variations within a grid cell as interval bounds, one can use a much coarser grid while still maintaining rigorous safety guarantees. The interval representation prevents discretization errors from compounding over long time horizons, allowing for scalable verification of high-dimensional systems.
The Correct-by-Construction Guarantee
Ultimately, interval-based transition modeling changes the goal of control design. Instead of finding a policy that performs well on average, it synthesizes a policy that is correct-by-construction.
As Nils Jansen detailed in Correct-by-Construction Control for Stochastic and Uncertain Dynamical Models via Formal Abstractions, this framework provides a mathematical certificate. When an autonomous agent plans using an IMDP, it can guarantee that the real-world system will satisfy its safety and performance goals with at least a specific, certified probability—fully accounting for both the randomness of its environment and the limitations of its own knowledge.
Key Foundational Work
Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes (1997) — contributed 2 concept elements to this direction.
A statistical approach to retrieval under user-dependent uncertainty in query-by-humming systems (2004) — contributed 1 concept elements to this direction.