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

Publikation: Beitrag in Buch/Bericht/Konferenzband › Konferenzbeitrag › Begutachtung

2 Zitate (Scopus)

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.

Originalsprache	Englisch
Titel	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
Redakteure/-innen	Patricia Bouyer, Lutz Schröder
Herausgeber (Verlag)	Springer Science and Business Media Deutschland GmbH
Seiten	40-60
Seitenumfang	21
ISBN (Print)	9783030992521
DOIs	https://doi.org/10.1007/978-3-030-99253-8_3
Publikationsstatus	Veröffentlicht - 2022
Extern publiziert	Ja
Veranstaltung	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, Deutschland Dauer: 4 Apr. 2022 → 6 Apr. 2022

Publikationsreihe

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

Konferenz

Konferenz	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
Land/Gebiet	Deutschland
Ort	Munich
Zeitraum	4/04/22 → 6/04/22

Zugriff auf Dokument

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

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

Baier, C., Funke, F., Piribauer, J., & Ziemek, R. (2022). On probability-raising causality in Markov decision processes. in P. Bouyer, & L. Schröder (Hrsg.), 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 (S. 40-60). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 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. Hrsg. / Patricia Bouyer ; Lutz Schröder. Springer Science and Business Media Deutschland GmbH, 2022. S. 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 (Hrsg.), 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), Bd. 13242 LNCS, Springer Science and Business Media Deutschland GmbH, S. 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, Deutschland, 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. Hrsg. / Patricia Bouyer; Lutz Schröder. Springer Science and Business Media Deutschland GmbH, 2022. S. 40-60 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Band 13242 LNCS).

Publikation: Beitrag in Buch/Bericht/Konferenzband › Konferenzbeitrag › Begutachtung

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, Hrsg., 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. S. 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

Publikationsreihe

Konferenz

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Dieses zitieren