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.CONCUR.2016.22
URN: urn:nbn:de:0030-drops-61837
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6183/
Go to the corresponding LIPIcs Volume Portal

Tang, Qiyi ; van Breugel, Franck

Computing Probabilistic Bisimilarity Distances via Policy Iteration

pdf-format:
LIPIcs-CONCUR-2016-22.pdf (0.5 MB)

Abstract

A transformation mapping a labelled Markov chain to a simple stochastic game is presented. In the resulting simple stochastic game, each vertex corresponds to a pair of states of the labelled Markov chain. The value of a vertex of the simple stochastic game is shown to be equal to the probabilistic bisimilarity distance, a notion due to Desharnais, Gupta, Jagadeesan and Panangaden, of the corresponding pair of states of the labelled Markov chain. Bacci, Bacci, Larsen and Mardare introduced an algorithm to compute the probabilistic bisimilarity distances for a labelled Markov chain. A modification of a basic version of their algorithm for a labelled Markov chain is shown to be the policy iteration algorithm applied to the corresponding simple stochastic game. Furthermore, it is shown that this algorithm takes exponential time in the worst case.

BibTeX - Entry

@InProceedings{tang_et_al:LIPIcs:2016:6183,
  author =	{Qiyi Tang and Franck van Breugel},
  title =	{{Computing Probabilistic Bisimilarity Distances via Policy Iteration}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Jos{\'e}e Desharnais and Radha Jagadeesan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6183},
  URN =		{urn:nbn:de:0030-drops-61837},
  doi =		{10.4230/LIPIcs.CONCUR.2016.22},
  annote =	{Keywords: labelled Markov chain, simple stochastic game, probabilistic bisimilarity, pseudometric, value function, policy iteration}
}

Keywords: labelled Markov chain, simple stochastic game, probabilistic bisimilarity, pseudometric, value function, policy iteration
Collection: 27th International Conference on Concurrency Theory (CONCUR 2016)
Issue Date: 2016
Date of publication: 24.08.2016

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