2026-10-12T18:12:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23986 2025-11-12T12:25:17Z ddc:004 open_access

Explainability is a Game for Probabilistic Bisimilarity Distances Vlasman, Emily Nanah Ji, Anto Worrell, James van Breugel, Franck probabilistic bisimilarity distance labelled Markov chain game policy explainability We revisit a game from the literature that characterizes the probabilistic bisimilarity distances of a labelled Markov chain. We illustrate how an optimal policy of the game can explain these distances. Like the games that characterize bisimilarity and probabilistic bisimilarity, the game is played on pairs of states and matches transitions of those states. To obtain more convincing and interpretable explanations than those provided by generic optimal policies, we restrict to optimal policies that delay reaching observably inequivalent state pairs for as long as possible (called 1-maximal) while quickly reaching equivalent ones (called 0-minimal). We present iterative algorithms that compute 1-maximal and 0-minimal policies and prove an exponential lower bound for the number of iterations of the algorithm that computes 1-maximal policies. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Emily Vlasman and Anto Nanah Ji and James Worrell and Franck van Breugel 2025 Is Part Of LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2025.36 urn:nbn:de:0030-drops-239861 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.36 eng https://creativecommons.org/licenses/by/4.0/legalcode