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

Endre Boros; Khaled Elbassioni; Vladimir Gurvich; Kazuhisa Makino

doi:10.1016/j.orl.2013.04.006

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

Endre Boros
, Khaled Elbassioni
, Vladimir Gurvich
, Kazuhisa Makino

Electrical Engineering

Research output: Contribution to journal › Article › peer-review

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 language	British English
Pages (from-to)	357-362
Number of pages	6
Journal	Operations Research Letters
Volume	41
Issue number	4
DOIs	https://doi.org/10.1016/j.orl.2013.04.006
State	Published - 2013

Keywords

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

Access to Document

10.1016/j.orl.2013.04.006

OpenUrl availability

Full text

Cite this

@article{748f8835bb7546bb9e725f7bca51af99,

title = "On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness",

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.",

keywords = "Discounted stochastic games, Markov decision processes, Pseudo-polynomial algorithms, Saddle point, Zero-sum stochastic games",

author = "Endre Boros and Khaled Elbassioni and Vladimir Gurvich and Kazuhisa Makino",

note = "Funding Information: The authors are thankful to the anonymous referee for the careful reading and helpful suggestions. The first author also thanks for partial support the NSF (Grants CMMI-0856663 and IIS-1161476 ). The fourth author was partially supported by Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology of Japan.",

year = "2013",

doi = "10.1016/j.orl.2013.04.006",

language = "British English",

volume = "41",

pages = "357--362",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

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

AU - Boros, Endre

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

AU - Makino, Kazuhisa

N1 - Funding Information: The authors are thankful to the anonymous referee for the careful reading and helpful suggestions. The first author also thanks for partial support the NSF (Grants CMMI-0856663 and IIS-1161476 ). The fourth author was partially supported by Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology of Japan.

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Discounted stochastic games

KW - Markov decision processes

KW - Pseudo-polynomial algorithms

KW - Saddle point

KW - Zero-sum stochastic games

UR - https://www.scopus.com/pages/publications/84877625389

U2 - 10.1016/j.orl.2013.04.006

DO - 10.1016/j.orl.2013.04.006

M3 - Article

AN - SCOPUS:84877625389

SN - 0167-6377

VL - 41

SP - 357

EP - 362

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

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

Abstract

Keywords

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Cite this