Bordais, Benjamin ;
Guha, Shibashis ;
Raskin, JeanFrançois
Expected Window MeanPayoff
Abstract
We study the expected value of the window meanpayoff measure in Markov decision processes (MDPs) and Markov chains (MCs). The window meanpayoff measure strengthens the classical meanpayoff measure by measuring the meanpayoff over a window of bounded length that slides along an infinite path. This measure ensures better stability properties than the classical meanpayoff. Window meanpayoff has been introduced previously for twoplayer zerosum games. As in the case of games, we study several variants of this definition: the measure can be defined to be prefixindependent 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 prefixindependent 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 meanpayoff value in twoplayer zerosum games, a problem for which it is not known if it can be solved in polynomial time. For the prefixdependent version, surprisingly, the expected window meanpayoff value cannot be computed in polynomial time unless P=PSPACE. For the parametric case and the prefixdependent 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 JeanFran{\c{c}}ois Raskin},
title = {{Expected Window MeanPayoff}},
booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
pages = {32:132:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771313},
ISSN = {18688969},
year = {2019},
volume = {150},
editor = {Arkadev Chattopadhyay and Paul Gastin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11594},
URN = {urn:nbn:de:0030drops115940},
doi = {10.4230/LIPIcs.FSTTCS.2019.32},
annote = {Keywords: meanpayoff, Markov decision processes, synthesis}
}
04.12.2019
Keywords: 

meanpayoff, Markov decision processes, synthesis 
Seminar: 

39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Issue date: 

2019 
Date of publication: 

04.12.2019 