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

详细信息    查看全文

• 作者：Endre Boros^a ; ^{boros@rutcor.rutgers.edu} ; Khaled Elbassioni^b ; ^{elbassio@mpi-inf.mpg.de} ; ^{kelbassioni@masdar.ac.ae} ; Vladimir Gurvich^a ; ^{gurvich@rutcor.rutgers.edu} ; Kazuhisa Makino^c ; ^{makino@kurims.kyoto-u.ac.jp}
• 关键词：Markov decision processes ; Zero-sum stochastic games ; Discounted stochastic games ; Pseudo-polynomial algorithms ; Saddle point
• 刊名：Operations Research Letters
• 出版年：2013
• 出版时间：July, 2013
• 年：2013
• 卷：41
• 期：4
• 页码：357-362
• 全文大小：275 K

文摘

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.