A New Converse Lyapunov Theorem for Global Exponential Stability and Applications to Stochastic Approximation

In this paper, we give a simple and direct proof of the convergence of the stochastic approximation algorithm under suitable conditions. The main result here can be compared to that in Borkar and Meyn (2000), which is based on the ODE method, that is, showing that the sample paths of the algorithm converge towards the deterministic trajectories of an associated ODE. In contrast, the present proof is based on martingale theory, first proposed in Gladyshev (1965). Consequently, there are fewer assumptions here compared to previous papers. An important part of the proof is a new converse Lyapunov theorem for global exponential stability. Aside from its application to stochastic approximation theory, this new converse Lyapunov theorem would be useful for researchers in stability theory.