论文标题
蒙特卡洛和线性随机近似的显式均方误差边界
Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation
论文作者
论文摘要
本文涉及递归方程的错误界限，但受到马尔可夫干扰的影响。马尔可夫链蒙特卡洛（MCMC）和增强学习（RL）领域中充满了激励的例子，并且这些算法中的许多算法都可以解释为特殊的随机近似案例（SA）。有人认为，即使基础马尔可夫链是可逆且几何刻化的，例如M/M/1队列，也不可能获得在误差序列上结合的HOEFFDING。这是关注参数估计的均方根误差范围的动机。结果表明，均方根误差达到了$ 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.
