A limit theorem for Markov decision processes

Mathias Staudigl

doi:10.3934/jdg.2014.1.639

Article Contents

2014, Volume 1, Issue 4: 639-659. Doi: 10.3934/jdg.2014.1.639

This issue Previous Article Payoff performance of fictitious play Next Article

A limit theorem for Markov decision processes

Mathias Staudigl^1,

1.
Center for Mathematical Economics, University Bielefeld, Postfach 100131, 33501 Bielefeld

Received: January 2014

Revised: June 2014

Published: October 2014

Abstract / Introduction Related Papers Cited by

Abstract

In this paper I prove a deterministic approximation theorem for a sequence of Markov decision processes with finitely many actions and general state spaces as they appear frequently in economics, game theory and operations research. Using viscosity solution methods no a-priori differentiabililty assumptions are imposed on the value function.

Keywords:

Mathematics Subject Classification: Primary: 49L20, 49L25, 90C40; Secondary: 60J20, 60F17.

Citation:

Related Papers

Cited by

References

[1]	R. J. Aumann and M. Maschler, Repeated Games with Incomplete Information, MIT Press, Cambridge, MA, 1995.
[2]	M. Bardi and I. Capuzzo-Dolcetta, Optimal control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser - Systems & Control: Foundations & Applications, 1997.doi: 10.1007/978-0-8176-4755-1.
[3]	D. P. Bertsekas and S. E. Shreve, Stochastic Optimal Control: The Discrete Time Case, Academic Press, 1978.
[4]	P. Billingsley, Convergence of Probability Measures, Wiley Series in Probability and Statistics, John Wiley & Sons, Inc., New York, 1999.doi: 10.1002/9780470316962.
[5]	I. Capuzzo-Dolcetta and H. Ishii, Approximate solutions of the Bellman equation of deterministic control theory, Applied Mathematics & Optimization, 11 (1984), 161-181.doi: 10.1007/BF01442176.
[6]	P. Cardaliaguet, C. Rainer, D. Rosenberg and N. Vieille, Markov games with frequent actions and incomplete information, 2013. arXiv:1307.3365v1 [math.OC].
[7]	N. El Karoui, D. Nguyen and M. Jeanblanc-Picqué, Compactification methods in the control of degenerate diffusions: Existence of an optimal control, Stochastics, 20 (1987), 169-219.doi: 10.1080/17442508708833443.
[8]	S. N. Ethier and T. G. Kurtz, Markov Processes: Characterization and Convergence, Wiley, New York, 1986.doi: 10.1002/9780470316658.
[9]	M. Falcone, A numerical approach to the infinite horizon problem of deterministic control theory, Applied Mathematics & Optimization, 15 (1987), 1-13.doi: 10.1007/BF01442644.
[10]	W. H. Fleming, The convergence problem for differential games, Journal of Mathematical Analysis and Applications, 3 (1961), 102-116.doi: 10.1016/0022-247X(61)90009-9.
[11]	N. Gast, B. Gaujal and J.-Y. Le Boudec, Mean field for markov decision processes: From discrete to continuous optimization, IEEE Transactions on Automatic Control, 57 (2012), 2266-2280.doi: 10.1109/TAC.2012.2186176.
[12]	F. Gensbittel, Continuous-time Limit of Dynamic Games with Incomplete Information and a More Informed Player, hal-00910970, version 1, 2013.
[13]	R. Gonzalez and E. Rofman, On deterministic control problems: An approximation procedure for the optimal cost I. the stationary problem, SIAM Journal on Control and Optimization, 23 (1985), 242-266.doi: 10.1137/0323018.
[14]	X. Guo and O. Hernández-Lerma, Nonzero-sum games for continuous-time markov chains with unbounded discounted payoffs, Journal of Applied Probability, 42 (2005), 303-320.doi: 10.1239/jap/1118777172.
[15]	O. Hernández-Lerma and J. B. Laserre, Discrete-Time Markov Control Processes: Basic Optimality criteria, Springer-Verlag, 1996.doi: 10.1007/978-1-4612-0729-0.
[16]	J. Hörner, T. Sugaya, S. Takahashi and N. Vieille, Recursive methods in discounted stochastic games: An algorithm for $\delta\rightarrow 1$ and a folk theorem, Econometrica, 79 (2011), 1277-1318.doi: 10.3982/ECTA9004.
[17]	O. Kallenberg, Foundations of Modern Probability, Springer, New York [u.a.], 2nd edition, 2002.doi: 10.1007/978-1-4757-4015-8.
[18]	I. Karatzas and S. E. Shreve, Brownian Motion and Stochastic Calculus, Springer-Verlag, 2nd edition, 2000.
[19]	H. J. Kushner, Weak convergence Methods and Singularly Perturbed Stochastic Control and Filtering Problems, Birkhäuser - Systems & Control: Foundations & Applications, Boston, MA, 1990.doi: 10.1007/978-1-4612-4482-0.
[20]	H. J. Kushner and P. Dupuis, Numerical Methods for Stochastic Control Problems in Continuous Time, Springer, New York, 2nd edition, 2001.doi: 10.1007/978-1-4613-0007-6.
[21]	A. Neyman, Stochastic games with short-stage duration, Dynamic Games and Applications, 3 (2013), 236-278.doi: 10.1007/s13235-013-0083-x.
[22]	A. S. Nowak and T. E. S. Raghavan, Existence of stationary correlated equilibria with symmetric information for discounted stochastic games, Mathematics of Operations Research, 17 (1992), 519-526.doi: 10.1287/moor.17.3.519.
[23]	W. H. Sandholm and M. Staudigl, Stochastic stability in the small noise double limit, I: Theory, Unpublished manuscript, University of Wisconsin and Bielefeld University, 2014.
[24]	W. H. Sandholm and M. Staudigl, Stochastic stability in the small noise double limit, II: The logit model, Unpublished manuscript, University of Wisconsin and Bielefeld University, 2014.
[25]	Y. Sannikov, Games with imperfectly observable actions in continuous time, Econometrica, 75 (2007), 1285-1329.doi: 10.1111/j.1468-0262.2007.00795.x.
[26]	S. Soulaimani, M. Quincampoix and S. Sorin, Repeated games and qualitative differential games: Approachability and comparison of strategies, SIAM Journal on Control and Optimization, 48 (2009), 2461-2479.doi: 10.1137/090749098.
[27]	M. Staudigl, Stochastic stability in asymmetric binary choice coordination games, Games and Economic Behavior, 75 (2012), 372-401.doi: 10.1016/j.geb.2011.11.003.
[28]	M. Staudigl and J.-H. Steg, On repeated games with imperfect public monitoring: From discrete to continuous time, Bielefeld University, unpublished manuscript, 2014.
[29]	J. Warga, Optimal Control of Differential and Functional Equations, Academic Press, New York-London, 1972.