Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2020

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

Résumé

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

Dates et versions

hal-03094275 , version 1 (04-01-2021)

Identifiants

Citer

Shuhang Chen, Adithya M. Devraj, Ana Bušić, Sean Meyn. Explicit Mean-Square Error Bounds for Monte-Carlo and Linear Stochastic Approximation. AISTATS 2020: 23rd International Conference on Artificial Intelligence and Statistics, Aug 2020, Palermo / Virtual, Italy. ⟨hal-03094275⟩
53 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More