Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
This work provides theoretical guarantees for algorithm design in fields like MCMC and RL, though it is incremental as it builds on existing stochastic approximation theory.
The paper tackles the problem of deriving explicit error bounds for stochastic approximation algorithms under Markovian disturbances, showing that mean square error achieves the optimal O(1/n) rate with exact constants, which aids in algorithm design.
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.