Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation

Abstract

This paper concerns error bounds for recursive equations subject to Markovian disturbances. Motivating examples abound within the fields of Markov chain Monte Carlo (MCMC) and Reinforcement Learning (RL), and many of these algorithms can be interpreted as special cases of stochastic approximation (SA). It is argued that it is not possible in general to obtain a Hoeffding bound on the error sequence, even when the underlying Markov chain is reversible and geometrically ergodic, such as the M/M/1 queue. This is motivation for the focus on mean square error bounds for parameter estimates. It is shown that mean square error achieves the optimal rate of $O(1/n)$, subject to conditions on the step-size sequence. Moreover, the exact constants in the rate are obtained, which is of great value in algorithm design.

References in corpus (6)

• Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning
• Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Fastest Convergence for Q-learning
• Most likely paths to error when estimating the mean of a reflected random walk
• Zap Q-Learning With Nonlinear Function Approximation

Cited by in corpus (2)

• On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning
• On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias