📊 statistics

Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains

This paper establishes the first regret and sample complexity bounds for classical online Q-learning in infinite-horizon discounted MDPs without optimism, demonstrating that while Boltzmann exploration's performance depends critically on suboptimality gaps, a proposed Smoothed $\epsilon_n$ -Greedy scheme achieves near-optimal, gap-robust guarantees by leveraging a novel high-probability concentration bound for time-inhomogeneous stochastic approximation.

Original authors: Rahul Singh, Siddharth Chandak, Eric Moulines, Vivek S. Borkar, Nicholas Bambos

Published 2026-05-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rahul Singh, Siddharth Chandak, Eric Moulines, Vivek S. Borkar, Nicholas Bambos

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 teaching a robot to navigate a giant, complex maze to find the treasure. The robot doesn't have a map; it only knows what happens when it takes a step (does it hit a wall? does it find a coin?). This is the world of Reinforcement Learning, and the specific method the robot uses to learn is called Q-Learning.

The paper you provided tackles a very specific, tricky problem: How do we prove that this robot is learning efficiently and not wasting too much time making mistakes, without cheating?

Here is the breakdown of their work using simple analogies.

1. The Problem: The "Optimism" Cheat Code

In the past, researchers proved that robots learn well by giving them a "cheat code" called Optimism. Imagine the robot is told, "Every time you try a new path, assume it's the best path until proven otherwise." This forces the robot to explore aggressively. While this works mathematically, it's not how most real-world AI (like the ones playing video games or controlling robots) actually works. Real AI usually uses simpler, more "honest" strategies like Boltzmann exploration (trying actions based on how good they look right now, with some randomness) or $\epsilon$ -greedy (mostly doing the best thing, but occasionally picking a random action just to be safe).

The Gap: No one had ever mathematically proven that these "honest" strategies would actually learn efficiently in a finite amount of time without the "optimism" cheat. They were just assumed to work.

2. The Solution: A New Lens for Watching the Robot

The authors developed a new mathematical "lens" (a concentration bound) to watch the robot's learning process.

The Old Lens: Previous math tools assumed the maze's rules (the wind, the slippery floors) stayed the same forever.
The New Lens: In this paper, the authors realized that as the robot learns, it changes the maze. Because the robot is learning which paths are good, it stops walking down the bad ones. This means the "rules" of the maze (the probability of where it goes next) are constantly shifting and becoming more unpredictable as it gets better.
The Analogy: Imagine trying to predict the weather. If the weather is static, it's easy. But if the weather changes because you are watching it, that's hard. The authors built a tool to handle this "moving target" scenario where the robot's own learning makes the environment harder to predict over time.

3. The Two Strategies They Tested

The authors tested two common ways the robot decides what to do:

A. Boltzmann Exploration (The "Temperature" Strategy)

The robot acts like a chef tasting soup. If the soup is too hot (high "temperature"), the chef tastes everything randomly. As the soup cools (temperature drops), the chef starts focusing only on the best-tasting spoonfuls.

The Finding: They found that if the "suboptimality gap" (the difference between the best path and a bad path) is huge, this strategy works great. But if the difference is tiny (the paths look almost the same), the robot gets confused and keeps making mistakes, leading to a lot of wasted time (linear regret). It's like trying to distinguish between two shades of blue that look identical; the robot just guesses forever.

B. Smoothed $\epsilon$ -Greedy (The "Safety Net" Strategy)

To fix the weakness of the first strategy, they created a hybrid. Imagine the robot has a "Safety Net."

90% of the time, it picks the action it thinks is best.
10% of the time, it picks a random action just to be sure it hasn't missed anything.
Crucially, this "10%" slowly shrinks over time, but never disappears completely.
The Finding: This "Safety Net" approach is much more robust. Even when the paths look very similar, the robot keeps checking the random paths. They proved this method achieves a sublinear regret.
- What does that mean? It means the robot makes mistakes, but the rate of mistakes slows down over time. It doesn't just keep making the same number of mistakes every day; it gets smarter and smarter.

4. The Big Result: "Near-Optimal" Without Cheating

