Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guarantees
For researchers and practitioners in probabilistic model checking and reinforcement learning, this work provides a sample-efficient method to identify causes of undesired outcomes in unknown MDPs with formal guarantees.
This paper addresses the problem of identifying probability-raising (PR) causes for reachability in Markov decision processes (MDPs) when transition probabilities are unknown. The authors propose a learning approach with probabilistic guarantees, using a restart-based MDP modification that reduces PR-cause checking to two conditional reachability queries, and develop an anytime algorithm that classifies states as causal, non-causal, or undecided. Experiments on two benchmarks show reliable and fast identification.
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.