Skip to content

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

Nov 2026 · 0 citations · 23 references
Computer Science

TL;DR

Finite-time convergence guarantee for synchronous relative value iteration (RVI) $Q-learning for finite weakly communicating Markov decision processes (MDPs) is established and linear regularity and the noise condition for the centered Bellman operator for finite weakly communicating MDPs are verified.

Abstract

We establish finite-time convergence guarantee for synchronous relative value iteration (RVI) $Q$-learning for finite weakly communicating Markov decision processes (MDPs). For stochastic Krasnosel'ski\u{\i}--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^{-a}$ yield an $O(n^{-a})$ rate for $0<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})$ bound on the mean-squared Bellman span residual of RVI $Q$-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})$ bound on the expected suboptimality of the greedy policy. Consequently, $O(\epsilon^{-1})$ synchronous iterations suffice for an $\epsilon$-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.

View source

Similar papers

#machine learning Preprint Oct 2026

Hitting-Time Bounds for Asynchronous Q-Learning

We study the last iterate of standard asynchronous Q-learning from a single trajectory of a finite Markov decision process. The trajectory follows a fixed behavior policy whose state--action chain is irreducible and may be periodic. For discount factor $\gamma$, write $H=(1-\gamma)^{-1}$, and let $\mu_{\min}$ be the mi...

Peng Yang · 0 citations
#machine learning Preprint Sep 2026

Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data

We study the last iterate of standard importance-weighted temporal-difference (TD) learning from a single trajectory of a finite Markov decision process. The trajectory follows a behavior policy $b$ with an irreducible, possibly periodic state chain; a target policy $\pi$ covered by $b$ is evaluated with action importa...

Peng Yang · 1 citation
Preprint Oct 2026

On the Complexity of Finding Stationary Points in Stochastic $(L_0, L_1)$-Smooth Nonconvex Optimization

We study the stochastic first-order oracle (SFO) complexity of finding $\epsilon$-stationary points of $(L_0,L_1)$-smooth nonconvex functions. Under bounded-variance noise, existing analyses of normalized and clipped stochastic gradient descent (SGD) establish optimal dependence on $\epsilon$ and $L_0$, but the jointly...

Yan Liang, Luo Luo · 1 citation
#machine learning Preprint Oct 2026

Optimal Oracle Complexity for Finite-Sum Monotone Inclusions

We present an oracle-optimal method for finite-sum monotone inclusions under mean-square Lipschitz continuity. Our switching regularization method finds a point $y$ and a certificate $g\in G(y)$ with $(\mathbb{E}\|F(y)+g\|^2)^{1/2}\le\varepsilon$ using $\mathcal{O}(n+\sqrt{n}LR/\varepsilon)$ expected component evaluati...

Qi-Hao Zhou · 1 citation
Preprint Sep 2026

Adaptivity, Anchoring, and the Exact Oracle Complexity of Stochastic Fixed-Point Iterations

We study stochastic fixed-point iterations $x_{n+1}=\theta_nx_0+(1-\theta_n)\widehat T(x_n)$ for nonexpansive and contractive operators on Hilbert spaces, with a single-point unbiased oracle of bounded variance. Deterministically, every anchor schedule $\theta_n=c_n/(n+2)$ whose density $c_n\in(0,1]$ does not oscillate...

Y. Shehu · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.