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

Standard probabilistic model checking tools, such as PCTL, are powerful for verifying whether a system meets specific requirements—for instance, ensuring the probability of a system crash remains below a critical threshold. However, these models typically require exact, "sharp" probability values for every transition. In real-world applications, such as computational biology or hospital management, data is often uncertain, non-homogeneous, or incomplete. While Parametric Markov Chains can address uncertainty, they are often computationally prohibitive. This research introduces a robust and efficient alternative using Imprecise Markov Reward Models (IMRMs).

Methodology: IPRCTL and Imprecise Probabilities

The core contribution of this work is a new logical language: IPRCTL (Imprecise Probabilistic Reward Computational Tree Logic). This framework leverages the theory of imprecise probabilities, replacing single probability distributions with "credal sets"—collections of possible distributions often represented as intervals.

A simple Markov model illustrating state transitions and probabilities.

Key technical components include:

  • Non-linear Transition Operators: Standard linear operators are extended to non-linear versions to calculate "best-case" (upper) and "worst-case" (lower) bounds for system properties.
  • Recursive Algorithms: The authors derived efficient schemes to compute lower and upper hitting probabilities, expected cumulative rewards, and reward-bounded probabilities.
  • Computational Efficiency: Crucially, the transition from precise to imprecise probabilities does not increase the complexity class; the algorithms remain polynomial relative to the number of states and time steps.

Case Study and Key Results

The framework was evaluated using a real-world case study of geriatric medicine departments, tracking patients through states such as Acute Care, Long Stay, and Discharge/Death. Daily costs and transition rates were treated as intervals to account for variance across different hospital departments.

Lower and upper hitting probabilities for the 'lost' state over short and long time horizons.

Key findings include:

  • Hospital Sustainability: The authors verified department sustainability, defined by a total cumulative cost per patient under £15,000 per year. For one department, the expected yearly cost was bounded between £2,910 and £6,421, allowing for a robust pass/fail grade on budget requirements.
  • Sensitivity Analysis: The researchers visualized how "hitting probability ranges" (e.g., the likelihood of a message being lost) evolve as uncertainty ((\epsilon)) increases, providing a clear picture of system robustness over time.
  • Robustness via Intervals: By ensuring requirements hold across an entire range of possible probabilities, engineers can achieve significantly higher confidence in system safety and efficiency.

Limitations and Future Directions

While promising, the current work is limited to discrete-time models. Many physical systems operate in continuous time, representing a necessary next step for this research. Additionally, while state-space complexity is polynomial, complexity still grows exponentially with the nesting depth of logical formulas. Future efforts will also aim to extend this framework to Imprecise Markov Decision Processes (MDPs) to support robust decision-making and strategy optimization under uncertainty.

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