License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2019.32
URN: urn:nbn:de:0030-drops-115940
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11594/
Go to the corresponding LIPIcs Volume Portal

Bordais, Benjamin ; Guha, Shibashis ; Raskin, Jean-François

Expected Window Mean-Payoff

pdf-format:
LIPIcs-FSTTCS-2019-32.pdf (0.6 MB)

Abstract

We study the expected value of the window mean-payoff measure in Markov decision processes (MDPs) and Markov chains (MCs). The window mean-payoff measure strengthens the classical mean-payoff measure by measuring the mean-payoff over a window of bounded length that slides along an infinite path. This measure ensures better stability properties than the classical mean-payoff. Window mean-payoff has been introduced previously for two-player zero-sum games. As in the case of games, we study several variants of this definition: the measure can be defined to be prefix-independent or not, and for a fixed window length or for a window length that is left parametric. For fixed window length, we provide polynomial time algorithms for the prefix-independent version for both MDPs and MCs. When the length is left parametric, the problem of computing the expected value on MDPs is as hard as computing the mean-payoff value in two-player zero-sum games, a problem for which it is not known if it can be solved in polynomial time. For the prefix-dependent version, surprisingly, the expected window mean-payoff value cannot be computed in polynomial time unless P=PSPACE. For the parametric case and the prefix-dependent case, we manage to obtain algorithms with better complexities for MCs.

BibTeX - Entry

@InProceedings{bordais_et_al:LIPIcs:2019:11594,
  author =	{Benjamin Bordais and Shibashis Guha and Jean-Fran{\c{c}}ois Raskin},
  title =	{{Expected Window Mean-Payoff}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11594},
  URN =		{urn:nbn:de:0030-drops-115940},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.32},
  annote =	{Keywords: mean-payoff, Markov decision processes, synthesis}
}

Keywords: mean-payoff, Markov decision processes, synthesis
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI