🔢 mathematics

Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning

This paper extends the Robbins-Siegmund theorem to handle almost supermartingales with square-summable (rather than summable) zero-order terms under a novel mild assumption, thereby establishing new convergence rates and concentration bounds that yield the first almost sure convergence guarantees for $Q$ -learning with linear function approximation.

Original authors: Xinyu Liu, Zixuan Xie, Shangtong Zhang

Published 2026-05-28

📖 4 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 park your car in a very crowded, chaotic parking lot. You have a GPS (an algorithm) that gives you directions, but the GPS is a bit glitchy. Sometimes it tells you to turn left when you should turn right, or it gives you a huge, sudden jolt of a direction that sends you flying across the lot.

For decades, mathematicians had a very famous rule (the Robbins-Siegmund theorem) to predict if your car would eventually stop moving and park perfectly in one spot. However, this old rule had a strict requirement: the "glitches" or "jolts" from the GPS had to get smaller and smaller so quickly that their total sum was finite. In other words, the noise had to die out fast.

The Problem:
In many modern Reinforcement Learning (RL) scenarios—like teaching a computer to play a game or drive a car—the "glitches" don't die out fast enough to satisfy that old rule. They are "square-summable" (they get smaller, but not that fast). Under the old rules, mathematicians couldn't prove if the car would ever stop; they could only say, "Well, it might fly off into infinity, or it might just spin in circles forever."

The Solution:
The authors of this paper, Xinyu Liu, Zixuan Xie, and Shangtong Zhang, decided to rewrite the rulebook. They created an extended version of the Robbins-Siegmund theorem.

Here is how they did it, using simple metaphors:

1. The "Bounded Set" vs. The "Single Point"

The old theorem promised that your car would eventually stop at one exact parking spot (a single point).
The new theorem admits that in a chaotic lot, you might never hit one exact spot. Instead, it proves that your car will eventually stop wandering outside a specific, safe zone (a bounded set).

Analogy: Instead of promising you'll park perfectly in the center of a single square, the new rule promises you will stay safely within a 10-foot circle. You might drift around inside that circle, but you won't crash into the next row of cars.

2. The "Speed Limit" on the Jolts

To make this new rule work, the authors added a safety guardrail. They assumed that even if the GPS gives a big jolt, the car's speed can't increase too wildly.

Analogy: Imagine the car has a governor. If the GPS yells "JUMP!" the car can jump, but the height of the jump is limited by how fast the car is currently going. It can't jump to the moon just because the GPS glitched. This prevents the "pathological spikes" (sudden, infinite jumps) that caused the old rules to fail.

3. The Results: Not Just "It Stops," but "How Fast?"

The authors didn't just say, "It stays in the circle." They provided a detailed dashboard with three new gauges:

Almost Sure Convergence Rate: How fast does the car settle into that circle? (e.g., "It gets 90% of the way there in 100 steps.")
High Probability Concentration: How likely is it that the car stays in the circle? (e.g., "99.9% chance you won't see the car outside the circle after 500 steps.")
$L_p$ Convergence: A mathematical way of measuring the average "wobble" of the car inside the circle.

4. The Real-World Test: Linear Q-Learning

The authors tested their new rulebook on a specific, famous, and notoriously difficult algorithm called Linear Q-Learning.

