Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data

arXiv:2302.07690 · math.ST, stat.ME, stat.ML, stat.TH · Submitted 2026-08-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data".

Jane: The paper was written by Xiang Li, Jiadong Liang and Zhihua Zhang from Peking University.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the show, everyone. Today we’re digging into a brand new paper that just hit arXiv, and the title alone is a mouthful — “Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data.” Jane, I’m going to need you to translate that for our listeners who don’t live and breathe math.

Jane: Happy to, Tom. So imagine you’re training a model that learns from data arriving one piece at a time, like a stream. The algorithm updates its parameters after every single observation. That’s stochastic approximation — it’s the engine behind a lot of reinforcement learning and online machine learning. The paper asks a really practical question: after all that learning, how do you know how confident you should be in the answer?

Tom: And that’s the “statistical inference” part. Usually, to get a confidence interval, you need to know how noisy your estimate is. But this paper says, hey, we can build that interval directly from the same trajectory the algorithm already produced. No extra runs, no estimating a complicated covariance matrix.

Jane: Exactly. And the “Markovian data” part is the twist. The data isn’t independent — each new observation depends on the previous one, like a robot moving through a hallway where its next step depends on where it is now. That dependence makes the math much harder, because the usual textbook tools assume independence.

Tom: So the authors — Xiang Li, Jiadong Liang, and Zhihua Zhang from Peking University — they’re tackling the hardest version of this problem. Nonlinear updates, dependent data, and they want to do it all online with constant memory. That’s a big deal.

Jane: It really is. And the implications go straight to Q-learning, which is how agents learn to make decisions in games and robotics. If you can get a confidence interval for the learned value of an action, you can decide when to stop exploring and start trusting the model.

Tom: Right, and that’s the hook for our next segment — we’re going to break down what they actually proved and why the proof is so clever. Stay with us.

Summary: Tom: So we’re back, and we’ve got the full team here. Jane, you set the stage — now let’s get into what the paper actually delivers. Lu, you’ve been staring at the proof — what’s the headline result?

Lu: The headline is a functional central limit theorem. That sounds scary, but here’s the plain version: if you look at the average of all the iterates the algorithm has produced so far, and you scale the error properly, the whole path of those averages — not just the final number — converges to a Brownian motion. That’s the mathematical object behind random walks and stock prices.

Jane: And why does the whole path matter, not just the endpoint? Because the path gives you a way to measure the noise scale from the data itself. The final error and the shape of the path share the same unknown scale, so when you take their ratio, that scale cancels out. That’s the self-normalization trick.

Meng: I’m the engineer here, so let me ask the practical question. Does this actually run on a real system? Because a lot of beautiful theory never makes it to production.

Lu: That’s the beautiful part, Meng. The main method they propose uses just five polynomial projections of the path — that’s eleven scalar accumulators in memory. The update per observation is constant time. No covariance estimation, no bootstrap replicas. It’s genuinely online.

Meng: So I can run this on a streaming pipeline without blowing up my memory budget. That’s actually a big deal for deployment.

Jane: And they prove the ratio converges to a Student’s t distribution with five degrees of freedom. That means the critical values are just printed in a textbook — you don’t need to simulate anything.

Tom: But the proof, Lu — you said it’s clever. What’s the hard part?

Lu: The hard part is that the data is Markovian, so the noise is correlated. They use a Poisson equation to decompose the noise into a martingale part plus remainders. The martingale part behaves nicely, but the remainders depend on the endpoint of the partial sum, and those are not martingales. Standard tools don’t apply.

Jane: And that’s where their Lemma four comes in — a uniform bound that controls those endpoint-dependent remainders for decreasing step sizes. That lemma is the technical heart of the paper.

Meng: So the theory is solid, but does it hold up in practice? I want to see numbers.

Tom: That’s exactly what we’re covering next — the experiments. They ran this on Q-learning, logistic regression, and even LoRA for fine-tuning. Stay tuned.

Improvements: Tom: We’re back, and now we get to the fun part — did it actually work? Meng, you wanted numbers, and the paper delivers. Five experiments, two hundred fifty replications each, ninety-five percent confidence intervals.

Meng: And the headline is that their main method, which they call P5 — that’s the five-polynomial normalizer — hits near-nominal coverage in four out of five settings. RiverSwim was the exception, and that’s because the value signal takes a long time to propagate through that chain.

Jane: So coverage is good, but what about the length of the intervals? A confidence interval that’s too wide is useless in practice.

Meng: That’s where P5 shines. In every experiment, it produced shorter intervals than the L2 bridge method, which was the previous state of the art for this kind of random-scaling inference. We’re talking three point six percent to ten point four percent shorter at the final checkpoint.

Lu: And compared to the online bootstrap — which is the standard practical baseline — the improvement is dramatic. The bootstrap intervals were two point four to two point eight times longer than P5, and the bootstrap needs ten perturbed recursions running in parallel. That’s a massive computational cost.

Tom: So the improvement here isn’t just a tweak — it’s a different philosophy. Instead of estimating the noise variance or running extra copies of the algorithm, you read the noise scale directly off the path you already have.

Jane: And that’s the real contribution. They also show the method works for projected linear Q-learning, entropy-regularized Q-learning, and even balanced LoRA — where the parameterization is non-identified, but the product you care about is identifiable.

Meng: The LoRA result is genuinely surprising to me. The factors B and A are not unique — you can rotate them and get the same product. But they prove that the product itself has stable dynamics, and you can build a confidence interval for it. That’s a clean solution to a messy problem.

Lu: And they handle the second-order term from updating both factors — that’s the η2 perturbation — by showing it doesn’t change the limit. That’s a nice touch of rigor.

Tom: So the improvements are real: shorter intervals, lower cost, constant memory, and coverage that holds up. But what does this mean for the field? That’s the question for our final segment.

Conclusion: Tom: Alright, let’s wrap this up. We’ve been talking about “Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data” — and honestly, this paper feels like it closes a gap that’s been open for a while.

Jane: It really does. Before this, if you wanted uncertainty quantification for Q-learning or Markov SGD, you had two choices: estimate a complicated covariance matrix, which is slow and unstable, or run a bootstrap with many parallel copies, which is expensive. This paper offers a third way — read the scale off the same trajectory you already have.

Meng: And from a deployment standpoint, that’s the difference between a method that lives in a paper and one that ships in a product. Constant memory, constant time per update, and the critical values are just a t-table. I could wire this into a monitoring dashboard tomorrow.

Lu: The theoretical contribution is just as important. The uniform lemma for decreasing step sizes — Lemma four — is a standalone tool. Anyone working on functional limit theorems for stochastic approximation is going to cite that lemma for years.

Jane: And the applications are broad. Q-learning, generalized linear models, LoRA — that covers a huge chunk of modern machine learning. The fact that they verified the conditions for each setting, rather than hand-waving, gives me confidence the method will transfer to other problems.

Tom: The authors also point to future work — quantitative rates for the convergence, optimal choices of the normalizer, and extending this to AdamW and Muon. So this isn’t the end of the road; it’s a foundation.

Meng: I’ll say this — if the next paper delivers coverage guarantees with a rate, I’m going to be very happy.

Tom: That’s a great note to end on. Thanks to Lu and Meng for joining us, and to our listeners for sticking with us through the math. We’re saying goodbye to this paper — it’s been a good one — and we’ll be back with the next arXiv gem soon. Until then, keep learning.

Xiang Li, Jiadong Liang, Zhihua Zhang

Peking University

math.ST, stat.ME, stat.ML, stat.TH

Submitted: 2026-08-10

Comments: This version substantially revises the manuscript and focuses on statistical inference. The weak-convergence-rate results in version 2 have been removed and will be studied in a separate paper. 47 pages

Code: https://github.com/lx10077/nonlinear-sa-inference

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 56/100

The gist: The paper develops an online inference framework for nonlinear stochastic approximation (SA) algorithms driven by a single Markov trajectory, addressing two key challenges: nonlinear recursion

Terminology

Summary

