Statistical Efficiency of Distributional Temporal Difference Learning and Freedman’s Inequality in Hilbert Spaces
Abstract
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.

