Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
Authors:
- Zaiwei ChenZCZaiwei Chen
Preprint
Abstract
Stochastic Approximation (SA) is a popular approach for solving fixed point equations where the information is corrupted by noise. In this paper, we consider an SA involving a contraction mapping with respect to an arbitrary norm, and show its finite-sample bound for using either constant or diminishing step sizes. The idea is to construct a smooth Lyapunov function using the generalized Moreau envelope, and show that the iterates of SA are contracting in expectation with respect to that Lyapunov function. The result is applicable to various Reinforcement Learning (RL) algorithms. In particular, we use it to establish the first-known convergence rate of the V-trace algorithm for the off-policy TD-Learning [15], and improve the existing bound for the tabular $Q$-Learning algorithm. Further, for these two applications, our construction of the Lyapunov functions results in only a logarithmic dependence of the convergence bound on the state-space dimension.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- A Finite Time Analysis of Temporal Difference Learning with Linear Function ApproximationOperations Research, 2021
- A Concentration Bound for Stochastic Approximation via Alekseev’s FormulaStochastic Systems, 2019
- Stochastic Model-Based Minimization of Weakly Convex FunctionsSIAM Journal on Optimization, 2019
- Error bounds for constant step-size -learningSystems & Control Letters, 2012
- Convergence Results for Some Temporal Difference Methods Based on Least SquaresIEEE Transactions on Automatic Control, 2009
- Boundedness of iterates in Q-LearningSystems & Control Letters, 2006
- Learning Rates for Q-LearningLecture Notes in Computer Science, 2001
- The O.D.E. Method for Convergence of Stochastic Approximation and Reinforcement LearningSIAM Journal on Control and Optimization, 2000
- Temporal difference learning and TD-GammonCommunications of the ACM, 1995
- Importance Sampling for Stochastic SimulationsManagement Science, 1989