The paper develops an online inference framework for nonlinear stochastic approximation (SA) algorithms driven by a single Markov trajectory, addressing two key challenges: nonlinear recursion dynamics and serial dependence in observations. The central contribution is a functional central limit theorem (FCLT) for the partial-sum path of the iterate errors, which enables self-normalized confidence intervals without estimating the asymptotic variance.

The paper considers the SA recursion

[

x t+1 = x t - eta t H(x t, xi t),

]

where x in R d, (xi t) t 0 is a Markov chain with transition kernel P and invariant distribution mu, and H: R d times X to R d is the update function. The target x is a root of the mean field g(x):= integral H(x, xi), mu(d xi), so g(x) = 0. Because x t is F t-1-measurable, the conditional expectation EH(x t, xi t) F t-1 = PH(x t, xi t-1) generally differs from g(x t), making the update conditionally biased.

Theorem 1 (Functional central limit theorem). Under Assumptions 1–4, the linearly interpolated partial-sum process

[

T(r) = T-1/2 sum t=1 Tr(x t - x) + (Tr - Tr)(x Tr +1 - x), r in [0,1],

]

converges weakly in C([0,1], R d) under the uniform norm to G-1S 1/2W(times), where W is standard d-dimensional Brownian motion, G is the local Jacobian of the mean field at x, and S is the long-run covariance of the update noise at x. At r=1, this recovers the Polyak–Ruppert CLT: sqrt T (T - x) so N(0, G-1SG-).

Key assumptions:

  • Assumption 1 (Local mean field): g(x) = G(x-x) + r g(x) near x with r g(x)/x-x to 0, and every eigenvalue of G has strictly positive real part.

  • Assumption 2 (Poisson regularity): The Poisson equation U(x, xi) - PU(x, xi) = H(x, xi) - g(x) admits a solution for every x, with a global weighted Lipschitz bound in x and bounded p>2 moments at x.

  • Assumption 3 (Slowly decreasing step size): eta t to 0, (eta t-1-eta t)/eta t-1 squared to 0, t eta t to infinity, and sum t eta t squared < infinity. The canonical choice eta t = eta(t+1)-kappa for kappa in (1/2,1) satisfies this.

  • Assumption 4 (Path stability): Uniform p-th moment bounds, L squared consistency of the iterates, and negligibility of the accumulated local nonlinearity.

Proposition 1 provides a primitive verification route via V-geometric ergodicity: if the chain is V-geometrically ergodic and the update satisfies H(x, times) - H(y, times) V 1/p Cx-y, then the resolvent series U(x, xi) = sum k 0P k H(x, xi) - g(x) solves the Poisson equation and satisfies the required regularity.

Proposition 2 extends the FCLT to recursions with second-order perturbations of the form x t+1 = x t - eta t H(x t, xi t) + eta t squared zeta t, where zeta t is F t-measurable with bounded p-th moments.

Corollary 1 extends the FCLT from linear contrasts to smooth scalar functionals psi: R d to R satisfying a first-order expansion condition, yielding psi T(times) so sigma psi W(times) with sigma psi squared = v G-1SG-v for v = grad psi(x).

The proof uses a Poisson-equation decomposition. Define the martingale difference epsilon t = PU(x t, xi t-1) - U(x t, xi t). The decomposition

[

H(x t, xi t) - g(x t) = -eta t+1 over eta t epsilon t + nu t + c t

]

separates the update noise into a martingale term, a residual nu t, and a coboundary c t that telescopes. An auxiliary iterate t = x t - eta t PU(x t, xi t-1) absorbs the coboundary, leading to the recursion

[

t+1 = (I - eta t G) t + eta t epsilon t - r t - nu t,

]

where t = t - x and r t = r g(x t) + eta t G PU(x t, xi t-1).

The partial-sum error is then decomposed into four remainders: initialization, Poisson residuals, fixed-endpoint weight approximation, and endpoint-dependent weight change. The most delicate term is

[

R 3,T(n) = T-1/2 sum j=1 n (A j T - A j n) epsilon j,

]

