mlsanityData to 14 Oct 2026

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

arXiv 2502.14172 ↗First posted 20 Feb 2025stat.ML cs.LGcited by 6

Not on the map. Why?

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.

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

45 of 74 references.

References · 45

  1. 2017A Distributional Perspective on Reinforcement Learningcited by 765
  2. 2017Distributional Reinforcement Learning with Quantile Regressioncited by 474
  3. 2018Implicit Quantile Networks for Distributional Reinforcement Learningcited by 369
  4. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  5. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
  6. 2014Algorithms for CVaR Optimization in MDPscited by 99
  7. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  8. 2019Fully Parameterized Quantile Function for Distributional Reinforcement Learningcited by 88
  9. 2018An Analysis of Categorical Distributional Reinforcement Learningcited by 68
  10. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
  11. 2019Statistics and Samples in Distributional Reinforcement Learningcited by 63
  12. 2015Preconditioned Stochastic Gradient Descentcited by 50
33 more
  1. 2019A Comparative Analysis of Expected and Distributional Reinforcement Learningcited by 47
  2. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  3. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  4. 2023An Analysis of Quantile Temporal-Difference Learningcited by 31
  5. 2022Bias and Extrapolation in Markovian Linear Stochastic Approximation with Constant Stepsizescited by 30
  6. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  7. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  8. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  9. 2023Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Datacited by 20
  10. 2023Distributional Offline Policy Evaluation with Predictive Error Guaranteescited by 20
  11. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  12. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  13. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  14. 2024A Distributional Analogue to the Successor Representationcited by 17
  15. 2024Foundations of Multivariate Distributional Reinforcement Learningcited by 17
  16. 2018Distributional Multivariate Policy Evaluation and Exploration with the Bellman GANcited by 16
  17. 2019Distributional reinforcement learning with linear function approximationcited by 16
  18. 2020Implicit Distributional Reinforcement Learningcited by 16
  19. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  20. 2021Non-decreasing Quantile Function Network with Efficient Exploration for Distributional Reinforcement Learningcited by 15
  21. 2024Statistical Inference for Policy Evaluation with Temporal Difference Learningcited by 15
  22. 2023The Statistical Benefits of Quantile Temporal-Difference Learning for Value Estimationcited by 14
  23. 2023Beyond Average Return in Markov Decision Processescited by 11
  24. 2022The Nature of Temporal Difference Errors in Multi-step Distributional Reinforcement Learningcited by 10
  25. 2025Optimizing Return Distributions with Distributional Dynamic Programmingcited by 10
  26. 2023Distributional Model Equivalence for Risk-Sensitive Reinforcement Learningcited by 9
  27. 2022Distributional Reinforcement Learning with Regularized Wasserstein Losscited by 8
  28. 2023Estimation and Inference in Distributional Reinforcement Learningcited by 8
  29. 2024Statistical Efficiency of Distributional Temporal Difference Learning and Freedman's Inequality in Hilbert Spacescited by 8
  30. 2024Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Modelcited by 7
  31. 2018Nonlinear Distributional Gradient Temporal-Difference Learningcited by 6
  32. 2025Beyond CVaR: Leveraging Static Spectral Risk Measures for Enhanced Decision-Making in Distributional Reinforcement Learningcited by 6
  33. 2023Distributional Bellman Operators over Mean Embeddingscited by 4

Built on by

Cited by year (2026 to 14 Oct)

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

6 papers.

  1. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Featurescited by 5
  2. 2026Statistical Efficiency and Inference of Quantile Distributional Reinforcement Learningcited by 3
  3. 2025Accelerated Distributional Temporal Difference Learning with Linear Function Approximationcited by 1
  4. 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learningcited by 1
  5. 2026Online Inference for Quantile Temporal Difference Learning in Distributional Reinforcement Learningcited by 1
  6. 2026A Finite-Sample Analysis of Quantile Temporal-Difference Learningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Towards Parameter-Free Temporal Difference Learning
  2. 2025A Differential Perspective on Distributional Reinforcement Learning
  3. 2024On Policy Evaluation Algorithms in Distributional Reinforcement Learning
  4. 2024Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
  5. 2025Convergence of TD(0) under Polynomial Mixing with Nonlinear Function Approximation
  6. 2025Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning
  7. 2024A Finite-Sample Analysis of an Actor-Critic Algorithm for Mean-Variance Optimization in a Discounted MDP
  8. 2024Asymptotic and Finite Sample Analysis of Nonexpansive Stochastic Approximations with Markovian Noise