# Statistical Efficiency of Distributional Temporal Difference Learning and Freedman's Inequality in Hilbert Spaces

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

## Key facts

- Cited by 8 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.
- First posted on arXiv 9 Mar 2024.

## Placed in

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

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

- [A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.14172/) (2025)
- [A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning](https://mlsanity.com/paper/2605.06866/) (2026)
- [Accelerated Distributional Temporal Difference Learning with Linear Function Approximation](https://mlsanity.com/paper/2511.12688/) (2025)
- [Adapt or Forget: Provable Tradeoffs Between Adam and SGD in Nonstationary Optimization](https://mlsanity.com/paper/2605.04269/) (2026)
- [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)
- [Tail-Influence Sampling for CVaR Policy Evaluation](https://mlsanity.com/paper/2609.38096/) (2026)

## Abstract (arXiv)

Distributional reinforcement learning (DRL) has achieved empirical success in various domains. One core task in DRL is distributional policy evaluation, which involves estimating the return distribution ηπ for a given policy π. Distributional temporal difference learning has been accordingly proposed, which extends the classic temporal difference learning (TD) in RL. In this paper, we focus on the non-asymptotic statistical rates of distributional TD. To facilitate theoretical analysis, we propose non-parametric distributional TD (NTD). For a γ-discounted infinite-horizon tabular Markov decision process, we show that for NTD with a generative model, we need tildeO(varepsilon-2μmin-1(1-γ)-3) interactions with the environment to achieve an varepsilon-optimal estimator with high probability, when the estimation error is measured by the 1-Wasserstein. This sample complexity bound is minimax optimal up to logarithmic factors. In addition, we revisit categorical distributional TD (CTD), showing that the same non-asymptotic convergence bounds hold for CTD in the case of the 1-Wasserstein distance. We also extend our analysis to the more general setting where the data generating process is Markovian. In the Markovian setting, we propose variance-reduced variants of NTD and CTD, and show that both can achieve a tildeO(varepsilon-2 μπ,min-1(1-γ)-3+tmixμπ,min-1(1-γ)-1) sample complexity bounds in the case of the 1-Wasserstein distance, which matches the state-of-the-art statistical results for classic policy evaluation. To achieve the sharp statistical rates, we establish a novel Freedman's inequality in Hilbert spaces. This new Freedman's inequality would be of independent interest for statistical analysis of various infinite-dimensional online learning problems.