Thomas Brihaye ; Florent Delgrange ; Youssouf Oualhadj ; Mickael Randour - Life is Random, Time is Not: Markov Decision Processes with Window Objectives

lmcs:5968 - Logical Methods in Computer Science, December 14, 2020, Volume 16, Issue 4 -
Life is Random, Time is Not: Markov Decision Processes with Window Objectives

Authors: Thomas Brihaye ; Florent Delgrange ; Youssouf Oualhadj ; Mickael Randour

    The window mechanism was introduced by Chatterjee et al. to strengthen classical game objectives with time bounds. It permits to synthesize system controllers that exhibit acceptable behaviors within a configurable time frame, all along their infinite execution, in contrast to the traditional objectives that only require correctness of behaviors in the limit. The window concept has proved its interest in a variety of two-player zero-sum games because it enables reasoning about such time bounds in system specifications, but also thanks to the increased tractability that it usually yields. In this work, we extend the window framework to stochastic environments by considering Markov decision processes. A fundamental problem in this context is the threshold probability problem: given an objective it aims to synthesize strategies that guarantee satisfying runs with a given probability. We solve it for the usual variants of window objectives, where either the time frame is set as a parameter, or we ask if such a time frame exists. We develop a generic approach for window-based objectives and instantiate it for the classical mean-payoff and parity objectives, already considered in games. Our work paves the way to a wide use of the window mechanism in stochastic models.

    Volume: Volume 16, Issue 4
    Published on: December 14, 2020
    Accepted on: October 17, 2020
    Submitted on: December 12, 2019
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Artificial Intelligence,Computer Science - Formal Languages and Automata Theory,Computer Science - Computer Science and Game Theory,Mathematics - Probability

    Linked data

    Source : ScholeXplorer IsCitedBy ARXIV 2001.03894
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.concur.2020.24
    Source : ScholeXplorer IsCitedBy DOI 10.46298/lmcs-18(1:11)2022
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2001.03894
    • 10.46298/lmcs-18(1:11)2022
    • 10.46298/lmcs-18(1:11)2022
    • 10.48550/arxiv.2001.03894
    • 10.4230/lipics.concur.2020.24
    • 2001.03894
    Games Where You Can Play Optimally with Arena-Independent Finite Memory
    Bouyer, Patricia ; Roux, St├ęphane Le ; Oualhadj, Youssouf ; Randour, Mickael ; Vandenhove, Pierre ;


    Consultation statistics

    This page has been seen 429 times.
    This article's PDF has been downloaded 202 times.