🤖 machine learning

Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning

This paper establishes non-asymptotic central limit theorems for vector-valued martingale differences and Markov chains using Stein's method and Poisson's equation, subsequently applying these results to provide convergence rates for Temporal Difference (TD) learning with averaging.

Original authors: R. Srikant

Published 2026-02-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: R. Srikant

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.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 learn how to throw a dart at a bullseye. You aren't a professional, so your throws are a bit shaky. Every time you throw, your hand wobbles slightly, and sometimes the wind blows.

If you throw one dart, you might miss wildly. But if you throw 1,000 darts and calculate the average position of all those darts, you’ll get a much better idea of where your "true" aim is.

This paper is essentially a mathematical "quality control" manual for that process. It looks at how quickly we can trust that average as we keep practicing.

Here is the breakdown of the paper using three simple concepts:

1. The "Wobble" (The Martingale Central Limit Theorem)

In math, a "Martingale" is like a series of steps where, even though you don't know exactly where you'll land next, you know that on average, you aren't being pushed in any specific direction. You are just "wobbling" around.

The Central Limit Theorem (CLT) is a famous rule that says: "If you wobble enough times, the pattern of your mistakes will eventually look like a perfect Bell Curve (a Normal Distribution)."

The Problem: Most math books tell you that if you wobble forever, you'll eventually see that Bell Curve. But they don't tell you how long you have to wait. If you are a robot learning to walk, you can't wait "forever"—you need to know if you'll be stable after 10 steps or 10,000 steps.

The Paper’s Contribution: The author uses a technique called "Stein’s Method" to provide a stopwatch. He calculates the Rate of Convergence, which is a way of saying: "By the time you reach step X, your pattern of mistakes will be 99% close to a perfect Bell Curve."

2. The "Memory" (Markov Chains)

The paper then moves from simple "wobbles" to something more complex: Markov Chains.

Imagine a game of Snakes and Ladders. Your next position depends entirely on where you are standing right now. This is a Markov Chain. It has "memory"—the wind doesn't just blow randomly; the wind's direction might depend on where the clouds were a moment ago.

The author shows how to take these complex, "memory-based" movements and turn them back into those simple "wobbles" (Martingales) using a mathematical trick called Poisson’s Equation. This allows him to apply his "stopwatch" to much more complicated, real-world systems.

3. The Application: Teaching a Robot (TD Learning)

Finally, the paper applies all this math to TD Learning (Temporal Difference learning). This is a core way that Artificial Intelligence (like the software in self-driving cars or game-playing bots) learns from experience.

In TD learning, the AI tries to predict the future. It says, "I thought this turn would be good, but it was actually bad; I need to adjust my strategy."

However, because the AI is learning from a sequence of events (a Markov Chain), its learning process is "wobbly." If the AI tries to learn too fast, it overreacts to a single mistake. If it learns too slowly, it takes forever to improve.

The "Averaging" Trick: To fix this, engineers use "averaging" (called Polyak-Ruppert averaging). Instead of just looking at the very last thing the AI learned, they look at the average of everything it has learned so far. This smooths out the mistakes.

The Paper’s Result: The author provides the mathematical proof for exactly how fast this "averaging" technique works. He tells engineers: "If you use this specific mathematical recipe for your learning steps, here is exactly how quickly your AI's errors will settle into a predictable, manageable pattern."

Summary in a Nutshell

The Goal: Don't just tell me the AI will eventually learn; tell me how fast it will become predictable.
The Tool: A mathematical "stopwatch" (Rate of Convergence) using a high-tech measuring tape (Wasserstein distance).
The Result: A blueprint for making Reinforcement Learning (AI) more efficient and reliable by knowing exactly how much "averaging" is needed to tame the chaos.

This paper, titled "Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learning" by R. Srikant, addresses the gap between asymptotic theory and finite-time analysis in stochastic approximation and machine learning.

1. The Problem

