Linear Stochastic Approximation: Constant Step-Size and Iterate\n Averaging

2017/09/12 by Chandrashekar Lakshminarayanan, Csaba Szepesvári, Lakshminarayanan, Chandrashekar +1 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Age of Information Optimization #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.1709.04073

openalex publication_date 2017/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider d-dimensional linear stochastic approximation algorithms (LSAs)\nwith a constant step-size and the so called Polyak-Ruppert (PR) averaging of\niterates. LSAs are widely applied in machine learning and reinforcement\nlearning (RL), where the aim is to compute an appropriate \θ_* \∈\n\ℝ^d (that is an optimum or a fixed point) using noisy data and O(d)\nupdates per iteration. In this paper, we are motivated by the problem (in RL)\nof policy evaluation from experience replay using the \temporal\ndifference (TD) class of learning algorithms that are also LSAs. For LSAs with\na constant step-size, and PR averaging, we provide bounds for the mean squared\nerror (MSE) after t iterations. We assume that data is iid with finite\nvariance (underlying distribution being P) and that the expected dynamics is\nHurwitz. For a given LSA with PR averaging, and data distribution P\nsatisfying the said assumptions, we show that there exists a range of constant\nstep-sizes such that its MSE decays as O(\(1)/(t)).\n We examine the conditions under which a constant step-size can be chosen\nuniformly for a class of data distributions \P, and show that not\nall data distributions `admit' such a uniform constant step-size. We also\nsuggest a heuristic step-size tuning algorithm to choose a constant step-size\nof a given LSA for a given data distribution P. We compare our results with\nrelated work and also discuss the implication of our results in the context of\nTD algorithms that are LSAs.\n

Cited by

• Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates
• A Distributional Analysis of Sampling-Based Reinforcement Learning\n Algorithms

Related

• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration
• Revisiting Step-Size Assumptions in Stochastic Approximation
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation
• Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning
• The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning