Statistical Model Checking (SMC) is a computationally very efficient verification technique based on selective system sampling. One well identified shortcoming of SMC is that, unlike probabilistic model checking, it cannot be applied to systems featuring nondeterminism, such as Markov Decision Processes (MDP). We address this limitation by developing an algorithm that resolves nondeterminism probabilis- tically, and then uses multiple rounds of sampling and Reinforcement Learning to provably improve resolutions of nondeterminism with respect to satisfying a Bounded Linear Temporal Logic (BLTL) prop- erty. Our algorithm thus reduces an MDP to a fully probabilistic Markov chain on which SMC may be applied to give an approxi- mate solution to the problem of checking the probabilistic BLTL prop- erty. We integrate our algorithm in a parallelised modifiation of the PRISM simulation framework. Extensive validation with both new and PRISM benchmarks demonstrates that the approach scales very well in scenarios where symbolic algorithms fail to do so.

31 pages

*Also with SQIG - Instituto de Telecommunicaçôes, Department of Mathematics, IST-TU Lisbon
**Also with CENTRIA, Departamento de Informática, Universidade Nova de Lisboa

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu