提出统一方法,分析带乘性噪声的随机逼近收敛性。
Concentration and Mean-Square Bounds for Contractive Stochastic Approximation: A Unified Elementary Approach
- 用平均噪声和辅助迭代直接推导误差漂移不等式。
- 首次获得乘性噪声下子高斯尾部的最大集中界。
- 适合研究强化学习与迭代算法收敛性的研究人员。
我们为具有任意范数收缩映射的随机逼近(SA)建立了均方和集中度界,适用于噪声可仿射依赖于迭代器范数且迭代器可能无界的乘性噪声模型。该设定常见于强化学习中,其中算子通常在ℓ∞范数下收缩且噪声随迭代器规模变化。以往工作通过广义Moreau包络构造光滑李雅普诺夫函数处理非光滑范数,并采用多阶段自举论证分析集中性。本文提出统一且初等的分析框架:引入平均噪声序列和相应辅助迭代,直接建立范数误差的一步李雅普诺夫漂移不等式,无需平滑范数或构造包络。均方界通过归纳法证明迭代器期望有界;集中界则基于一系列“良好事件”的概率归纳,使标准Azuma-Hoeffding不等式可应用。该方法首次在乘性噪声下获得子高斯尾部的全时间最大集中界,允许步长对置信水平取对数依赖。此外,讨论了该证明技巧在其他噪声模型与迭代算法中的推广潜力。
原文摘要 · Abstract (English)
We establish mean-square and concentration bounds for stochastic approximation (SA) with arbitrary norm contractive mappings, under a multiplicative noise model where the noise may scale affinely with the norm of the iterates, and the iterates are potentially unbounded. These settings arise in reinforcement learning, where operators are often contractive in the $\ell_\infty$ norm and the noise scales with the iterates. To address the arbitrary norm, earlier works replace the non-smooth squared norm with a smooth Lyapunov function constructed via the generalized Moreau envelope. For concentration analysis, these works handle multiplicative noise and unbounded iterates through a multi-stage bootstrapping argument that starts from a time-varying worst-case bound and iteratively refines it. We instead present a unified and elementary analysis that yields both bounds. Using an averaged noise sequence and corresponding auxiliary iterates, we obtain a one-step Lyapunov drift inequality for the normed error directly, without smoothing the norm or constructing an envelope. For the mean-square bound, we combine this drift inequality with an induction argument showing that the iterates remain bounded in expectation. For the concentration bound, we develop a probabilistic induction over a sequence of "good" events on which the iterates are controlled, allowing the standard Azuma-Hoeffding bound to be applied. Our approach yields the first sub-Gaussian tailed maximal (all-time) concentration bound for SA under multiplicative noise, by allowing the stepsize to depend logarithmically on the confidence level. Beyond the specific setting considered here, we discuss the generalizability of these proof techniques to other noise models and iterative algorithms.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。