Computer Science Department
School of Computer Science, Carnegie Mellon University


Statistical Model Checking for
Markov Decision Processes

David Henriques*, Joâo Martins**, Paolo Zuliani,
André Platzer, Edmund M. Clarke

May 2012


This technical report is a more detailed version of a published paper:
"Statistical model checking for Markov decision processes",
QEST, IEEE Computer Society, 2012

Keywords: Statistical Model Checking, Markov Decision Processes, Reinforcement Learning

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