The ODE method for asymptotic statistics in stochastic approximation and reinforcement learning

The paper concerns the stochastic approximation recursion, θn+1=θn+αn+1f(θn,Φn+1),n≥0, where the estimates {θn} evolve on Rd, and Φ:={Φn} is a stochastic process on a general state space, satisfying a conditional Markov property that allows for parameter-dependent noise. In addition to standard Lipschitz assumptions and conditions on the vanishing step-size sequence, it is assumed that the associated mean flow ddtϑt=f‾(ϑt) is globally asymptotically stable, with stationary point denoted θ∗. The main results are established under additional conditions on the mean flow and an extension of the Donsker–Varadhan Lyapunov drift condition known as (DV3): (i) A Lyapunov function is constructed for the joint process {θn,Φn} 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 E[znzn⊺] to the asymptotic covariance ΣΘ in the CLT, where zn:=(θn−θ∗)/α n. (iii) The CLT holds for the normalized averaged parameters znPR:=n(θ nPR−θ∗), with θnPR:=n−1∑k=1nθk, subject to standard assumptions on the step-size. Moreover, the covariance of znPR converges to ΣΘPR, the minimal covariance of Polyak and Ruppert. (iv) An example is given where f and f‾ are linear in θ, and Φ 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.