An arXiv preprint extends path abstraction from reachability probabilities on discrete-time Markov chains to expected rewards on Markov reward models. Its formal framework assumes a finite, non-empty state space and uses the term Markov chain for substochastic discrete-time chains. Alongside reachability probabilities, the extension gives an abstract transition a normalized expected reward accumulated while a path passes through the chosen set of states.
The paper asks whether this extension preserves Markov reward model structure and behaves consistently when abstraction is applied in stages. Its formal results say that abstraction over any state subset produces another Markov reward model. For nested abstraction sets, applying the operation first to the smaller set and then to the larger set gives the same model as applying the larger abstraction directly.
What the abstraction retains
A Markov reward model is a Markov model whose transitions carry rewards. Path abstraction compresses the passage through a selected state set into an output transition, and for an MRM that transition carries the normalized expected reward accumulated during the passage. The reward extension therefore places expected-reward information inside the abstract transition structure.
For reachable absorbing targets, full abstraction stores two quantities on the transition from the initial state: the probability of reaching the target and the expected reward normalized by that probability. The abstract representation consequently retains both the target-reaching probability and the associated normalized reward.
The target condition is part of the result. The stated quantity concerns reachable absorbing targets, and the reward is reported in normalized form rather than as an unqualified expected-reward value for every possible outcome.
From paths to a solvable system
To define the framework, the authors use a free-monoid formulation, an algebraic way to represent the formal paths used in the model. This gives the paper a common language for describing transitions, paths and the rewards accumulated along them.
The reward calculation is expressed through expected-visiting times, which describe how often transitions are expected to be visited. The expected reward of an MRM is then represented as the sum of each transition's expected-visiting time multiplied by that transition's reward.
That representation provides the link to the numerical method. The recipe starts with the transition matrix T, subtracts it from the identity matrix, and inverts the resulting matrix to compute Q. In this form, the abstraction can be written as a system of linear equations.
The paper states that the recipe is correct because the expected-reward calculation is connected to the expected-visiting-time representation. The linear system is therefore presented as the numerical route for obtaining the abstract reward quantities defined by the construction.
A reference implementation, with engineering work ahead
The paper includes a high-level PARI/GP reference implementation for Markov reward model path abstraction. The listing extends reachability-probability abstraction to expected rewards, giving a coded version of the construction described in the paper.
The authors identify development of an efficient implementation as future work. The supplied implementation is described as high-level, while the paper's numerical recipe provides the stated linear-equation basis for the method.
The paper's stated setting
The front matter labels the manuscript as an arXiv version and supplies its publication date. The work is presented as a formal extension for finite, substochastic, discrete-time Markov models and Markov reward models.
A funding footnote reports support from the EU Horizon programme, the Interreg North Sea project STORM_SAFE and an NWO VIDI grant.
Paper data and sources
Original title: Path Abstraction for Markov Reward Models
Authors: Arnd Hartmanns, Robert Modderman
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text