mlsanityData to 14 Oct 2026

Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features

arXiv 2505.21391 ↗First posted 27 May 2025cs.LG cs.AI stat.MLcited by 5

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Linear TD(λ) is one of the most fundamental reinforcement learning algorithms for policy evaluation. Previously, convergence rates are typically established under the assumption of linearly independent features, which does not hold in many practical scenarios. This paper instead establishes the first L2 convergence rates for linear TD(λ) operating under arbitrary features, without making any algorithmic modification or additional assumptions. Our results apply to both the discounted and average-reward settings. To address the potential non-uniqueness of solutions resulting from arbitrary features, we develop a novel stochastic approximation result featuring convergence rates to the solution set instead of a single point.

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 38 of its 71 references that are in the map. First posted on arXiv 27 May 2025.

Builds on

38 of 71 references.

Closest ancestors · 6

Same direction, newest first

  1. 2025Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits7 Feb
  2. 2025Linear Q-Learning Does Not Diverge in L2: Convergence Rates to a Bounded Set31 Jan
  3. 2024Almost Sure Convergence Rates and Concentration of Stochastic Approximation and Reinforcement Learning with Markovian Noise20 Nov
  4. 2024Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem29 Oct
  5. 2024Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features18 Sep
  6. 2024The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise15 Jan

Other references · 32

  1. 2020Towards Continual Reinforcement Learning: A Review and Perspectivescited by 274
  2. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  3. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  4. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  5. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  6. 2020GradientDICE: Rethinking Generalized Offline Estimation of Stationary Valuescited by 70
  7. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
  8. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  9. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  10. 2020Finite-Sample Analysis of Proximal Gradient TD Algorithmscited by 32
  11. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 32
  12. 2021Average-Reward Off-Policy Policy Evaluation with Function Approximationcited by 31
20 more
  1. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  2. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 24
  3. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  4. 2015On Convergence of Emphatic Temporal-Difference Learningcited by 21
  5. 2021Doubly Robust Off-Policy Actor-Critic: Convergence and Optimalitycited by 21
  6. 2019Neural Temporal-Difference and Q-Learning Provably Converge to Global Optimacited by 20
  7. 2021Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operatorscited by 17
  8. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  9. 2024A Simple Finite-Time Analysis of TD Learning with Linear Function Approximationcited by 16
  10. 2022On the Convergence of SARSA with Linear Function Approximationcited by 15
  11. 2021Truncated Emphatic Temporal Difference Methods for Prediction and Controlcited by 10
  12. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noisecited by 10
  13. 2025A Non-Asymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithmscited by 10
  14. 2022Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulatorcited by 8
  15. 2023Revisiting a Design Choice in Gradient Temporal Difference Learningcited by 7
  16. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 6
  17. 2015Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsizecited by 4
  18. 2020On Convergence of Gradient Expected Sarsa(λ)cited by 4
  19. 2022Finite-Time Error Bounds for Greedy-GQcited by 3
  20. 2024Finite-Time Analysis of Asynchronous Multi-Agent TD Learningcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 3.

5 papers.

  1. 2025Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approachcited by 7
  2. 2026Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processescited by 2
  3. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  4. 2026Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Driftcited by 1
  5. 2026On the Divergence of Differential Temporal Difference Learning without Local Clockscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Towards Parameter-Free Temporal Difference Learning
  2. 2025A Robust widetildeO(1/√T) Rate for Unprojected TD Learning with Linear Function Approximation
  3. 2024Statistical Inference for Policy Evaluation with Temporal Difference Learning
  4. 2025Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation
  5. 2025Accelerated Distributional Temporal Difference Learning with Linear Function Approximation
  6. 2024An MRP Formulation for Supervised Learning: Generalized Temporal Difference Learning Models
  7. 2025Stabilizing Temporal Difference Learning via Implicit Stochastic Recursion
  8. 2025Implicit Updates for Average-Reward Temporal Difference Learning