Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Model

Mark Rowland, Li Kevin Wenliang, Rémi Munos, Clare Lyle, Yunhao Tang, Will Dabney

TL;DR

Researchers from Google DeepMind and Meta have introduced the Direct Categorical Fixed-Point (DCFP) algorithm, proving it is minimax-optimal for estimating return distributions in reinforcement learning. Their work surprisingly shows that learning a full probability distribution of future rewards is statistically no harder than simply estimating the average reward, resolving a major open question in the field.

What Problem Does This Paper Address?

Standard Reinforcement Learning (RL) typically focuses on the "value function"—the expected average of future rewards. However, Distributional RL aims for a richer signal: the full probability distribution of those returns. This is crucial for risk-sensitive applications like robotics or healthcare, where knowing the "worst-case" or "best-case" scenario is as important as the average.

A foundational question has lingered: Is estimating a full distribution statistically harder than estimating a single mean? In other words, do we need significantly more data to get a good handle on the distribution? Previous research suggested a gap between what was theoretically possible and what current algorithms could achieve. This paper closes that gap by studying the "generative model" setting, where an agent can query transitions from any state.

Methods

The authors focus on Categorical RL, where return distributions are represented by a set of "atoms" (fixed points on a grid).

  1. Direct Categorical Fixed-Point (DCFP): Instead of the standard approach of iteratively applying a Bellman operator until convergence (which can be slow), DCFP formulates the problem as a linear system of equations. By working with Cumulative Distribution Functions (CDFs) rather than probability masses, the authors show that the constraints (like probabilities summing to one) become much easier to handle, allowing for a direct, exact solution.
  2. Stochastic Categorical CDF Bellman Equation: To prove optimality, the authors introduced a new theoretical tool. This equation models how the "noise" from random samples propagates through the categorical projection process.
  3. Hilbert Space Analysis: The proof relies on analyzing the Cramér distance between distributions using embeddings in a Reproducing Kernel Hilbert Space (RKHS), allowing the use of powerful concentration inequalities to bound estimation errors.
Figure 1: (a) The density of a distribution ν (grey), and its categorical projection Πmν ∈ P({z1, . . . , zm}) (blue). (b) A categorical distribution (blue); its update after being scaled by γ and shifted by r by the distributional Bellman operator T , moving its support off the grid {z1, . . . , zm} (pink); the resulting realigned distribution supported on the grid {z1, . . . , zm} after projection via Πm (green). (c) Hat functions hi (solid) and hm (dashed).

Datasets

The authors evaluated DCFP against Quantile Dynamic Programming (QDP) and standard Categorical Dynamic Programming (CDP) across four synthetic environments:

  • Chain: A 10-state linear environment with sparse rewards.
  • Low Random: A 5-state environment with highly deterministic transitions (sampled from a Dirichlet distribution with low concentration).
  • High Random: A 5-state environment with highly stochastic transitions.
  • Two-state: A specific environment designed to highlight the approximation errors inherent in quantile-based methods.

Evaluation was performed by measuring the Wasserstein-1 distance between the estimated distributions and the "ground truth" return distributions calculated via extensive Monte Carlo sampling.

Key Insights and Ideas

  • Statistical Parity: The most striking insight is that distributional RL is "essentially no harder" than value-based RL. The number of samples required to estimate the return distribution to a certain accuracy matches the lower bound for estimating the mean return.
  • The CDF Advantage: Switching from probability mass functions to CDFs isn't just a notation change; it simplifies the underlying linear algebra. In the CDF space, the requirement that the final atom must contain all remaining probability mass becomes a simple "axis-aligned" constraint ($F_m = 1$), making the linear system easier to solve uniquely.
  • Sparsity is Key: Even though the DCFP involves solving a large linear system, the transition matrix is extremely sparse. This allows practitioners to use efficient sparse solvers, making the algorithm much faster than iterative methods in many cases.

Key Results

  • Minimax Optimality: The authors prove that DCFP achieves the lower bound of $N = \tilde{\Omega}(\epsilon^{-2}(1-\gamma)^{-3})$ samples, where $\epsilon$ is the desired accuracy and $\gamma$ is the discount factor.
  • Empirical Speed and Accuracy: In experiments, DCFP was generally faster than QDP. While QDP sometimes performed better in low-stochasticity environments with few atoms, DCFP dominated as the number of atoms increased or in environments with high discount factors.
Comparison of Wasserstein distance vs. wallclock time. DCFP (orange) often reaches lower error faster than QDP (blue) or iterative CDP (dashed lines).

Limitations and Future Work

  • Tabular Setting: The current theoretical guarantees are limited to tabular (finite state) environments. While the authors suggest DCFP could be adapted for function approximation (like deep neural networks), the minimax optimality proof does not yet extend to that regime.
  • Policy Optimization: The paper focuses on policy evaluation (estimating returns for a fixed policy). Extending these sample complexity results to policy optimization (finding the best policy) is a natural next step, though the authors note that the non-uniqueness of optimal return distributions makes this theoretically tricky.
  • Instance-Dependent Bounds: The current bounds are "worst-case." The authors suggest that future work could look for "instance-dependent" bounds that account for the specific structure of a given environment, which might be even tighter.

Summary updated

Abstract

We propose a new algorithm for model-based distributional reinforcement learning (RL), and prove that it is minimax-optimal for approximating return distributions with a generative model (up to logarithmic factors), resolving an open question of Zhang et al. (2023). Our analysis provides new theoretical results on categorical approaches to distributional RL, and also introduces a new distributional Bellman equation, the stochastic categorical CDF Bellman equation, which we expect to be of independent interest. We also provide an experimental study comparing several model-based distributional RL algorithms, with several takeaways for practitioners.
BibTeX
@inproceedings{rowland2024near,
  author = {Mark Rowland and Li Kevin Wenliang and Rémi Munos and Clare Lyle and Yunhao Tang and Will Dabney},
  title = {{Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=JXKbf1d4ib},
}
Figure