Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913674994647040 |
|---|---|
| author | Samsonov, Sergey Moulines, Eric Shao, Qi-Man Zhang, Zhuo-Song Naumov, Alexey |
| author_facet | Samsonov, Sergey Moulines, Eric Shao, Qi-Man Zhang, Zhuo-Song Naumov, Alexey |
| contents | 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. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16644 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning Samsonov, Sergey Moulines, Eric Shao, Qi-Man Zhang, Zhuo-Song Naumov, Alexey Machine Learning Optimization and Control Probability Statistics Theory 60F05, 62L20, 62E20 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. 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. |
| title | Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning |
| topic | Machine Learning Optimization and Control Probability Statistics Theory 60F05, 62L20, 62E20 |
| url | https://arxiv.org/abs/2405.16644 |