A Hemimetric Extension of Simulation for Semi-Markov Decision Processes

Mathias Ruggaard Pedersen; Giorgio Bacci; Kim Guldstrand Larsen; Radu Iulian Mardare

doi:10.1007/978-3-319-99154-2_21

A Hemimetric Extension of Simulation for Semi-Markov Decision Processes

Mathias Ruggaard Pedersen, Giorgio Bacci, Kim Guldstrand Larsen, Radu Iulian Mardare

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

2 Citations (Scopus)

124 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 language	English
Title of host publication	Quantitative Evaluation of Systems : 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings
Editors	Anabelle McIver, Andras Horvath
Number of pages	17
Publisher	Springer
Publication date	4 Sept 2018
Pages	339-355
ISBN (Print)	978-3-319-99153-5
ISBN (Electronic)	978-3-319-99154-2
DOIs	https://doi.org/10.1007/978-3-319-99154-2_21
Publication status	Published - 4 Sept 2018
Event	Quantitative Evaluation of Systems 2018 - Beijing, China Duration: 4 Sept 2018 → 7 Sept 2018 http://www.qest.org/qest2018/

Conference

Conference	Quantitative Evaluation of Systems 2018
Country/Territory	China
City	Beijing
Period	04/09/2018 → 07/09/2018
Internet address	http://www.qest.org/qest2018/

Series	Lecture Notes in Computer Science
Volume	11024
ISSN	0302-9743

Access to Document

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

mainAccepted author manuscript, 352 KB

AUB Link

Search for the material in Aalborg University Library's search engine

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. https://doi.org/10.1007/978-3-319-99154-2_21

Pedersen, Mathias Ruggaard ; Bacci, Giorgio ; Larsen, Kim Guldstrand et al. / 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 = sep,

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",

note = "Quantitative Evaluation of Systems 2018 ; Conference date: 04-09-2018 Through 07-09-2018",

url = "http://www.qest.org/qest2018/",

}

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, Quantitative Evaluation of Systems 2018, 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 et al.
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 proceeding › Article in proceeding › Research › peer-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

T2 - Quantitative Evaluation of Systems 2018

Y2 - 4 September 2018 through 7 September 2018

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). doi: 10.1007/978-3-319-99154-2_21

A Hemimetric Extension of Simulation for Semi-Markov Decision Processes

Abstract

Conference

Access to Document

AUB Link

Other files and links

Fingerprint

Approximate Reasoning for Stochastic Markovian Systems

IDEA4CPS: Foundations for Cyber-Physical Sytems

Cite this

A Hemimetric Extension of Simulation for Semi-Markov Decision Processes

Abstract

Conference

Access to Document

AUB Link

Other files and links

Fingerprint

Projects

Approximate Reasoning for Stochastic Markovian Systems

IDEA4CPS: Foundations for Cyber-Physical Sytems

Cite this