License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.49
URN: urn:nbn:de:0030-drops-132903
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13290/
Go to the corresponding LIPIcs Volume Portal

Kiefer, Stefan ; Tang, Qiyi

Comparing Labelled Markov Decision Processes

pdf-format:
LIPIcs-FSTTCS-2020-49.pdf (0.6 MB)

Abstract

A labelled Markov decision process is a labelled Markov chain with nondeterminism, i.e., together with a strategy a labelled MDP induces a labelled Markov chain. The model is related to interval Markov chains. Motivated by applications of equivalence checking for the verification of anonymity, we study the algorithmic comparison of two labelled MDPs, in particular, whether there exist strategies such that the MDPs become equivalent/inequivalent, both in terms of trace equivalence and in terms of probabilistic bisimilarity. We provide the first polynomial-time algorithms for computing memoryless strategies to make the two labelled MDPs inequivalent if such strategies exist. We also study the computational complexity of qualitative problems about making the total variation distance and the probabilistic bisimilarity distance less than one or equal to one.

BibTeX - Entry

@InProceedings{kiefer_et_al:LIPIcs:2020:13290,
  author =	{Stefan Kiefer and Qiyi Tang},
  title =	{{Comparing Labelled Markov Decision Processes}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Nitin Saxena and Sunil Simon},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13290},
  URN =		{urn:nbn:de:0030-drops-132903},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.49},
  annote =	{Keywords: Markov decision processes, Markov chains, Behavioural metrics}
}

Keywords: Markov decision processes, Markov chains, Behavioural metrics
Collection: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Issue Date: 2020
Date of publication: 04.12.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI