首次实现无需调参的$Q$-learning最优收敛率，突破半范数非单调难题
Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to $Q$-Learning
- 将平均误差重构为含非线性扰动的线性递推式
- 通过诱导范数单调性控制非线性，达成$ ilde{O}(1/ ext{sqrt}{t})$速率
- 适用于同步/异步、单智能体/分布式、模拟/马尔可夫轨迹等场景
求解非线性不动点方程（如平均奖励$Q$-learning和TD学习）的算法常涉及半范数收缩。由于半范数的非单调性，利用Polyak-Ruppert平均实现无参数最优收敛率一直未获突破。本文通过（i）将平均误差重写为含非线性扰动的线性递推，（ii）借助适当诱导范数的单调性控制非线性，首次在平均奖励与指数折扣设定下，实现参数自由的$ ilde{O}(1/ ext{sqrt}{t})$最优收敛率，其中$t$为迭代次数。该结果适用于同步与异步更新、单智能体与分布式部署，以及来自模拟器或马尔可夫轨迹的数据流。
原文摘要 · Abstract (English)
Algorithms for solving \textit{nonlinear} fixed-point equations -- such as average-reward \textit{$Q$-learning} and \textit{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 $\tilde{O}(1/\sqrt{t})$ optimal rates for $Q$-learning in both average-reward and exponentially discounted settings, where $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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。