Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909179782889472 |
|---|---|
| author | Zhang, Yixuan Huo, Dongyan Chen, Yudong Xie, Qiaomin |
| author_facet | Zhang, Yixuan Huo, Dongyan Chen, Yudong Xie, Qiaomin |
| contents | Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant stepsize. We focus on two important classes of dynamics: 1) nonsmooth contractive SA with additive noise, and 2) synchronous and asynchronous Q-learning, which features both additive and multiplicative noise. For both dynamics, we establish weak convergence of the iterates to a stationary limit distribution in Wasserstein distance. Furthermore, we propose a prelimit coupling technique for establishing steady-state convergence and characterize the limit of the stationary distribution as the stepsize goes to zero. Using this result, we derive that the asymptotic bias of nonsmooth SA is proportional to the square root of the stepsize, which stands in sharp contrast to smooth SA. This bias characterization allows for the use of Richardson-Romberg extrapolation for bias reduction in nonsmooth SA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_06023 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA Zhang, Yixuan Huo, Dongyan Chen, Yudong Xie, Qiaomin Machine Learning Optimization and Control Probability Motivated by Q-learning, we study nonsmooth contractive stochastic approximation (SA) with constant stepsize. We focus on two important classes of dynamics: 1) nonsmooth contractive SA with additive noise, and 2) synchronous and asynchronous Q-learning, which features both additive and multiplicative noise. For both dynamics, we establish weak convergence of the iterates to a stationary limit distribution in Wasserstein distance. Furthermore, we propose a prelimit coupling technique for establishing steady-state convergence and characterize the limit of the stationary distribution as the stepsize goes to zero. Using this result, we derive that the asymptotic bias of nonsmooth SA is proportional to the square root of the stepsize, which stands in sharp contrast to smooth SA. This bias characterization allows for the use of Richardson-Romberg extrapolation for bias reduction in nonsmooth SA. |
| title | Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA |
| topic | Machine Learning Optimization and Control Probability |
| url | https://arxiv.org/abs/2404.06023 |