mlsanityData to 14 Oct 2026

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

arXiv 1806.02450 ↗First posted 6 Jun 2018cs.LG stat.MLcited by 229

Not on the map. Why?

Cited by 61 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 40; 2022: 36; 2023: 41; 2024: 45; 2025: 35; 2026: 32.

229 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 110
  2. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 96
  3. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  4. 2024Simplifying Deep Temporal Difference Learningcited by 78
  5. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
  6. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  7. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  8. 2022Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guaranteescited by 42
  9. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  10. 2021Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithmcited by 39
  11. 2021Deeply-Debiased Off-Policy Interval Estimationcited by 36
  12. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
38 more
  1. 2022Stochastic first-order methods for average-reward Markov decision processescited by 32
  2. 2022Finite-time analysis of single-timescale actor-criticcited by 32
  3. 2024Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learningcited by 31
  4. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 30
  5. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  6. 2021Mean-Field Multi-Agent Reinforcement Learning: A Decentralized Network Approachcited by 28
  7. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 27
  8. 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 27
  9. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  10. 2021Online Bootstrap Inference For Policy Evaluation in Reinforcement Learningcited by 26
  11. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 26
  12. 2023When Demonstrations Meet Generative World Models: A Maximum Likelihood Framework for Offline Inverse Reinforcement Learningcited by 26
  13. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  14. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
  15. 2022A Small Gain Analysis of Single Timescale Actor Criticcited by 24
  16. 2021On the Stability of Random Matrix Product with Markovian Noise: Application to Linear Stochastic Approximation and TD Learningcited by 23
  17. 2021Concentration of Contractive Stochastic Approximation and Reinforcement Learningcited by 23
  18. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  19. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  20. 2021Tighter Analysis of Alternating Stochastic Gradient Method for Stochastic Nested Problemscited by 22
  21. 2021Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learningcited by 22
  22. 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 20
  23. 2021Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPscited by 19
  24. 2023Prediction and Control in Continual Reinforcement Learningcited by 19
  25. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  26. 2024Reward-Directed Score-Based Diffusion Models via q-Learningcited by 19
  27. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  28. 2023Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Criticcited by 18
  29. 2024Deep Policy Gradient Methods Without Batch Updates, Target Networks, or Replay Bufferscited by 18
  30. 2021Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operatorscited by 17
  31. 2022Stochastic linear optimization never overfits with quadratically-bounded losses on general datacited by 17
  32. 2022A Single-Timescale Analysis For Stochastic Approximation With Multiple Coupled Sequencescited by 17
  33. 2022Linear Convergence for Natural Policy Gradient with Log-linear Policy Parametrizationcited by 17
  34. 2023On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Explorationcited by 17
  35. 2024Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolationcited by 17
  36. 2024Rates of Convergence in the Central Limit Theorem for Markov Chains, with an Application to TD Learningcited by 17
  37. 2021Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximationcited by 16
  38. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16

50 most cited of 229 All 229 (JSON)