# A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation

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

## Key facts

- Cited by 229 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2018.

## Built on by (most cited first, 30 of 229)

- [Recent Advances in Reinforcement Learning in Finance](https://mlsanity.com/paper/2112.04553/) (2021)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Simplifying Deep Temporal Difference Learning](https://mlsanity.com/paper/2407.04811/) (2024)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [On the Linear convergence of Natural Policy Gradient Algorithm](https://mlsanity.com/paper/2105.01424/) (2021)
- [Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2210.01808/) (2022)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2101.10506/) (2021)
- [Deeply-Debiased Off-Policy Interval Estimation](https://mlsanity.com/paper/2105.04646/) (2021)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Stochastic first-order methods for average-reward Markov decision processes](https://mlsanity.com/paper/2205.05800/) (2022)
- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning](https://mlsanity.com/paper/2401.15273/) (2024)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [A Statistical Analysis of Polyak-Ruppert Averaged Q-learning](https://mlsanity.com/paper/2112.14582/) (2021)
- [Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approach](https://mlsanity.com/paper/2108.02731/) (2021)
- [Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize](https://mlsanity.com/paper/2106.01257/) (2021)
- [Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneity](https://mlsanity.com/paper/2302.02212/) (2023)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm](https://mlsanity.com/paper/2102.09318/) (2021)
- [Online Bootstrap Inference For Policy Evaluation in Reinforcement Learning](https://mlsanity.com/paper/2108.03706/) (2021)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learning](https://mlsanity.com/paper/2302.07457/) (2023)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximation](https://mlsanity.com/paper/2402.15399/) (2024)
- [A Small Gain Analysis of Single Timescale Actor Critic](https://mlsanity.com/paper/2203.02591/) (2022)
- [On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/2102.00185/) (2021)
- [Concentration of Contractive Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2106.14308/) (2021)
- [Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation](https://mlsanity.com/paper/2210.05918/) (2022)

## Abstract (arXiv)

Temporal difference learning (TD) is a simple iterative algorithm used to estimate the value function corresponding to a given policy in a Markov decision process. Although TD is one of the most widely used algorithms in reinforcement learning, its theoretical analysis has proved challenging and few guarantees on its statistical efficiency are available. In this work, we provide a simple and explicit finite time analysis of temporal difference learning with linear function approximation. Except for a few key insights, our analysis mirrors standard techniques for analyzing stochastic gradient descent algorithms, and therefore inherits the simplicity and elegance of that literature. Final sections of the paper show how all of our main results extend to the study of TD learning with eligibility traces, known as TD(λ), and to Q-learning applied in high-dimensional optimal stopping problems.