2026-07-27T03:51:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11594 2024-03-06T10:48:24Z ddc:004 open_access

Expected Window Mean-Payoff Bordais, Benjamin Guha, Shibashis Raskin, Jean-François mean-payoff Markov decision processes synthesis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Bordais and Shibashis Guha and Jean-François Raskin 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.32 urn:nbn:de:0030-drops-115940 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.32 eng https://creativecommons.org/licenses/by/3.0/legalcode