Convergence of stochastic approximation for Lyapunov stable dynamics : a proof from rst principles
In this short note we present a proof, aimed at beginners, of the convergence of the stochastic approximation recursion i+1 = i+ i+1h( i)+ i+1 i+1 under the classical 0-level Kushner-Clark noise condition when the underlying dynamic is Lyapunov stable. The technique of proof relies on simple calculus arguments and bypasses the need for the introduction of the associated continuous time ODE. Future work includes the extension of the result to the case where the 0-level Kushner-Clark condition is replaced with a r-level condition for r > 0 [2]. We study the convergence of the recursion i+1 = i + i+1h( i) + i+1 i+1; for a given function h : ! R , a sequence of stepsizes f ig and a noise sequence f ig under simple and veriable conditions. We dene for any T > 0 m(n; T ) := max ( j n : j X