Delayed Nondeterminism in Continuous-Time Markov Decision Processes

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

32 Citations (Scopus)

Abstract

Schedulers in randomly timed games can be classified as to whether they use timing information or not. We consider continuous-time Markov decision processes (CTMDPs) and define a hierarchy of positional (P) and history-dependent (H) schedulers which induce strictly tighter bounds on quantitative properties on CTMDPs. This classification into time abstract (TA), total time (TT) and fully time-dependent (T) schedulers is mainly based on the kind of timing details that the schedulers may exploit. We investigate when the resolution of nondeterminism may be deferred. In particular, we show that TTP and TAP schedulers allow for delaying nondeterminism for all measures, whereas this does neither hold for TP nor for any TAH scheduler. The core of our study is a transformation on CTMDPs which unifies the speed of outgoing transitions per state.
Original languageUndefined
Title of host publicationFoundations of Software Science and Computational Structures
Place of PublicationBerlin
PublisherSpringer
Pages364-379
Number of pages16
ISBN (Print)978-3-642-00595-4
DOIs
Publication statusPublished - 27 Mar 2009

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume5504
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • METIS-264289
  • EWI-17102
  • IR-69312

Cite this

Neuhausser, M., Stoelinga, M. I. A., & Katoen, J. P. (2009). Delayed Nondeterminism in Continuous-Time Markov Decision Processes. In Foundations of Software Science and Computational Structures (pp. 364-379). [10.1007/978-3-642-00596-1_26] (Lecture Notes in Computer Science; Vol. 5504). Berlin: Springer. https://doi.org/10.1007/978-3-642-00596-1_26
Neuhausser, M. ; Stoelinga, Mariëlle Ida Antoinette ; Katoen, Joost P. / Delayed Nondeterminism in Continuous-Time Markov Decision Processes. Foundations of Software Science and Computational Structures. Berlin : Springer, 2009. pp. 364-379 (Lecture Notes in Computer Science).
@inproceedings{e54afc54ae3e458e87d4bbcf958a148a,
title = "Delayed Nondeterminism in Continuous-Time Markov Decision Processes",
abstract = "Schedulers in randomly timed games can be classified as to whether they use timing information or not. We consider continuous-time Markov decision processes (CTMDPs) and define a hierarchy of positional (P) and history-dependent (H) schedulers which induce strictly tighter bounds on quantitative properties on CTMDPs. This classification into time abstract (TA), total time (TT) and fully time-dependent (T) schedulers is mainly based on the kind of timing details that the schedulers may exploit. We investigate when the resolution of nondeterminism may be deferred. In particular, we show that TTP and TAP schedulers allow for delaying nondeterminism for all measures, whereas this does neither hold for TP nor for any TAH scheduler. The core of our study is a transformation on CTMDPs which unifies the speed of outgoing transitions per state.",
keywords = "METIS-264289, EWI-17102, IR-69312",
author = "M. Neuhausser and Stoelinga, {Mari{\"e}lle Ida Antoinette} and Katoen, {Joost P.}",
note = "10.1007/978-3-642-00596-1_26",
year = "2009",
month = "3",
day = "27",
doi = "10.1007/978-3-642-00596-1_26",
language = "Undefined",
isbn = "978-3-642-00595-4",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "364--379",
booktitle = "Foundations of Software Science and Computational Structures",

}

Neuhausser, M, Stoelinga, MIA & Katoen, JP 2009, Delayed Nondeterminism in Continuous-Time Markov Decision Processes. in Foundations of Software Science and Computational Structures., 10.1007/978-3-642-00596-1_26, Lecture Notes in Computer Science, vol. 5504, Springer, Berlin, pp. 364-379. https://doi.org/10.1007/978-3-642-00596-1_26

Delayed Nondeterminism in Continuous-Time Markov Decision Processes. / Neuhausser, M.; Stoelinga, Mariëlle Ida Antoinette; Katoen, Joost P.

Foundations of Software Science and Computational Structures. Berlin : Springer, 2009. p. 364-379 10.1007/978-3-642-00596-1_26 (Lecture Notes in Computer Science; Vol. 5504).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Delayed Nondeterminism in Continuous-Time Markov Decision Processes

AU - Neuhausser, M.

AU - Stoelinga, Mariëlle Ida Antoinette

AU - Katoen, Joost P.

N1 - 10.1007/978-3-642-00596-1_26

PY - 2009/3/27

Y1 - 2009/3/27

N2 - Schedulers in randomly timed games can be classified as to whether they use timing information or not. We consider continuous-time Markov decision processes (CTMDPs) and define a hierarchy of positional (P) and history-dependent (H) schedulers which induce strictly tighter bounds on quantitative properties on CTMDPs. This classification into time abstract (TA), total time (TT) and fully time-dependent (T) schedulers is mainly based on the kind of timing details that the schedulers may exploit. We investigate when the resolution of nondeterminism may be deferred. In particular, we show that TTP and TAP schedulers allow for delaying nondeterminism for all measures, whereas this does neither hold for TP nor for any TAH scheduler. The core of our study is a transformation on CTMDPs which unifies the speed of outgoing transitions per state.

AB - Schedulers in randomly timed games can be classified as to whether they use timing information or not. We consider continuous-time Markov decision processes (CTMDPs) and define a hierarchy of positional (P) and history-dependent (H) schedulers which induce strictly tighter bounds on quantitative properties on CTMDPs. This classification into time abstract (TA), total time (TT) and fully time-dependent (T) schedulers is mainly based on the kind of timing details that the schedulers may exploit. We investigate when the resolution of nondeterminism may be deferred. In particular, we show that TTP and TAP schedulers allow for delaying nondeterminism for all measures, whereas this does neither hold for TP nor for any TAH scheduler. The core of our study is a transformation on CTMDPs which unifies the speed of outgoing transitions per state.

KW - METIS-264289

KW - EWI-17102

KW - IR-69312

U2 - 10.1007/978-3-642-00596-1_26

DO - 10.1007/978-3-642-00596-1_26

M3 - Conference contribution

SN - 978-3-642-00595-4

T3 - Lecture Notes in Computer Science

SP - 364

EP - 379

BT - Foundations of Software Science and Computational Structures

PB - Springer

CY - Berlin

ER -

Neuhausser M, Stoelinga MIA, Katoen JP. Delayed Nondeterminism in Continuous-Time Markov Decision Processes. In Foundations of Software Science and Computational Structures. Berlin: Springer. 2009. p. 364-379. 10.1007/978-3-642-00596-1_26. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-00596-1_26