Delayed Nondeterminism in Continuous-Time Markov Decision Processes

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

    35 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 languageEnglish
    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
    EventFoundations of Software Science and Computational Structures, 12th International Conference - York, UK
    Duration: 27 Mar 200927 Mar 2009

    Publication series

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

    Conference

    ConferenceFoundations of Software Science and Computational Structures, 12th International Conference
    Period27/03/0927/03/09

    Keywords

    • Markov decision process (MDP)
    • Continuous-time Markov decision process (CTMDP)

    Cite this