A Hemimetric Extension of Simulation for Semi-Markov Decision Processes

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

1 Citation (Scopus)
26 Downloads (Pure)

Abstract

Semi-Markov decision processes (SMDPs) are continuous-time Markov decision processes where the residence-time on states is governed by generic distributions on the positive real line.

In this paper we consider the problem of comparing two SMDPs with respect to their time-dependent behaviour. We propose a hemimetric between processes, which we call simulation distance, measuring the least acceleration factor by which a process needs to speed up its actions in order to behave at least as fast as another process. We show that this distance can be computed in time O(n2(f(l)+k)+mn7) , where n is the number of states, m the number of actions, k the number of atomic propositions, and f(l) the complexity of comparing the residence-time between states. The theoretical relevance and applicability of this distance is further argued by showing that (i) it is suitable for compositional reasoning with respect to CSP-like parallel composition and (ii) has a logical characterisation in terms of a simple Markovian logic.
Original languageEnglish
Title of host publicationQuantitative Evaluation of Systems : 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings
EditorsAnabelle McIver, Andras Horvath
Number of pages17
PublisherSpringer
Publication date4 Sep 2018
Pages339-355
ISBN (Print)978-3-319-99153-5
ISBN (Electronic)978-3-319-99154-2
DOIs
Publication statusPublished - 4 Sep 2018
EventQuantitative Evaluation of Systems 2018 - Beijing, China
Duration: 4 Sep 20187 Sep 2018
http://www.qest.org/qest2018/

Conference

ConferenceQuantitative Evaluation of Systems 2018
CountryChina
CityBeijing
Period04/09/201807/09/2018
Internet address
SeriesLecture Notes in Computer Science
Volume11024
ISSN0302-9743

Fingerprint

Chemical analysis

Cite this

Pedersen, M. R., Bacci, G., Larsen, K. G., & Mardare, R. I. (2018). A Hemimetric Extension of Simulation for Semi-Markov Decision Processes. In A. McIver, & A. Horvath (Eds.), Quantitative Evaluation of Systems: 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings (pp. 339-355). Springer. Lecture Notes in Computer Science, Vol.. 11024 https://doi.org/10.1007/978-3-319-99154-2_21
Pedersen, Mathias Ruggaard ; Bacci, Giorgio ; Larsen, Kim Guldstrand ; Mardare, Radu Iulian. / A Hemimetric Extension of Simulation for Semi-Markov Decision Processes. Quantitative Evaluation of Systems: 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings. editor / Anabelle McIver ; Andras Horvath. Springer, 2018. pp. 339-355 (Lecture Notes in Computer Science, Vol. 11024).
@inproceedings{e94641b452b54349a9dbbe69395466f4,
title = "A Hemimetric Extension of Simulation for Semi-Markov Decision Processes",
abstract = "Semi-Markov decision processes (SMDPs) are continuous-time Markov decision processes where the residence-time on states is governed by generic distributions on the positive real line.In this paper we consider the problem of comparing two SMDPs with respect to their time-dependent behaviour. We propose a hemimetric between processes, which we call simulation distance, measuring the least acceleration factor by which a process needs to speed up its actions in order to behave at least as fast as another process. We show that this distance can be computed in time O(n2(f(l)+k)+mn7) , where n is the number of states, m the number of actions, k the number of atomic propositions, and f(l) the complexity of comparing the residence-time between states. The theoretical relevance and applicability of this distance is further argued by showing that (i) it is suitable for compositional reasoning with respect to CSP-like parallel composition and (ii) has a logical characterisation in terms of a simple Markovian logic.",
keywords = "semi-markov process, markov decision process, simulation, hemimetric",
author = "Pedersen, {Mathias Ruggaard} and Giorgio Bacci and Larsen, {Kim Guldstrand} and Mardare, {Radu Iulian}",
year = "2018",
month = "9",
day = "4",
doi = "10.1007/978-3-319-99154-2_21",
language = "English",
isbn = "978-3-319-99153-5",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "339--355",
editor = "Anabelle McIver and Andras Horvath",
booktitle = "Quantitative Evaluation of Systems",
address = "Germany",

}

