Search papers, labs, and topics across Lattice.
This paper introduces confidence sequences tailored for online statistical model checking of Markov Decision Processes (MDPs), addressing the limitations of traditional methods that rely on exact probability knowledge. By developing a new framework that efficiently gathers samples and provides tighter bounds on transition probabilities, the authors demonstrate a significant improvement in sample efficiency, requiring 50 times fewer samples than existing approaches. The results highlight the practical applicability of these confidence sequences, making them a valuable tool for decision-making in uncertain environments like cyber-physical systems and biological processes.
Confidence sequences can cut sample requirements by 50x in online statistical model checking of MDPs, transforming how we approach uncertainty in decision-making.
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 \emph{confidence sequences}, which are specifically designed for such \enquote{online} settings, implement all of them in an efficient tool, and show their practical applicability. In particular, we show that they outperform classical \enquote{union-bound} style approaches, and overall our implementation requires 50x less samples on average than previous state of the art.
