Confidence Sequences for Online Model Checking of MDPs

Konstantin Kueffner, Tobias Meggendorfer, Maximilian Weininger and Patrick Wienhöft submitted a paper on 24 June 2026 that introduces confidence sequences designed for online statistical model checking of Markov decision processes. The authors implement several such sequences in an efficient tool and report their implementation requires 50x less samples on average than previous state of the art.

What did the paper introduce?

The paper introduces several confidence sequences specifically tailored to online settings for Markov decision processes, and implements them in an efficient tool. The authors explain that Markov decision processes combine non-deterministic choice and probabilistic uncertainty, and that classical analyses assume exact knowledge of transition probabilities while their sequences operate from sampled data.

The practical contribution in the submission (arXiv:2606.25797, submitted 24 Jun 2026) is twofold: a set of confidence sequences adapted to the online sampling workflow used in statistical model checking, and an implementation showing those sequences outperform classical union-bound style approaches.

How do these confidence sequences change online statistical model checking?

They replace the classical gather-sample-derive-bound-repeat loop with statistical guarantees that remain valid as samples accumulate, which the authors say avoids subtle incorrectness and sub-optimality present in existing implementations. The paper positions confidence sequences as methods that provide valid, time-uniform bounds while sampling proceeds.

The abstract frames the traditional pipeline as drawing samples to bound transition probabilities and repeating when bounds are too broad. The authors claim existing implementations of that pipeline are often either subtly incorrect or sub-optimal. Their confidence sequences are designed for this online setting to yield tighter, valid bounds without the repeated restart cycle the classical approach implies.

How much improvement do the authors demonstrate?

Their implementation requires 50x less samples on average than previous state of the art, and the paper states these sequences outperform classical union-bound style approaches. The 50x figure is presented in the abstract as an average reduction in required samples compared with prior methods.

Beyond that summary, the submission describes the methodic shift: instead of union-bound based guarantees that accumulate conservative penalties across checks, confidence sequences maintain valid intervals at every time step to avoid those penalties. The authors state they implemented all proposed sequences and evaluated their practical applicability.

Why it matters

Reducing sample requirements addresses a core practical bottleneck in statistical model checking: the time and cost to gather enough transitions to obtain tight probability bounds. Cutting average sample needs by a factor of 50 directly lowers computational and experimental expense for verification tasks on cyber-physical and biological models where exact probabilities are unavailable. Tighter, time-uniform bounds also reduce the risk of deploying verification procedures that silently rely on incorrect statistical approximations.

What to watch

Look for independent reproductions of the paper's claim that the implementation needs 50x fewer samples on average than prior work, and for community benchmarks comparing the tool against classical union-bound approaches in concrete MDP case studies.

Paper details: arXiv:2606.25797 (cs), submitted 24 Jun 2026; authors Konstantin Kueffner, Tobias Meggendorfer, Maximilian Weininger, Patrick Wienhöft.