# A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation

arXiv: https://arxiv.org/abs/2403.02476 · HTML: https://mlsanity.com/paper/2403.02476/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 33 references that are in the map.
- First posted on arXiv 4 Mar 2024.

## Builds on (most cited first, 15 of 15)

- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates](https://mlsanity.com/paper/1806.10188/) (2018)
- [The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2110.14427/) (2021)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity](https://mlsanity.com/paper/2302.02212/) (2023)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)
- [On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence](https://mlsanity.com/paper/1411.3224/) (2014)
- [Temporal Difference Learning as Gradient Splitting](https://mlsanity.com/paper/2010.14657/) (2020)
- [On Communication Compression for Distributed Optimization on Heterogeneous Data](https://mlsanity.com/paper/2009.02388/) (2020)
- [Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning](https://mlsanity.com/paper/2301.00944/) (2023)
- [Linear Stochastic Approximation: Constant Step-Size and Iterate Averaging](https://mlsanity.com/paper/1709.04073/) (2017)
- [The case for and against fixed step-size: Stochastic approximation algorithms in optimization and machine learning](https://mlsanity.com/paper/2309.02944/) (2023)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)

## Built on by (most cited first, 16 of 16)

- [Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2409.12135/) (2024)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [A General-Purpose Theorem for High-Probability Bounds of Stochastic Approximation with Polyak Averaging](https://mlsanity.com/paper/2505.21796/) (2025)
- [Scalable Policy-Based RL Algorithms for POMDPs](https://mlsanity.com/paper/2510.06540/) (2025)
- [Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis](https://mlsanity.com/paper/2503.17454/) (2025)
- [Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling](https://mlsanity.com/paper/2504.11645/) (2025)
- [A Robust widetildeO(1/√T) Rate for Unprojected TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2506.01052/) (2025)
- [Implicit Updates for Average-Reward Temporal Difference Learning](https://mlsanity.com/paper/2510.06149/) (2025)
- [A Single Stepsize Suffices for Unprojected Linear TD(0): Simultaneous Robust and Fast Rates via Polyak--Ruppert Averaging](https://mlsanity.com/paper/2606.24981/) (2026)
- [Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates](https://mlsanity.com/paper/2509.08933/) (2025)
- [Towards Parameter-Free Temporal Difference Learning](https://mlsanity.com/paper/2603.02577/) (2026)
- [A Short and Unified Convergence Analysis of the SAG, SAGA, and IAG Algorithms](https://mlsanity.com/paper/2602.05304/) (2026)
- [Model-free LQG Control with Chance Constraints](https://mlsanity.com/paper/2605.31310/) (2026)
- [Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples](https://mlsanity.com/paper/2606.05967/) (2026)
- [A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noise](https://mlsanity.com/paper/2606.18183/) (2026)
- [Robust Asynchronous Q-Learning under Reward and State Corruption via Batching](https://mlsanity.com/paper/2607.20822/) (2026)

## Abstract (arXiv)

We study the finite-time convergence of TD learning with linear function approximation under Markovian sampling. Existing proofs for this setting either assume a projection step in the algorithm to simplify the analysis, or require a fairly intricate argument to ensure stability of the iterates. We ask: textitIs it possible to retain the simplicity of a projection-based analysis without actually performing a projection step in the algorithm? Our main contribution is to show this is possible via a novel two-step argument. In the first step, we use induction to prove that under a standard choice of a constant step-size α, the iterates generated by TD learning remain uniformly bounded in expectation. In the second step, we establish a recursion that mimics the steady-state dynamics of TD learning up to a bounded perturbation on the order of O(α2) that captures the effect of Markovian sampling. Combining these pieces leads to an overall approach that considerably simplifies existing proofs. We conjecture that our inductive proof technique will find applications in the analyses of more complex stochastic approximation algorithms, and conclude by providing some examples of such applications.