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

Ryohei Oura, Georgios Fainekos, Hideki Okamoto, Bardh Hoxha
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:5168-5196, 2026.

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 ill-suited for learning: the gap between conditional and unconditional reachability probabilities can be hard to detect from samples, and construction requires reachability probabilities of the original {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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-oura26a, title = {Sample-Efficient Learning of Probabilistic Causes for Reachability in {Markov} Decision Processes with Probabilistic Guarantees}, author = {Oura, Ryohei and Fainekos, Georgios and Okamoto, Hideki and Hoxha, Bardh}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {5168--5196}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/oura26a/oura26a.pdf}, url = {https://proceedings.mlr.press/v337/oura26a.html}, 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 ill-suited for learning: the gap between conditional and unconditional reachability probabilities can be hard to detect from samples, and construction requires reachability probabilities of the original {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.} }
Endnote
%0 Conference Paper %T Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guarantees %A Ryohei Oura %A Georgios Fainekos %A Hideki Okamoto %A Bardh Hoxha %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-oura26a %I PMLR %P 5168--5196 %U https://proceedings.mlr.press/v337/oura26a.html %V 337 %X 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 ill-suited for learning: the gap between conditional and unconditional reachability probabilities can be hard to detect from samples, and construction requires reachability probabilities of the original {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.
APA
Oura, R., Fainekos, G., Okamoto, H. & Hoxha, B.. (2026). Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guarantees. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:5168-5196 Available from https://proceedings.mlr.press/v337/oura26a.html.

Related Material