Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning

By Rayadurgam Srikant, Lei Ying. Annual Conference Computational Learning Theory, 2019

305 citations recorded by the source corpus.

We consider the dynamics of a linear stochastic approximation algorithm driven by Markovian noise, and derive finite-time bounds on the moments of the error, i.e., deviation of the output of the algorithm from the equilibrium point of an associated ordinary differential equation (ODE). We obtain finite-time bounds on the mean-square error in the case of constant step-size algorithms by considering the drift of an appropriately chosen Lyapunov function. The Lyapunov function can be interpreted either in terms of Stein's method to obtain bounds on steady-state performance or in terms of Lyapunov stability theory for linear ODEs. We also provide a comprehensive treatment of the moments of the square of the 2-norm of the approximation error. Our analysis yields the following results: (i) for a given step-size, we show that the lower-order moments can be made small as a function of the step-size and can be upper-bounded by the moments of a Gaussian random variable; (ii) we show that the higher-order moments beyond a threshold may be infinite in steady-state; and (iii) we characterize the number of samples needed for the finite-time bounds to be of the same order as the steady-state bounds. As a by-product of our analysis, we also solve the open problem of obtaining finite-time bounds for the performance of temporal difference learning algorithms with linear function approximation and a constant step-size, without requiring a projection step or an i.i.d. noise assumption.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/1e9f0ef50206416b1453871a0875298d0f03947c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Zhuoran Yang
2. Kaiqing Zhang
3. Tamer Basar
4. Xin Chen
5. Guannan Qu
6. Steven H. Low
7. Na Li
8. Yujie Tang

In Computer Networks and Communications

1. Guannan Qu
2. Na Li
3. Zhuoran Yang
4. Kaiqing Zhang
5. Tamer Basar
6. Steven H. Low
7. Angelia Nedić
8. Davood Hajinezhad

In Statistics and Probability

1. Zhuoran Yang
2. Kaiqing Zhang
3. Xin Chen
4. Tamer Basar
5. Guannan Qu
6. Steven H. Low
7. Na Li
8. Yujie Tang

Citations in the corpus

• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction (2020, unknown): “Convergence of several model-free RL algorithms has been studied recently in the presence of Markovian data, including but not limited to TD learning and its variants [6, 11, 12, 15, 23, 27, 30, 39, 50, 51], Q-learning [10, 49], and SARSA [53].”
• Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, background): “Furthermore, motivated by the recent progress in [210], finite-time performance of the more general distributed TD(λ) algorithm is provided in [157], with neither projection nor i.”
• Reinforcement Learning for Selective Key Applications in Power Systems: Recent Advances and Future Challenges (2021, methodology): “Essentially, TD learning (5) is a stochastic approximation scheme for solving the Bellman Equation (3) [22], and can be shown to converge to the true Q π under mild assumptions [21], [23].”