Berry--Esseen bounds for stochastic approximation with Markovian noise

This paper studies the convergence rate of the Polyak-Ruppert average estimator in one-dimensional linear stochastic approximation recursion driven by Markov chains, allowing the Markov chain to start from any initial distribution. Under the conditions of positive Harris recurrence, non-periodicity, and one-step domination, combined with the fourth-moment condition of the coefficient function with respect to the stationary distribution, this paper uses the exchangeable pair technique to prove that after deterministic bias correction for the average estimator, a Berry--Esseen bound of order n-α/2 can be obtained, where the step size exponent is α∈ (1/2, 1). Moreover, for the statistics without bias correction and after variance normalization, the asymptotic normal approximation error is asymptotically equivalent to a normal constant multiplied by n1/2 - α.