License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.103
URN: urn:nbn:de:0030-drops-49074
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4907/
Go to the corresponding LIPIcs Volume Portal

Boros, Endre ; Elbassioni, Khaled ; Gurvich, Vladimir ; Makino, Kazuhisa

Markov Decision Processes and Stochastic Games with Total Effective Payoff

pdf-format:
7.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{boros_et_al:LIPIcs:2015:4907,
  author =	{Endre Boros and Khaled Elbassioni and Vladimir Gurvich and Kazuhisa Makino},
  title =	{{Markov Decision Processes and Stochastic Games with Total Effective Payoff}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{103--115},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4907},
  URN =		{urn:nbn:de:0030-drops-49074},
  doi =		{10.4230/LIPIcs.STACS.2015.103},
  annote =	{Keywords: Markov decision processes, undiscounted stochastic games, linear programming, mean payoff, total payoff}
}

Keywords: Markov decision processes, undiscounted stochastic games, linear programming, mean payoff, total payoff
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI