Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
复制标题
DOI：
--
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
Shuhang Chen;Adithya M. Devraj;A. Bušić;Sean P. Meyn
中科院分区：
文献类型：
--
作者：
Shuhang Chen;Adithya M. Devraj;A. Bušić;Sean P. Meyn
本文研究了带有马尔可夫扰动的递归方程的误差界。在马尔可夫链蒙特卡罗（MCMC）和强化学习（RL）领域中有很多令人鼓舞的例子，其中许多算法可以被解释为随机近似（SA）的特殊情况。有人认为，这是不可能的，在一般情况下，以获得一个Hoeffding界的错误序列，即使当底层马尔可夫链是可逆的和几何遍历，如M/M/1队列。这是聚焦于参数估计的均方误差界的动机。结果表明，均方误差达到最佳的速度为O（1/n）$，受步长序列的条件。此外，还得到了速率常数的精确表达式，这对算法设计具有重要的参考价值。
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.