cs.LGNov 5, 2026

O(1/n)O(1/n) Convergence Rate for RVI QQ-Learning

Authors: Avik Kar, Siddharth Chandak, Rahul Singh, Shalabh Bhatnagar

Organizations: Department of Computer Science and Automation, Indian Institute of Science, Bengaluru, India. · Department of Electrical Engineering, Stanford University, Stanford, California, USA. · EPITA, Laboratoire Recherche de l’EPITA, Paris, France.

Abstract

We establish finite-time convergence guarantee for synchronous relative value iteration (RVI) QQ-learning for finite weakly communicating Markov decision processes (MDPs). For stochastic Krasnosel'skiĭ--Mann iterations driven by a non-expansive, linearly regular map on a finite-dimensional normed space, we establish last-iterate mean-squared residual bounds under martingale-difference noise whose conditional second moment grows at most linearly with the squared residual. Suitable polynomial stepsizes of order n−an^{-a} yield an O(n−a)O(n^{-a}) rate for 0<a≤10<a\leq1. We verify linear regularity and the noise condition for the centered Bellman operator for finite weakly communicating MDPs. Applying the general result gives an O(n−1)O(n^{-1}) bound on the mean-squared Bellman span residual of RVI QQ-learning iterates when a suitable stepsize sequence is used. The positive gap between optimal and suboptimal stationary deterministic policies then yields an O(n−1)O(n^{-1}) bound on the expected suboptimality of the greedy policy. Consequently, O(ε−1)O(ε^{-1}) synchronous iterations suffice for an εε-optimal policy in expectation. These guarantees are instance-dependent, with constants that depend on the hitting-time parameters and the suboptimality gap of the second-best policy.

Explore similar work

Apr 19, 2026

Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration

Q-value iteration (Q-VI) is usually analyzed through the γγ-contraction of the Bellman operator. This argument proves convergence to Q∗Q^*, but it gives only a coarse account of when the induced greedy policy becomes optimal. We study discounted Q-VI as a switching system and focus on the practically optimal solution set (POSS), the set of QQ-functions whose tie-broken greedy policies are optimal. The main result shows that Q-VI reaches the optimal action class in finite time by entering an invariant tube around X1=Q∗+span⁡(1)\mathcal X_1=Q^*+\operatorname{span}(\mathbf 1), which is contained in the POSS. For every ε>0\varepsilon>0, the distance to X1\mathcal X_1 satisfies an exponential bound with rate (ρˉ+ε)k(\barρ+\varepsilon)^k, where ρˉ\barρ is the joint spectral radius of the projected switching family restricted to directions transverse to X1\mathcal X_1. When ρˉ<γ\barρ<γ, this transverse convergence is faster than the classical contraction rate. The analysis separates fast policy identification from the subsequent convergence to Q∗Q^*, which may still be governed by the all-ones mode. We also give spectral and graph-theoretic conditions under which the strict inequality ρˉ<γ\barρ<γ holds or fails.
Nov 15, 2026

Sharp Gaussian Approximation for Q-Learning

Gaussian approximation provides a foundation for online statistical inference in reinforcement learning. We establish sharp non-asymptotic Gaussian approximation rates in Wasserstein distance for asynchronous Q-learning with Polyak-Ruppert averaging. We prove an upper bound of O~(n−1/4)\widetilde{O}(n^{-1/4}), where nn is the number of iterations, together with a matching lower bound up to logarithmic factors. Q-learning is more challenging to analyze than linear stochastic approximation due to the nonlinearity of the Bellman operator. Asynchronous updates introduce further challenges due to Markovian noise. Our analysis separates the errors from Bellman nonlinearity, Markovian noise, and the finite-sample covariance discrepancy. In particular, we show that Markovian noise induces an unavoidable bias even when the Bellman operator is linear. The trade-off between this bias and the covariance discrepancy determines the convergence rate. We further extend our analysis to the synchronous setting and establish a sharp rate of O~(n−1/2)\widetilde{O}(n^{-1/2}).
Oct 14, 2026

Non-asymptotic Convergence of Average-reward Q-learning with Options

We study the finite-sample convergence of Q-learning algorithms for the average-reward formulation of Reinforcement Learning (RL) with options. While options allow temporarily extended and hierarchical actions, the average-reward formulation incorporates continual tasks beyond discounted and episodic RL. We establish the first O~(1/iterations)\tilde{O}(1/\text{iterations}) convergence guarantees, in the mean-square sense, for average-reward option Q-learning algorithms in both the inter- and intra-option settings. First, we prove that both inter- and intra-option Bellman operators satisfy multi-step span contractions under unichain assumptions. Then, we propose synchronous estimators of these multi-step option Bellman operators leading to two variants of option Q-learning. Finally, we extend the stochastic approximation framework to prove convergence rates of these two algorithms under the minimal assumptions used in the literature.