The most exciting claim in the paper is that they proved this "Safety Net" strategy (Smoothed $\epsilon$ -Greedy) works almost as well as the "cheating" Optimism methods, but without the cheat.

The Math: They showed the robot's total "regret" (total lost opportunity) grows at a rate of roughly $N^{0.9}$ (where $N$ is the number of steps).
The Comparison: The "cheating" methods can get down to $N^{0.5}$ . The authors admit their method isn't quite as fast as the cheaters, but it is the first time anyone has proven that a standard, non-cheating Q-learning algorithm can learn efficiently in the long run.

Summary in One Sentence

The authors built a new mathematical tool to prove that a robot learning a maze using standard, honest exploration methods (without "optimism" cheats) will eventually stop making mistakes and learn efficiently, provided it keeps a tiny bit of randomness in its decision-making process.

What they did NOT claim:

They did not say this works for Large Language Models (LLMs) specifically, though they mention RL is used there.
They did not claim this solves healthcare or robotics problems immediately; they only provided the theoretical proof that the math works.
They did not claim their method is faster than the "cheating" methods; they only claimed it is the first proven efficient method that doesn't cheat.

Technical Summary: Regret and Sample Complexity of Online Q-Learning via Concentration of Stochastic Approximation with Time-Inhomogeneous Markov Chains

1. Problem Statement

This work addresses the theoretical analysis of classical, model-free online Q-learning in infinite-horizon discounted Markov Decision Processes (MDPs). While Q-learning is a foundational algorithm in Reinforcement Learning (RL), underpinning modern methods like Deep Q-Networks (DQN), existing finite-time analyses have significant limitations:

Offline Bias: Most sample complexity results focus on the offline setting, where data is generated by a fixed behavioral policy. These analyses control estimation error ( $\|Q_n - Q^\star\|_\infty$ ) but do not guarantee performance (regret) during the learning process.
Reliance on Optimism: Existing regret bounds for online Q-learning typically rely on "optimism in the face of uncertainty" (e.g., bonus terms) or model-based approaches.
Exploration Gaps: There are no theoretical guarantees for standard exploration strategies like $\epsilon$ -greedy or Boltzmann (softmax) exploration when used with unmodified Q-learning updates in the online setting.

The core challenge is to establish regret and sample complexity guarantees for online Q-learning using standard exploration policies without adding optimism terms, while accounting for the fact that the policy (and thus the data distribution) evolves over time, creating a time-inhomogeneous Markovian noise structure.

2. Methodology

The authors develop a novel analytical framework based on Stochastic Approximation (SA) to analyze the convergence and regret of Q-learning.

2.1 Stochastic Approximation Framework with Time-Inhomogeneous Chains

The Q-learning update is cast as a contractive SA iteration:
$x_{n+1} = x_n + \beta_n (F(x_n, y_n) - x_n + M_{n+1})$
where $x_n$ represents the Q-values, $y_n = (s_n, a_n)$ is the state-action pair generated by the current policy, and $M_{n+1}$ is martingale noise.

The key innovation lies in handling the time-inhomogeneous Markov chain $\{y_n\}$ . Unlike prior work that assumes time-homogeneous chains or uniform mixing times, this framework allows:

Time-Varying Transition Dynamics: The transition kernel $p(\zeta_n, x_n)$ depends on the iterate $x_n$ and an external control sequence $\zeta_n$ (e.g., temperature $\lambda_n$ or exploration rate $\epsilon_n$ ).
Asymptotically Vanishing Contraction: The contraction factor $\alpha(\zeta_n)$ is allowed to converge to 1 as $n \to \infty$ . This models the scenario where suboptimal actions are chosen with vanishing probability, causing the mixing time of the induced Markov chain to diverge.
Lipschitz Sensitivity: The transition kernel's sensitivity to changes in the iterate $x$ is allowed to grow (e.g., as temperature $\lambda_n \to 0$ , the softmax policy becomes increasingly sensitive to Q-value differences).

2.2 High-Probability Concentration Bound

The authors derive a high-probability concentration bound for the SA iterates. The proof technique involves:

Poisson Equation Decomposition: Converting the Markovian noise into a martingale difference sequence plus a residual term using the solution to the Poisson equation associated with the time-varying transition kernel.
Noise Averaging: Developing a novel argument to bound the decay of noise despite the weakening contraction and varying transition kernels.
Result: The bound shows that $\|x_n - x^\star\|$ decays at a rate dependent on the stepsize schedule and the rates at which the contraction factor approaches 1 and the transition kernel varies.

2.3 Exploration Schemes Analyzed

The framework is applied to two specific exploration policies:

Boltzmann Q-learning: Actions are selected via a softmax distribution $\sigma(Q_n/\lambda_n)$ with a decaying temperature $\lambda_n$ .
Smoothed $\epsilon_n$ -Greedy (S $\epsilon$ G): A convex combination of a uniform policy and a softmax policy. This smoothing is introduced to ensure the transition kernel remains smooth with respect to Q-values, facilitating the analysis, while effectively mimicking standard $\epsilon$ -greedy behavior.

3. Key Contributions and Results

3.1 First Regret Bounds for Classical Online Q-Learning

The paper provides the first regret bounds for classical, fully model-free Q-learning without optimism terms.

Boltzmann Q-learning: The regret depends critically on the suboptimality gap ( $\text{gap}(M)$ $gap (M)$ ) of the MDP.
- For large gaps, regret is sublinear.
- For small gaps, the regret can deteriorate and approach linear growth ( $O(N)$ ), consistent with known limitations of Boltzmann exploration in bandits.
Smoothed $\epsilon_n$ -Greedy (S $\epsilon$ G): This scheme achieves a gap-robust regret bound of near- $\tilde{O}(N^{9/10})$ . While this is worse than the $\tilde{O}(\sqrt{N})$ achieved by optimism-based methods, it demonstrates that sublinear regret is attainable for unmodified online Q-learning.

3.2 Sample Complexity Guarantees

The authors establish high-probability sample complexity bounds exhibiting sub-Gaussian tail behavior:

Boltzmann: The sample complexity is $\tilde{O}((1-\gamma)^{-4}\epsilon^{-2})$ under specific parameter choices, approaching the optimal offline rate as the temperature decay parameter $b \to 0$ .
S $\epsilon$ G: The sample complexity is $\tilde{O}((1-\gamma)^{-5}\epsilon^{-2})$ , matching known bounds for offline Q-learning derived via SA techniques but extending them to the online setting.

3.3 Novel Concentration Bound for SA

A primary technical contribution is the concentration bound for contractive Markovian SA with time-inhomogeneous dynamics.

The bound holds with high probability and allows the contraction factor to approach 1 asymptotically.
It handles the case where the mixing time diverges and the transition kernel varies with the iterate.
This result is presented as potentially of independent interest for RL and optimization algorithms involving controlled Markovian noise.

4. Significance and Claims

The paper claims to bridge a critical gap in RL theory by providing rigorous finite-time guarantees for standard Q-learning algorithms that are widely used in practice (e.g., DQN with $\epsilon$ -greedy or Boltzmann exploration) but previously lacked theoretical justification in the online setting.

Practical Relevance: The results apply to algorithms that do not require model-based components or complex optimism bonuses, aligning with the "model-free" nature of many successful modern RL systems.
Theoretical Limitations: The authors acknowledge that the achieved regret rate ( $\tilde{O}(N^{9/10})$ ) is suboptimal compared to optimism-based methods ( $\tilde{O}(\sqrt{N})$ ). They attribute this to fundamental limitations of exploration without optimism, drawing parallels to multi-armed bandit results where $\epsilon$ -greedy and Boltzmann strategies yield worse rates than UCB.
Future Directions: The paper identifies potential extensions, including improving the regret rate to match bandit results ( $\tilde{O}(N^{2/3})$ ), extending the analysis to function approximation, and applying the bounds to average-reward RL.

In summary, this work establishes that classical online Q-learning can achieve sublinear regret and high-probability convergence without algorithmic modifications, provided the exploration parameters are carefully tuned, by leveraging a new analytical tool for time-inhomogeneous stochastic approximation.