mlsanityData to 14 Oct 2026

Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features

arXiv 2409.12135 ↗First posted 18 Sep 2024cs.LG cs.AIcited by 5

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

Abstract (arXiv)

Temporal difference (TD) learning with linear function approximation (linear TD) is a classic and powerful prediction algorithm in reinforcement learning. While it is well-understood that linear TD converges almost surely to a unique point, this convergence traditionally requires the assumption that the features used by the approximator are linearly independent. However, this linear independence assumption does not hold in many practical scenarios. This work is the first to establish the almost sure convergence of linear TD without requiring linearly independent features. We prove that the weight iterates of linear TD converge to a bounded set, and that the value estimates derived from the weights in that set are the same almost everywhere. We also establish a notion of local stability of the weight iterates. Importantly, we do not impose assumptions tailored to feature dependence and do not modify the linear TD algorithm. Key to our analysis is a novel characterization of bounded invariant sets of the mean ODE of linear TD.

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 87 references that are in the map. First posted on arXiv 18 Sep 2024.

Builds on

38 of 87 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise15 Jan

Other references · 37

  1. 2020Towards Continual Reinforcement Learning: A Review and Perspectivescited by 274
  2. 2019DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Correctionscited by 254
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  4. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  5. 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 122
  6. 2015An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learningcited by 103
  7. 2023A Definition of Continual Reinforcement Learningcited by 101
  8. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  9. 2020GradientDICE: Rethinking Generalized Offline Estimation of Stationary Valuescited by 70
  10. 2021Breaking the Deadly Triad with a Target Networkcited by 47
  11. 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
  12. 2020Finite-Sample Analysis of Proximal Gradient TD Algorithmscited by 32
25 more
  1. 2021The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learningcited by 32
  2. 2021Average-Reward Off-Policy Policy Evaluation with Function Approximationcited by 31
  3. 2023Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noisecited by 26
  4. 2022Stochastic fixed-point iterations for nonexpansive maps: Convergence and error boundscited by 24
  5. 2015State of the Art Control of Atari Games Using Shallow Reinforcement Learningcited by 23
  6. 2024Transformers Can Learn Temporal Difference Methods for In-Context Reinforcement Learningcited by 23
  7. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  8. 2015On Convergence of Emphatic Temporal-Difference Learningcited by 21
  9. 2021Doubly Robust Off-Policy Actor-Critic: Convergence and Optimalitycited by 21
  10. 2019Target-Based Temporal Difference Learningcited by 20
  11. 2019Neural Temporal-Difference and Q-Learning Provably Converge to Global Optimacited by 20
  12. 2021Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatchcited by 17
  13. 2024A Simple Finite-Time Analysis of TD Learning with Linear Function Approximationcited by 16
  14. 2022On the Convergence of SARSA with Linear Function Approximationcited by 15
  15. 2019Geometric Insights into the Convergence of Nonlinear TD Learningcited by 13
  16. 2021Truncated Emphatic Temporal Difference Methods for Prediction and Controlcited by 10
  17. 2024Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximationcited by 10
  18. 2023A Better Match for Drivers and Riders: Reinforcement Learning at Lyftcited by 9
  19. 2022Global Convergence of Two-timescale Actor-Critic for Solving Linear Quadratic Regulatorcited by 8
  20. 2023Revisiting a Design Choice in Gradient Temporal Difference Learningcited by 7
  21. 2017Rates of convergence for inexact Krasnosel'skii-Mann iterations in Banach spacescited by 5
  22. 2015Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsizecited by 4
  23. 2020On Convergence of Gradient Expected Sarsa(λ)cited by 4
  24. 2022Finite-Time Error Bounds for Greedy-GQcited by 3
  25. 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. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  3. 2026Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processescited by 2
  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. 2025Stabilizing Temporal Difference Learning via Implicit Stochastic Recursion
  4. 2024Statistical Inference for Policy Evaluation with Temporal Difference Learning
  5. 2025Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation
  6. 2025Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits
  7. 2025Reinforcement Learning From State and Temporal Differences
  8. 2024An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks