Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data

Many stochastic approximation (SA) algorithms evolve along a single trajectory, making uncertainty quantification challenging under nonlinear dynamics and Markov dependence. We develop an online inference framework for nonlinear SA with decreasing step sizes. Under local stability and verifiable conditions, we establish a functional central limit theorem for the partial-sum path. The proof uses a Poisson-equation decomposition to handle Markov dependence and a uniform bound to control endpoint-dependent remainders induced by decreasing step sizes. The resulting path limit yields self-normalized confidence intervals without estimating the asymptotic variance. Our primary construction uses a five-dimensional polynomial-series normalizer, has an asymptotic Student t5 pivot, and requires only constant memory. We apply the framework to Q-learning, including asynchronous tabular, projected linear, and entropy-regularized updates, as well as SGD for generalized linear models with Markov data and inference for the identified product in low-rank adaptation (LoRA). Across four settings, the polynomial-series method achieves near-nominal coverage, with shorter confidence intervals and lower computational cost than online bootstrap.