Research map / Learning theory and algorithms / Sample complexity
A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation
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.
Proposes a preconditioned linear-categorical TD (LCTD) algorithm for distributional policy evaluation with linear function approximation and proves finite-sample rates matching classic linear TD learning.
Problem
Statistical efficiency of distributional TD learning with linear function approximation: whether learning the full return distribution (in 1-Wasserstein distance) is as sample-efficient as learning the expected value when function approximation is used.
Approach
Derive LCTD by solving the linear-categorical projected Bellman equation as a linear system with linear stochastic approximation, preconditioning away the C^T C matrix so the rate is independent of the number of categorical supports K; analyze via exponential stability of products of random matrices.
Key results
- Sample complexity of LCTD with constant step size and Polyak-Ruppert averaging is T = Õ((ε^-2 + λ_min^-1)(1-γ)^-2 λ_min^-1 (||θ*||²_{V1}+1)) for instance-dependent step size, matching classic LTD.
- Convergence rate of LCTD is independent of the number of supports K, whereas vanilla SSGD with PMF representation needs step size scaling as (1-√γ)/K² and sample complexity growing with K.
- Numerical experiments confirm LCTD converges and consistently outperforms vanilla SSGD across different K.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the preconditioner that removes the CᵀC factor | Linear-categorical TD (LCTD) · Linear-categorical TD with varying support count K | convergence rate dependence on K | Helped |
| use LCTD instead of vanilla SSGD with PMF representation | Linear-categorical TD · Numerical experiments with different K | convergence | Helped |
| use linear function approximation for distributional TD learning | LCTD · Distributional policy evaluation | sample complexity relative to classic linear TD | No clear effect |
Surprising findings
- Learning the full return distribution with linear categorical function approximation is statistically no harder than learning the value function, matching LTD rates.
Limitations
- Softmax-based linear-categorical algorithm (closer to C51) not analyzed due to nonlinearity
- Sample size barrier: optimal lambda_min^-1 dependence only when epsilon is small relative to sqrt(lambda_min)
- Results stated for generative model; Markovian setting only sketched in a remark
Experimental setup
Metrics: 1-Wasserstein distance (mu_pi-weighted) sample complexity
Baselines: LTD (linear TD learning) vanilla linear categorical TD (SSGD with PMF representation) linear-categorical TD with softmax
Builds on: linear TD learning categorical TD learning (C51-style projection) exponential stability analysis of LSA (Chen et al.) Polyak-Ruppert averaging
Closest papers by meaning
- Statistical Efficiency of Distributional Temporal Difference Learning (NeurIPS 2024 · similarity 0.91)
- Finite Sample Analysis of Linear Temporal Difference Learning with Arbitrary Features (NeurIPS 2025 · similarity 0.89)
- Foundations of Multivariate Distributional Reinforcement Learning (NeurIPS 2024 · similarity 0.89)
- Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Model (NeurIPS 2024 · similarity 0.88)
- Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation (ICML 2025 · similarity 0.88)
- Almost Sure Convergence of Linear Temporal Difference Learning with Arbitrary Features (NeurIPS 2026 · 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.