### 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 language | English |
---|---|

Title of host publication | Mathematical Foundations of Computer Science 2013 |

Editors | K. Chatterjee, J. Sgall |

Place of Publication | Berlin |

Publisher | Springer-Verlag |

Pages | 74-85 |

Number of pages | 12 |

ISBN (Print) | 9783642403125 |

DOIs | |

Publication status | Published - 15 Oct 2013 |

Event | 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 - Klosterneuburg, Austria Duration: 26 Aug 2013 → 30 Aug 2013 |

### Publication series

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

Volume | 8087 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013 |
---|---|

Country | Austria |

City | Klosterneuburg |

Period | 26/08/13 → 30/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