License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2019.8
URN: urn:nbn:de:0030-drops-109103
URL: http://drops.dagstuhl.de/opus/volltexte/2019/10910/
Go to the corresponding LIPIcs Volume Portal


Brihaye, Thomas ; Delgrange, Florent ; Oualhadj, Youssouf ; Randour, Mickael

Life Is Random, Time Is Not: Markov Decision Processes with Window Objectives

pdf-format:
LIPIcs-CONCUR-2019-8.pdf (0.6 MB)


Abstract

The window mechanism was introduced by Chatterjee et al. [Krishnendu Chatterjee et al., 2015] 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, thanks to the ability to reason about such time bounds in system specifications, but also the increased tractability that it usually yields. In this work, we extend the window framework to stochastic environments by considering the fundamental threshold probability problem in Markov decision processes for window objectives. That is, given such an objective, we want to synthesize strategies that guarantee satisfying runs with a given probability. We solve this problem 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.

BibTeX - Entry

@InProceedings{brihaye_et_al:LIPIcs:2019:10910,
  author =	{Thomas Brihaye and Florent Delgrange and Youssouf Oualhadj and Mickael Randour},
  title =	{{Life Is Random, Time Is Not: Markov Decision Processes with Window Objectives}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Wan Fokkink and Rob van Glabbeek},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10910},
  URN =		{urn:nbn:de:0030-drops-109103},
  doi =		{10.4230/LIPIcs.CONCUR.2019.8},
  annote =	{Keywords: Markov decision processes, window mean-payoff, window parity}
}

Keywords: Markov decision processes, window mean-payoff, window parity
Seminar: 30th International Conference on Concurrency Theory (CONCUR 2019)
Issue Date: 2019
Date of publication: 26.08.2019


DROPS-Home | Imprint | Privacy Published by LZI