where A j n = eta j sum k=j n X j+1 k with X j n = product i=j n (I - eta i G). Because these coefficients depend on the endpoint n, the process is not a martingale, so standard martingale maximal inequalities do not apply.

Lemma 4 (Uniform negligibility under decreasing step sizes) provides the required control: for a recursion z t+1 = (I - eta t G)z t + eta t d t with martingale differences d t and t Ed t p 2, one has

[

0 t Tz t+1 over sqrt T eta t+1 0.

]

The proof handles non-diagonalizable G via Jordan decomposition, using a diagonalizable case (Lemma 5) and a stability transfer lemma (Lemma 6).

The FCLT yields joint convergence

[

(sqrt T (T -), B T(times)) so (sigma v W(1), sigma v B(times)),

]

where Y t = v x t, = v x, and B T(r) = v T(r) - r T(1) is the observed bridge (fully computable since x cancels). For any continuous, scale-equivariant functional D: C 0([0,1]) to [0, infinity) that is positive almost surely at a Brownian bridge, the pivot

[

sqrt T (T -) over D(B T) so W(1) over D(B)

]

has a nuisance-free limit, yielding the confidence interval

[

[T - c 1-alpha,D D(B T) over sqrt T, T + c 1-alpha,D D(B T) over sqrt T].

]

Proposition 3 establishes a lower bound on the normalized expected asymptotic half-width alpha(D)-1(1-alpha/2), attained only by the textbook Gaussian interval with known variance.

Proposition 4 (Polynomial-series normalizer P K). For fixed K, define projections a j,T = integral 0 1 B T(r) r j-1 dr and D P K,T squared = K-1 a T K-1 a T with (K) jk = 1/(j+1)(k+1)(j+k+1). Then

[

sqrt T (T -) over D P K,T so t K,

]

the Student t distribution with K degrees of freedom. The interval uses t K,1-alpha/2 as critical value. The normalized expected asymptotic half-width is alpha,K = t K,1-alpha/2 sqrt 2/K, ((K+1)/2)/ (K/2) to-1(1-alpha/2) as K to infinity. The implementation uses 2K+1 scalar accumulators and O(K) operations per iteration.

Proposition 5 (Bridge-norm normalizers L m). For fixed m 1, define D L m,T = (integral 0 1 B T(r) m dr) 1/m. Then

[

Z L m,T:= sqrt T (T -) over D L m,T so W(1) over(integral 0 1 B(r) m dr) 1/m.

]

For even m, an online implementation uses m+2 scalar running sums and O(m) operations per iteration.

The framework is specialized to five applications:

1. Asynchronous tabular Q-learning (Proposition 6). Under a full-support behavior policy and unique optimal actions, the asynchronous update

[

q t+1(s,a) = q t(s,a) - eta t 1(s,a) = (S t,A t) (q t(s,a) - R t - gamma a' q t(S t+1,a'))

]

satisfies the FCLT with Jacobian G Q = D pi b(I d Q - gamma P), where D pi b is the diagonal stationary state-action mass matrix and selects the unique optimal action. The Jacobian is a nonsingular M-matrix, so all eigenvalues have positive real parts.

2. Projected linear Q-learning (Proposition 7). For the projected semi-gradient recursion on a compact convex set, the stability condition

[

gamma squared sum s d pi b(s) a phi(s,a) u squared < sum s,a d pi b(s) pi b(as) phi(s,a) u squared

]

for all nonzero u ensures convergence. The Jacobian is G phi = E pi b[phi(S,A) phi(S,A) - gamma phi(S',a(S'))].

3. Entropy-regularized tabular Q-learning (Proposition 8). Replacing the hard maximum by log-sum-exp with temperature tau > 0, the Jacobian is G tau = D pi b(I d Q - gamma P tau), where tau is the softmax selector at the soft optimal value. The smoothness of log-sum-exp removes the unique-optimal-action requirement.

4. Markov generalized linear stochastic gradients (Proposition 9). For H glm(theta, z t, y t) = b'(z t theta) - y tz t with a geometrically ergodic Markov covariate process, the Jacobian is G glm = E mu[b''(z theta)zz], assumed positive definite uniformly on the compact constraint set.

