Confidence Sequences for Online Statistical Model Checking of Markov Decision Processes
Konstantin Kueffner, Tobias Meggendorfer, Maximilian Weininger, Patrick Wienhöft · 2026
Read Confidence Sequences for Online Statistical Model Checking of Markov Decision Processes by Konstantin Kueffner, Tobias Meggendorfer, Maximilian Weininger, Patrick Wienhöft (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25797.txt.
Introduction
A Markov decision process mixes choice with chance, and checking its behaviour statistically usually assumes you may peek, sample, and peek again. Konstantin Kueffner, Tobias Meggendorfer, Maximilian Weininger, and Patrick Wienhöft supply the right statistics for that online rhythm in 2026. Classical workflows sample in rounds and widen bounds with blunt union bound corrections. Worse, existing implementations are often subtly incorrect, or wasteful, or both. The team's confidence sequences are built for continuous monitoring: valid at every moment, not just at preplanned checkpoints.
All variants are implemented in one efficient tool and tested for practical use. They beat the classical union bound style approaches head to head. Against the previous state of the art, the implementation needed fifty times fewer samples on average to reach its guarantees. For engineers verifying systems with unknown probabilities, that is the difference between a check that runs and one that merely exists.
Catalog record
| CREATOR | Konstantin Kueffner, Tobias Meggendorfer, Maximilian Weininger, Patrick Wienhöft |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 120 KB |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.25797
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Confidence Sequences for Online Statistical Model Checking of Markov Decision Processes Konstantin Kueffner, Tobias Meggendorfer, Maximilian Weininger, Patrick Wienhöft Abstract 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 “online” settings, implement all of them in an efficient tool, and show their practical applicability. In particular, we show that they outperform classical “union-bound” style approaches, and overall our implementation requires 50x less samples on average than previous state of the art. 1 Introduction Markov decision processes (MDPs) [ 55 ] are the classic modelling formalism for dynamic systems with probabilistic and nondeterministic behaviour. Taking one of the available actions in each state moves the system to a successor state, which is chosen from a probability distribution associated with the state-action pair. This is aleatory uncertainty, i.e. the inherent randomness of the process, e.g. a coin toss. However, there may also be epistemic uncertainty (lack of knowledge), e.g. not knowing the bias of the coin, see [ 8 ] . While verification procedures traditionally assume full knowledge of the MDP (also called “white box” , with no epistemic uncertainty), over the past decade there has been an increasing interest in reliable analysis of MDPs where the exact transition probabilities are unknown (grey box) or even the presence of the transitions (positivity of the transition probability) is unknown (black box). For example, consider the task of finding the optimal probability of getting heads from a coin toss when choosing among multiple coins. Given knowledge of the coins’ biases (white box), we clearly choose the coin with the highest biases towards heads. This does not guarantee winning (there still is aleatoric uncertainty), but we know which coin to pick and the resulting value (the chances we get). With unknown biases (grey box), we cannot with certainty determine the value nor choose the best coin. Statistical model checking (SMC) [ 69 ] tackles this problem by gathering simulations of the system (e.g. tossing each coin several times) and drawing statistical conclusions from the obtained data. One of the strongest guarantees possible are probably approximately correct (PAC) results, where the reported value is \varepsilon -close to the true result with confidence at least \gamma . When considering discounted or finite-horizon objectives, the distance between estimation and true value can be upper-bounded for paths of a certain length. Thus, PAC-guarantees and even bounds on sample-complexity can be derived in a straightforward manner, see e.g. [ 1 , 39 , 32 , 58 , 61 , 66 ] . In contrast, for infinite-horizon objectives, more involved methods are required. There, the prevalent approach to obtain PAC guarantees (in the grey box setting) [ 4 , 65 , 2 , 59 , 9 , 7 , 54 ] is to repeat the following three steps: (i) Sample the unknown MDP, counting occurrences of every transition, (ii) Infer an interval MDP (IMDP) [ 27 ] by obtaining confidence intervals of the transition probabilities, and finally (iii) Solve the IMDP, obtaining lower and upper bounds a,b , that, with probability \gamma , bound the true value of the unknown MDP, i.e. v\in[a,b] . If additionally |b-a|<\varepsilon , the algorithm terminates; otherwise, it repeats the steps, i.e. gathers more data, increasing the precision of the confidence intervals in the IMDP, until a and b are \varepsilon -close. However, existing variants rely on flawed correctness arguments or are too conservative , and quite often both. Firstly, naively repeating the three steps compromises the PAC-guarantee, as the entire confidence \gamma is “reused” across multiple Infer s. Intuitively, this is akin to repeating a statistical experiment until the result “looks right” . (In Appendix 0.B we provide a general counterexample based on the law of iterated logarithm [ 40 , 28 ] .) Secondly, the used statistical methods are overly conservative: On the one hand, the statistical methods used in Infer are suboptimal, providing wide confidence intervals, in turn requiring more samples, see [ 51 ] . However, even the “optimal” methods of [ 51 ] are sub-optimal when we can repeatedly interact with the system. Intuitively, estimates for the same distribution in different Infer steps do not exploit the fact that the samples they are working with actually stem from the same distribution. So, on the other hand, strictly dividing the process into these three phases is fundamentally problematic. Contributions. We improve SMC with PAC guarantees for MDPs by employing confidence sequences [ 23 ] . For a stream of samples, these yield a stream of estimates with a statistical guarantee for the entire (arbitrarily long) stream. Using such sequentially correct estimates, we address the flawed correctness proof of previous works. Moreover, confidence sequences exploit the fact that estimates at different times are not independent , also replacing previous overly conservative estimates and significantly reducing the required number of samples. Technically, we analyse gridded variants of classical confidence intervals such as Hoeffding [ 35 ] , (empirical) Bernstein [ 49 ] , and Clopper-Pearson [ 21 ] . Moreover, we adapt several confidence sequences, based on stitching [ 37 ] , betting [ 64 ] , and test-martingales [ 64 ] , to our setting. Finally, we introduce a novel value-based hypothesis test for SMC, which entirely circumvents estimating probabilities. For all these methods, we discuss correctness, convergence, and computability. Practically, we provide an efficient, extensible Java tool embedding the confidence sequences not only in the state-of-the-art Sample - Infer - Solve pipeline, but also a new interwoven approach. Our new variant exploits the continuous guarantees of confidence sequences to avoid constructing an IMDP for the whole model and instead locally applies the robust value iteration of [ 50 ] . This enables soundly incorporating guidance heuristics for sampling [ 16 ] and utilizing the novel value-based hypothesis test. Our evaluation shows a significant reduction in the number of samples required, on average 50x less than state-of-the-art, and that all of our contributions (confidence sequences, in particular the value test, and our interwoven approach) are instrumental to this improvement. Additionally, our evaluation provides, to our knowledge for the first time, an empirical comparison of all presented statistical methods, both on single distributions and on SMC of MDPs. This additionally demonstrates the benefits of confidence sequences and their individual strengths and weaknesses, also beyond our focus of SMC for MDPs. Related Work Section 2.3 discusses other works on SMC of MDPs. Appendix 0.A details common SMC assumptions and how they reduce to the grey box setting we consider. Other Formalisms for System and Specification. Continuous time systems can be tackled by estimating transitions rates