Markov decision processes and stochastic games with total effective payoff

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Research output: Contribution to journalArticlepeer-review


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
StateAccepted/In press - May 28 2018

All Science Journal Classification (ASJC) codes

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


  • 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