Robust Model Checking with Imprecise Markov Reward Models

Alberto Termine, Alessandro Antonucci, Alessandro Facchini, Giuseppe Primiero

Abstract

In recent years probabilistic model checking has become an important area of research because of the diffusion of computational systems of stochastic nature. Despite its great success, standard probabilistic model checking suffers the limitation of requiring a sharp specification of the probabilities governing the model behaviour. The theory of imprecise probabilities offers a natural approach to overcome such limitation by a sensitivity analysis with respect to the values of these parameters. However, only extensions based on discrete-time imprecise Markov chains have been considered so far for such a robust approach to model checking. We present a further extension based on imprecise Markov reward models. In particular, we derive efficient algorithms to compute lower and upper bounds of the expected cumulative reward and probabilistic bounded rewards based on existing results for imprecise Markov chains. These ideas are tested on a real case study involving the spend-down costs of geriatric medicine departments.

Introduction

Probabilistic model checking is a powerful tool for verifying that a system—such as a communication protocol or a biological process—behaves as intended. However, standard techniques like Probabilistic Computational Tree Logic (PCTL) require exact numerical values for transition probabilities. In real-world scenarios, these values are rarely precise due to limited data, expert disagreement, or non-homogeneous processes. While Parametric Markov Chains can model this uncertainty, they are often computationally expensive, scaling exponentially with the number of states. This paper introduces IPRCTL, a new logic framework that enables robust model checking by accounting for uncertainty in system probabilities and rewards through polynomial-time algorithms.

Methodology

The authors build their framework on Imprecise Markov Reward Models (IMRMs), which extend standard Markov Reward Models using the theory of imprecise probabilities.

Illustrative state transition diagram for a Markov model.

Key components include:

  1. Imprecise Markov Chains (IMCs): Instead of a single transition matrix, an IMC uses a "credal set"—a set of possible probability distributions for each state transition.
  2. Logic Extension (IPRCTL): This new logic replaces exact probability and reward operators with lower ($\underline{P}, \underline{E}$) and upper ($\overline{P}, \overline{E}$) bounds.
  3. Recursive Algorithms: The core technical contribution is a set of recursive algorithms used to compute expected cumulative rewards and bounded-reward probabilities. At each step, the algorithm solves a local linear programming task to find the "worst-case" or "best-case" probability within the allowed ranges.

Key Insights and Results

A major advantage of this approach is complexity parity: shifting from precise to imprecise probabilities does not increase the overall computational complexity class. The algorithms remain polynomial relative to the number of states, making them significantly more practical than parametric approaches.

Convergence of upper and lower bounds for hitting probabilities.

The framework naturally performs sensitivity analysis. If the upper bound of a failure probability is below a safety threshold, the system is proven robust against any probability fluctuations within the specified ranges. The authors demonstrated this with a geriatric medicine case study, modeling patient transitions between care states. They calculated expected annual costs and verified that hospital departments remained sustainable even under pessimistic probability scenarios. Furthermore, they showed that for long-term horizons, the upper and lower bounds of hitting probabilities converge, providing a stable long-term outlook for the system.

Limitations and Future Work

While the algorithms are polynomial relative to the number of states, complexity remains exponential relative to the nesting depth of logic formulas. However, in practice, nesting depths are typically small. Future work includes extending this framework to Imprecise Markov Decision Processes (IMDPs), where agents make choices, and to continuous-time models for more high-fidelity physical and biological simulations.

Summary updated

Abstract

In recent years probabilistic model checking has become an important area of research because of the diffusion of computational systems of stochastic nature. Despite its great success, standard probabilistic model checking suffers the limitation of requiring a sharp specification of the probabilities governing the model behaviour. The theory of imprecise probabilities offers a natural approach to overcome such limitation by a sensitivity analysis with respect to the values of these parameters. However, only extensions based on discrete-time imprecise Markov chains have been considered so far for such a robust approach to model checking. We present a further extension based on imprecise Markov reward models. In particular, we derive efficient algorithms to compute lower and upper bounds of the expected cumulative reward and probabilistic bounded rewards based on existing results for imprecise Markov chains. These ideas are tested on a real case study involving the spend-down costs of geriatric medicine departments.
BibTeX
@inproceedings{termine2021robust,
  author = {Alberto Termine and Alessandro Antonucci and Alessandro Facchini and Giuseppe Primiero},
  title = {{Robust Model Checking with Imprecise Markov Reward Models}},
  booktitle = {ISIPTA},
  year = {2021},
  url = {https://openreview.net/forum?id=A3J3QwGhFX},
}
Figure