⚡ electrical engineering

On the Optimality of Uncertain MDP Abstractions

This paper establishes that abstraction-based control synthesis for uncertain MDPs of nonlinear stochastic systems achieves asymptotic optimality and completeness if the abstraction satisfies a "vanishing ambiguity" condition, a property met by set-valued MDPs but not by interval MDPs.

Original authors: Ibon Gracia, Morteza Lahijanian

Published 2026-04-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ibon Gracia, Morteza Lahijanian

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Navigating a Foggy City

Imagine you are trying to drive a car through a complex, foggy city to reach a specific destination (like a charging station) while avoiding potholes and obstacles. You have a map, but the map is blurry. You don't know exactly where the car will end up after you turn the steering wheel because of the fog (uncertainty) and the slippery roads (random disturbances).

In the world of robotics and AI, this is a Stochastic System. The goal is to write a "controller" (a set of rules for the driver) that guarantees you will reach the goal safely, even in the worst-case fog.

The Problem: The "Blurry Map" Approach

To solve this, engineers use a trick called Abstraction. Instead of trying to calculate every possible position on the continuous road (which is impossible), they divide the city into a grid of square blocks (like a chessboard). They pretend the car is always in the center of a block.

This turns the complex, blurry problem into a simpler one called a UMDP (Uncertain Markov Decision Process). However, because the map is blurry, the transitions between blocks are uncertain.

Example: If you drive North from Block A, you might end up in Block B, or maybe Block C, or maybe you hit a wall. The "Uncertainty" is the range of possibilities.

The paper asks a critical question: "If we make the grid blocks smaller and smaller (refining the map), will our solution eventually become perfect?"

The Two Types of Maps (The Core Discovery)

The authors discovered that not all ways of making these "blurry maps" are created equal. They compared two specific methods:

1. The "Set-Valued" Map (SMDP) – The Smart Detective

Imagine a detective who says: "If you drive North from here, you will definitely end up somewhere inside this specific cluster of blocks."

How it works: It groups all possible outcomes into a "cluster" and acknowledges that the car could be anywhere inside that cluster, but it knows exactly which cluster it is.
The Result: As the detective makes the clusters smaller and smaller, their guess gets closer and closer to the truth. Eventually, the error disappears. This method is Asymptotically Optimal. It guarantees that if you keep refining the map, you will get the perfect driving plan.

2. The "Interval" Map (IMDP) – The Guessing Game

Imagine a different detective who says: "If you drive North, there is a 0% to 100% chance you end up in Block B, and a 0% to 100% chance you end up in Block C."

How it works: This method uses "intervals" (ranges) for probabilities. It's very conservative. It assumes the worst-case scenario for every single possibility.
The Result: The authors found a nasty flaw. Even if you make the blocks tiny, this detective's guess never gets better. The uncertainty remains stuck at "0% to 100%." It's like trying to solve a puzzle where the pieces are glued together; no matter how hard you squint, you can't see the picture. This method is NOT asymptotically optimal.

The "Vanishing Ambiguity" Secret

The paper introduces a concept called "Vanishing Ambiguity."

Think of "Ambiguity" as the size of the "fog" in your map.

In the Smart Detective (SMDP) method, as you zoom in (refine the grid), the fog shrinks until it disappears completely. The map becomes crystal clear.
In the Guessing Game (IMDP) method, the fog stays thick no matter how much you zoom in. The "Ambiguity" does not vanish.

The authors prove mathematically that if the ambiguity vanishes, the solution becomes perfect. If it doesn't vanish, you are stuck with a bad solution forever.

The Algorithm: The "Refinement Loop"

The paper proposes a step-by-step recipe (Algorithm 1) to find the best driving plan:

Start Simple: Draw a coarse grid (big blocks).
Calculate: Figure out the best driving strategy and the safety bounds (e.g., "You have a 60% to 90% chance of success").
Check the Gap: Is the difference between the best and worst case (60% vs 90%) too big?
- Yes: Make the grid finer (smaller blocks) and go back to step 2.
- No: Stop! You have a good enough plan.
The Catch: This loop only works if you use the Smart Detective (SMDP) method. If you use the Guessing Game (IMDP), the loop will run forever because the gap (the error) will never shrink to zero.

Real-World Tests

The authors tested this on two scenarios:

Temperature Control: Keeping a room at a perfect temperature.
A Self-Driving Cart: A robot moving through an office with obstacles, water puddles, and carpets.

The Results:

The SMDP method quickly found a tight, accurate solution. The "gap" between the best and worst case shrank to almost zero in just a few steps.
The IMDP method got stuck. No matter how many times they refined the map, the safety bounds remained useless (e.g., "You have a 0% to 100% chance of success"). It was like a broken thermometer that always reads "somewhere between freezing and boiling."

The Takeaway

If you are building a robot or a safety-critical system (like an autonomous car or a medical device) and you need to prove it will work:

Don't just refine your grid. You must also choose the right type of abstraction.
Use "Set-Valued" methods (SMDP). They are the only ones guaranteed to get you the perfect answer if you keep trying.
Avoid "Interval" methods (IMDP) for complex, non-linear systems, because they might trap you in a loop of uncertainty that never resolves.

In short: Refining a blurry map only helps if the blurriness actually goes away. Some maps just get sharper but stay blurry forever.

1. Problem Statement

The paper addresses the challenge of formal control synthesis for nonlinear stochastic systems subject to temporal logic specifications (specifically Linear Temporal Logic over finite traces, LTLf).

