# Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features

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

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 38)

- [Towards Continual Reinforcement Learning: A Review and Perspectives](https://mlsanity.com/paper/2012.13490/) (2020)
- [DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections](https://mlsanity.com/paper/1906.04733/) (2019)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning](https://mlsanity.com/paper/1503.04269/) (2015)
- [A Definition of Continual Reinforcement Learning](https://mlsanity.com/paper/2307.11046/) (2023)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [GradientDICE: Rethinking Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2001.11113/) (2020)
- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms](https://mlsanity.com/paper/2005.03557/) (2020)
- [Finite-Sample Analysis of Proximal Gradient TD Algorithms](https://mlsanity.com/paper/2006.14364/) (2020)
- [The ODE Method for Asymptotic Statistics in Stochastic Approximation and Reinforcement Learning](https://mlsanity.com/paper/2110.14427/) (2021)
- [Average-Reward Off-Policy Policy Evaluation with Function Approximation](https://mlsanity.com/paper/2101.02808/) (2021)
- [Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise](https://mlsanity.com/paper/2303.15740/) (2023)
- [Stochastic fixed-point iterations for nonexpansive maps: Convergence and error bounds](https://mlsanity.com/paper/2208.04193/) (2022)
- [The ODE Method for Stochastic Approximation and Reinforcement Learning with Markovian Noise](https://mlsanity.com/paper/2401.07844/) (2024)
- [State of the Art Control of Atari Games Using Shallow Reinforcement Learning](https://mlsanity.com/paper/1512.01563/) (2015)
- [Transformers Can Learn Temporal Difference Methods for In-Context Reinforcement Learning](https://mlsanity.com/paper/2405.13861/) (2024)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation](https://mlsanity.com/paper/2105.12540/) (2021)
- [On Convergence of Emphatic Temporal-Difference Learning](https://mlsanity.com/paper/1506.02582/) (2015)
- [Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality](https://mlsanity.com/paper/2102.11866/) (2021)
- [Target-Based Temporal Difference Learning](https://mlsanity.com/paper/1904.10945/) (2019)
- [Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima](https://mlsanity.com/paper/1905.10027/) (2019)
- [Global Optimality and Finite Sample Analysis of Softmax Off-Policy Actor Critic under State Distribution Mismatch](https://mlsanity.com/paper/2111.02997/) (2021)
- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [On the Convergence of SARSA with Linear Function Approximation](https://mlsanity.com/paper/2202.06828/) (2022)
- [Geometric Insights into the Convergence of Nonlinear TD Learning](https://mlsanity.com/paper/1905.12185/) (2019)
- [Truncated Emphatic Temporal Difference Methods for Prediction and Control](https://mlsanity.com/paper/2108.05338/) (2021)
- [Target Networks and Over-parameterization Stabilize Off-policy Bootstrapping with Function Approximation](https://mlsanity.com/paper/2405.21043/) (2024)

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

- [Towards Formalizing Reinforcement Learning Theory: A Robbins-Siegmund Approach](https://mlsanity.com/paper/2511.03618/) (2025)
- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2602.16629/) (2026)
- [Almost Sure Convergence Rates of Stochastic Approximation and Reinforcement Learning via a Poisson-Moreau Drift](https://mlsanity.com/paper/2605.07104/) (2026)
- [On the Divergence of Differential Temporal Difference Learning without Local Clocks](https://mlsanity.com/paper/2605.06874/) (2026)

## 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.