Establishes an O(1/k) MSE convergence rate for TD(0) with LFA that is independent of the smallest eigenvalue of the uncentered covariance matrix and robust to ill-conditioning.
A finite-time analysis of td learning with linear function approximation without projections nor strong convexity
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
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.
verdicts
UNVERDICTED 3representative citing papers
Presents an SDE diffusion approximation for linear TD(0) under Markovian noise that explains the constant-stepsize error floor via interaction of long-run covariance and projected Bellman operator geometry.
A novel robust asynchronous Q-learning algorithm achieves finite-time convergence rates that match clean-data bounds up to an additive term proportional to the corruption fraction, with a matching information-theoretic lower bound.
citing papers explorer
-
Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples
Establishes an O(1/k) MSE convergence rate for TD(0) with LFA that is independent of the smallest eigenvalue of the uncentered covariance matrix and robust to ill-conditioning.
-
A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noise
Presents an SDE diffusion approximation for linear TD(0) under Markovian noise that explains the constant-stepsize error floor via interaction of long-run covariance and projected Bellman operator geometry.
-
Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates
A novel robust asynchronous Q-learning algorithm achieves finite-time convergence rates that match clean-data bounds up to an additive term proportional to the corruption fraction, with a matching information-theoretic lower bound.