📊 statistics

Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

This paper establishes almost sure convergence rates for stochastic approximation and reinforcement learning algorithms with contractive expected updates under Markovian noise by introducing a novel Lyapunov drift construction that combines Poisson-equation corrections with Moreau-envelope smoothing, achieving rates arbitrarily close to $o(n^{1-2\eta})$ for power-law learning rates and $o(n^{-1})$ for harmonic learning rates.

Original authors: Xinyu Liu, Zixuan Xie, Shangtong Zhang

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Xinyu Liu, Zixuan Xie, Shangtong Zhang

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 find the perfect spot to set up a campfire in a vast, foggy forest. You can't see the whole forest at once; you only know the ground right under your feet. Every step you take is guided by a "learning rate," which is like how big of a step you decide to take. If you take steps that are too big, you might overshoot the perfect spot. If they are too small, you'll never get there in a reasonable time.

This paper is about a mathematical method (called Stochastic Approximation) that helps algorithms figure out the best path to a solution when the information they get is noisy and unpredictable.

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

1. The Problem: The Foggy Forest and the "Markovian" Wind

In many learning algorithms (like those used in video game AI or self-driving cars), the data doesn't come in neat, random packages. Instead, it comes in a chain. If you see a bear today, you are more likely to see a bear tomorrow than if you saw a flower today. This is called Markovian noise.

Previous methods for proving that these algorithms would eventually find the "perfect spot" (converge) were like saying, "Don't worry, if you walk long enough, you'll probably get there." But they couldn't tell you how fast you would get there for any single person walking through the fog. They lacked a speedometer for the journey.

2. The Goal: A Precise Speedometer

The authors wanted to create a "speedometer" that guarantees exactly how fast a specific traveler (a specific computer program) will reach the destination, even when the wind (the noise) is blowing in a connected, chain-like pattern. They wanted to prove that the traveler doesn't just eventually arrive, but arrives at a specific, predictable speed.

3. The Solution: The "Poisson-Moreau Drift"

To solve this, the authors built a new mathematical tool they call the Poisson-Moreau Drift. Think of this as a special pair of hiking boots and a compass combined.

The "Moreau" Part (The Smooth Boots):
Imagine the terrain of the forest is very jagged and rocky (mathematically, the "norm" is weird and non-Euclidean). Standard boots might get stuck. The "Moreau" part of their tool is like a pair of boots with a special, smooth sole that flattens out the jagged rocks. It makes the path easier to walk on, allowing the algorithm to slide smoothly toward the solution even on difficult terrain.
The "Poisson" Part (The Wind-Correcting Compass):
The "Markovian" wind is tricky because it pushes you in a pattern. If you just walk forward, the wind might keep pushing you off course. The "Poisson" part is like a smart compass that knows the wind's pattern. It calculates exactly how much the wind will push you next and tells you to step slightly in the opposite direction now to cancel it out.
The "Drift" (The Combined Strategy):
By combining the smooth boots (Moreau) with the wind-canceling compass (Poisson), the authors created a "Drift." This drift is a mathematical guarantee that, step-by-step, the traveler is getting closer to the goal, and the "noise" of the wind is being neutralized.

4. The Results: How Fast Do We Get There?

Using this new tool, the authors proved two main things about the speed of the journey:

For "Power-Law" Steps (Medium-sized steps): If the algorithm takes steps that get smaller at a specific rate (like $1/\sqrt{n}$ ), they proved the algorithm gets closer to the goal almost as fast as theoretically possible.
For "Harmonic" Steps (The perfect step size): If the algorithm takes steps that shrink at the rate of $1/n$ (like $1/1, 1/2, 1/3...$ ), they proved the algorithm converges incredibly fast. In fact, it's almost as fast as the absolute best speed allowed by the laws of probability (a famous rule called the "Law of the Iterated Logarithm").

5. Why This Matters for AI

The authors specifically mention that this applies to Reinforcement Learning (where AI learns by trial and error, like a robot learning to walk or a program learning to play chess).

Q-Learning and TD-Learning: These are the "GPS" systems for AI. The authors showed that even when the AI is learning from a single, continuous stream of experiences (like a robot walking down a hallway and seeing the same walls in a pattern), it will find the best strategy very quickly and reliably.
The "Single-Trajectory" Guarantee: Unlike older methods that might say "If you run this experiment a million times, the average result is good," this paper says, "If you run this experiment once, your specific path will reach the goal at this speed."

Summary

The paper introduces a new mathematical "hiking gear" (Poisson-Moreau Drift) that allows us to predict exactly how fast an AI learning algorithm will solve a problem, even when the data it receives is messy and connected in a chain. They proved that with the right step sizes, these algorithms reach their goals almost as fast as mathematically possible, providing a much stronger guarantee of success than we had before.

Technical Summary: Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift

Problem Statement
The paper addresses the fundamental theoretical challenge of establishing almost sure convergence rates for stochastic approximation (SA) and reinforcement learning (RL) algorithms operating under Markovian noise. While classical theory (e.g., the ODE method) establishes that sequences $\{\theta_n\}$ converge almost surely, it often fails to quantify the speed of this convergence for individual sample paths. Existing literature on almost sure rates faces significant limitations:

Many results rely on independent and identically distributed (i.i.d.) noise, which does not reflect the single-trajectory sampling common in RL.
Results handling Markovian noise often require the expected update to be linear or rely on restrictive learning rate regimes.
Recent work by Qian et al. [2024] handles Markovian noise with general contractive mappings but yields slower convergence rates and fails to cover certain learning rate regimes (specifically $\eta \in (1/2, 2/3]$ ).

