Research map / Learning theory and algorithms / Sample complexity
Statistical Efficiency of Distributional Temporal Difference Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives finite-sample analysis of model-free distributional TD (non-parametric NTD and categorical CTD) for policy evaluation, showing near-minimax sample complexity in p-Wasserstein distance, via a new Freedman's inequality in Hilbert spaces.
Problem
Finite-sample (non-asymptotic) statistical efficiency of distributional policy evaluation with model-free distributional temporal difference learning, which previously had only asymptotic guarantees in the tabular case.
Approach
Analyze distributional TD as a stochastic approximation in the zero-mass signed measure space with Cramér norm, and prove a Freedman's inequality in Hilbert spaces with high-probability bounded quadratic variation; this yields sample complexity Õ(1/(ε²(1-γ)³)) in W1 that matches the minimax lower bound up to logs, and the same bound for CTD.
Key results
- NTD needs Õ(1/(ε²(1-γ)^(2p+1))) iterations for ε-accurate p-Wasserstein estimate with high probability; for p=1 this is Õ(1/(ε²(1-γ)³)), minimax optimal up to logs (Theorem B.1).
- CTD attains the same non-asymptotic W1 bound Õ(1/(ε²(1-γ)³)) as NTD, improving on SCPE's Õ(1/(ε²(1-γ)⁴)).
- Under Cramér (ℓ2) metric, both NTD and CTD need Õ(1/(ε²(1-γ)^(5/2))) iterations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use NTD for distributional policy evaluation | Distributional policy evaluation · 1-Wasserstein | sample complexity: eO(1/(ε²(1−γ)³)) | Helped |
| Use CTD without an acceleration term, rather than SCPE | Distributional policy evaluation · 1-Wasserstein | sample complexity: eO(1/(ε²(1−γ)⁴)) -> eO(1/(ε²(1−γ)³)) | Helped |
| Use CTD instead of NTD | Distributional policy evaluation · p-Wasserstein | sample complexity: eO(1/(ε²(1−γ)^(2p+1))) | No clear effect |
Limitations
- NTD is non-parametric and not practical; analysis is for the synchronous generative-model setting
- Bounds for p>1 incur slow rate in ε inevitable without extra regularity conditions
- Results for CTD require K large enough (K > 4/(1-γ) and K scaling with 1/ε)
Experimental setup
Metrics: sample complexity p-Wasserstein distance Cramér distance
Baselines: CTD (Rowland et al. 2018) QTD (Rowland et al. 2024a) DCFP (Rowland et al. 2024b) SCPE (Böck and Heitzinger 2022) model-based distributional policy evaluation (Zhang et al. 2023)
Builds on: Freedman's inequality categorical distributional RL (C51 / CTD) Li et al. 2024 TD finite-sample analysis Rowland et al. 2018 CTD asymptotic analysis
Closest papers by meaning
- A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation (NeurIPS 2025 · similarity 0.91)
- Nonlinear Distributional Gradient Temporal-Difference Learning (ICML 2019 · similarity 0.91)
- Towards Parameter-Free Temporal Difference Learning (ICML 2026 · similarity 0.90)
- Discerning Temporal Difference Learning (AAAI 2024 · similarity 0.87)
- The surprising efficiency of temporal difference learning for rare event prediction (NeurIPS 2024 · similarity 0.87)
- Foundations of Multivariate Distributional Reinforcement Learning (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.