# Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 57 references that are in the map.
- First posted on arXiv 15 Feb 2023.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Statistical Inference for Model Parameters in Stochastic Gradient Descent](https://mlsanity.com/paper/1610.08637/) (2016)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Bootstrapping Fitted Q-Evaluation for Off-Policy Inference](https://mlsanity.com/paper/2102.03607/) (2021)
- [Asymptotic Optimality in Stochastic Optimization](https://mlsanity.com/paper/1612.05612/) (2016)
- [Online Covariance Matrix Estimation in Stochastic Gradient Descent](https://mlsanity.com/paper/2002.03979/) (2020)
- [The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2110.14427/) (2021)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Fast and Robust Online Inference with Stochastic Gradient Descent via Random Scaling](https://mlsanity.com/paper/2106.03156/) (2021)
- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [Statistical inference using SGD](https://mlsanity.com/paper/1705.07477/) (2017)
- [Online Statistical Inference for Stochastic Optimization via Kiefer-Wolfowitz Methods](https://mlsanity.com/paper/2102.03389/) (2021)
- [HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation](https://mlsanity.com/paper/1802.04876/) (2018)
- [On Constructing Confidence Region for Model Parameters in Stochastic Gradient Descent via Batch Means](https://mlsanity.com/paper/1911.01483/) (2019)

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

- [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)
- [Estimation and Inference in Distributional Reinforcement Learning](https://mlsanity.com/paper/2309.17262/) (2023)
- [Online covariance estimation for stochastic gradient descent under Markovian sampling](https://mlsanity.com/paper/2308.01481/) (2023)
- [Central Limit Theorem for Two-Timescale Stochastic Approximation with Markovian Noise: Theory and Applications](https://mlsanity.com/paper/2401.09339/) (2024)
- [A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.14172/) (2025)
- [Effectiveness of Constant Stepsize in Markovian LSA and Statistical Inference](https://mlsanity.com/paper/2312.10894/) (2023)
- [Asymptotic Time-Uniform Inference for Parameters in Averaged Stochastic Approximation](https://mlsanity.com/paper/2410.15057/) (2024)
- [Statistical Efficiency and Inference of Quantile Distributional Reinforcement Learning](https://mlsanity.com/paper/2607.08444/) (2026)
- [Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks](https://mlsanity.com/paper/2401.09665/) (2024)
- [Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD](https://mlsanity.com/paper/2409.17499/) (2024)
- [Optimism Stabilizes Thompson Sampling for Adaptive Inference](https://mlsanity.com/paper/2602.06014/) (2026)
- [Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs](https://mlsanity.com/paper/2505.18300/) (2025)
- [Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling](https://mlsanity.com/paper/2608.10896/) (2026)
- [Online Inference for Quantile Temporal Difference Learning in Distributional Reinforcement Learning](https://mlsanity.com/paper/2608.12973/) (2026)
- [Enhancing Stochastic Optimization for Statistical Efficiency Using ROOT-SGD with Diminishing Stepsize](https://mlsanity.com/paper/2407.10955/) (2024)
- [Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling](https://mlsanity.com/paper/2505.18327/) (2025)
- [Sharp asymptotic theory for Q-learning with LDTZ learning rate and its generalization](https://mlsanity.com/paper/2604.04218/) (2026)
- [Nonparametric Variance-Penalized Actor-Critic: Statistical Inference for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2609.14327/) (2026)
- [Limit Theory for Online Expectile Estimation under Short and Long Range Dependence](https://mlsanity.com/paper/2610.16030/) (2026)

## Abstract (arXiv)

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.