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

The paper concerns convergence and asymptotic statistics for stochastic approximation driven by Markovian noise: θₙ₊₁= θₙ + αn + 1 f(θₙ, Φₙ₊₁) \,, n≥ 0, in which each θₙ∈ᵈ, \ Φₙ \ is a Markov chain on a general state space X with stationary distribution π, and f:ᵈ× X →ᵈ. In addition to standard Lipschitz bounds on f, and conditions on the vanishing step-size sequence \αₙ\, it is assumed that the associated ODE is globally asymptotically stable with stationary point denoted θ^*, where f(θ)=E[f(θ,Φ)] with Φ~π. Moreover, the ODE@∞ defined with respect to the vector field, f_∞(θ):= limr→∞ r⁻¹ f(rθ) \,, θ∈ᵈ, is asymptotically stable. The main contributions are summarized as follows: (i) The sequence θ is convergent if Φ is geometrically ergodic, and subject to compatible bounds on f. The remaining results are established under a stronger assumption on the Markov chain: A slightly weaker version of the Donsker-Varadhan Lyapunov drift condition known as (DV3). (ii) A Lyapunov function is constructed for the joint process \θₙ,Φₙ\ that implies convergence of \ θₙ\ in L₄. (iii) A functional CLT is established, as well as the usual one-dimensional CLT for the normalized error zₙ:= (θₙ-θ^*)/√αₙ. Moment bounds combined with the CLT imply convergence of the normalized covariance, limn → ∞ E [ zₙ zₙT ] = Σ_θ, where Σ_θ is the asymptotic covariance appearing in the CLT. (iv) An example is provided where the Markov chain Φ is geometrically ergodic but it does not satisfy (DV3). While the algorithm is convergent, the second moment is unbounded.