On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness

Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Kazuhisa Makino

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

It is shown that the discount factor needed to solve an undiscounted mean payoff stochastic game to optimality is exponentially close to 1, even in one-player games with a single random node and polynomially bounded rewards and transition probabilities. For the class of the so-called irreducible games with perfect information and a constant number of random nodes, we obtain a pseudo-polynomial algorithm using discounts.

Original languageEnglish (US)
Pages (from-to)357-362
Number of pages6
JournalOperations Research Letters
Volume41
Issue number4
DOIs
StatePublished - May 15 2013

All Science Journal Classification (ASJC) codes

  • Software
  • Applied Mathematics
  • Industrial and Manufacturing Engineering
  • Management Science and Operations Research

Keywords

  • Discounted stochastic games
  • Markov decision processes
  • Pseudo-polynomial algorithms
  • Saddle point
  • Zero-sum stochastic games

Fingerprint Dive into the research topics of 'On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness'. Together they form a unique fingerprint.

  • Cite this