Stochastic approximation algorithms with constant step size whose average is cooperative
Open Access
- 1 February 1999
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 9 (1), 216-241
- https://doi.org/10.1214/aoap/1029962603
Abstract
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.Keywords
This publication has 17 references indexed in Scilit:
- Recursive algorithms, urn processes and chaining number of chain recurrent setsErgodic Theory and Dynamical Systems, 1998
- Asymptotic pseudotrajectories and chain recurrent flows, with applicationsJournal of Dynamics and Differential Equations, 1996
- Dynamics of Morse-Smale urn processesErgodic Theory and Dynamical Systems, 1995
- Domains of attraction of generic ω-limit sets for strongly monotone discrete-time semigroups.Journal für die reine und angewandte Mathematik (Crelles Journal), 1992
- Attractors in strongly monotone flowsJournal of Mathematical Analysis and Applications, 1991
- Gaussian Approximations to the AlgorithmsPublished by Springer Nature ,1990
- Large Deviations Analysis of Some Recursive Algorithms with State Dependent NoiseThe Annals of Probability, 1988
- Systems of Differential Equations that are Competitive or Cooperative II: Convergence Almost EverywhereSIAM Journal on Mathematical Analysis, 1985
- THE AVERAGING PRINCIPLE AND THEOREMS ON LARGE DEVIATIONSRussian Mathematical Surveys, 1978
- Analysis of recursive stochastic algorithmsIEEE Transactions on Automatic Control, 1977