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

Ankur Naskar; Gugan Thoppe; Vijay Gupta

AAAI 2026technical0 citations

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

Abstract

Algorithms for solving nonlinear fixed-point equations---such as average-reward 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

BibTeX

@inproceedings{aaai2026_parameterfreeopt,
  title = {Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learning},
  author = {Ankur Naskar and Gugan Thoppe and Vijay Gupta},
  booktitle = {AAAI 2026},
  year = {2026}
}