A Robust \widetildeO(1/√(T)) Rate for Unprojected TD Learning with Linear Function Approximation

2025/06/01 by Wei‐Cheng Lee, Francesco Orabona, Lee, Wei-Cheng +1 · 1 citation
Computer Science · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Neural Networks and Applications #Optimization and Control (math.OC) #Speech and Audio Processing

paper · pdf · doi:10.48550/arxiv.2506.01052

openalex publication_date 2025/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the finite-time convergence properties of Temporal Difference (TD) learning with linear function approximation, a cornerstone of reinforcement learning. We are interested in the so-called ``robust'' setting, where the convergence guarantee does not depend on the potential function's minimal curvature. While prior work has established convergence guarantees in this setting, these results typically rely on the artificial assumption that each iterate is projected onto a bounded set. Removing such a condition was left as an open problem by Bhandari et al. (COLT'18), hypothesizing the need for additional ``regularity conditions''. In this paper, we show that the simple unprojected TD(0) converges with a rate of \widetildeO((‖θ^*‖²₂)/(√(T))) in expectation, even in the presence of Markovian noise. We do not require an additional regularity condition, but only a minor polylog correction to the learning rate. Our analysis reveals a novel self-bounding property of the TD updates and exploits it to guarantee bounded iterates.

Citations

• A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation
• Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability
• DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule
• Stochastic linear optimization never overfits with quadratically-bounded losses on general data
• Parameter-free Stochastic Optimization of Variationally Coherent Functions
• Temporal Difference Learning as Gradient Splitting
• Adaptive Temporal Difference Learning with Linear Function Approximation
• Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
• Finite-Time Error Bounds For Linear Stochastic Approximation and TD\n Learning
• A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation
• Approximate Temporal Difference Learning is a Gradient Descent for Reversible Policies
• Black-Box Reductions for Parameter-free Online Learning in Banach Spaces
• Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updates
• Adam: A Method for Stochastic Optimization
• On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence
• Logarithmic Sobolev inequalities for finite Markov chains

Cited by

• Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates

Related

• A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation
• Finite Sample Analyses for TD(0) with Function Approximation
• A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation
• Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features
• Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features