On probability-raising causality in Markov decision processes

Christel Baier; Florian Funke; Jakob Piribauer; Robin Ziemek

doi:10.1007/978-3-030-99253-8_3

On probability-raising causality in Markov decision processes

Christel Baier, Florian Funke, Jakob Piribauer, Robin Ziemek

Technische Universität Dresden

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-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 language	English
Title of host publication	Foundations 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
Editors	Patricia Bouyer, Lutz Schröder
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	40-60
Number of pages	21
ISBN (Print)	9783030992521
DOIs	https://doi.org/10.1007/978-3-030-99253-8_3
State	Published - 2022
Externally published	Yes
Event	25th 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 2022 → 6 Apr 2022

Publication series

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

Conference

Conference	25th 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/Territory	Germany
City	Munich
Period	4/04/22 → 6/04/22

Access to Document

10.1007/978-3-030-99253-8_3

Cite this

Baier, C., Funke, F., Piribauer, J., & Ziemek, R. (2022). On probability-raising causality in Markov decision processes. In P. Bouyer, & L. Schröder (Eds.), Foundations 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 (pp. 40-60). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13242 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-99253-8_3

Baier, Christel ; Funke, Florian ; Piribauer, Jakob et al. / On probability-raising causality in Markov decision processes. Foundations 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. editor / Patricia Bouyer ; Lutz Schröder. Springer Science and Business Media Deutschland GmbH, 2022. pp. 40-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6b3fa4d0e3b24f05aa2a48239fa45916,

title = "On probability-raising causality in Markov decision processes",

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.",

author = "Christel Baier and Florian Funke and Jakob Piribauer and Robin Ziemek",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s).; 25th 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 ; Conference date: 04-04-2022 Through 06-04-2022",

year = "2022",

doi = "10.1007/978-3-030-99253-8_3",

language = "English",

isbn = "9783030992521",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "40--60",

editor = "Patricia Bouyer and Lutz Schr{\"o}der",

booktitle = "Foundations 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",

}

Baier, C, Funke, F, Piribauer, J & Ziemek, R 2022, On probability-raising causality in Markov decision processes. in P Bouyer & L Schröder (eds), Foundations 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13242 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 40-60, 25th 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, 4/04/22. https://doi.org/10.1007/978-3-030-99253-8_3

On probability-raising causality in Markov decision processes. / Baier, Christel; Funke, Florian; Piribauer, Jakob et al.
Foundations 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. ed. / Patricia Bouyer; Lutz Schröder. Springer Science and Business Media Deutschland GmbH, 2022. p. 40-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13242 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - On probability-raising causality in Markov decision processes

AU - Baier, Christel

AU - Funke, Florian

AU - Piribauer, Jakob

AU - Ziemek, Robin

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85128461255&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-99253-8_3

DO - 10.1007/978-3-030-99253-8_3

M3 - Conference contribution

AN - SCOPUS:85128461255

SN - 9783030992521

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 40

EP - 60

BT - Foundations 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

A2 - Bouyer, Patricia

A2 - Schröder, Lutz

PB - Springer Science and Business Media Deutschland GmbH

T2 - 25th 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

Y2 - 4 April 2022 through 6 April 2022

ER -

Baier C, Funke F, Piribauer J, Ziemek R. On probability-raising causality in Markov decision processes. In Bouyer P, Schröder L, editors, Foundations 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. Springer Science and Business Media Deutschland GmbH. 2022. p. 40-60. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-99253-8_3

On probability-raising causality in Markov decision processes

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this