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.
Introduction
Standard Reinforcement Learning (RL) usually focuses on the value function—the expected sum of future rewards. However, the average doesn't tell the whole story. In many real-world scenarios, like healthcare or autonomous driving, we care about the distribution of outcomes (e.g., "What is the 5% worst-case scenario?"). This is the domain of Distributional RL.
A foundational, unanswered question in the field was: Is learning the full distribution statistically harder than learning the mean? Intuitively, one might think far more data is required to map out an entire probability curve than to just find its center. This work tackles this question in the "generative model" setting, where an agent can request samples of transitions from any state.
The DCFP Algorithm
The paper introduces the Direct Categorical Fixed-Point (DCFP) algorithm. Most distributional RL methods are iterative—they update their estimates repeatedly until they converge. DCFP takes a different shortcut. By representing distributions as Cumulative Distribution Functions (CDFs) on a fixed grid of "atoms," the authors show that the distributional Bellman equation becomes a system of linear equations.
DCFP solves this system directly, which is both computationally efficient and theoretically "cleaner." To prove their theoretical bounds, the authors developed a new mathematical framework: the Stochastic Categorical CDF Bellman Equation. This equation describes how the "noise" from random samples propagates through the categorical representation, allowing them to prove that DCFP is minimax-optimal—meaning no other algorithm can do significantly better with the same amount of data.
Key Insights and Ideas
- Distributional RL is "Free": The most surprising takeaway is that the number of samples required to estimate the return distribution (to a certain accuracy $\epsilon$) is essentially the same as what is required to estimate the mean. Statistically speaking, you get the full distribution for the price of the average.
- The Power of CDFs: While many algorithms work with probability density (PDFs), switching to CDFs makes the math linear. This linearity is what allows for the "direct" solution in DCFP and simplifies the proof of optimality.
- Sparsity is a Feature: The authors highlight that the matrices involved in DCFP are often very sparse. This means that even though the system of equations looks large, modern sparse solvers can handle them extremely quickly, often outperforming iterative methods.
Empirical Results
The authors evaluated their approach on four distinct Markov Reward Processes (MRPs): Chain, Low Random, High Random, and a Two-state loop.
In empirical tests, DCFP was generally faster than Quantile Dynamic Programming (QDP). While QDP can be more accurate in near-deterministic environments because it "moves" its atoms to where the data is, DCFP is more robust and faster in highly stochastic settings or when using a high discount factor ($\gamma$). The direct solver (DCFP) consistently outperformed iterative categorical methods (CDP) in terms of "wallclock" time, especially as the discount factor approached 1.0, where iterative methods typically slow down.
Limitations and Future Work
The current proof and algorithm are designed for "tabular" RL—where the number of states is finite and small enough to fit in a matrix. Extending these minimax-optimal guarantees to Deep RL (using neural networks for function approximation) remains a major challenge. Additionally, DCFP uses a fixed grid of atoms; if the return distribution is extremely narrow, a fixed grid might be less efficient than "floating" atom methods. Finally, this paper focuses on policy evaluation; extending this to optimal control (finding the best possible policy) is a natural next step.
Summary updated