Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise
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_ | 1866909913745195008 |
|---|---|
| author | Blaser, Ethan Zhang, Shangtong |
| author_facet | Blaser, Ethan Zhang, Shangtong |
| contents | Stochastic approximation is a powerful class of algorithms with celebrated success. However, a large body of previous analysis focuses on stochastic approximations driven by contractive operators, which is not applicable in some important reinforcement learning settings like the average reward setting. This work instead investigates stochastic approximations with merely nonexpansive operators. In particular, we study nonexpansive stochastic approximations with Markovian noise, providing both asymptotic and finite sample analysis. Key to our analysis are novel bounds of noise terms resulting from the Poisson equation. As an application, we prove for the first time that classical tabular average reward temporal difference learning converges to a sample-path dependent fixed point. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_19546 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise Blaser, Ethan Zhang, Shangtong Machine Learning Artificial Intelligence Optimization and Control Stochastic approximation is a powerful class of algorithms with celebrated success. However, a large body of previous analysis focuses on stochastic approximations driven by contractive operators, which is not applicable in some important reinforcement learning settings like the average reward setting. This work instead investigates stochastic approximations with merely nonexpansive operators. In particular, we study nonexpansive stochastic approximations with Markovian noise, providing both asymptotic and finite sample analysis. Key to our analysis are novel bounds of noise terms resulting from the Poisson equation. As an application, we prove for the first time that classical tabular average reward temporal difference learning converges to a sample-path dependent fixed point. |
| title | Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise |
| topic | Machine Learning Artificial Intelligence Optimization and Control |
| url | https://arxiv.org/abs/2409.19546 |