@inproceedings{f860ee2db5ee4bb39b2340642b958cb2,
title = "Markov decision processes and stochastic games with total effective payoff",
abstract = "We consider finite Markov decision processes (MDPs) with undiscounted total effective payoff. We show that there exist uniformly optimal pure stationary strategies that can be computed by solving a polynomial number of linear programs. We apply this result to two-player zero-sum stochastic games with perfect information and undiscounted total effective payoff, and derive the existence of a saddle point in uniformly optimal pure stationary strategies.",
keywords = "Linear programming, Markov decision processes, Mean payoff, Total payoff, Undiscounted stochastic games",
author = "Endre Boros and Khaled Elbassioni and Vladimir Gurvich and Kazuhisa Makino",
note = "Publisher Copyright: {\textcopyright} 2015 LIPICS.; 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015 ; Conference date: 04-03-2015 Through 07-03-2015",
year = "2015",
month = feb,
day = "1",
doi = "10.4230/LIPIcs.STACS.2015.103",
language = "British English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
pages = "103--115",
editor = "Mayr, \{Ernst W.\} and Nicolas Ollinger",
booktitle = "32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015",
}