Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation

Stochastic approximation methods such as stochastic gradient descent and temporal-difference learning return either the last iterate or the Polyak--Ruppert average. We establish finite-sample Wasserstein- p Gaussian approximation bounds for both outputs under a common framework combining moment bounds for the normalized iterates with quantitative Gaussian approximation of the appropriately weighted driving noise. These bounds yield convergence of admissible moments and high probability bounds with Gaussian leading terms: heavier dependence on the confidence level is confined to a correction that vanishes with the sample size. We verify the framework's conditions for nonlinear stochastic approximation with independent or Markovian observations and linear stochastic approximation with Markovian observations, with applications to stochastic gradient descent and temporal-difference learning.