5. Balanced LoRA (Proposition 10). For the balanced factor updates

[

t+1 = B t - eta t (W t, xi t)A t, t+1 = A t - eta t B t (W t, xi t),

]

followed by balancing (B t+1,A t+1) = B(t+1, t+1), the product W t = B tA t follows the closed recursion

[

W t+1 = W t - eta t (W t, xi t)M R(W t) + M L(W t) (W t, xi t) + eta t squared (W t, xi t)W t(W t, xi t),

]

where M L(W) = (WW) 1/2 and M R(W) = (W W) 1/2. The local dynamics on the rank- r tangent space are governed by L[] = M R, + M L,, which is positive definite on the tangent space, so factor nonidentifiability creates no unstable direction for product inference. The target is a linear summary C = C, W F of the identified fitted product.

Five experiments use 250 independent replications, nominal 95% intervals, and eight checkpoints. The primary method is P 5 (five-dimensional polynomial-series normalizer), compared with L 2, L 4, Markov overlapping batch means (OBM), and online bootstrap with B=10 perturbed recursions.

Q-learning experiments: RiverSwim (asynchronous tabular), projected linear Q-learning, and entropy-regularized CliffWalking. At 10 5 updates, P 5 coverages are 91.2%, 95.2%, and 94.4%, with intervals 10.4%, 4.5%, and 6.4% shorter than L 2. Markov OBM under-covers (84.4%, 83.2%, 87.2%), while online bootstrap covers (94.4%, 92.4%, 91.2%) but with intervals 2.4–2.8 times longer.

Nonlinear Markov logistic SGD: At 10 5 updates, P 5 covers 94.4% with interval 4.3% shorter than L 2 (93.2%). Markov OBM covers 84.8% and online bootstrap 88.8%.

Balanced LoRA: At 10 5 updates, P 5 covers 96.8% with interval 3.6% shorter than L 2 (96.0%). Markov OBM and online bootstrap each cover 91.2%.

Computation: For 50,000 tabular-Q observations, P 5 stores 11 scalar accumulators and adds 18.1% to point-estimation runtime, versus 4.8% for L 2 and 7.8% for Markov OBM. The online bootstrap uses 11 times as many update-function evaluations and takes 2.36 times the runtime.

Ablation: Comparing P 5, P 10, P 20, L 2, L 4, L 6, average coverage across the five applications is 94.4%, 94.2%, and 92.5% for P 5, P 10, P 20, with mean length ratios relative to L 2 of 94.2%, 82.0%, and 73.5%. Larger K shortens intervals but makes coverage less stable, supporting P 5 as a balanced default.

The paper identifies three future directions: (i) establishing weak-convergence rates for the partial-sum process under Markov noise to yield coverage-error guarantees; (ii) studying optimal self-normalizing functionals that optimize expected length subject to coverage accuracy and computational cost; (iii) extending path-level inference to more complex methods such as AdamW and Muon, for which CLTs and convergence results exist but FCLTs and self-normalized inference remain open.

Improvements for AI systems

Based on the paper, here are specific improvements I can make to AI systems and what the improved systems can do:

Improvement: Add the polynomial-series self-normalized confidence interval (P5 method) to Q-learning agents operating in online/streaming environments.

What the improved system can do:

  • Report a confidence interval for each estimated Q-value (e.g., Q(s,a) = 12.3 ± 1.1 with 95% confidence) while learning from a single Markov trajectory

  • Maintain this uncertainty estimate using only constant memory (11 scalar accumulators) and no additional environment interactions

  • Provide valid intervals for asynchronous tabular Q-learning, projected linear Q-learning, and entropy-regularized Q-learning

  • Detect when the agent's value estimates are still unreliable (wide intervals) versus converged (narrow intervals), enabling safer exploration or early stopping

These improvements are directly implementable from the paper's theoretical results (Theorem 1, Propositions 4–5, and the application-specific verifications in Section 6) and have been validated in the paper's experiments across five settings.

Sources

Related papers