Linear Stochastic Approximation: Constant Step-Size and Iterate Averaging
Chandrashekar Lakshminarayanan and Csaba Szepesvári, University of Alberta
Abstract
We consider $d$ -dimensional linear stochastic approximation algorithms (LSAs) with a constant step-size and the so called Polyak-Ruppert (PR) averaging of iterates. LSAs are widely applied in machine learning and reinforcement learning (RL), where the aim is to compute an appropriate $\theta_{*}\in\mathbb{R}^{d}$ (that is an optimum or a fixed point) using noisy data and $O(d)$ updates per iteration. In this paper, we are motivated by the problem (in RL) of policy evaluation from experience replay using the temporal difference (TD) class of learning algorithms that are also LSAs. For LSAs with a constant step-size, and PR averaging, we provide bounds for the mean squared error (MSE) after $t$ iterations. We assume that data is i.i.d. with finite variance (underlying distribution being $P$ ) and that the expected dynamics is Hurwitz. For a given LSA with PR averaging, and data distribution $P$ satisfying the said assumptions, we show that there exists a range of constant step-sizes such that its MSE decays as $O(\frac{1}{t})$ .
中文速览
用固定步长加 Polyak-Ruppert（PR）均值化来运行线性随机近似算法（LSA）是强化学习中策略评估的常用手段，但何时能保证误差以 O(1/t) 速率收敛、步长又该怎么选，此前缺乏系统性分析。本文针对 i.i.d. 数据、期望动态矩阵满足 Hurwitz 条件的一般 LSA，首次给出了有限时间内均方误差（MSE）的显式上界，证明只要步长落在某个与分布相关的范围内，MSE 就能以 O(1/t) 衰减。进一步，文章发现并非所有分布族都允许选出一个"通用"固定步长来保证误差一致有界——这一负面结论直接适用于强化学习中的 TD 算法族，说明步长必须依赖具体问题实例来选取；为此作者还提出了一种启发式自动步长调节方法，实验表明它能有效防止 MSE 发散。这项工作填补了 CS-PR 技术从 SGD 推广到一般 LSA（包括 GTD/GTD2 等离轨策略算法）的理论空白，并将 GTD 类算法的收敛率从已知的 O(1/√t) 提升至 O(1/t)。
原文 arXiv:1709.04073;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1709.04073v1