📊 statistics

Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning

This paper establishes novel high-dimensional concentration inequalities and Berry-Esseen bounds for Markov chain-induced martingales, which are applied to derive sharp consistency guarantees and a $O(T^{-1/4}\log T)$ Gaussian approximation rate for Temporal Difference learning with linear function approximation.

Original authors: Weichen Wu, Yuting Wei, Alessandro Rinaldo

Published 2026-05-22

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: Weichen Wu, Yuting Wei, Alessandro Rinaldo

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to navigate a foggy, winding mountain path. You have a map (your algorithm) and a compass (your data), but the terrain is tricky: the ground you stand on today depends heavily on where you were yesterday. This is the world of Markov chains, a mathematical way to describe systems where the future depends on the present, like the weather, stock markets, or a robot learning to walk.

This paper is about building a better, more reliable "fog detector" for these systems. Specifically, it focuses on a popular navigation tool called Temporal Difference (TD) Learning, used in Reinforcement Learning (AI) to figure out how good a certain move is.

Here is a breakdown of what the authors did, using simple analogies:

1. The Problem: The "Fog" of Uncertainty

When an AI learns from a sequence of events (like a video game), the data isn't random; it's connected. If you roll a "6" on a die, the next roll isn't independent of the first in this specific "Markov" world.

Because the data is connected, it's hard to know how much you can trust your AI's answer.

The Analogy: Imagine you are trying to guess the average height of trees in a forest. If you pick trees that are all clustered together in one small grove (dependent data), your guess might be way off if that grove happens to be unusually short. You need a way to measure the "fog" (uncertainty) to know if your guess is reliable.

2. The First Breakthrough: A New "Ruler" for the Fog

The authors created new mathematical tools (called concentration inequalities and Berry-Esseen bounds) to measure this uncertainty more precisely.

The Analogy: Think of previous tools as a rough, stretchy rubber band used to measure distance. It gives you a general idea, but it's loose. The authors invented a laser-measuring tape.
What it does: This new "laser tape" can measure the uncertainty of the AI's learning process even when the data is messy and connected. It tells you exactly how close the AI's current guess is to the "true" answer, with a very high level of confidence.
The "Martingale" Connection: The authors realized that the errors in the AI's learning process behave like a specific type of mathematical object called a "martingale" (think of it as a fair game where your winnings depend on the past). They figured out how to measure the "fairness" and stability of this game even when the rules change slightly based on the path taken.

3. The Second Breakthrough: Testing the AI's "Compass" (TD Learning)

They applied their new "laser tape" to TD Learning, the specific algorithm used to teach AI how to value future rewards.

The Analogy: Imagine the AI is a hiker trying to find the peak of a mountain (the best strategy). The hiker takes steps based on what they see right now.
- Old Way: We knew the hiker would eventually reach the peak, but we didn't know how fast or how wobbly the path would be.
- New Way: The authors proved that with their new tools, we can guarantee the hiker is on the right path with a specific, tight margin of error. They showed that the hiker's path converges to the peak at a predictable speed, matching the theoretical best speed possible (up to some small "logarithmic" factors, which are like tiny, manageable bumps on the road).

4. The "Gaussian" Surprise: Predicting the Shape of Mistakes

One of the most powerful parts of the paper is proving that the errors made by the AI follow a specific, predictable shape (a Gaussian or "Bell Curve" distribution).

The Analogy: Imagine the AI makes mistakes. Sometimes it guesses too high, sometimes too low. The authors proved that if you look at a huge number of these mistakes, they don't look like random chaos. Instead, they form a perfect, symmetrical bell curve.
Why it matters: Because the mistakes form a bell curve, we can use standard statistical tools to say things like, "There is a 95% chance the AI's error is within this specific range." This allows us to build confidence intervals—essentially, a safety zone around the AI's answer.

5. The Bottom Line

The paper does two main things:

Invented a new, sharper ruler to measure uncertainty in systems where data depends on the past (Markov chains).
Used that ruler to prove that a specific AI learning method (TD Learning) is statistically reliable, showing exactly how fast it learns and how much we can trust its final answer.

What the paper does NOT claim:

It does not claim this will immediately fix self-driving cars or cure diseases.
It does not claim the AI will now be "smarter" in a general sense.
It is purely a theoretical proof. It provides the mathematical guarantee that the "fog" can be measured and that the AI's learning process is stable and predictable under specific conditions.

In short, the authors didn't build a better car; they built a better speedometer and GPS that tells us exactly how reliable the car's navigation system is, even when the road is foggy and winding.

Problem Statement

The paper addresses the challenge of providing rigorous probabilistic guarantees for statistical learning algorithms operating on dependent data generated by Markov chains. Specifically, it focuses on two interconnected problems:

Theoretical Gap: While concentration inequalities and Gaussian approximations (Berry–Esseen bounds) are well-established for independent and identically distributed (i.i.d.) data, high-dimensional finite-sample bounds for vector-valued martingales induced by non-reversible Markov chains are largely missing from the literature. Existing tools often fail to capture the specific dependency structures of Markovian data or provide suboptimal convergence rates in high dimensions.
Application Gap: Temporal Difference (TD) learning is a cornerstone of Reinforcement Learning (RL) for policy evaluation, often utilizing linear function approximations. While asymptotic Central Limit Theorems (CLTs) exist for TD estimators, there is a lack of sharp, non-asymptotic characterizations of their convergence rates and distributional approximations when the data is generated by a Markov chain rather than i.i.d. samples. Current literature largely focuses on independent samples, leaving a gap in statistical inference for RL algorithms relying on Markovian trajectories.

Methodology

