aiqbench analysis
This paper resolves a longstanding open problem in reinforcement learning by proving that unprojected TD(0) with linear function approximation converges at a robust $\widetilde{\mathcal{O}}(1/\sqrt{T})$ rate without requiring artificial projection assumptions or additional regularity conditions. The authors achieve this by identifying a novel self-bounding property in the TD updates that inherently guarantees bounded iterates, even under Markovian noise. This theoretical advancement simplifies the practical implementation of TD learning by removing unnecessary constraints while maintaining strong convergence guarantees.
A Robust $\widetilde{\mathcal{O}}(1/\sqrt{T})$ Rate for Unprojected TD Learning with Linear Function Approximation
arXiv:2506.01052v3 Announce Type: replace 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 $\widetilde{\mathcal{O}}\left(\frac{\|\theta^*\|^2_2}{\sqrt{T}}\right)$ 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.
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 $\widetilde{\mathcal{O}}\left(\frac{\|\theta^*\|^2_2}{\sqrt{T}}\right)$ 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.
Machine Learning (cs.LG); Optimization and Control (math.OC); Machine Learning (stat.ML)
arXiv:2506.01052 [cs.LG]
(or arXiv:2506.01052v3 [cs.LG] for this version)
Full text under the publisher's open licence · 169 words
Related coverage
Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication
arXiv · Sep 30, 2026
Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
arXiv · Sep 15, 2026
Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret
arXiv · Oct 7, 2026
Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Convex Sets
arXiv · Oct 14, 2026