mlsanityData to 14 Oct 2026

Accelerated Distributional Temporal Difference Learning with Linear Function Approximation

arXiv 2511.12688 ↗First posted 16 Nov 2025stat.ML cs.LGcited by 1

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 purpose 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 focus mainly on the tabular case. We first consider the linear function approximation setting and conduct a fine-grained analysis of the linear-categorical Bellman equation. Building on this analysis, we further incorporate variance reduction techniques in our new algorithms to establish tight sample complexity bounds independent of the support size K when K is large. Our theoretical results imply that, when employing distributional TD learning with linear function approximation, learning the full distribution of the return function from streaming data is no more difficult than learning its expectation. This work provide new insights into the statistical efficiency of distributional reinforcement learning algorithms.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 28 of its 43 references that are in the map. First posted on arXiv 16 Nov 2025.

Builds on

28 of 43 references.

References · 28

  1. 2017A Distributional Perspective on Reinforcement Learningcited by 765
  2. 2014SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectivescited by 402
  3. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  4. 2013Minimizing Finite Sums with the Stochastic Average Gradientcited by 164
  5. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  6. 2018An Analysis of Categorical Distributional Reinforcement Learningcited by 68
  7. 2019A Comparative Analysis of Expected and Distributional Reinforcement Learningcited by 47
  8. 2020Is Temporal Difference Learning Optimal? An Instance-Dependent Analysiscited by 41
  9. 2020Simple and optimal methods for stochastic variational inequalities, I: operator extrapolationcited by 35
  10. 2021Optimal and instance-dependent guarantees for Markovian linear stochastic approximationcited by 33
  11. 2023An Analysis of Quantile Temporal-Difference Learningcited by 31
  12. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
16 more
  1. 2023Distributional Offline Policy Evaluation with Predictive Error Guaranteescited by 20
  2. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  3. 2024Gaussian Approximation and Multiplier Bootstrap for Polyak-Ruppert Averaged Linear Stochastic Approximation with Applications to TD Learningcited by 19
  4. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  5. 2024Foundations of Multivariate Distributional Reinforcement Learningcited by 17
  6. 2019Distributional reinforcement learning with linear function approximationcited by 16
  7. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  8. 2024Statistical Inference for Policy Evaluation with Temporal Difference Learningcited by 15
  9. 2025Optimizing Return Distributions with Distributional Dynamic Programmingcited by 10
  10. 2023Distributional Model Equivalence for Risk-Sensitive Reinforcement Learningcited by 9
  11. 2023Estimation and Inference in Distributional Reinforcement Learningcited by 8
  12. 2024Statistical Efficiency of Distributional Temporal Difference Learning and Freedman's Inequality in Hilbert Spacescited by 8
  13. 2024Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Modelcited by 7
  14. 2018Nonlinear Distributional Gradient Temporal-Difference Learningcited by 6
  15. 2025Beyond CVaR: Leveraging Static Spectral Risk Measures for Enhanced Decision-Making in Distributional Reinforcement Learningcited by 6
  16. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Online Inference in Distributional Temporal-Difference Learningcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2026Towards Parameter-Free Temporal Difference Learning
  2. 2024Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
  3. 2025A Differential Perspective on Distributional Reinforcement Learning
  4. 2025Uncertainty quantification for Markov chain induced martingales with application to temporal difference learning
  5. 2025Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features
  6. 2024The surprising efficiency of temporal difference learning for rare event prediction
  7. 2026Online Inference for Quantile Temporal Difference Learning in Distributional Reinforcement Learning
  8. 2024On Policy Evaluation Algorithms in Distributional Reinforcement Learning