Context: Safety-critical cyber-physical systems require formal guarantees. Abstraction-based methods model continuous systems as finite-state Uncertain Markov Decision Processes (UMDPs) to compute probability bounds for satisfying specifications.
The Gap: While existing methods provide sound (conservative) bounds, they often lack asymptotic optimality. This means that refining the abstraction (making the discretization finer) does not necessarily converge to the true optimal satisfaction probability or zero error bounds. In some cases, finer discretizations can even degrade the bounds.
Core Question: Under what conditions do UMDP abstraction-based methods guarantee asymptotic optimality and algorithmic completeness (termination in finite time for a desired $\epsilon$ -optimality)?

2. Methodology

The authors propose a general framework for abstraction-refinement and introduce a specific condition to guarantee convergence.

A. System and Problem Formulation

System: Discrete-time stochastic systems $x_{t+1} = f(x_t, u_t, w_t)$ with nonlinear dynamics and bounded disturbances.
Specification: LTLf formulas (e.g., $\square p_{safe} \land \phi$ ) requiring the system to stay safe while satisfying temporal goals.
Goal: Synthesize a controller $\kappa_\epsilon$ that achieves a satisfaction probability within $\epsilon$ of the optimal probability $Pr^*$ , with tight upper and lower bounds.

B. Abstraction Framework

The approach uses an iterative Abstraction-Refinement loop:

Partitioning: The state space is partitioned into regions.
Abstraction: The continuous system is abstracted into a UMDP where transitions are represented by sets of probability distributions (ambiguity sets) rather than single probabilities.
Synthesis: A controller is synthesized using Robust Dynamic Programming (RDP) on the product of the UMDP and a Deterministic Finite Automaton (DFA) representing the LTLf formula.
Refinement: If the gap between the lower and upper probability bounds exceeds $\epsilon$ , the partition is refined, and the process repeats.

C. Key Theoretical Concept: "Vanishing Ambiguity"

The central theoretical contribution is the definition of Ambiguity Diameter ( $\phi(U_\eta)$ ), which measures the maximum Wasserstein distance between any two probability distributions in the ambiguity sets of the UMDP.

The authors prove that Vanishing Ambiguity is a sufficient condition for asymptotic optimality:
$\lim_{\eta \to 0} \phi(\text{Abs}_U(S, \eta)) = 0$
If the ambiguity diameter vanishes as the partition size $\eta$ approaches zero, the abstraction procedure is guaranteed to be asymptotically optimal.

3. Key Contributions

Sufficient Condition for Asymptotic Optimality:
The paper derives a rigorous sufficient condition (vanishing ambiguity) that guarantees an abstraction procedure will converge to the true optimal satisfaction probability as the discretization becomes infinitely fine. This resolves the open question of when refinement leads to optimal results.
Comparative Analysis of Abstraction Classes:
The authors apply their condition to two common abstraction classes:
- Set-valued MDPs (SMDPs): They prove that SMDP abstractions (which use reachable sets to define clusters of states) satisfy the vanishing ambiguity condition. Thus, SMDPs are asymptotically optimal.
- Interval MDPs (IMDPs): They demonstrate via counterexample that standard IMDP abstractions (which use interval bounds on transition probabilities) do not satisfy the vanishing ambiguity condition for general nonlinear dynamics. Consequently, IMDPs are not guaranteed to be asymptotically optimal; refinement may fail to tighten bounds.
Complete Algorithm for $\epsilon$ -Optimal Control:
The paper presents Algorithm 1, an abstraction-refinement algorithm that synthesizes an $\epsilon$ -optimal controller.
- Completeness: If the underlying abstraction procedure satisfies the vanishing ambiguity condition, the algorithm is proven to terminate in finite time for any $\epsilon > 0$ .
- Optimality: The synthesized controller guarantees that the satisfaction probability is within $\epsilon$ of the true optimum.

4. Results and Empirical Validation

The theoretical findings were validated through two case studies:

1D Temperature Regulation (Reach-Avoid):
- SMDP: The gap between upper and lower bounds converged to zero as iterations increased (8 iterations reduced error to <2%).
- IMDP: The gap did not shrink with refinement. The bounds remained loose (vacuous), failing to converge to the true probability.
2D Nonlinear Cart (LTLf Specification):
- The task involved navigating a cart with obstacles, water, and a carpet while satisfying complex temporal logic.
- SMDP: Produced tight, meaningful probability bounds that improved with refinement.
- IMDP: Produced vacuous bounds (effectively $[0, 1]$ ) over large portions of the state space, which did not improve even with finer discretization.

5. Significance

Theoretical Foundation: This work establishes the first general theory for the asymptotic optimality of UMDP abstractions under temporal logic specifications. It clarifies why some abstraction methods work while others fail to converge.
Practical Guidance: It provides a clear directive for practitioners: avoid standard IMDP abstractions for general nonlinear systems if asymptotic optimality is required. Instead, SMDP abstractions (or methods ensuring vanishing ambiguity) should be used.
Algorithmic Completeness: The paper proves that with the correct abstraction class, formal verification and control synthesis can be automated to a desired precision ( $\epsilon$ ) in finite time, a crucial requirement for deploying safety-critical autonomous systems.
Robustness: The approach handles general nonlinear vector fields and general disturbance distributions, moving beyond the restrictive assumptions (e.g., linear dynamics, Gaussian noise) of previous works.

In summary, the paper identifies vanishing ambiguity as the critical property for successful abstraction-based control, proves that SMDPs possess this property while IMDPs do not, and provides a complete algorithm to synthesize near-optimal controllers for complex stochastic systems.