1 Search Results for "Gurvich, Vladimir"

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-dev.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}
}
  • Refine by Author
  • 1 Boros, Endre
  • 1 Elbassioni, Khaled
  • 1 Gurvich, Vladimir
  • 1 Makino, Kazuhisa

  • Refine by Classification

  • Refine by Keyword
  • 1 Markov decision processes
  • 1 linear programming
  • 1 mean payoff
  • 1 total payoff
  • 1 undiscounted stochastic games

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact