Confidence Sequences for Online Statistical Model Checking of Markov Decision Processes

Markov decision processes (MDPs) are a classic model of decision making under uncertainty, exhibiting both non-deterministic choice as well as probabilistic uncertainty. Traditionally, exact knowledge of the underlying probabilities is assumed. However, this often is unrealistic, e.g. when modelling cyber-physical systems or biological processes. Here, statistical methods provide a way towards obtaining meaningful guarantees. The classical approach is to gather samples in the MDP, use these to draw statistical conclusions about the transition probabilities, and from there obtain bounds on the true value; then, if these bounds are too broad, repeat. However, existing implementations of this approach are either subtly incorrect or sub-optimal, and quite often both. We present several confidence sequences, which are specifically designed for such enquoteonline settings, implement all of them in an efficient tool, and show their practical applicability. In particular, we show that they outperform classical enquoteunion-bound style approaches, and overall our implementation requires 50x less samples on average than previous state of the art.