Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q Q -Learning

Ankur Naskar, Gugan Thoppe, Vijay Gupta · 2025

Read Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q Q -Learning by Ankur Naskar, Gugan Thoppe, Vijay Gupta (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05984.txt.

Introduction

Ankur Naskar, Gugan Thoppe, and Vijay Gupta tackled a math problem in 2025 that sits behind many learning algorithms. These methods hunt for a fixed point of a shrinking map, but the shrink is measured in a loose way that breaks the usual tools for proving fast progress.

The authors recast the averaged error as a simple step by step process with a small bent term. They then tame that term by pairing the loose measure with a stricter one that behaves well. The result gives the first rates for a key learning method that need no tuning values, in both steady reward and fading reward settings. The proof covers single and shared setups.

Catalog record

CREATORAnkur Naskar, Gugan Thoppe, Vijay Gupta
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-05984

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q Q -Learning Ankur Naskar, Gugan Thoppe, Vijay Gupta Abstract Algorithms for solving nonlinear fixed-point equations—such as average-reward Q Q -learning and TD-learning —often involve semi-norm contractions. Achieving parameter-free optimal convergence rates for these methods via Polyak–Ruppert averaging has remained elusive, largely due to the non-monotonicity of such semi-norms. We close this gap by (i.) recasting the averaged error as a linear recursion involving a nonlinear perturbation, and (ii.) taming the nonlinearity by coupling the semi-norm’s contraction with the monotonicity of a suitably induced norm. Our main result yields the first parameter-free O ~ ​ ( 1 / t ) \tilde{O}(1/\sqrt{t}) optimal rates for Q Q -learning in both average-reward and exponentially discounted settings, where t t denotes the iteration index. The result applies within a broad framework that accommodates synchronous and asynchronous updates, single-agent and distributed deployments, and data streams obtained either from simulators or along Markovian trajectories. 1 Introduction Stochastic fixed-point iterations with contractive operators ( Borkar 2009 ) permeate many fields. In Reinforcement Learning (RL), Temporal Difference (TD) 1 1 1 Although Q -learning falls within the broader family of TD methods, we use TD exclusively for policy-evaluation algorithms. learning and Q -learning are canonical examples ( Bertsekas and Tsitsiklis 1996 ; Sutton and Barto 2018 ; Szepesvári 2022 ) . Game-theoretic approaches to decentralized learning and Nash-equilibrium computation adopt the same template ( Sayin et al. 2021 ; Hu and Wellman 2003 ) . In optimization, stochastic fixed-point iterations underpin methods for regularized least squares in over-parameterized models and for low-rank matrix completion ( Li, Ma, and Zhang 2018 ; Marjanovic and Solo 2012 ) . They are likewise of growing importance in nonlinear dynamical systems, where fixed-point theory has become an important tool for analysis and control design, particularly in robotics ( Lohmiller and Slotine 1997 ; Manchester and Slotine 2014 ; Manchester, Tang, and Slotine 2017 ; Tsukamoto, Chung, and Slotine 2021 ) . Here, we focus on stochastic fixed-point iterations driven by semi-norm contractions. Their generic update rule is Q_{t+1}=Q_{t}+\alpha_{t}\left[h(Q_{t},y_{t})-Q_{t}\right], (1) where (y_{t}) is an ergodic Markov chain on a state space \mathcal{Y} with a unique stationary distribution \eta and h:\mathbb{R}^{d}\times\mathcal{Y}\to\mathbb{R}^{d} is such that the expected map H(Q)=\mathbb{E}_{y\sim\eta}h(Q,y) is a semi-norm contraction. In other words, we have a semi-norm \upsilon:\mathbb{R}^{d}\to\mathbb{R} and a factor \beta\in[0,1) so that \upsilon(H(x)-H(y))\leq\beta\ \upsilon(x-y)\quad\forall x,y\in\mathbb{R}^{d}. (2) A semi-norm is similar to a norm that need not satisfy the positive definiteness condition. Specifically, for all x,y\in\mathbb{R}^{d} and \lambda\in\mathbb{R}, a semi-norm \upsilon satisfies non-negativity ( \upsilon(x)\geq 0 ), absolute homogeneity ( \upsilon(\lambda x)=|\lambda|\upsilon(x) ), and sub-additivity ( \upsilon(x+y)\leq\upsilon(x)+\upsilon(y) ), but not necessarily positive definiteness ( \upsilon(x)=0\nRightarrow x=0 ). As a result, every norm is a semi-norm, but the converse does not hold. Reference Distributed Discounting Asynchronous Optimal rate Universal stepsize TD Learning Dalal et al. 2018 ✗ Exp ✓ ✗ ✓ Patil et al. 2023 ✗ Exp ✓ ✓ ✓ Chen et al. 2021a ✗ Exp ✓ ✓ ✗ Lakshminarayanan and Szepesvari 2018 ✗ Exp and Avg ✓ ✓ ✗ Bhandari, Russo, and Singal 2018 ✗ Exp ✓ ✓ ✗ Chen et al. 2021b ✗ Exp ✓ ✓ ✗ Durmus et al. 2025 ✗ Exp ✓ ✓ ✗ Bhandari, Russo, and Singal 2021 ✗ Exp ✓ ✓ ✗ Chen et al. 2025 ✗ Exp and Avg ✓ ✓ ✗ Dal Fabbro, Mitra, and Pappas 2023 ✓ Exp ✓ ✓ ✗ Khodadadian et al. 2022 ✓ Exp ✓ ✓ ✗ Liu and Olshevsky 2023 ✓ Exp ✓ ✓ ✗ Wang et al. 2024 ✓ Exp ✓ ✓ ✗ Naskar et al. 2024 ✓ Exp ✓ ✓ ✓ Q -Learning Even-Dar and Mansour 2003 ✗ Exp ✗ ✗ ✓ Zhang, Zhang, and Maguluri 2021 ✗ Avg ✗ ✓ ✗ Wainwright 2019 ✗ Exp ✗ ✓ ✗ Li et al. 2023 ✗ Exp ✗ ✓ ✓ Our Work ✓ Exp and Avg ✓ ✓ ✓ Table 1: Comparison of our work with the existing literature on TD-learning and Q -learning algorithms. In the column labeled discounting, Exp refers to exponential, while Avg refers to average reward. The role of semi-norm contractions in RL methods such as TD and Q -learning is fundamental. In these methods, the Bellman operator is contractive—under a semi-norm in the average-reward formulation and under a true norm (hence, also a semi-norm) in exponential discounting ( Bertsekas and Tsitsiklis 1996 ) . The generic recursion in ( 1 ) subsumes all variants of TD methods and Q -learning—including the ones with synchronous and asynchronous updates, single-agent and distributed deployments, and data drawn from generative models and Markovian trajectories. Achieving optimal convergence rates in such algorithms is of fundamental interest. Several works have obtained such bounds for TD algorithms and Q -learning in their various forms. TD methods, for instance, have been looked at in ( Dalal et al. 2018 ; Lakshminarayanan and Szepesvari 2018 ; Bhandari, Russo, and Singal 2018 ; Zhang, Zhang, and Maguluri 2021 ; Liu and Olshevsky 2023 ; Khodadadian et al. 2022 ; Dal Fabbro, Mitra, and Pappas 2023 ) and ( Wang et al. 2024 ) . On the other hand, tabular Q -learning has been the focus of ( Even-Dar and Mansour 2003 ; Chen et al. 2021a ; Zhang, Zhang, and Maguluri 2021 ) and ( Chen et al. 2025 ) . Table 1 summarizes the key differences in these results. However, a key drawback of these results is that the optimal root mean squared bound, \tilde{O}(1/\sqrt{t}) , is achieved only with a stepsize \alpha_{t}=c/t , where the constant c depends on unknown transition probabilities. Such a c is rarely available, making these rates effectively impractical. For linear stochastic approximation, ( Polyak and Juditsky 1992 ) and ( Ruppert 1991 ) proposed a remarkable solution—now called Polyak–Ruppert averaging. Applied to an update rule like ( 1 ), this procedure works in two steps: 1. Generate base iterates : Run (Q_{t}) with the parameter-free stepsize \alpha_{t}=1/(t+1)^{\alpha} for some \alpha\in(1/2,1). 2. Average them : Form the running mean \bar{Q}_{T}=\frac{1}{T}\sum_{t=0}^{T-1}Q_{t}, again without any problem-specific tuning. While this procedure yields a suboptimal convergence rate of \tilde{O}(1/t^{\alpha/2}) for the (Q_{t}) sequence, the averaged sequence (\bar{Q}_{t}) attains the desired optimal rate of \tilde{O}(1/\sqrt{t}). For TD-learning with linear function approximation—a special case of linear stochastic approximation—Polyak–Ruppert averaging already achieves parameter-free optimal rates, both for exponential discounting ( Patil et al. 2023 ) and for average reward ( Naskar et al. 2024 ) . Q -learning with Polyak–Ruppert averaging is challenging due to the algorithm’s inherent nonlinearity. A recent breakthrough by Li et al. 2023 addresses this challenge for synchronous Q-learning with exponential discounting . In this setting, the Bellman operator is a contraction in the monotone \|\cdot\|_{\infty} norm. The authors’ key idea is to construct two auxiliary sequences, (L_{t}) and (U_{t}) , whose Polyak–Ruppert averages bound the error in (\bar{Q}_{t}) from below and above, respectively. Each auxiliary sequence follows the template of a linear stochastic approximation with a rapidly vanishing nonlinear remainder. Classical Polyak–Ruppert analysis then yields a \tilde{O}(1/\sqrt{t}) rate for both. By the monotonicity of \|\cdot\|_{\infty} , these bounds transfer directly to \bar{Q}_{t} . For synchronous Q -learning with exponential discounting, the raw iterates (Q_{t}) already achieve the optimal rate

Read the complete text