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

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › peer review

1 Citationer (Scopus)

106 Downloads (Pure)

Abstrakt

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(n^2 (f(l) + k) + mn^7), 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.

Originalsprog	Engelsk
Titel	Quantitative Evaluation of Systems : 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings
Redaktører	Anabelle McIver, Andras Horvath
Antal sider	17
Forlag	Springer
Publikationsdato	4 sep. 2018
Sider	339-355
ISBN (Trykt)	978-3-319-99153-5
ISBN (Elektronisk)	978-3-319-99154-2
DOI	https://doi.org/10.1007/978-3-319-99154-2_21
Status	Udgivet - 4 sep. 2018
Begivenhed	Quantitative Evaluation of Systems 2018 - Beijing, Kina Varighed: 4 sep. 2018 → 7 sep. 2018 http://www.qest.org/qest2018/

Konference

Konference	Quantitative Evaluation of Systems 2018
Land/Område	Kina
By	Beijing
Periode	04/09/2018 → 07/09/2018
Internetadresse	http://www.qest.org/qest2018/

Navn	Lecture Notes in Computer Science
Vol/bind	11024
ISSN	0302-9743

Emneord

semi-markov process
markov decision process
simulation
hemimetric

Adgang til dokumentet

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

mainAccepteret manuskript, 352 KB

Andre filer og links

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

Approximate Reasoning for Stochastic Markovian Systems
Mardare, R. & Larsen, K. G.
01/11/2015 → 31/10/2019
Projekter: Projekt › Forskning
IDEA4CPS: Foundations for Cyber-Physical Sytems
Larsen, K. G., Skou, A., Nielsen, B., Bulychev, P., Ravn, A. P. & Poulsen, D. B.
01/04/2011 → 30/04/2015
Projekter: Projekt › Forskning

Citationsformater

Pedersen, M. R., Bacci, G., Larsen, K. G., & Mardare, R. I. (2018). A Hemimetric Extension of Simulation for Semi-Markov Decision Processes. I A. McIver, & A. Horvath (red.), Quantitative Evaluation of Systems: 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings (s. 339-355). Springer. Lecture Notes in Computer Science Bind 11024 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. red. / Anabelle McIver ; Andras Horvath. Springer, 2018. s. 339-355 (Lecture Notes in Computer Science, Bind 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 = "null ; 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. i A McIver & A Horvath (red), Quantitative Evaluation of Systems: 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings. Springer, Lecture Notes in Computer Science, bind 11024, s. 339-355, Quantitative Evaluation of Systems 2018, Beijing, Kina, 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. red. / Anabelle McIver; Andras Horvath. Springer, 2018. s. 339-355 (Lecture Notes in Computer Science, Bind 11024).

Publikation: Bidrag til bog/antologi/rapport/konference proceeding › Konferenceartikel i proceeding › Forskning › 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

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. I McIver A, Horvath A, red., Quantitative Evaluation of Systems: 15th International Conference, QEST 2018, Beijing, China, September 4-7, 2018, Proceedings. Springer. 2018. s. 339-355. (Lecture Notes in Computer Science, Bind 11024). doi: 10.1007/978-3-319-99154-2_21

A Hemimetric Extension of Simulation for Semi-Markov Decision Processes

Abstrakt

Konference

Emneord

Adgang til dokumentet

Andre filer og links

Fingeraftryk

Projekter

Approximate Reasoning for Stochastic Markovian Systems

IDEA4CPS: Foundations for Cyber-Physical Sytems

Citationsformater