The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning

The paper concerns the d-dimensional stochastic approximation recursion, θn+1= θn + αn + 1 f(θn, Phin+1) where Phin is a stochastic process on a general state space, satisfying a conditional Markov property that allows for parameter-dependent noise. The main results are established under additional conditions on the mean flow and a version of the Donsker-Varadhan Lyapunov drift condition known as (DV3): (i) An appropriate Lyapunov function is constructed that implies convergence of the estimates in L4. (ii) A functional central limit theorem (CLT) is established, as well as the usual one-dimensional CLT for the normalized error. Moment bounds combined with the CLT imply convergence of the normalized covariance textsfE[ zn znT ] to the asymptotic covariance in the CLT, where zn =: (θn-θ^*)/√αn. (iii) The CLT holds for the normalized version zPRn =: √n [θPRn -θ^*], of the averaged parameters θPRn =:n-1 sumk=1nθk, subject to standard assumptions on the step-size. Moreover, the covariance in the CLT coincides with the minimal covariance of Polyak and Ruppert. (iv) An example is given where f and barf are linear in θ, and Phi is a geometrically ergodic Markov chain but does not satisfy (DV3). While the algorithm is convergent, the second moment of θn is unbounded and in fact diverges. This arXiv version represents a major extension of the results in prior versions.The main results now allow for parameter-dependent noise, as is often the case in applications to reinforcement learning.