On probability-raising causality in Markov decision processes

Christel Baier, Florian Funke, Jakob Piribauer, Robin Ziemek

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Scopus citations

Abstract

The purpose of this paper is to introduce a notion of causality in Markov decision processes based on the probability-raising principle and to analyze its algorithmic properties. The latter includes algorithms for checking cause-effect relationships and the existence of probability-raising causes for given effect scenarios. Inspired by concepts of statistical analysis, we study quality measures (recall, coverage ratio and f-score) for causes and develop algorithms for their computation. Finally, the computational complexity for finding optimal causes with respect to these measures is analyzed.

Original languageEnglish
Title of host publicationFoundations of Software Science and Computation Structures - 25th International Conference, FOSSACS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Proceedings
EditorsPatricia Bouyer, Lutz Schröder
PublisherSpringer Science and Business Media Deutschland GmbH
Pages40-60
Number of pages21
ISBN (Print)9783030992521
DOIs
StatePublished - 2022
Externally publishedYes
Event25th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 2022, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022 - Munich, Germany
Duration: 4 Apr 20226 Apr 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13242 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 2022, held as part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022
Country/TerritoryGermany
CityMunich
Period4/04/226/04/22

Fingerprint

Dive into the research topics of 'On probability-raising causality in Markov decision processes'. Together they form a unique fingerprint.

Cite this