Policy improvement for perfect information additive reward andadditive transition stochastic games with discounted and average payoffs

Matthew Bourque; T. E. S. Raghavan

doi:10.3934/jdg.2014.1.347

Article Contents

2014, Volume 1, Issue 3: 347-361. Doi: 10.3934/jdg.2014.1.347

This issue Previous Article Asymptotic behavior of compositions of under-relaxed nonexpansive operators Next Article Pure and Random strategies in differential game with incomplete informations

Policy improvement for perfect information additive reward and additive transition stochastic games with discounted and average payoffs

Matthew Bourque^1, and
T. E. S. Raghavan^2,

1.
Department of Mathematics and Statistics, Loyola University Chicago, 1032 W. Sheridan Road, Chicago, IL 60660
2.
Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago, 322 Science and Engineering Offices (M/C 249), 851 S. Morgan Street, Chicago, IL 60607-7045

Received: November 30, 2012

Revised: November 30, 2013

Published: June 2014

Abstract Related Papers Cited by

Abstract

We give a policy improvement algorithm for additive reward, additive transition (ARAT) zero-sum two-player stochastic games for both discounted and average payoffs. The class of ARAT games includes perfect information games.

Keywords:

Mathematics Subject Classification: Primary: 91A15, 91A05; Secondary: 90C40.

Citation:

Related Papers

Cited by

References

[1]	M. Akian, J. Cochet-Terrasson, S. Detournay and S. Gaubert, Policy iteration algorithm for zero-sum multichain stochastic games with mean payoff and perfect information, preprint arXiv:1208.0446
[2]	K. Avrachenkov, L. Cottatellucci and L. Maggi, Algorithms for uniform optimal strategies in two-player zero-sum stochastic games with perfect information, Operations Research Letters, 40 (2012), 56-60.doi: 10.1016/j.orl.2011.10.005.
[3]	D. Blackwell, Discrete dynamic programming, The Annals of Mathematical Statistics, 33 (1962), 719-726.doi: 10.1214/aoms/1177704593.
[4]	J. Cochet-Terrasson and S. Gaubert, A policy iteration algorithm for zero-sum stochastic games with mean payoff, Comptes Rendus Mathematique, 343 (2006), 377-382.doi: 10.1016/j.crma.2006.07.011.
[5]	J. Cochet-Terrasson, G. Cohen, S. Gaubert, M. Mc Gettrick and J.-p. Quadrat, Numerical computation of spectral elements in max-plus algebra, in Proceedings SSC'98 (IFAC Conference on System Structure and Control), Pergamon, Nantes, France, (1998), 667-674.
[6]	J. A. Filar and B. Tolwinski, On the algorithm of Pollatschek and Avi-ltzhak, in Stochastic Games And Related Topics (eds. T. E. S. Raghavan, T. S. Ferguson, T. Parthasarathy, O. J. Vrieze, W. Leinfellner, G. Eberlein and S. H. Tijs), Theory and Decision Library, 7, Springer, Netherlands, 1991, 59-70.doi: 10.1007/978-94-011-3760-7_6.
[7]	J, A. Filar and K, Vrieze, Competitive Markov Decision Processes, Springer, 1997.
[8]	B. L. Fox and D. M. Landi, An algorithm for identifying the ergodic subchains and transient states of a stochastic matrix, Commun. ACM, 11 (1968), 619-621.
[9]	A. Hordijk, R. Dekker and L. C. M. Kallenberg, Sensitivity-analysis in discounted Markovian decision problems, OR Spektrum, 7 (1985), 143-151.doi: 10.1007/BF01721353.
[10]	R. A. Howard, Dynamic Programming and Markov Process, The Technology Press of M.I.T., Cambridge, Mass.; John Wiley & Sons, Inc., New York-London, 1960.
[11]	R. G. Jeroslow, Asymptotic linear programming, Operations Research, 21 (1973), 1128-1141.doi: 10.1287/opre.21.5.1128.
[12]	J. G. Kemeny and J. L. Snell, Finite Markov Chains, The University Series in Undergraduate Mathematics, D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto-London-New York, 1960.
[13]	E. Kohlberg, Invariant half-lines of nonexpansive piecewise-linear transformations, Mathematics of Operations Research, 5 (1980), 366-372.doi: 10.1287/moor.5.3.366.
[14]	J.-F. Mertens and A. Neyman, Stochastic games have a value, Proceedings of the National Academy of Sciences of the United States of America, 79 (1982), 2145-2146.doi: 10.1073/pnas.79.6.2145.
[15]	T. Parthasarathy and T. E. S. Raghavan, An orderfield property for stochastic games when one player controls transition probabilities, Journal of Optimization Theory and Applications, 33 (1981), 375-392.doi: 10.1007/BF00935250.
[16]	T. E. S. Raghavan, S. H. Tijs and O. J. Vrieze, On stochastic games with additive reward and transition structure, Journal of Optimization Theory and Applications, 47 (1985), 451-464.doi: 10.1007/BF00942191.
[17]	T. E. S. Raghavan and Z. Syed, A policy-improvement type algorithm for solving zero-sum two-person stochastic games of perfect information, Mathematical Programming, 95 (2003), 513-532.doi: 10.1007/s10107-002-0312-3.
[18]	L. S. Shapley, Stochastic games, Proceedings of the National Academy of Sciences of the United States of America, 39 (1953), 1095-1100.doi: 10.1073/pnas.39.10.1095.
[19]	Z. U. Syed, Algorithms for Stochastic Games and Related Topics, Ph.D thesis, University of Illinois at Chicago, Chicago, IL, USA, 1999.
[20]	A. F. Veinott, On finding optimal policies in discrete dynamic programming with no discounting, The Annals of Mathematical Statistics, 37 (1966), 1284-1294.doi: 10.1214/aoms/1177699272.