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

Yang Peng, Kaicheng Jin, Liangyu Zhang, Zhihua Zhang

TL;DR

Does learning the full probability distribution of future rewards require more data than just learning their average? This paper provides the first finite-sample analysis of distributional temporal difference (TD) learning with linear function approximation, proving that tracking the entire distribution is statistically no harder than tracking the expected value. By introducing a preconditioned algorithm called Linear-CTD, the authors achieve a sample complexity that completely matches classic linear TD learning.

What Problem Does This Paper Address?

In reinforcement learning (RL), traditional policy evaluation focuses on estimating the value function—the expected (average) cumulative future return. However, average returns don't capture risk or uncertainty. Distributional RL solves this by estimating the full probability distribution of returns, which is vital for risk-sensitive applications like autonomous driving or financial trading.

While distributional RL performs exceptionally well in practice, its theoretical foundations are mostly limited to the "tabular" setting (where the state space is small enough to be represented as a simple table). In real-world scenarios with massive or continuous state spaces, researchers must use function approximation (like linear models or neural networks).

This paper tackles a fundamental open question: When function approximation is employed, does learning the full return distribution remain as statistically efficient as learning just its expectation?

Methods

The authors focus on the categorical parametrization approach, where a continuous probability distribution is approximated using a discrete set of $K$ fixed points (supports).

Their core contributions are algorithmic and theoretical:

  1. Linear-CTD (Linear Categorical TD): Instead of using standard stochastic semi-gradient descent (SSGD) to update parameters, the authors directly formulate the linear-categorical projected Bellman equation into a linear system and apply linear stochastic approximation to solve it.
  2. Preconditioning: A major issue with vanilla categorical algorithms is that their performance degrades as the number of distribution supports ($K$) increases, requiring the learning rate (step size) to shrink at a rate of $O(K^{-2})$. The authors introduce a mathematical preconditioner—effectively removing a troublesome matrix product ($C^\top C$)—which makes the algorithm's convergence rate and step size completely independent of $K$.
  3. Polyak-Ruppert Tail Averaging: The algorithm uses a constant step size and averages the parameter iterates over the second half of the training run to ensure tight convergence bounds.

Datasets

As a primarily theoretical paper, no large-scale real-world datasets were used. The authors validated their mathematical findings using a synthetic 3-state Markov Decision Process (MDP) with a discount factor of $\gamma = 0.75$ and a full-rank feature matrix.

Key Insights and Ideas

  • The "No Harder Than Average" Result: The most significant insight is that the sample complexity of learning a full distribution matches that of classic linear TD. Mathematically, streaming data yields enough information to map the entire distribution shape just as fast as mapping its mean.
  • Escaping the Support Curse: In vanilla categorical distributional RL, choosing a finer grain for your distribution (larger $K$) forces you to take drastically smaller steps during optimization. The preconditioning technique in Linear-CTD completely decouples the step size from $K$, allowing robust, fast convergence regardless of distribution resolution.
  • Mean Preservation: Linear-CTD is "mean-preserving." If you initialize it identically to a classic Linear-TD algorithm and feed them the same data stream, the expected value of Linear-CTD’s distribution tracks the classic TD value function exactly at every single step.

Key Results

  • Sample Complexity Bound: The authors prove that to achieve an $\varepsilon$-accurate estimate of the return distribution under a generative model, the required number of online interactions $T$ scales as: $$T = \tilde{O}\left( \frac{\varepsilon^{-2} + \lambda_{\min}^{-1}}{(1 - \gamma)^2 \lambda_{\min}} \right)$$ where $\gamma$ is the discount factor and $\lambda_{\min}$ is the minimum eigenvalue of the feature covariance matrix. This bound perfectly mirrors the state-of-the-art bounds for classic Linear-TD.

  • Empirical Validation: In numerical simulations, when given a fixed step size ($\alpha = 0.01$), Linear-CTD successfully converged across all tested support sizes ($K = 1$ to $K = 500$). Meanwhile, the baseline SSGD algorithm completely failed to converge (diverging to infinity/NaN) as soon as $K \ge 44$, validating the necessity of the preconditioner.

Limitations and Future Work

  • Sample Size Barrier: The derived bound contains a "sample size barrier" regarding its dependence on $\lambda_{\min}$. The authors note that incorporating variance-reduction techniques might be necessary to break this barrier.
  • Step Size Restrictions: The current analysis is restricted to constant step sizes; exploring polynomial-decaying step sizes remains open.
  • Linear Limitation: This work is strictly bounded to linear function approximation. Extending these sharp, non-asymptotic guarantees to non-linear architectures, such as neural networks or softmax-based categorical algorithms, is left for future research.

Summary updated

Abstract

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.
BibTeX
@inproceedings{peng2025finite,
  author = {Yang Peng and Kaicheng Jin and Liangyu Zhang and Zhihua Zhang},
  title = {{A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=2lNCktd2c3},
}
Figure