提出通用方法，精准刻画平均化随机逼近的高概率误差边界。
A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging
- 基于未平均迭代的集中界，推导出平均后迭代的紧致误差界。
- 首次获得带平均的时序差分与Q-learning在复杂场景下的新误差界。
- 适用于需高概率保证的强化学习和优化算法，适合研究者参考。
Polyak-Ruppert平均是实现随机逼近（SA）算法最优渐近方差的常用技术，但其在一般设置下的高概率性能保证仍缺乏深入研究。本文提出一个通用框架，用于建立平均化SA迭代误差的非渐近集中界。该方法仅需假设未平均迭代的集中性，并可导出平均迭代的紧致上界。我们还构造了一个例子，证明结果在常数因子意义下紧致。作为直接应用，我们推导出收缩型SA算法，以及带有平均的时序差分学习和Q-learning的紧致集中界，在传统分析困难的设置中获得了新结果。
原文摘要 · Abstract (English)
Polyak-Ruppert averaging is a widely used technique to achieve the optimal asymptotic variance of stochastic approximation (SA) algorithms, yet its high-probability performance guarantees remain underexplored in general settings. In this paper, we present a general framework for establishing non-asymptotic concentration bounds for the error of averaged SA iterates. Our approach assumes access to individual concentration bounds for the unaveraged iterates and yields a sharp bound on the averaged iterates. We also construct an example, showing the tightness of our result up to constant multiplicative factors. As direct applications, we derive tight concentration bounds for contractive SA algorithms and for algorithms such as temporal difference learning and Q-learning with averaging, obtaining new bounds in settings where traditional analysis is challenging.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。