The authors develop a two-part framework combining novel martingale theory with specific applications to TD learning.

1. Markov Chain Induced Martingales:
The authors introduce the concept of "Markov chain induced martingales." They consider a discrete-time Markov chain $\{s_t\}$ and a sequence of functions $\{f_i\}$ satisfying a zero-mean condition under the transition kernel. The sequence $f_i(s_{i-1}, s_i)$ forms a martingale difference sequence.

Poisson Equation Decomposition: To analyze additive functionals of the Markov chain (e.g., $\sum g(s_i)$ ), the authors utilize the Poisson equation $g(s) = U(s) - PU(s)$ to decompose the sum into a martingale difference sequence plus boundary terms. This reduces the analysis of Markovian sums to the analysis of martingales.
Concentration Inequalities: They derive a Bernstein-style concentration inequality for the Euclidean norm of the average of these martingales. The proof leverages a Freedman-type inequality for Hilbert space martingales and a one-dimensional Hoeffding inequality for Markov chains to control the difference between the conditional covariance and the stationary covariance.
Gaussian Approximation: To establish Berry–Esseen bounds, the authors employ Stein's method and Lindeberg swapping. A key technical innovation is the construction of an auxiliary martingale with deterministic terminal quadratic variation. They refine existing proof strategies (specifically addressing gaps in Srikant [2025]) to handle the discrepancy between the target martingale and the auxiliary one, utilizing a novel matrix Hoeffding inequality for Markov chains.

2. Application to TD Learning:
The theoretical results are applied to TD learning with linear function approximation and Polyak-Ruppert averaging.

Setup: The TD estimator $\theta_T$ is analyzed under Markovian samples with polynomially decaying step sizes $\eta_t = \eta_0 t^{-\alpha}$ .
Decomposition: The estimation error is decomposed into terms involving martingale differences (related to the noise in the TD updates) and bias terms arising from the Markovian dependence and step-size decay.
Mixing Time Analysis: The authors explicitly account for the mixing time of the Markov chain to bound the correlation between the estimator iterates and the current data samples, using a "separation" technique where samples are spaced by the mixing time to approximate independence.

Key Contributions and Results

1. Novel High-Dimensional Bounds for Markov Martingales:

Bernstein Inequality (Theorem 3.1): The paper establishes a high-probability concentration bound for the Euclidean norm of the average of bounded Markov chain induced martingales. The bound scales with the trace of the asymptotic variance matrix and converges at a rate of $O(n^{-1/2})$ up to logarithmic factors, matching the i.i.d. case behavior.
Berry–Esseen Bound (Theorem 3.2): The authors provide a high-dimensional Berry–Esseen bound for these martingales measured in convex distance. The convergence rate is $O(n^{-1/4} \log n)$ . This result is novel for this class of data and allows for the construction of confidence regions, which is difficult with other metrics like Wasserstein distance in high dimensions.
General Martingale Bounds (Theorem 3.3 & Corollary 3.4): They derive new high-dimensional Berry–Esseen bounds for general vector-valued martingales with deterministic terminal quadratic variation in Wasserstein distance. These bounds improve upon existing literature by refining the smoothness analysis of the Stein equation solution and fixing flaws in previous proofs (e.g., Anastasiou et al. [2019]).

2. Statistical Inference for TD Learning:

High-Probability Convergence (Theorem 4.2): The paper establishes a high-probability bound on the TD estimation error $\|\theta_T - \theta^*\|_2$ . The bound matches the asymptotic variance $\tilde{\Lambda}_\star/T$ up to logarithmic factors, with a sample dependence of $O(T^{-1/2})$ . This is the first such guarantee for TD learning with Markov samples that achieves the optimal variance dependence.
Distributional Convergence (Theorem 4.3): The authors prove a high-dimensional Berry–Esseen bound for the rescaled TD estimator $\sqrt{T}(\theta_T - \theta^*)$ $T (θ_{T} - θ^{*})$ in convex distance. The convergence rate is $O(T^{-1/4} \log T)$ $O (T^{- 1/4} lo g T)$ .
- The paper notes that while the rate $O(T^{-1/4} \log T)$ is slower than the $O(T^{-1/3})$ rate achieved for independent samples (Wu et al. [2024]), the generalization to Markovian data is non-trivial.
- They provide a lower bound (Relation 25) suggesting that for step sizes $\alpha > 3/4$ , the $O(T^{-1/4} \log T)$ rate might be optimal for Markovian data, indicating a fundamental gap between independent and dependent settings.

Significance and Claims

The paper claims to bridge the gap between classical stochastic approximation theory and modern RL applications by providing the first sharp, non-asymptotic uncertainty quantification tools for TD learning under Markovian data.

Novelty: The authors state that their high-dimensional Berry–Esseen bounds for Markov chain induced martingales are novel, as no such bounds existed for this specific data form in the literature.
Improvement: The results improve upon the state of the art by providing bounds that explicitly depend on problem parameters (mixing time, spectral gap, dimension) and by offering guarantees in convex distance, which is crucial for statistical inference (confidence sets).
Methodological Impact: The developed tools, particularly the matrix Hoeffding inequality for Markov chains and the refined Stein's method arguments, are presented as having broad applicability beyond TD learning, potentially aiding the analysis of MCMC sampling, Q-learning, and other stochastic approximation algorithms.
Modesty: The authors acknowledge that the $O(T^{-1/4} \log T)$ rate for TD learning is slower than the independent case and do not claim it is the absolute theoretical limit, though they provide evidence (via lower bounds) that it may be optimal for the specific step-size regimes considered. They also note that constructing efficient estimators for the asymptotic variance matrix remains an open problem.