# Gaussian Approximation in Wasserstein-p: Markovian Martingale Differences and Stochastic Approximation

arXiv: https://arxiv.org/abs/2609.09480 · HTML: https://mlsanity.com/paper/2609.09480/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 27 references that are in the map.
- First posted on arXiv 8 Sep 2026.

## Builds on (most cited first, 7 of 7)

- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Normal Approximation for Stochastic Gradient Descent via Non-Asymptotic Rates of Martingale CLT](https://mlsanity.com/paper/1904.02130/) (2019)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation](https://mlsanity.com/paper/2401.13884/) (2024)
- [Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning](https://mlsanity.com/paper/2401.15719/) (2024)
- [Finite-Sample Wasserstein Error Bounds and Concentration Inequalities for Nonlinear Stochastic Approximation](https://mlsanity.com/paper/2602.02445/) (2026)

## Built on by (most cited first, 1 of 1)

- [Sharp Stationary Gaussian Approximation for Constant-Stepsize SGD](https://mlsanity.com/paper/2609.39144/) (2026)

## Abstract (arXiv)

We establish nonasymptotic Gaussian approximation bounds in higher-order Wasserstein distance Wp, p≥2, for deterministic matrix-weighted sums of multivariate Poisson martingale differences generated by uniformly ergodic Markov chains. Under an L(2+η)p-moment condition, η>0, we obtain the explicit bound Oleft(p3|A|42+pd1/4|A|21/2|A|42right), where A∈ℝn collects the moment sizes of the weighted increments. When these sizes are of order n-1/2, the bound achieves the first optimal O(n-1/2) rate for fixed p and d. Consequently, we also obtain the first optimal O(n-1/2) Wp Gaussian approximation rate for multivariate additive functionals of uniformly ergodic Markov chains. Our analysis develops two techniques for addressing the interplay between higher-order Wasserstein distance and temporal dependence. First, building on the Ornstein--Uhlenbeck relative-score approach of Fang and Koike (2023), we formulate the bound in terms of antisymmetric Stein couplings while retaining the conditional tensor structure. Second, we develop a refresh-then-maximal coupling that combines an independent first-step resampling, which preserves the desired Stein identity, with a subsequent maximal coupling that provides effective control of the coupling increment. We apply these bounds to nonlinear Markovian stochastic approximation by decomposing normalized errors into matrix-weighted Poisson martingale sums and remainders. This yields the first sharp Wp Gaussian approximation rates for both last iterates and Polyak--Ruppert averages. In particular, the optimized rates are O(n-1/3) for polynomial-stepsize last iterates and O(n-1/4) for Polyak--Ruppert averages, with an O(n-1/2) rate for harmonic-stepsize last iterates under an additional spectral condition.