Markov decision processes and stochastic games with total effective payoff

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Research output: Contribution to journalArticle

Abstract

We consider finite Markov decision processes with undiscounted total effective payoff. We show that there exist uniformly optimal pure and stationary strategies that can be computed by solving a polynomial number of linear programs. This implies that in a two-player zero-sum stochastic game with perfect information and with total effective payoff there exists a stationary best response to any stationary strategy of the opponent. From this, we derive the existence of a uniformly optimal pure and stationary saddle point. Finally we show that mean payoff can be viewed as a special case of total payoff.

Original languageEnglish (US)
Pages (from-to)1-29
Number of pages29
JournalAnnals of Operations Research
DOIs
StateAccepted/In press - May 28 2018

All Science Journal Classification (ASJC) codes

  • Decision Sciences(all)
  • Management Science and Operations Research

Keywords

  • Equilibrium computation
  • Linear programming
  • Markov decision processes
  • Optimal stationary strategies
  • Stochastic games

Fingerprint Dive into the research topics of 'Markov decision processes and stochastic games with total effective payoff'. Together they form a unique fingerprint.

  • Cite this