Abstract
In this paper, we investigate 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 $\pi$. Prior 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 the classic linear TD learning. This implies that, with linear function approximation, learning the full distribution of the return using streaming data is no more difficult than learning its expectation (i.e., the value function). To derive tight sample complexity bounds, we conduct a fine-grained analysis of the linear-categorical Bellman equation and employ exponential stability arguments for products of random matrices. Our findings provide new insights into the statistical efficiency of distributional reinforcement learning algorithms.
Introduction
In Reinforcement Learning (RL), the standard objective is to estimate the value function—the expected sum of discounted future rewards. However, the expectation alone often fails to capture the full picture of an agent's potential outcomes. In safety-critical domains such as robotics or autonomous driving, understanding the variance and tail risks of the return distribution is essential for robust decision-making. This necessity has driven the rise of Distributional RL.
While the theoretical foundations of distributional RL are well-established for tabular settings, most real-world applications require function approximation to handle high-dimensional state spaces. Until now, a significant theoretical gap remained: the sample complexity of these algorithms under function approximation was unknown. A central question persisted: Does learning an entire distribution require significantly more data than learning a single scalar mean? This paper addresses this gap by providing the first finite-sample analysis of distributional TD learning with linear function approximation.
The Linear-CTD Algorithm
The authors introduce Linear-CTD (Linear Categorical TD), an algorithm designed to perform distributional policy evaluation efficiently. The method relies on several key technical components:
- Categorical Parametrization: The return distribution is represented using a set of $K$ fixed "bins" or categories (supports).
- Linear Projection: High-dimensional states are mapped to these distribution parameters using linear function approximation.
- Preconditioning: Standard stochastic gradient descent (SSGD) for this problem typically suffers from a convergence rate that degrades as the number of bins ($K$) increases. Linear-CTD introduces a preconditioning step—specifically $(C^\top C)^{-1}$—which reformulates the Bellman equation into a linear system. This effectively "normalizes" the geometry of the bins, decoupling the learning speed from the resolution of the distribution.
- Polyak-Ruppert Averaging: To achieve optimal statistical rates using a constant step size, the algorithm employs tail averaging of the iterates.
Theoretical Insights: Statistical Parity
The most significant finding of this research is the concept of statistical parity. The authors prove that the sample complexity of Linear-CTD matches that of classic Linear-TD. This suggests that learning the full distribution of the return is statistically "free"—it requires no more data than learning just the expected value.
Furthermore, the algorithm's convergence rate is independent of the resolution $K$. In vanilla distributional algorithms, increasing the number of supports to achieve a higher-resolution distribution requires a progressively smaller step size, leading to slower convergence. Linear-CTD bypasses this limitation, maintaining stability and speed regardless of how finely the distribution is discretized.
Key Results and Empirical Validation
The paper derives a sharp finite-sample rate of $\tilde{O}(1/T)$ for the mean squared error, which is the optimal rate for stochastic approximation problems of this nature. The analysis also demonstrates that Linear-CTD is exponentially stable, a property derived through the study of products of random matrices.
To validate these theoretical claims, the authors conducted experiments using a synthetic 3-state Markov Decision Process (MDP). The results confirmed that:
- Consistency: Linear-CTD is a true generalization of classic TD. When initialized identically, the mean of the distribution learned by Linear-CTD tracks the value learned by standard TD exactly.
- Robustness to Resolution: In tests where $K$ ranged from 1 to 500, Linear-CTD converged consistently with a fixed step size. Conversely, the baseline SSGD algorithm failed to converge once $K$ exceeded 44, highlighting the necessity of the preconditioning approach for high-resolution distributional learning.
Limitations and Future Directions
While this work provides a rigorous foundation for linear distributional RL, several avenues for future research remain:
- Non-linear Approximation: The current analysis is restricted to linear function approximation. Extending these guarantees to non-linear neural networks remains a challenge due to the complex optimization landscapes involved.
- Signed Measures: To maintain linearity in the math, the authors utilize "signed measures," which allow for negative probability values during intermediate computation steps. Practical implementations like C51 use softmax functions to ensure valid probability distributions, introducing non-linearities not covered here.
- Variance Reduction: Future work could incorporate techniques like SVRG (Stochastic Variance Reduced Gradient) to further improve the constants within the sample complexity bounds.
Conclusion
This paper establishes that learning the full return distribution is no more difficult than learning the mean in the context of linear function approximation. By introducing Linear-CTD and its associated preconditioning framework, the authors provide a statistically efficient path forward for risk-aware reinforcement learning, ensuring that high-resolution distribution estimation remains computationally and statistically tractable.
Summary updated