A Finite-Time Analysis of TD Learning with Linear Function Approximation without Projections or Strong Convexity
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911174997573632 |
|---|---|
| author | Lee, Wei-Cheng Orabona, Francesco |
| author_facet | Lee, Wei-Cheng Orabona, Francesco |
| contents | We investigate the finite-time convergence properties of Temporal Difference (TD) learning with linear function approximation, a cornerstone algorithm in the field of reinforcement learning.
We are interested in the so-called ``robust'' setting, where the convergence guarantee does not depend on the minimal curvature of the potential function.
While prior work has established convergence guarantees in this setting, these results typically rely on the assumption that each iterate is projected onto a bounded set, a condition that is both artificial and does not match the current practice.
In this paper, we challenge the necessity of such an assumption and present a refined analysis of TD learning. For the first time, we show that the simple projection-free variant converges with a rate of $\widetilde{\mathcal{O}}(\frac{||θ^*||^2_2}{\sqrt{T}})$, even in the presence of Markovian noise. Our analysis reveals a novel self-bounding property of the TD updates and exploits it to guarantee bounded iterates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01052 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Finite-Time Analysis of TD Learning with Linear Function Approximation without Projections or Strong Convexity Lee, Wei-Cheng Orabona, Francesco Machine Learning Optimization and Control We investigate the finite-time convergence properties of Temporal Difference (TD) learning with linear function approximation, a cornerstone algorithm in the field of reinforcement learning. We are interested in the so-called ``robust'' setting, where the convergence guarantee does not depend on the minimal curvature of the potential function. While prior work has established convergence guarantees in this setting, these results typically rely on the assumption that each iterate is projected onto a bounded set, a condition that is both artificial and does not match the current practice. In this paper, we challenge the necessity of such an assumption and present a refined analysis of TD learning. For the first time, we show that the simple projection-free variant converges with a rate of $\widetilde{\mathcal{O}}(\frac{||θ^*||^2_2}{\sqrt{T}})$, even in the presence of Markovian noise. Our analysis reveals a novel self-bounding property of the TD updates and exploits it to guarantee bounded iterates. |
| title | A Finite-Time Analysis of TD Learning with Linear Function Approximation without Projections or Strong Convexity |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2506.01052 |