Pedersen, MR, Bacci, G, Larsen, KG & Mardare, RI 2018, A Hemimetric Extension of Simulation for Semi-Markov Decision Processes. in A McIver & A Horvath (eds), Quantitative Evaluation of Systems: 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings. Springer, Lecture Notes in Computer Science, vol. 11024, pp. 339-355, Beijing, China, 04/09/2018. https://doi.org/10.1007/978-3-319-99154-2_21

A Hemimetric Extension of Simulation for Semi-Markov Decision Processes. / Pedersen, Mathias Ruggaard; Bacci, Giorgio; Larsen, Kim Guldstrand; Mardare, Radu Iulian.

Quantitative Evaluation of Systems: 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings. ed. / Anabelle McIver; Andras Horvath. Springer, 2018. p. 339-355 (Lecture Notes in Computer Science, Vol. 11024).

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - A Hemimetric Extension of Simulation for Semi-Markov Decision Processes

AU - Pedersen, Mathias Ruggaard

AU - Bacci, Giorgio

AU - Larsen, Kim Guldstrand

AU - Mardare, Radu Iulian

PY - 2018/9/4

Y1 - 2018/9/4

N2 - Semi-Markov decision processes (SMDPs) are continuous-time Markov decision processes where the residence-time on states is governed by generic distributions on the positive real line.In this paper we consider the problem of comparing two SMDPs with respect to their time-dependent behaviour. We propose a hemimetric between processes, which we call simulation distance, measuring the least acceleration factor by which a process needs to speed up its actions in order to behave at least as fast as another process. We show that this distance can be computed in time O(n2(f(l)+k)+mn7) , where n is the number of states, m the number of actions, k the number of atomic propositions, and f(l) the complexity of comparing the residence-time between states. The theoretical relevance and applicability of this distance is further argued by showing that (i) it is suitable for compositional reasoning with respect to CSP-like parallel composition and (ii) has a logical characterisation in terms of a simple Markovian logic.

AB - Semi-Markov decision processes (SMDPs) are continuous-time Markov decision processes where the residence-time on states is governed by generic distributions on the positive real line.In this paper we consider the problem of comparing two SMDPs with respect to their time-dependent behaviour. We propose a hemimetric between processes, which we call simulation distance, measuring the least acceleration factor by which a process needs to speed up its actions in order to behave at least as fast as another process. We show that this distance can be computed in time O(n2(f(l)+k)+mn7) , where n is the number of states, m the number of actions, k the number of atomic propositions, and f(l) the complexity of comparing the residence-time between states. The theoretical relevance and applicability of this distance is further argued by showing that (i) it is suitable for compositional reasoning with respect to CSP-like parallel composition and (ii) has a logical characterisation in terms of a simple Markovian logic.

KW - semi-markov process

KW - markov decision process

KW - simulation

KW - hemimetric

UR - http://www.scopus.com/inward/record.url?scp=85053162810&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-99154-2_21

DO - 10.1007/978-3-319-99154-2_21

M3 - Article in proceeding

SN - 978-3-319-99153-5

T3 - Lecture Notes in Computer Science

SP - 339

EP - 355

BT - Quantitative Evaluation of Systems

A2 - McIver, Anabelle

A2 - Horvath, Andras

PB - Springer

ER -

Pedersen MR, Bacci G, Larsen KG, Mardare RI. A Hemimetric Extension of Simulation for Semi-Markov Decision Processes. In McIver A, Horvath A, editors, Quantitative Evaluation of Systems: 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings. Springer. 2018. p. 339-355. (Lecture Notes in Computer Science, Vol. 11024). https://doi.org/10.1007/978-3-319-99154-2_21