Research map / Reinforcement learning / Policy gradient and actor-critic
Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Model
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 direct categorical fixed-point (DCFP), a linear-system solver for categorical distributional RL with a generative model, and proves it attains the minimax sample complexity (up to logs) for return-distribution estimation in Wasserstein-1.
Problem
Sample complexity of estimating return distributions (in Wasserstein-1) from a generative model, and whether distributional RL is statistically harder than value estimation; prior analyses were loose by a (1-γ)^{-1} factor and prior algorithms were impractical.
Approach
Computes the categorical fixed point exactly by solving a linear system over CDF values (after fixing the final CDF entry to 1), rather than by iterating categorical projected Bellman updates; applied to the empirical transition matrix, and analysed via a new stochastic categorical CDF Bellman equation and local/global squared-Cramér variation.
Key results
- Theorem: model-based DCFP with N = Omega(eps^-2 (1-gamma)^-3 polylog) samples achieves max-state W1 error eps with probability 1-delta, matching the known lower bound up to logs and closing the gap left by prior analysis.
- Empirically, QDP achieves lower asymptotic error than DCFP at low discount and atom counts, while DCFP is generally faster and outperforms QDP at high discount and/or large atom counts.
- DCFP outperforms CDP in wallclock time at high discounts because DP needs many iterations to converge.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use QDP instead of DCFP at low discount factors and low atom counts | distributional RL in the 5-state random MRP · low discount factors and atom counts | asymptotic estimation error | Helped |
| use DCFP instead of QDP | distributional RL in the 5-state random MRP · larger discounts and/or larger atom count | estimation error | Helped |
| use DCFP instead of QDP | distributional RL in the 5-state random MRP · larger discounts and/or larger atom count | speed | Helped |
| use QDP in near-deterministic environments | distributional RL · near-deterministic environments | performance | Helped |
| use DCFP in settings with short high-probability paths from a state to itself | distributional RL · MRPs with short high-probability self-return paths | performance | Helped |
| use DCFP rather than CDP | distributional RL at high discounts · high discounts | wallclock time | Helped |
| set atom support based on maximal/minimal values of r | DCFP and CDP · 5-state random MRP | estimation error | Helped |
Surprising findings
- Return-distribution estimation with a generative model is statistically no harder than estimating the value function (minimax rate matches mean-return rate up to logs).
Limitations
- Main theorem restricts epsilon in (0, (1-gamma)^{-1/2}) and requires m scaling as (1-gamma)^{-2} eps^{-2}.
- Dense linear system solving is cubic in |X| m, so tractability relies on sparsity.
- Analysis covers only DCFP and CDP, not QDP, whose operator is nonlinear.
Experimental setup
Datasets: synthetic 5-state MRPs with Dirichlet transitions and Unif[0,1] rewards
Benchmarks: synthetic 5-state MRP environments
Metrics: maximum Wasserstein-1 error vs Monte Carlo true return distr wallclock time
Baselines: quantile dynamic programming (QDP) categorical dynamic programming (CDP) empirical distributional Bellman operator (Rowland et al. 2024 style analysis)
Builds on: categorical dynamic programming certainty equivalence quantile dynamic programming Bernstein inequality in Hilbert space
Closest papers by meaning
- Categorical Distributional Reinforcement Learning with Kullback-Leibler Divergence: Convergence and Asymptotics (ICML 2025 · similarity 0.91)
- Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation (ICML 2025 · similarity 0.90)
- Intrinsic Benefits of Categorical Distributional Loss: Uncertainty-aware Regularized Exploration in Reinforcement Learning (NeurIPS 2025 · similarity 0.89)
- A Distributional Analogue to the Successor Representation (ICML 2024 · similarity 0.89)
- Distributional Bellman Operators over Mean Embeddings (ICML 2024 · similarity 0.88)
- A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation (NeurIPS 2025 · similarity 0.88)
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.