Computing behavioral distances, compositionally

Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Radu Mardare

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

15 Citations (Scopus)

Abstract

We propose a general definition of composition operator on Markov Decision Processes with rewards (MDPs) and identify a well behaved class of operators, called safe, that are guaranteed to be non-extensive w.r.t. the bisimilarity pseudometrics of Ferns et al. [10], which measure behavioral similarities between MDPs. For MDPs built using safe/non-extensive operators, we present the first method that exploits the structure of the system for (exactly) computing the bisimilarity distance on MDPs. Experimental results show significant improvements upon the non-compositional technique.

Original languageEnglish
Title of host publication Mathematical Foundations of Computer Science 2013
EditorsK. Chatterjee, J. Sgall
Place of PublicationBerlin
PublisherSpringer-Verlag
Pages74-85
Number of pages12
ISBN (Print)9783642403125
DOIs
Publication statusPublished - 15 Oct 2013
Event38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 - Klosterneuburg, Austria
Duration: 26 Aug 201330 Aug 2013

Publication series

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

Conference

Conference38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013
CountryAustria
CityKlosterneuburg
Period26/08/1330/08/13

Keywords

  • discount factor
  • multi-agent system
  • composition operator
  • Markov decision processes
  • parallel composition

Fingerprint Dive into the research topics of 'Computing behavioral distances, compositionally'. Together they form a unique fingerprint.

  • Cite this

    Bacci, G., Bacci, G., Larsen, K. G., & Mardare, R. (2013). Computing behavioral distances, compositionally. In K. Chatterjee, & J. Sgall (Eds.), Mathematical Foundations of Computer Science 2013 (pp. 74-85). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8087 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-642-40313-2_9