文章基本信息

标题：Markov Decision Processes and Stochastic Games with Total Effective Payoff
本地全文：下载
作者：Endre Boros ; Khaled Elbassioni ; Vladimir Gurvich 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：30
页码：103-115
DOI：10.4230/LIPIcs.STACS.2015.103
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Markov decision processes; undiscounted stochastic games; linear programming; mean payoff; total payoff