Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guarantees

• URL: http://arxiv.org/abs/2606.29681v1
• Date: Mon, 29 Jun 2026 01:07:06 GMT
• Title: Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guarantees
• Abstract summary: We propose a learning approach with probabilistic guarantees for PR-cause identification.<n>Key ingredient is a restart-based MDP modification that reduces PR-cause checking to two conditional reachability queries.<n>We prove correctness, establish sample-complexity bounds, and develop an anytime learning-and-checking algorithm.
• Score: 3.514619847244207
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Probabilistic model checking for Markov decision processes (MDPs) provides quantitative guarantees, but often offers limited insight into why undesired outcomes occur. Probability-raising (PR) causality addresses this by identifying states whose visitation increases the probability of reaching designated states. Existing PR-cause identification methods, however, use MDP modifications not well-suited for learning: the gap between conditional and unconditional reachability probabilities can be hard to detect from transition samples, and construction requires reachability probabilities of the MDP, which are unavailable when transition probabilities are unknown. We study unknown MDPs and propose a learning approach with probabilistic guarantees for PR-cause identification. Our key ingredient is a restart-based MDP modification that reduces PR-cause checking to two conditional reachability queries without using reachability values of the original MDP. We prove correctness, establish sample-complexity bounds, and develop an anytime learning-and-checking algorithm based on two-sided value iteration that progressively classifies states as causal, non-causal, or undecided. Experiments on two benchmarks demonstrate reliable and fast identification of PR causes.

Related papers

• How to Verify Consistency of Probabilistic Claims [49.47758039235095]
  We construct an interactive PCP to prove a predictive model's consistency.<n>We show how a small additive-soundness gap removes dependence on B.<n>We view our interactive PCP as a first step toward predictive models to prove their own consistency.
  arXiv  Detail & Related papers  (2026-08-11T17:41:39Z)
• Robust Parameter Learning for Uncertain MDPs [55.60489406616378]
  Learning-based approaches to verifying unknown Markov decision processes (MDPs) often employ uncertain MDPs.<n>We propose to learn such models using parametric MDPs (pMDPs), where transition probabilities are expressions over a set of parameters.<n>We project statistical uncertainty from empirical transition frequencies onto the pMDP's parameter space, yielding a probably approximately correct (PAC) uncertainty model for the underlying MDP.
  arXiv  Detail & Related papers  (2026-05-02T09:22:05Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives [16.101435842520473]
  This paper studies the challenging yet important problem in POMDPs known as the (indefinite-horizon) Maximal Reachability Probability Problem. Inspired by the success of point-based methods developed for discounted problems, we study their extensions to MRPP. We present a novel algorithm that leverages the strengths of these techniques for efficient exploration of the belief space.
  arXiv  Detail & Related papers  (2024-06-05T02:33:50Z)
• 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)
• Learning Algorithms for Verification of Markov Decision Processes [20.5951492453299]
  We present a general framework for applying learning algorithms to the verification of Markov decision processes (MDPs)<n>The presented framework focuses on probabilistic reachability, which is a core problem in verification.
  arXiv  Detail & Related papers  (2024-03-14T08:54:19Z)
• Decomposing Uncertainty for Large Language Models through Input Clarification Ensembling [69.83976050879318]
  In large language models (LLMs), identifying sources of uncertainty is an important step toward improving reliability, trustworthiness, and interpretability. In this paper, we introduce an uncertainty decomposition framework for LLMs, called input clarification ensembling. Our approach generates a set of clarifications for the input, feeds them into an LLM, and ensembles the corresponding predictions.
  arXiv  Detail & Related papers  (2023-11-15T05:58:35Z)
• Robust Anytime Learning of Markov Decision Processes [8.799182983019557]
  In data-driven applications, deriving precise probabilities from limited data introduces statistical errors. Uncertain MDPs (uMDPs) do not require precise probabilities but instead use so-called uncertainty sets in the transitions. We propose a robust anytime-learning approach that combines a dedicated Bayesian inference scheme with the computation of robust policies.
  arXiv  Detail & Related papers  (2022-05-31T14:29:55Z)
• 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)
• Multivariate Probabilistic Regression with Natural Gradient Boosting [63.58097881421937]
  We propose a Natural Gradient Boosting (NGBoost) approach based on nonparametrically modeling the conditional parameters of the multivariate predictive distribution. Our method is robust, works out-of-the-box without extensive tuning, is modular with respect to the assumed target distribution, and performs competitively in comparison to existing approaches.
  arXiv  Detail & Related papers  (2021-06-07T17:44:49Z)
• Evaluating probabilistic classifiers: Reliability diagrams and score decompositions revisited [68.8204255655161]
  We introduce the CORP approach, which generates provably statistically Consistent, Optimally binned, and Reproducible reliability diagrams in an automated way. Corpor is based on non-parametric isotonic regression and implemented via the Pool-adjacent-violators (PAV) algorithm.
  arXiv  Detail & Related papers  (2020-08-07T08:22:26Z)

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.