The authors focus on a class of SA algorithms where the expected update is contractive (potentially in a non-Euclidean norm, such as $\ell_\infty$ ) and the noise forms a Markov chain. This setting encompasses core RL algorithms like Q-learning and linear Temporal Difference (TD) learning.

Methodology: The Poisson-Moreau Drift
The core technical novelty is the construction of a novel Lyapunov drift function, termed the Poisson-Moreau drift. The authors combine two established techniques with a new correction mechanism:

Moreau-Envelope Smoothing: To handle the contractive mapping $T$ which may be defined under a non-Euclidean norm $\|\cdot\|$ , the authors utilize the Moreau envelope $M_\xi$ . This smooths the non-differentiable norm-based energy function into a continuously differentiable function $M_\xi(x)$ , allowing for gradient-based analysis while preserving the contraction properties.
Poisson-Equation Correction: To address the Markovian noise, the authors apply a correction based on the Poisson equation. The noise term $F(\theta, Y) - f(\theta)$ is decomposed into a martingale difference and a telescoping remainder using a solution $H_\theta$ to the Poisson equation: $H_\theta(y) - (PH_\theta)(y) = F(\theta, y) - f(\theta)$ .
The Novel Construction: Unlike prior works that either take total expectations (losing pathwise control) or use "skeleton iterates" (subsequences), the authors directly incorporate the Poisson correction into the Lyapunov function. They define the drift:
$V_n^\xi = M_\xi(e_n) + \alpha_n \langle \nabla M_\xi(e_n), H_{\theta_n}(Y_n) \rangle + K \alpha_n^2$
where $e_n = \theta_n - \theta^*$ $e_{n} = θ_{n} - θ^{*}$ is the error, $\alpha_n$ $α_{n}$ is the learning rate, and $K$ $K$ is a sufficiently large constant.
- The middle term (Poisson correction) cancels the leading bias term arising from Markovian dependence in the conditional drift.
- The final term ( $K \alpha_n^2$ ) ensures the drift remains non-negative and controls residual terms.

This construction allows the authors to establish that $V_n^\xi$ satisfies an almost-supermartingale inequality directly on the conditional expectation, enabling the application of recent almost-supermartingale convergence rate theorems (Liu and Yuan [2024]) to the full sequence of iterates, not just subsequences.

Key Results
Under assumptions of contractive expected updates, Lipschitz continuity, and the existence of a Poisson equation solution for the Markov chain, the paper derives the following almost sure convergence rates for the error $\|\theta_n - \theta^*\|$ :

Power-law learning rates $\alpha_n = O(n^{-\eta})$ with $\eta \in (1/2, 1)$ :
The error converges almost surely at a rate arbitrarily close to $o(n^{-(2\eta - 1)})$ .
Harmonic learning rates $\alpha_n = O(n^{-1})$ $α_{n} = O (n^{- 1})$ (i.e., $\eta = 1$ $η = 1$ ):
The error converges almost surely at a rate arbitrarily close to $o(n^{-1})$ .
- The authors note this is a strong result, approaching the optimal rate $O(n^{-1} \log \log n)$ given by the law of the iterated logarithm for i.i.d. noise.

Comparison with Prior Work

vs. Qian et al. [2024]: The proposed method covers a broader range of learning rates (specifically $\eta \in (1/2, 2/3]$ where Qian et al. provide no rates) and achieves strictly faster convergence rates for $\eta \in (2/3, 1]$ .
vs. Expectation-based analyses: The method provides pathwise (almost sure) guarantees rather than just convergence in expectation or probability.
Side Result: By taking unconditional expectations of the drift inequality, the authors also derive $L_2$ convergence rates for the full range $\eta \in (0, 1]$ , showing $E[\|\theta_n - \theta^*\|^2] = O(n^{-\eta})$ for $\eta < 1$ .

Applications
The theoretical framework is applied to a generalized family of tabular TD algorithms with generalized importance sampling factors. This unified template recovers several standard algorithms, including:

On-policy and off-policy $n$ -step TD.
$Q^\pi(\lambda)$ , Tree-Backup, Retrace, and Q-trace.

For these algorithms, the paper verifies that the structural conditions (Hurwitz matrix for the mean operator, existence of Poisson solutions for finite-state chains) hold, thereby establishing the first pathwise almost sure convergence rates for the single-trajectory version of these generalized TD recursions under Markovian sampling.

Significance and Claims
The paper claims to provide sharper almost sure convergence rates for general stochastic approximations under Markovian noise and non-Euclidean contractivity. The significance lies in:

Technical Novelty: The "Poisson-Moreau drift" is presented as a novel construction that successfully bridges the gap between handling non-Euclidean contractions (via Moreau envelopes) and Markovian noise (via Poisson corrections) within a single almost-supermartingale framework.
Tightness: The derived rates for harmonic learning rates ( $\eta=1$ ) are argued to be close to the theoretical optimum, surpassing previous results in the RL literature.
Completeness: The work fills a gap in the literature by addressing the specific combination of Markovian noise and general (non-linear, non-Euclidean) contractive mappings, a setting characteristic of modern RL algorithms.

The authors remain modest regarding the tightness of the rates, acknowledging that while their results are sharper than existing literature, they do not yet fully match the $O(n^{-1} \log \log n)$ bound of the law of the iterated logarithm. They also note that extending the almost sure rates to the full range $\eta \in (0, 1]$ (currently proven for $L_2$ ) remains an open question.