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

Published Online:https://doi.org/10.1287/opre.2025.1639

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 (TD) learning has been accordingly proposed, which extends the classic TD learning in RL. In this paper, we focus on the non-asymptotic statistical rates of distributional TD learning. To facilitate theoretical analysis, we propose non-parametric distributional TD learning (NTD). For a γ-discounted tabular Markov decision process, we show that for NTD with a fixed-distribution generative model (at time t ∈ ℕ, sample one state st ~ μ with μmin := mins∈S μ(s) > 0 and observe a single transition from st), we need Õ(ε−2 μmin−1(1−γ)−3) interactions with the environment to achieve an ε-optimal estimator with high probability when the estimation error is measured by the supremum 1-Wasserstein distance. This sample complexity bound is minimax optimal up to logarithmic factors. In addition, we revisit categorical distributional TD learning (CTD), showing that the same non-asymptotic convergence bounds hold for CTD. 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 sample complexity bound matching the state-of-the-art statistical results for classic policy evaluation. We validate our theoretical results through numerical experiments on an inventory management problem, illustrating the practical utility of distributional policy evaluation in risk-sensitive decision-making. 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.

INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.