Confidence Sequences for Online Statistical Model Checking of Markov Decision Processes

• URL: http://arxiv.org/abs/2606.25797v1
• Date: Wed, 24 Jun 2026 13:16:08 GMT
• Title: Confidence Sequences for Online Statistical Model Checking of Markov Decision Processes
• Abstract summary: We present several emphconfidence sequences, which are specifically designed for such enquoteonline settings.<n>Overall our implementation requires 50x less samples on average than previous state of the art.
• Score: 6.947242730984886
• License: http://creativecommons.org/licenses/by-sa/4.0/
• 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 \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.

Related papers

• Deterministic Mode Proposals: An Efficient Alternative to Generative Sampling for Ambiguous Segmentation [3.5493798890908113]
  We introduce a deterministic framework that efficiently produces a fixed-size set of proposal masks in a single forward pass.<n>Our approach significantly reduces inference time while achieving higher ground-truth coverage than existing generative models.<n>We demonstrate that our model can be trained without knowing the full distribution of outcomes, making it applicable to real-world datasets.
  arXiv  Detail & Related papers  (2026-03-20T17:59:26Z)
• A Principled Approach to Randomized Selection under Uncertainty: Applications to Peer Review and Grant Funding [61.86327960322782]
  We propose a principled framework for randomized decision-making based on interval estimates of the quality of each item.<n>We introduce MERIT, an optimization-based method that maximizes the worst-case expected number of top candidates selected.<n>We prove that MERIT satisfies desirable axiomatic properties not guaranteed by existing approaches.
  arXiv  Detail & Related papers  (2025-06-23T19:59:30Z)
• Distances for Markov chains from sample streams [16.443304244634767]
  Bisimulation metrics are powerful tools for measuring similarities between processes, and specifically Markov chains.<n>Recent advances have uncovered that bisimulation metrics are, in fact, optimal-transport distances, which has enabled the development of fast algorithms for computing such metrics with provable accuracy and runtime guarantees.<n>This is often an impractical assumption in most real-world scenarios, where typically only sample trajectories are available.<n>We propose a new optimization method that addresses this limitation and estimates bisimulation metrics based on sample access, without requiring explicit transition models.
  arXiv  Detail & Related papers  (2025-05-23T15:09:04Z)
• Conformal Calibration of Statistical Confidence Sets [1.8840155706520811]
  We introduce two novel methods, TRUST and TRUST++, for calibrating confidence sets to achieve distribution-free conditional coverage.<n>We demonstrate that our methods outperform existing approaches, particularly in small-sample regimes.
  arXiv  Detail & Related papers  (2024-11-28T20:45:59Z)
• Probabilistic Conformal Prediction with Approximate Conditional Validity [81.30551968980143]
  We develop a new method for generating prediction sets that combines the flexibility of conformal methods with an estimate of the conditional distribution. Our method consistently outperforms existing approaches in terms of conditional coverage.
  arXiv  Detail & Related papers  (2024-07-01T20:44:48Z)
• What Are the Odds? Improving the foundations of Statistical Model Checking [3.789219860006095]
  Markov decision processes (MDPs) are a fundamental model for decision making under uncertainty.<n>Traditionally verification algorithms assume exact knowledge of the probabilities that govern the behaviour of an MDP.<n>We propose specialised approaches that exploit our knowledge of the MDP.
  arXiv  Detail & Related papers  (2024-04-08T11:47:46Z)
• When Does Confidence-Based Cascade Deferral Suffice? [69.28314307469381]
  Cascades are a classical strategy to enable inference cost to vary adaptively across samples. A deferral rule determines whether to invoke the next classifier in the sequence, or to terminate prediction. Despite being oblivious to the structure of the cascade, confidence-based deferral often works remarkably well in practice.
  arXiv  Detail & Related papers  (2023-07-06T04:13:57Z)
• User-defined Event Sampling and Uncertainty Quantification in Diffusion Models for Physical Dynamical Systems [49.75149094527068]
  We show that diffusion models can be adapted to make predictions and provide uncertainty quantification for chaotic dynamical systems. We develop a probabilistic approximation scheme for the conditional score function which converges to the true distribution as the noise level decreases. We are able to sample conditionally on nonlinear userdefined events at inference time, and matches data statistics even when sampling from the tails of the distribution.
  arXiv  Detail & Related papers  (2023-06-13T03:42:03Z)
• Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noise [59.47042225257565]
  We present a novel planning method that does not rely on any explicit representation of the noise distributions. First, we abstract the continuous system into a discrete-state model that captures noise by probabilistic transitions between states. We capture these bounds in the transition probability intervals of a so-called interval Markov decision process (iMDP)
  arXiv  Detail & Related papers  (2021-10-25T06:18:55Z)
• Learning Probabilistic Ordinal Embeddings for Uncertainty-Aware Regression [91.3373131262391]
  Uncertainty is the only certainty there is. Traditionally, the direct regression formulation is considered and the uncertainty is modeled by modifying the output space to a certain family of probabilistic distributions. How to model the uncertainty within the present-day technologies for regression remains an open issue.
  arXiv  Detail & Related papers  (2021-03-25T06:56:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.