💻 computer science

Path Abstraction for Markov Reward Models

This paper extends the path abstraction technique from reachability probabilities in discrete-time Markov chains to expected rewards in Markov reward models, proving that it preserves model structure and monotonicity while providing a numerical method for its computation based on expected visiting times.

Original authors: Arnd Hartmanns, Robert Modderman

Published 2026-08-27

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Arnd Hartmanns, Robert Modderman

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

In the world of computer science, there is a field dedicated to understanding systems that behave with a degree of randomness. Think of a network of computers sending messages, a robot navigating a room with slippery floors, or a communication protocol that might drop a packet by chance. These are not deterministic machines where one input always leads to one specific output; instead, they are governed by probabilities. To ensure these systems are safe and efficient, researchers use a method called probabilistic model checking. This process involves building a mathematical map of every possible way the system can move from one state to another, then calculating the likelihood of reaching a desired goal or the average cost of getting there. The goal might be to reach a destination, while the cost could be time, energy, or the number of messages sent.

However, these maps can become impossibly large. A system with just a few dozen components can generate more possible paths than there are atoms in the universe, making it impossible to check every single one. To solve this, researchers use a technique called path abstraction. Imagine you are looking at a complex road map and want to understand the journey between two cities without worrying about every single side street in the middle. Path abstraction allows you to collapse a whole neighborhood of intermediate stops into a single, direct connection, summarizing the probability of getting through and the average cost of the trip. This simplifies the map, making it possible to analyze systems that would otherwise be too big to handle.

A team of researchers at the University of Twente in the Netherlands has taken this technique a significant step further. While path abstraction was already known to work well for calculating simple probabilities—like the chance of reaching a goal—it had not been successfully adapted to calculate expected rewards, which are more complex measures of cost or performance. In their new work, the authors have extended the method to handle these rewards, proving that the technique remains mathematically sound and reliable even when summarizing the "cost" of a journey, not just the likelihood of it happening.

The researchers focused on a specific type of system called a Markov reward model. In these models, every step a system takes carries a numerical value, representing a reward or a cost. For instance, a robot might gain a reward for moving forward but lose energy with every step. The goal is to find the total expected reward accumulated before the system reaches a final state. The challenge is that when you simplify a system by removing intermediate states, you cannot just guess the new cost of the shortcut. You must calculate the precise average cost of all the different ways the system could have traveled through the removed section, weighted by how likely each path was.

The team proved that their new method correctly performs this calculation. They demonstrated that if you take a complex model, remove a specific group of states, and replace them with a single summarized transition, the resulting smaller model preserves the exact same expected rewards as the original. This is a crucial finding because it means engineers can now break down massive, complicated systems into smaller, manageable pieces, solve the math for each piece, and stitch the results together without losing accuracy. They showed that this process is "monotonically absorbing," a technical way of saying that the order in which you simplify the system does not matter. Whether you remove one group of states first and then another, or remove them all at once, the final result is identical. This flexibility is vital for building tools that can automatically simplify models in the most efficient way possible.

To make this theory useful in practice, the researchers developed a concrete set of instructions for computing these abstractions. They translated the abstract mathematical concepts into a method that relies on solving systems of linear equations, a standard and powerful tool in mathematics. They also provided a working computer program, written in a specialized algebra system, that anyone can use to perform these calculations. This program takes a detailed model and a chosen set of states to remove, then outputs a simplified model with the correct probabilities and rewards. By connecting the concept of expected rewards to the concept of how often a system visits certain transitions, they were able to prove that their numerical recipe produces the exact same results as the theoretical definition.

The significance of this work lies in its ability to make the verification of complex, random systems more feasible. By allowing researchers to summarize parts of a system while keeping the cost calculations accurate, they open the door to analyzing larger and more realistic models of technology. This could lead to more reliable communication networks, safer autonomous vehicles, and more efficient energy management systems. The researchers have not just proposed a new idea; they have provided the mathematical proof that it works and the practical tools to use it. Their work ensures that when we simplify a complex world to understand it, we do not lose the truth of how much it truly costs to get where we are going.

Technical Summary: Path Abstraction for Markov Reward Models

Problem Statement
Probabilistic model checking (PMC) verifies quantitative properties of stochastic systems, such as discrete-time Markov chains (DTMCs) and Markov reward models (MRMs). A central challenge in PMC is the state-space explosion problem. While techniques like state elimination can solve DTMCs locally, they often increase the number of transitions, potentially worsening complexity. Path abstraction, introduced by Ábrahám et al. [1], offers an alternative by summarizing the probabilities of paths through a subset of states onto new transitions of a smaller chain. However, prior work on path abstraction was confined to unbounded reachability probabilities on DTMCs. It lacked formal proofs regarding its correctness when applied to expected rewards (ERs) on MRMs, and the property of "monotonic absorption" (where abstracting over a subset then a superset yields the same result as abstracting over the superset directly) remained unproven for the reward setting.

Methodology
The authors extend the path abstraction technique from reachability probabilities to expected rewards on MRMs. A core methodological innovation is the adoption of a "free monoid view" of Markov chains throughout the paper. Instead of the classical automata-based definition where transitions are pairs of states, the authors define Markov chains and MRMs over the free monoid $S^*$ of the state space $S$ .

Free Monoid View: Probabilities and rewards are defined on sequences of states (words). The transition probability function $P: S^+ \to [0, 1]$ satisfies $P(xsy) = P(xs)P(sy)$, and the reward function $R: S^+ \to \mathbb{R}$ satisfies $R(xsy) = R(xs) + R(sy)$. This perspective simplifies definitions and proofs.
Abstraction Mechanism: Given a set of states $A$ $A$ , the abstraction $abstr(A, M)$ removes internal transitions within $A$ $A$ (except those involving input states) and replaces them with new transitions connecting input states to output states.
- For probabilities, the new transition probability is the sum of probabilities of all paths through $A$ reduced by the operator $red(A)$, which collapses maximal factors of $A$ into single letters.
- For rewards, the new transition reward is the normalized expected reward of passing through $A$ . Specifically, it is the sum of (probability $\times$ reward) for all paths through $A$ , divided by the total probability of those paths. This normalization is crucial for preserving the additive structure of rewards in the abstracted model.
Numerical Recipe: To compute the abstracted rewards without enumerating infinite paths, the authors derive a method based on Expected Visiting Times (EVTs). They establish that the expected reward of an MRM equals the sum of each transition's EVT multiplied by its reward. The computation is reduced to solving a system of linear equations involving the matrix of transition probabilities within the abstraction set.

Key Contributions

Extension to MRMs: The paper formally extends path abstraction from DTMCs (reachability) to MRMs (expected rewards). It defines the abstraction operator for MRMs and proves that the result is a valid MRM (Theorem 3).
Monotonic Absorption: The authors prove that path abstraction for MRMs satisfies the monotonic absorption property (Theorem 4). That is, $abstr(B, abstr(A, M)) = abstr(B, M)$ for $A \subseteq B$ . This property is essential for iterative counterexample refinement strategies.
Numerical Recipe and Implementation: A concrete algorithm is provided to compute the path abstraction of an MRM by solving linear equation systems. The authors provide a high-level reference implementation in the computer algebra system PARI/GP (Listing 1), which computes the new reward values using matrix operations derived from the EVT connection.
Theoretical Proofs: Using the free monoid framework, the paper provides rigorous proofs for the well-definedness of the abstraction and the preservation of the MRM structure and expected reward properties.

Results

Correctness: The paper demonstrates that the abstracted MRM preserves the total expected accumulated reward to reach goal states. If an MRM is fully abstracted (over all non-absorbing states), the resulting model directly encodes the reachability probabilities and expected rewards of the original model as transition probabilities and rewards.
Counterexample Refinement: The authors illustrate that the technique enables counterexample refinement. By abstracting subsets of states, one can identify "bad" paths in a smaller model that violate a specification (e.g., $ER > 10$ ). Since the abstraction preserves total expected rewards, a violation in the abstract model implies a violation in the original model.
Computational Efficiency: The numerical recipe reduces the problem of abstracting a complex MRM to solving a single linear system (inverting $I - T$ , where $T$ is the transition matrix of the abstraction set). This allows for exact solutions even for large systems, provided the abstraction set is small.

Significance
The paper claims significance primarily in bridging a gap in probabilistic model checking theory. While path abstraction was known for reachability, its application to rewards was unproven and lacked a formal framework. By introducing the free monoid view and proving monotonic absorption for MRMs, the authors enable the use of path abstraction for a broader class of quantitative properties. This facilitates more efficient model checking and debugging of systems where energy consumption, message counts, or termination times are critical. The provided PARI/GP implementation serves as a reference for verifying the correctness of the theoretical derivation and offers a starting point for future tool development, such as integration into the Modest Toolset or standalone tools for counterexample-guided abstraction refinement.

More like this