💻 computer science

Compositional Reasoning for Probabilistic Automata with Uncertainty

This paper establishes a comprehensive assume-guarantee framework for the compositional verification of probabilistic automata with uncertain transition probabilities, covering both parametric models and robust interval-based models through diverse proof rules, monotonicity analysis, and simulation relations.

Original authors: Hannah Mertens, Tim Quatmann, Joost-Pieter Katoen

Published 2026-04-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Hannah Mertens, Tim Quatmann, Joost-Pieter Katoen

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

Imagine you are the chief engineer of a massive, complex city. This city is made of thousands of independent parts: traffic lights, power grids, water pumps, and communication towers. Each part works on its own, but they all have to talk to each other to keep the city running.

Now, imagine you want to check if the city is safe. Will the lights stay green long enough? Will the power grid survive a storm?

The Problem: The "State-Space Explosion"
If you try to check the safety of the entire city at once, your computer will explode. Why? Because the number of possible scenarios grows exponentially. If you have 100 parts, and each has just 2 states (on/off), you have $2^{100}$ scenarios. That's more than the number of atoms in the universe. Checking them one by one is impossible.

The Solution: "Assume-Guarantee" Reasoning
Instead of checking the whole city, you check each part individually. You use a clever trick called Assume-Guarantee (AG) reasoning.

Think of it like a contract between neighbors:

The Assumption: "I promise to behave nicely if you promise to behave nicely."
The Guarantee: "If you keep your promise, I guarantee the street will be safe."

If Neighbor A guarantees they won't block the road assuming Neighbor B doesn't block the road, and Neighbor B guarantees the same, then the whole street is safe. You don't need to simulate every car in the city; you just check the contracts.

The Twist: Uncertainty
In the real world, things aren't perfect. We don't know the exact numbers.

Scenario A (Parametric): We know the traffic light is fast, but we don't know exactly how fast. It might be 2 seconds, or 2.5 seconds. Let's call this unknown speed "Parameter $p$ ."
Scenario B (Robust): We don't even know the range. We just know the traffic light is "somewhere between slow and fast," and the environment (Nature) might pick the worst possible speed at any moment to cause a crash.

This paper is about creating new contracts that work even when we don't know the exact numbers.

Part 1: The "Parametric" City (pPAs)

The Metaphor: The Recipe Book

Imagine a baker making bread. The recipe says: "Add $p$ cups of flour."

If $p=2$ , the bread is good.
If $p=5$ , the bread is a rock.

The baker doesn't know the exact value of $p$ yet. They just know it's a number. The paper creates a way to verify the bread is good for all possible values of $p$ without baking every single loaf.

What the paper does:

Lifting the Rules: It takes the old "Assume-Guarantee" rules (which worked for fixed numbers) and upgrades them to handle these "recipe variables."
Monotonicity (The "More is Better" Rule): Sometimes, you just want to know: "If I add more flour, does the bread get worse?" The paper creates a rule to check this. If the individual parts of the bread get worse when you add flour, the whole loaf will too. You don't need to bake the whole thing to know this; you just check the ingredients.
Simulation (The "Imposter" Test): Imagine you have a cheap toy car and a real Ferrari. If the toy car can mimic every move the Ferrari makes (even if it's slower), then the toy car is "safe" in the same way. The paper creates a way to check if one uncertain system can "mimic" another, ensuring safety without doing the heavy math.

Part 2: The "Robust" City (rPAs)

The Metaphor: The Adversarial Game

Now, imagine the city is being attacked by a "Gremlin" (Nature). The Gremlin doesn't just pick a random number; it actively tries to break the system.

Memoryless Gremlin: The Gremlin picks a bad setting once and sticks with it.
Memory-Full Gremlin: The Gremlin watches what you do and changes its strategy every second to cause the most chaos.

The Paper's Findings:
The authors tried to apply the "Assume-Guarantee" contracts to this Gremlin scenario.

The Bad News: The old contracts fail if the Gremlin is "Memoryless" (because the Gremlin can pick different bad settings for different parts of the city that look the same to the contract) or if the uncertainty is "Non-Convex" (too weird and jagged).
The Good News: If the Gremlin is "Memory-Full" (smart and adaptive) and the uncertainty is "Convex" (smooth and predictable), the contracts work, but only if you use a special "Convex Composition" tool. Think of this tool as a safety net that catches all the weird combinations the Gremlin might try.

Part 3: The "Interval" City (iPAs)

The Metaphor: The Ruler

Sometimes, we just know a number is between 0 and 10. We use a ruler.

The Trap: When you combine two rulers, the math gets messy. If you try to use a "relaxed" ruler (one that ignores the connection between the two numbers), the contracts break. The paper proves that you can't just use the easy math shortcuts here; you have to be precise, or the safety guarantee disappears.

Summary: Why Should You Care?

This paper is a toolkit for building trust in uncertain systems.

It saves time: Instead of checking a billion scenarios, you check a few small contracts.
It handles the unknown: It works even when you don't know the exact numbers (parameters) or when an enemy is trying to break your system (robustness).
It tells you when to stop: It clearly explains when these shortcuts fail (e.g., with certain types of greedy enemies or weird math), so engineers don't accidentally build unsafe bridges or self-driving cars.

In a nutshell:
If you have a giant, messy, uncertain machine, this paper gives you a way to prove it's safe by checking the small pieces and their contracts, rather than trying to simulate the whole mess at once. It's like verifying a massive puzzle by checking that every corner piece fits, rather than trying to assemble the whole thing in your head.

1. Problem Statement

The verification of complex probabilistic systems often suffers from the state-space explosion problem, where the number of states grows exponentially with the number of components. While Assume-Guarantee (AG) reasoning has been successfully applied to standard Probabilistic Automata (PAs) to decompose verification tasks, existing frameworks struggle with systems containing uncertain transition probabilities.

The paper addresses the gap in compositional verification for two specific extensions of PAs:

Parametric Probabilistic Automata (pPAs): Systems where transition probabilities are defined by polynomial functions over a set of real-valued parameters. Uncertainty is resolved globally by a single valuation.
Robust Probabilistic Automata (rPAs): Systems where transition probabilities are replaced by uncertainty sets (e.g., intervals or convex sets). Uncertainty is resolved locally by a "nature" player at each step, which can be memoryless (once-and-for-all) or memory-full (history-dependent).

The core challenge is to determine whether AG reasoning rules, which work for standard PAs, can be lifted to these uncertain models while maintaining soundness and completeness, particularly given the complexities of parameter dependencies and the non-probabilistic nature of "nature" in rPAs.

2. Methodology

The authors develop a comprehensive framework for compositional verification by extending the AG framework of Kwiatkowska et al. [KNPQ13] and simulation-based approaches [KPC12].

A. Strategy Projections and Parallel Composition

Strategy Projections: A critical technical contribution is the formalization of strategy projections for pPAs. The authors define how a strategy on a composed system ( $M_1 \parallel M_2$ ) projects onto individual components. They introduce a definition based on conditional probabilities, ensuring that the projected strategy correctly relates the probability measures of the composite system to its components.
Parallel Composition: They define parallel composition for pPAs (synchronizing on shared labels) and rPAs. Crucially, they analyze how uncertainty sets behave under composition.

B. Assume-Guarantee (AG) Rules for pPAs

Lifting AG Rules: The authors generalize asymmetric and circular AG proof rules to the parametric setting. These rules allow verifying multi-objective queries (probabilistic reachability, expected rewards, and their combinations) by checking properties on individual components under assumptions.
Monotonicity: They introduce a novel AG rule specifically for parameter monotonicity. This allows inferring that a property is monotonic with respect to a parameter in the composite system based solely on the monotonicity of that parameter in the individual components. This is significant for optimizing parameter synthesis.
Simulation-Based AG: As an alternative to property-based reasoning, they lift strong simulation and introduce robust-strong simulation relations for pPAs. This approach treats assumptions and guarantees as automata rather than logical formulas, offering completeness properties.

C. AG Rules for rPAs

The paper rigorously investigates the applicability of AG rules to rPAs under different semantic assumptions:

Negative Results: The authors prove that standard AG rules (specifically the asymmetric rule) are unsound for:
- rPAs with memoryless nature (even for convex/polytopic sets), because a memoryless nature in a component cannot capture the distinct behaviors required by the composed system's state-action pairs.
- rPAs with non-convex uncertainty sets, due to the inability to project nature choices effectively.
- rPAs using interval-arithmetic relaxation ( $\parallel_{iRel}$ ), which introduces spurious distributions that break the compositional link.
Positive Results: Sound AG rules are recovered for convex rPAs with memory-full (history-dependent) nature.
- PA-Reduction: They establish a reduction from convex rPAs to (possibly uncountably branching) standard PAs by lifting nature choices to strategy choices.
- Convex Parallel Composition ( $\parallel_{conv}$ ): Since standard parallel composition does not preserve convexity, they introduce a convexity-preserving operator that over-approximates the standard composition. This allows the application of AG rules derived from the PA reduction.

3. Key Contributions

First Framework for Parametric/Robust AG: The paper provides the first compositional reasoning framework for pPAs and rPAs, extending the foundational work on standard PAs.
Formalization of Strategy Projections: A refined definition of strategy projections for parametric models, essential for linking composite measures to component measures.
Monotonicity Rules: New proof rules enabling compositional reasoning about parameter monotonicity, a key property for efficient parameter synthesis.
Soundness Analysis for rPAs: A definitive characterization of when AG reasoning works for robust models:
- Works: Convex rPAs with memory-full nature (via $\parallel_{conv}$ ).
- Fails: Memoryless nature, non-convex sets, and interval-arithmetic relaxations.
Simulation-Based Approach: The introduction of robust-strong simulation for pPAs, providing a sound and complete AG framework based on automata conformance rather than property satisfaction.

4. Key Results

pPAs: The asymmetric and circular AG rules are sound and complete for safety, $\omega$ -regular, and expected reward properties. The monotonicity rule allows deriving global monotonicity from local component properties.
rPAs:
- The standard asymmetric AG rule fails for memoryless nature and non-convex sets. Counterexamples are provided showing that the composed system can violate guarantees even if components satisfy assumptions.
- For convex rPAs with memory-full nature, the authors prove that the system is equivalent to a standard PA under a specific reduction. Consequently, AG rules hold if the convex parallel composition ( $\parallel_{conv}$ ) is used.
Simulation: Strong and robust-strong simulation relations are proven to be preorders and compositional, enabling a complete simulation-based AG framework for pPAs.

5. Significance

This work lays the theoretical foundation for the modular verification of complex uncertain systems.

Scalability: By enabling compositional reasoning, it offers a pathway to verify systems that are too large for monolithic model checking, particularly those with parametric uncertainties (e.g., sensor noise, network conditions).
Robustness: It clarifies the limits of robust verification, warning practitioners that standard compositional techniques may fail for memoryless nature or non-convex uncertainties, guiding the design of correct verification tools.
Efficiency: The monotonicity rules provide a mechanism to speed up parameter synthesis by avoiding global searches when local monotonicity can be established.
Unification: It unifies the treatment of parametric and robust models under a single AG framework, bridging the gap between parametric MDPs and robust MDPs in a compositional setting.

In summary, the paper successfully extends the powerful paradigm of assume-guarantee reasoning to the challenging domain of uncertain probabilistic automata, providing both positive results for specific subclasses (parametric and convex robust) and necessary negative results that define the boundaries of compositional verification in this domain.