Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning

P. 12408–12460.

Samsonov S., Moulines E., Shao Q., Zhang Z., Naumov A.

In this paper, we obtain the Berry–Esseen bound for multivariate normal approximation for the Polyak-Ruppert averaged iterates of the linear stochastic approximation (LSA) algorithm with decreasing step size. Our findings reveal that the fastest rate of normal approximation is achieved when setting the most aggressive step size αk ≍ k −1/2 . Moreover, we prove the non-asymptotic validity of the confidence intervals for parameter estimation with LSA based on multiplier bootstrap. This procedure updates the LSA estimate together with a set of randomly perturbed LSA estimates upon the arrival of subsequent observations. We illustrate our findings in the setting of temporal difference learning with linear function approximation.

Keywords: stochastic approximation, Gaussian approximation, Multiplier bootstrap, Polyak-Ruppert averaging

Publication based on the results of: Development and theoretical analysis of new effective stochastic machine learning algorithms (2024)

In book

38th Conference on Neural Information Processing Systems (NeurIPS 2024)

[б.и.], 2024.