# A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 74 references that are in the map.
- First posted on arXiv 20 Feb 2025.

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

- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Distributional Reinforcement Learning with Quantile Regression](https://mlsanity.com/paper/1710.10044/) (2017)
- [Implicit Quantile Networks for Distributional Reinforcement Learning](https://mlsanity.com/paper/1806.06923/) (2018)
- [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)
- [Algorithms for CVaR Optimization in MDPs](https://mlsanity.com/paper/1406.3339/) (2014)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Fully Parameterized Quantile Function for Distributional Reinforcement Learning](https://mlsanity.com/paper/1911.02140/) (2019)
- [An Analysis of Categorical Distributional Reinforcement Learning](https://mlsanity.com/paper/1802.08163/) (2018)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [Statistics and Samples in Distributional Reinforcement Learning](https://mlsanity.com/paper/1902.08102/) (2019)
- [Preconditioned Stochastic Gradient Descent](https://mlsanity.com/paper/1512.04202/) (2015)
- [A Comparative Analysis of Expected and Distributional Reinforcement Learning](https://mlsanity.com/paper/1901.11084/) (2019)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [Optimal and instance-dependent guarantees for Markovian linear stochastic approximation](https://mlsanity.com/paper/2112.12770/) (2021)
- [An Analysis of Quantile Temporal-Difference Learning](https://mlsanity.com/paper/2301.04462/) (2023)
- [Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizes](https://mlsanity.com/paper/2210.00953/) (2022)
- [The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning](https://mlsanity.com/paper/2305.15703/) (2023)
- [Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation](https://mlsanity.com/paper/2210.05918/) (2022)
- [More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning](https://mlsanity.com/paper/2402.07198/) (2024)
- [Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data](https://mlsanity.com/paper/2302.07690/) (2023)
- [Distributional Offline Policy Evaluation with Predictive Error Guarantees](https://mlsanity.com/paper/2302.09456/) (2023)
- [Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability](https://mlsanity.com/paper/2310.14286/) (2023)
- [Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learning](https://mlsanity.com/paper/2405.16644/) (2024)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [A Distributional Analogue to the Successor Representation](https://mlsanity.com/paper/2402.08530/) (2024)
- [Foundations of Multivariate Distributional Reinforcement Learning](https://mlsanity.com/paper/2409.00328/) (2024)
- [Distributional Multivariate Policy Evaluation and Exploration with the Bellman GAN](https://mlsanity.com/paper/1808.01960/) (2018)
- [Distributional reinforcement learning with linear function approximation](https://mlsanity.com/paper/1902.03149/) (2019)
- [Implicit Distributional Reinforcement Learning](https://mlsanity.com/paper/2007.06159/) (2020)

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

- [Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features](https://mlsanity.com/paper/2505.21391/) (2025)
- [Statistical Efficiency and Inference of Quantile Distributional Reinforcement Learning](https://mlsanity.com/paper/2607.08444/) (2026)
- [Accelerated Distributional Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2511.12688/) (2025)
- [Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learning](https://mlsanity.com/paper/2605.11289/) (2026)
- [Online Inference for Quantile Temporal Difference Learning in Distributional Reinforcement Learning](https://mlsanity.com/paper/2608.12973/) (2026)
- [A Finite-Sample Analysis of Quantile Temporal-Difference Learning](https://mlsanity.com/paper/2608.27313/) (2026)

## Abstract (arXiv)

In this paper, we study the finite-sample statistical rates of distributional temporal difference (TD) learning with linear function approximation. The aim of distributional TD learning is to estimate the return distribution of a discounted Markov decision process for a given policy π. Previous works on statistical analysis of distributional TD learning mainly focus on the tabular case. In contrast, we first consider the linear function approximation setting and derive sharp finite-sample rates. Our theoretical results demonstrate that the sample complexity of linear distributional TD learning matches that of classic linear TD learning. This implies that, with linear function approximation, learning the full distribution of the return from streaming data is no more difficult than learning its expectation (value function). To derive tight sample complexity bounds, we conduct a fine-grained analysis of the linear-categorical Bellman equation and employ the exponential stability arguments for products of random matrices. Our results provide new insights into the statistical efficiency of distributional reinforcement learning algorithms.