Scenario-based verification of uncertain parametric MDPs

International Journal on Software Tools for Technology Transfer, vol. 24, pp. 803–819

Abstract

Abstract We consider parametric Markov decision processes (pMDPs) that are augmented with unknown probability distributions over parameter values. The problem is to compute the probability to satisfy a temporal logic specification with any concrete MDP that corresponds to a sample from these distributions. As solving this problem precisely is infeasible, we resort to sampling techniques that exploit the so-called scenario approach. Based on a finite number of samples of the parameters, the proposed method yields high-confidence bounds on the probability of satisfying the specification. The number of samples required to obtain a high confidence on these bounds is independent of the number of states and the number of random parameters. Experiments on a large set of benchmarks show that several thousand samples suffice to obtain tight and high-confidence lower and upper bounds on the satisfaction probability.

Authors 6

1. Thom Badings corresponding

   Radboud University Nijmegen

   Affiliation as printed

   Radboud University, Nijmegen, The Netherlands

2. Murat Cubuktepe

   The University of Texas at Austin

   Affiliation as printed

   The University of Texas at Austin, Austin, TX, USA

3. Nils Jansen

   Radboud University Nijmegen

   Affiliation as printed

   Radboud University, Nijmegen, The Netherlands

4. Sebastian Junges

   Radboud University Nijmegen

   Affiliation as printed

   Radboud University, Nijmegen, The Netherlands

5. Joost-Pieter Katoen Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

6. Ufuk Topcu

   The University of Texas at Austin

   Affiliation as printed

   The University of Texas at Austin, Austin, TX, USA