DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2015.103

Markov Decision Processes and Stochastic Games with Total Effective Payoff

Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

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.

Cite as

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino. Markov Decision Processes and Stochastic Games with Total Effective Payoff. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 103-115, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{boros_et_al:LIPIcs.STACS.2015.103,
  author =	{Boros, Endre and Elbassioni, Khaled and Gurvich, Vladimir and Makino, Kazuhisa},
  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 =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.103},
  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}
}

Search Results

Documents authored by Gurvich, Vladimir

Markov Decision Processes and Stochastic Games with Total Effective Payoff

Abstract

Cite as

Thanks for your feedback!

Could not send message