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

Shuhang Chen, Adithya Devraj, Ana Busic, Sean Meyn
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:4173-4183, 2020.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-chen20e, title = {Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation}, author = {Chen, Shuhang and Devraj, Adithya and Busic, Ana and Meyn, Sean}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {4173--4183}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/chen20e/chen20e.pdf}, url = {https://proceedings.mlr.press/v108/chen20e.html}, 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. } }
Endnote
%0 Conference Paper %T Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation %A Shuhang Chen %A Adithya Devraj %A Ana Busic %A Sean Meyn %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-chen20e %I PMLR %P 4173--4183 %U https://proceedings.mlr.press/v108/chen20e.html %V 108 %X 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.
APA
Chen, S., Devraj, A., Busic, A. & Meyn, S.. (2020). Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:4173-4183 Available from https://proceedings.mlr.press/v108/chen20e.html.

Related Material