Stochastic approximation algorithms with constant step size whose average is cooperative. (English) Zbl 0983.62046

Benaïm, Michel; Hirsch, Morris W.

Ann. Appl. Probab. 9, No. 1, 216-241 (1999).

Summary: We consider stochastic approximation algorithms with constant step size whose average ordinary differential equation (ODE) is cooperative and irreducible. We show that, under mild conditions on the noise process, invariant measures and empirical occupations measures of the process weakly converge (as the time goes to infinity and the step size goes to zero) toward measures which are supported by stable equilibria of the ODE. These results are applied to analyzing the long-term behavior of a class of learning processes arising in game theory.

MSC:

62L20	Stochastic approximation
37N99	Applications of dynamical systems
34F05	Ordinary differential equations and systems with randomness
93E35	Stochastic learning and adaptive control
91A99	Game theory
91A22	Evolutionary games
91A40	Other game-theoretic models

Keywords:

cooperative vector fields; large deviations; weak convergence; theory of learning in games

References:

[1]	Azencott, R. and Ruget, G. (1977). Mélanges d’équations differentielles et grands écarts a la loi des grands nombres. Z. Wahrsch. Verw. Gebiete 38 1-54. Benaïm, M. (1996a). A dy namical sy stem approach to stochastic approximations. Siam J. Control Optim. 34 437-472. · Zbl 0372.60082 · doi:10.1007/BF00534169
[2]	Benaïm, M. (1998). Recursive algorithms, urn processes and chaining number of chain recurrent sets. Ergodic Theory Dy nam. Sy stems 18 53-87. · Zbl 0921.60061 · doi:10.1017/S0143385798097557
[3]	Benaïm, M. and Hirsch, M. W. (1995). Dy namics of Morse Smale urn processes. Ergodic Theory Dy nam. Sy stems 15 1005-1030. · Zbl 0846.60054 · doi:10.1017/S0143385700009767
[4]	Benaïm, M. and Hirsch, M. W. (1996). Asy mptotic pseudo-trajectories and chain-recurrent flows, with applications. J. Dy nam. Differential Equations 8 141-174. · Zbl 0878.58053 · doi:10.1007/BF02218617
[5]	Benaïm, M. and Hirsch, M. W. (1997). Information games, Dy namical sy stems and stochastic approximation. Discussion paper for IIASA workshop Oct 17-20.
[6]	Benveniste, A. Métivier, M. and Priouret, P. (1990). Stochastic Approximations and Adaptive Algorithms. Springer, New York. · Zbl 0752.93073
[7]	Chow, S. N. and Hale, J. (1982). Methods of Bifurcation Theory. Springer, New York. · Zbl 0487.47039
[8]	Conley, C. C. (1978). Isolated Invariant Sets and the Morse Index. Amer. Math. Soc., Providence, RI. · Zbl 0397.34056
[9]	Duflo, M. (1996). Algorithmes Stochastiques. Springer, Berlin. · Zbl 0849.62043
[10]	Duflo, M. (1997). Random Iterative Models. Springer, New York. · Zbl 0868.62069
[11]	Dupuis, P. (1988). Large deviations analysis of some recursive algorithms with state dependent noise. Ann. Probab. 6 1509-1536. · Zbl 0661.60045 · doi:10.1214/aop/1176991581
[12]	Dupuis, P. and Ellis R. S. (1997). A Weak Convergence Approach to the Theory of Large Deviations. Wiley, New York. · Zbl 0904.60001
[13]	Fort, J. C. and Pages, G. (1996). Asy mptotics behaviour of a Markovian constant step size algorithm. Siam J. Control Optim.
[14]	Freidlin, M. I. (1978). The averaging principle and theorems on large deviations. Russian Math. Survey s 33 117-176. · Zbl 0416.60029 · doi:10.1070/RM1978v033n05ABEH002516
[15]	Freidlin, M. I. and Wentzell, A. D. (1984). Random Perturbation of Dy namical Sy stems. Springer, New York. · Zbl 0522.60055
[16]	Fudenberg, D. and Levine, D. (1998). Theory of Learning in Games. MIT Press. · Zbl 0939.91004
[17]	Hirsch, M. W. (1985). Sy stems of differential equations that are competitive or cooperative II: convergence almost every where. SIAM J. Math. Anal. 16 423-439. Hirsch, M. W. (1988a). Sy stems of differential equations which are competitive or cooperative III: competing species. Nonlinearity 1 51-71. Hirsch, M. W. (1988b). Stability and convergence in strongly monotone dy namical sy stems. J. Reine Angew. Math. 383 1-53. · Zbl 0658.34023 · doi:10.1137/0516030
[18]	Hirsch, M. W. (1996). Chain transitive sets for smooth strongly monotone maps. Preprint, Univ. California, Berkeley.
[19]	Jiang, J.-F. (1991). Attractors for strongly monotone flows. J. Math. Anal. Appl. 162 210-222. · Zbl 0754.34055 · doi:10.1016/0022-247X(91)90188-6
[20]	Jiang, J.-F. and Yu, S.-X. (1995). Stable cy cles for attractors of strongly monotone discrete-time dy namical sy stems. Comm. Appl. Nonlinear Anal. 2 455-458.
[21]	Kifer, Y. (1988). Random Perturbation of Dy namical Sy stems. Birkhäuser, Boston.
[22]	Kunze, H. and Siegel, D. (1994). A graph theoretic approach to monotonicity with respect to initial conditions. In Comparison Methods and Stability Theory (X. Liu and D. Siegel, eds.) Dekker, New York. · Zbl 0808.34003
[23]	Kushner, H. J. and Clark, D. S. (1978). Stochastic Approximation Methods for Constrained and Unconstrained Sy stems. Springer, New York. · Zbl 0381.60004
[24]	Ljung, L. (1977). Analy sis of recursive stochastic algorithms. IEEE Trans. Automat. Control AC22 551-575. · Zbl 0362.93031 · doi:10.1109/TAC.1977.1101561
[25]	Mierczy ński, J. (1994). P-arcs in strongly monotone discrete-time dy namical sy stems. Differential Integral Equations 7 1473-1494. · Zbl 0864.58054
[26]	Smith, H. (1995). Monotone Dy namical Sy stems. Amer. Math. Soc., Providence, RI.
[27]	Taká c, P. (1992). Domains of attraction of generic -limit sets for strongly monotone discretetime semigroups. J. Reine Angew. Math. 423 101-173. · Zbl 0729.54022
[28]	Tere s cák, I. (1994). Dy namics of C1 smooth strongly monotone discrete-time dy namical sy stems.
[29]	Varadhan, (1984). Large Deviations and Applications. SIAM, Philadelphia. · Zbl 0549.60023
[30]	Weibull, J. W. (1995). Evolutionary Game Theory. MIT Press. · Zbl 0879.90206