The Context: For decades, experts believed Linear Q-Learning was "unstable" or "deadly." They thought it would eventually crash or diverge because of the "deadly triad" (a mix of approximation, off-policy learning, and bootstrapping).
The Discovery: Using their new theorem, the authors proved that Linear Q-Learning is actually stable, provided you use a specific type of "tamed" behavior policy (a way of exploring that doesn't get too greedy).
The Breakthrough: They didn't just prove it stays safe; they gave the first-ever precise rates for how fast it stays safe, how likely it is to stay safe, and how much it wobbles.

Summary

Think of this paper as upgrading the navigation system for chaotic environments.

Old System: "If the road is perfectly smooth, you will reach the exact destination."
New System: "Even if the road is bumpy and the GPS glitches, as long as the bumps aren't too violent, you will stay within a safe neighborhood. And here is exactly how fast you will get there and how likely you are to stay there."

This is a major step forward because it allows scientists to confidently analyze and trust complex AI algorithms that were previously considered too unpredictable to study rigorously.

Technical Summary: Extensions of Robbins-Siegmund Theorem with Applications in Reinforcement Learning

1. Problem Statement

The Robbins-Siegmund theorem is a foundational tool for analyzing the convergence of stochastic iterative algorithms, particularly in stochastic approximation and reinforcement learning (RL). It establishes the almost sure convergence of "almost supermartingales" (sequences with noisy perturbations) under the condition that the zero-order term (the additive noise term) is summable.

However, a significant limitation exists for many modern RL algorithms, specifically those associated with Ordinary Differential Equations (ODEs) that are not globally asymptotically stable (GAS). Examples include linear SARSA and linear Q-learning. In these settings, the zero-order term arising from the analysis is typically only square-summable (i.e., $\sum T_n^2 < \infty$ ) rather than summable (i.e., $\sum T_n < \infty$ ), due to the nature of the learning rates and the algorithmic structure.

The standard Robbins-Siegmund theorem fails in this regime. As demonstrated by the authors, the Robbins-Monro condition alone (which requires $\sum T_n = \infty$ and $\sum T_n^2 < \infty$ ) is insufficient to guarantee convergence; without additional constraints, the iterates can diverge almost surely due to uncontrolled "spikes" in the noise. Consequently, existing theory often cannot provide convergence rates or concentration bounds for these algorithms, leaving them with only boundedness results under strong assumptions or specific policy designs.

2. Methodology

The paper develops a theoretical framework to extend the Robbins-Siegmund theorem to handle the case where the zero-order term is square-summable but not summable. The methodology proceeds in three stages:

A. Asymptotic Extensions

The authors introduce a novel, mild assumption on the increments of the stochastic process to control the growth of the sequence. Specifically, for a sequence $\{z_n\}$ satisfying a recurrence relation with a square-summable zero-order term, they impose a condition that the increment $|z_{n+1} - z_n|$ is bounded linearly by $T_n(z_n + 1)$ .

Theorem 3 & 4: Under this growth condition and the square-summability of the zero-order term, the authors prove that the sequence converges almost surely to a bounded set (specifically, a ball or interval) rather than a single point. This addresses the divergence issue seen in pathological examples where spikes cause unbounded growth.

B. Nonasymptotic Extensions

Building on the asymptotic results, the paper derives nonasymptotic convergence rates and concentration bounds.

Theorem 5: Establishes an almost sure convergence rate to the bounded set, assuming specific decay rates for the learning rates.
Theorem 6 & Corollary 7: Derive high-probability concentration bounds with exponential tails and $L_p$ convergence rates. These results utilize an inductive (bootstrapping) approach inspired by recent literature, allowing for maximal bounds that hold simultaneously for all time steps.

C. Application to Stochastic Approximation and RL

The authors apply these extended theorems to stochastic approximation (SA) algorithms with time-inhomogeneous Markovian noise.

Technique: They employ the "skeleton iterates" technique (from Qian et al., 2024) combined with a novel error decomposition (from Liu et al., 2025). This involves analyzing a subsequence of iterates where the cumulative learning rate satisfies the Robbins-Monro condition.
Bias Control: A critical technical contribution is the rigorous control of bias terms arising from the time-inhomogeneity of the Markov chain. By dissecting the proof into cases based on the relationship between the current time step and the mixing time of the Markov chain, they bound the bias terms effectively, making the skeleton technique compatible with time-inhomogeneous settings for the first time.

3. Key Contributions

Extension of Robbins-Siegmund Theorem: The paper provides the first extension of the Robbins-Siegmund theorem that relaxes the summable condition on the zero-order term to a square-summable condition. This is achieved by introducing a mild growth assumption on the increments, ensuring convergence to a bounded set.
Convergence Rates and Bounds: The authors derive the first almost sure convergence rates, high-probability concentration bounds (with exponential tails), and $L_p$ convergence rates for almost supermartingales in this non-summable regime.
Analysis of Time-Inhomogeneous SA: The framework successfully handles stochastic approximation with time-inhomogeneous Markovian noise, a setting where previous applications of the Robbins-Siegmund theorem were limited or required stronger assumptions.
Linear Q-Learning Results: Applying the theory to linear Q-learning with linear function approximation and a "tamed" Gibbs behavior policy (as proposed by Meyn, 2024), the paper establishes:
- The first almost sure convergence rate to a bounded set.
- The first high-probability concentration bound with exponential tails.
- The first $L_p$ convergence rate.
- These results hold without algorithmic tweaks (like target networks) or restrictive assumptions on features, provided the behavior policy satisfies specific stability conditions.

4. Results

The paper presents a comprehensive set of theoretical guarantees:

Convergence to a Set: For algorithms where the associated ODE is not GAS, the iterates are proven to converge almost surely to a bounded set, rather than a single point.
Quantifiable Rates: The convergence is not merely asymptotic; the paper provides explicit rates (e.g., $O(t^{-\zeta})$ ) and bounds on the probability of deviation.
Comparison with Prior Work:
- Unlike Meyn (2024) and Liu et al. (2025), which established almost sure boundedness or $L_2$ convergence rates for the second moment, this work establishes $L_p$ convergence rates for all $p \ge 2$ and almost sure convergence rates to the set.
- Unlike Qian et al. (2024) and Borkar et al. (2025), which focus on GAS ODEs (convergence to a point), this work addresses the non-GAS regime.
- The results for linear Q-learning represent a significant advancement over previous stability analyses, providing a complete characterization of convergence dynamics including rates and concentration.

5. Significance and Claims

The authors position this work as a necessary theoretical advancement for analyzing modern RL algorithms that do not fit the classical GAS framework.

Bridging the Gap: The paper claims to bridge a critical gap in the literature where the standard Robbins-Siegmund theorem is inapplicable due to the non-summability of the zero-order term.
Firsts: The authors explicitly claim to provide the "first" almost sure convergence rate, high-probability concentration bound, and $L_p$ convergence rate for linear Q-learning with linear function approximation under standard assumptions (specifically, the tamed Gibbs policy).
Modesty: The authors are modest regarding the scope of their claims. They acknowledge that their results rely on specific learning rate schedules (square-summable and diminishing) and do not directly address constant step-size regimes or non-square-summable learning rates. They also note that while their framework applies to linear SARSA, they focus the presentation on linear Q-learning to avoid verbosity. They further clarify that their results characterize convergence to a bounded set, which is the best possible outcome for non-GAS ODEs without imposing strong structural assumptions, rather than convergence to a unique fixed point.

In conclusion, the paper offers a robust theoretical toolkit for analyzing the stability and convergence of stochastic iterative algorithms in regimes previously considered theoretically intractable, specifically providing the first fine-grained convergence characterizations for linear Q-learning.