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

arXiv: https://arxiv.org/abs/2606.29681 · HTML: https://mlsanity.com/paper/2606.29681/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 43 references that are in the map.
- First posted on arXiv 29 Jun 2026.

## Builds on (most cited first, 28 of 28)

- [Explainable Reinforcement Learning Through a Causal Lens](https://mlsanity.com/paper/1905.10958/) (2019)
- [Counterfactual Off-Policy Evaluation with Gumbel-Max Structural Causal Models](https://mlsanity.com/paper/1905.05824/) (2019)
- [Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints](https://mlsanity.com/paper/1404.7073/) (2014)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Explainable Reinforcement Learning via a Causal World Model](https://mlsanity.com/paper/2305.02749/) (2023)
- [Temporal Logics for Hyperproperties](https://mlsanity.com/paper/1401.4492/) (2014)
- [Permissive Controller Synthesis for Probabilistic Systems](https://mlsanity.com/paper/1504.04662/) (2015)
- [Robust Anytime Learning of Markov Decision Processes](https://mlsanity.com/paper/2205.15827/) (2022)
- [A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs](https://mlsanity.com/paper/2310.12248/) (2023)
- [Distal Explanations for Model-free Explainable Reinforcement Learning](https://mlsanity.com/paper/2001.10284/) (2020)
- [From Verification to Causality-based Explications](https://mlsanity.com/paper/2105.09533/) (2021)
- [Reinforcement Learning of Control Policy for Linear Temporal Logic Specifications Using Limit-Deterministic Generalized B"uchi Automata](https://mlsanity.com/paper/2001.04669/) (2020)
- [Actual Causality and Responsibility Attribution in Decentralized Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2204.00302/) (2022)
- [Probabilistic Hyperproperties of Markov Decision Processes](https://mlsanity.com/paper/2005.03362/) (2020)
- [Probabilistic causes in Markov chains](https://mlsanity.com/paper/2104.13604/) (2021)
- [PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDP](https://mlsanity.com/paper/2206.01465/) (2022)
- [On probability-raising causality in Markov decision processes](https://mlsanity.com/paper/2201.08768/) (2022)
- [Causal Temporal Reasoning for Markov Decision Processes](https://mlsanity.com/paper/2212.08712/) (2022)
- [Counterexamples for Robotic Planning Explained in Structured Language](https://mlsanity.com/paper/1803.08966/) (2018)
- [Foundations of probability-raising causality in Markov decision processes](https://mlsanity.com/paper/2209.02973/) (2022)
- [Synthesis of Temporal Causality](https://mlsanity.com/paper/2405.10912/) (2024)
- [Closure and Complexity of Temporal Causality](https://mlsanity.com/paper/2505.10186/) (2025)
- [Probability-Raising Causality for Uncertain Parametric Markov Decision Processes with PAC Guarantees](https://mlsanity.com/paper/2507.07319/) (2025)
- [Maximizing the Conditional Expected Reward for Reaching the Goal](https://mlsanity.com/paper/1701.05389/) (2017)
- [Minimal witnesses for probabilistic timed automata](https://mlsanity.com/paper/2007.00637/) (2020)
- [Multi-Objective Controller Synthesis with Uncertain Human Preferences](https://mlsanity.com/paper/2105.04662/) (2021)
- [Counterfactuals Modulo Temporal Logics](https://mlsanity.com/paper/2306.08916/) (2023)
- [Counterfactual Explanations for MITL Violations](https://mlsanity.com/paper/2412.10386/) (2024)

## Abstract (arXiv)

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.