2026-07-20T05:39:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4907 2024-03-06T10:35:31Z ddc:004 open_access

Markov Decision Processes and Stochastic Games with Total Effective Payoff Boros, Endre Elbassioni, Khaled Gurvich, Vladimir Makino, Kazuhisa Markov decision processes undiscounted stochastic games linear programming mean payoff total payoff 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Endre Boros and Khaled Elbassioni and Vladimir Gurvich and Kazuhisa Makino 2015 Is Part Of LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2015.103 urn:nbn:de:0030-drops-49074 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.103 eng https://creativecommons.org/licenses/by/3.0/legalcode