While the Central Limit Theorem (CLT) is a standard tool for understanding the asymptotic efficiency of algorithms (like Stochastic Gradient Descent or Temporal Difference learning), most existing literature focuses on the limit as $n \to \infty$ . In practical machine learning, practitioners need non-asymptotic (finite-time) bounds to understand sample complexity and the error distribution for a specific number of iterations.

The author identifies two specific gaps in current research:

Vector-valued Martingales/Markov Chains: Existing rates of convergence for vector-valued martingales often use distance metrics (like total variation) that are too weak for certain applications.
TD Learning Efficiency: While the asymptotic behavior of Temporal Difference (TD) learning with Polyak-Ruppert averaging is known, the rate at which its distribution converges to a Gaussian is not well-quantified in a non-asymptotic setting.

2. Methodology

The paper employs a rigorous mathematical framework combining three major pillars:

Stein’s Method: This is the core technique used to bound the distance between a distribution and a Gaussian. Unlike traditional methods, Stein’s method allows the author to use the regularity of solutions to Stein's equation to derive bounds in the Wasserstein distance ( $d_W$ ), which is more robust for vector-valued variables.
Lindeberg Decomposition: The author uses this to break down the sum of martingale differences into manageable components, allowing for a term-by-term analysis of the deviation from normality.
Poisson’s Equation: To bridge the gap between Markov chains and martingales, the author uses Poisson’s equation. This converts a function of a Markov chain (which has temporal dependencies) into a martingale difference sequence (which has the orthogonality property $\mathbb{E}[m_k | \mathcal{F}_{k-1}] = 0$ ), making it amenable to Stein's method.

3. Key Contributions

New Martingale CLT Bound: The paper establishes a non-asymptotic CLT for vector-valued martingale differences measured in Wasserstein distance. Crucially, the bound is expressed in terms of the asymptotic covariance matrix $\Sigma_\infty$ , making it directly applicable to real-world convergence analysis.
Markov Chain CLT Extension: The author extends the martingale results to functions of Markov chains (both finite and general state-space) by leveraging geometric ergodicity and Lyapunov drift conditions.
Application to TD Learning: The paper provides the first non-asymptotic CLT for the averaged iterates of TD learning with decaying step-sizes.

4. Key Results

Theorem 1 (Martingale CLT): Provides an upper bound on the Wasserstein distance $d_W(W_n, \mathcal{N}(0, \Sigma_\infty))$ . The rate is determined by the convergence of the conditional covariances $\Sigma_k$ to the asymptotic covariance $\Sigma_\infty$ and the higher-order moments of the martingale differences.
Theorem 2 & 3 (Markov Chain CLT): For irreducible, aperiodic Markov chains, the author proves that the rate of convergence to normality is roughly $O(n^{-1/2})$ (specifically $O(\frac{\log n}{\sqrt{n}})$ under certain moment conditions).
Theorem 4 (TD Learning Application): For TD learning with Polyak-Ruppert averaging and step-size $\epsilon_k = 1/(k+1)^\delta$ , the scaled error $\sqrt{n}(\bar{\theta}_n - \theta^*)$ converges to a Gaussian distribution at a rate of:
$\max \left( \frac{\sqrt{\log n}}{n^{\delta-0.5}}, \frac{1}{n^{(1-\delta)/2}} \right)$
This result quantifies how the choice of the decay parameter $\delta$ affects the speed of distributional convergence.

5. Significance

The paper is significant because it provides the mathematical tools necessary to move from "asymptotic guarantees" to "finite-sample guarantees" in reinforcement learning.

By establishing rates in the Wasserstein distance, the author provides a more useful metric for engineers who need to know the probability of error within a specific range. Furthermore, the application to TD learning with averaging validates a common practical heuristic (averaging iterates to reduce variance) with a formal, non-asymptotic convergence rate, offering insights into the optimal selection of step-size decay parameters.