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

Rahul Singh; Siddharth Chandak; Eric Moulines; Vivek S. Borkar; Nicholas Bambos

cs.LGFeb 18, 2026

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

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

Organizations: MBZUAI, UAE · Stanford University, USA · EPITA, France · Indian Institute of Technology Bombay, India

Abstract

We present the first regret bound for classical online Q-learning in infinite-horizon discounted Markov decision processes (MDPs), without relying on optimism or bonus terms. We first analyze Boltzmann Q-learning with decaying temperature and show that its regret depends critically on the suboptimality gap of the MDP: for sufficiently large gaps, the regret is sublinear, while for small gaps it deteriorates and can approach linear growth. To address this limitation, we study a Smoothed $ε_n$ -Greedy exploration scheme that combines $ε_n$ -greedy and Boltzmann exploration, for which we prove a gap-robust regret bound of near- $\tilde{O}(N^{9/10})$ . We also obtain sample complexity guarantees, with both regret and sample complexity bounds holding with high probability. To analyze these algorithms, we develop a high-probability concentration bound for contractive Markovian stochastic approximation with iterate- and time-dependent transition dynamics. This bound may be of independent interest as the contraction factor in our framework is allowed to converge to one asymptotically.

Figures & tables

Panel of Figure 1 — Figure 1: Sensitivity of the Boltzmann exploration rule: heatmaps for a two-action policy, where the probability of selecting the first action is $P(x,\lambda)=(1+e^{-x/\lambda})^{-1}$ . As $\lambda$ decreases, sensitivity near the decision boundary increases, illustrating the growth of the Lipschitz constant.

Figure 2

Regret Minimization in RL

Regret minimization in reinforcement learning develops agents that learn effective policies while limiting cumulative loss against an optimal benchmark.

See all 56 papers

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation
Aug 23, 2026Shengbo WangQ-Learning Function Approximation in RL
Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California
On Gaussian approximation for entropy-regularized Q-learning with function approximation
May 17, 2026Artemy Rubtsov, Rahul Singh, Eric Moulines +2Reinforcement Learning Stochastic Approximation
HSE University, Moscow, Russia · Mohamed Bin Zayed University of AI, UAE · EPITA, France +1
Fast Rates for Offline Q-Learning with KL Regularization
Oct 13, 2026Yize Hao, Guangxin Jiang, Shuang QiuOffline RL Q-Learning
Harbin Institute of Technology. · City University of Hong Kong.

Aug 23, 2026J/K move · Enter open · S save

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

Shengbo Wang

Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California

Q-Learning Function Approximation in RL Linear Function Approximation Stochastic Approximation

Open paper AskPDF arXiv

Q-learning with linear function approximation can be unstable because an arbitrary approximation architecture need not preserve the Bellman contraction. We develop a stable infinite-dimensional linear function approximation framework for Q-learning from a single Markovian behavior-policy trajectory. The learning variable is a coefficient field

θ\in C(\mathbb L)

on a compact latent metric space

(\mathbb L,ρ)

. The framework uses a reconstruction operator that maps

θ

to a continuous Q-function and a compression operator that maps Bellman updates back to latent coordinates. Nonexpansiveness of both operators induces a contractive latent Bellman map on

C(\mathbb L)

, with a unique fixed point

θ^*

whose reconstruction approximates the optimal Q-function up to representation error. We propose two stochastic approximation (SA) algorithms and establish their sup-norm convergence bounds with a leading term of order

\widetilde O(n^{-1/2})

. The infinite-dimensional formulation provides a powerful abstraction for identifying the structures that govern statistical difficulty. Smoothness of the compression map in

ρ

is inherited by

θ^*

and the SA iterates, allowing uniform estimation errors to be controlled through covering numbers of

(\mathbb L,ρ)

rather than the dimension of

C(\mathbb L)

. Remarkably, the SA algorithms we propose are agnostic to the choice of

ρ

, and thus can automatically adapt to both the smoothness and the geometry. We further illustrate the framework through Q-measure-learning with linear density approximation and output-layer neural weight training under a frozen pretrained network.

Abstract

Regret Minimization in RL

Explore similar work

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

On Gaussian approximation for entropy-regularized Q-learning with function approximation

Fast Rates for Offline Q-Learning with KL Regularization