Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.orl.2013.04.006 | Operations Research Letters |
Keywords | Field | DocType |
Markov decision processes,Zero-sum stochastic games,Discounted stochastic games,Pseudo-polynomial algorithms,Saddle point | Combinatorics,Mathematical optimization,Saddle point,Discounting,Markov decision process,Approximations of π,Perfect information,Mathematics,Randomness,Stochastic game,Bounded function | Journal |
Volume | Issue | ISSN |
41 | 4 | 0167-6377 |
Citations | PageRank | References |
2 | 0.38 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Endre Boros | 1 | 1779 | 155.63 |
| Khaled M. Elbassioni | 2 | 287 | 42.96 |
| Vladimir Gurvich | 3 | 688 | 68.89 |
| Kazuhisa Makino | 4 | 1088 | 102.74 |