Bellman Diffusion: Generative Modeling as Learning a Linear Operator in the Distribution Space

Yangming Li, Chieh-Hsin Lai, Carola-Bibiane Schönlieb, Yuki Mitsufuji, Stefano ErmonSubmission to ICLR 2025 · Rejected

TL;DR

Modern Deep Generative Models (DGMs) struggle in distributional Reinforcement Learning (RL) because their parameterizations are inherently non-linear, which clashes with the linear structure of the Bellman equation. Bellman Diffusion resolves this by modeling both the scalar density field and its gradient field, preserving linearity under Bellman updates while avoiding the discretization errors of traditional histogram-based approaches. This yields an expressive generative model that converges $1.5\times$ faster and far more stably in distributional RL tasks.

What Problem Does This Paper Address?

In distributional RL, agents learn the full probability distribution of future returns rather than just the expected value ($Q$-function). Historically, this has been dominated by categorical or histogram-based approximations like C51. However, binning continuous return distributions introduces discretization errors at every step, which compound over long trajectories and cause training instability.

Why not just swap histograms for modern continuous generative models like Energy-Based Models (EBMs), Normalizing Flows, or Diffusion Models?

The authors identify a fundamental mathematical bottleneck: the Bellman update is linear in distribution space, defined as: $$p_z(\cdot) = \sum_{z', r} \alpha_{z, z', r} \, p_{z'}\left(\frac{\cdot - r}{\gamma}\right)$$ Most modern generative models parameterize densities through highly non-linear operators (for example, the partition function normalization $e^{-E(x)} / Z$ in EBMs or the pushforward maps in normalizing flows). Because these operators do not satisfy $\mathcal{M}(a f + b g) = a\mathcal{M}(f) + b\mathcal{M}(g)$, one cannot perform standard 1-step Bellman dynamic programming updates on the neural network proxies without sampling entire, computationally expensive rollout trajectories.

Methods

To retain linearity while modeling continuous distributions, Bellman Diffusion models the scalar field $p(x)$ and the gradient field $\nabla p(x)$ simultaneously:

$$\mathcal{M}_{\text{Bellman}} : p(\cdot) \mapsto \begin{bmatrix} \nabla p(\cdot) \\ p(\cdot) \end{bmatrix}$$

Because the gradient and identity operators are linear, the distributional Bellman equation holds directly for both outputs.

Key components include:

  • Field Matching Divergences: The authors define two statistical divergences ($D_{\text{grad}}$ and $D_{\text{id}}$) to train network proxies $g_\phi(x) \approx \nabla p(x)$ and $s_\varphi(x) \approx p(x)$ without needing intractable partition functions. By using a family of isotropic Gaussians that converge weakly to the Dirac delta function as $\epsilon \to 0$, they obtain tractable Monte Carlo training objectives.
  • Sliced Field Matching: For high-dimensional data, computing the Jacobian trace $\text{tr}(\nabla g_\phi)$ is expensive, and Gaussian densities suffer from curse of dimensionality. The authors introduce 1D random directional projections (the "slice trick") to keep gradient estimation scalable.
  • Bellman Diffusion Dynamics: Instead of using Langevin dynamics (which divides the gradient by the scalar density $\frac{g_\phi(x)}{s_\varphi(x)}$, creating explosive numerical instabilities when $p(x) \approx 0$), they introduce a novel SDE for sampling: $$dx(t) = \nabla p_{\text{target}}(x(t))\,dt + \sqrt{p_{\text{target}}(x(t))}\,d\omega(t)$$ They prove that marginal distributions under this SDE converge exponentially to $p_{\text{target}}$ in both KL-divergence and Wasserstein-2 distance.
       Bellman Update (Linear in Distribution Space)
                           │
             ┌─────────────┴─────────────┐
             ▼                           ▼
   Scalar Field: s_φ(x)        Gradient Field: g_ϕ(x)
       [ p_target(x) ]           [ ∇ p_target(x) ]
             │                           │
             └─────────────┬─────────────┘
                           ▼
              Bellman Diffusion Dynamics
      dx(t) = g_ϕ(x) dt + sqrt(s_φ(x)) dω(t)

Datasets

The authors evaluated Bellman Diffusion across several domains:

  • Distributional RL Environments: Classic control in OpenAI Gym, specifically Cart Pole (continuous balancing) and Frozen Lake (stochastic grid world).
  • Synthetic Benchmark Densities: A 1D uniform distribution on disjoint intervals, a 2D two-moon dataset, and an unbalanced 2D Mixture of Gaussians (MoG) with mode weights $(0.45, 0.45, 0.1)$.
  • Tabular Datasets (UCI): Five real-world benchmarks: Abalone, Telemonitoring, Mushroom, Parkinson’s, and Red Wine (dimensions ranging from 5 to 16).
  • Image Benchmark: Latent representations of MNIST (paired with a VAE).

Key Insights and Ideas

  • Linearity Unlocks Dynamic Programming: By avoiding normalization denominators and non-linear pushforward maps, Bellman updates can be applied directly to 1-step transitions, reducing sample complexity compared to naive Monte Carlo trajectory sampling.
  • Recovering Unbalanced Modes: In score-based models, learning $\nabla \log p(x)$ makes it notoriously difficult to capture relative mode weights for separated clusters, because the constant mode weight drops out when taking the gradient of the logarithm ($\nabla \log (a \cdot p_1) = \nabla \log p_1$). Because Bellman Diffusion tracks the raw scalar density field $s_\varphi(x)$, it correctly recovers unbalanced cluster weights.
  • No Division by Low Density: Standard score approximation $s(x) = \frac{\nabla p(x)}{p(x)}$ blows up in tail regions where $p(x) \to 0$. The proposed SDE avoids division entirely by putting the scalar density under a square root in the diffusion term.

Key Results

  • $1.5\times$ Faster Convergence in RL: On Cart Pole, Bellman Diffusion matched the peak return of 500 significantly faster than the baseline C51 algorithm, showing smooth, monotonic convergence where C51 suffered from variance and discretization error.
  • Accurate Density Tracking: On Frozen Lake, the model accurately captured shifting return distributions and boundaries as the agent neared the terminal reward state.
  • Competitive Generative Modeling: On the 5 UCI tabular benchmarks, Bellman Diffusion attained competitive or superior Wasserstein distance and Maximum Mean Discrepancy (MMD) relative to DDPM (e.g., Abalone Wasserstein: 0.763 vs. 0.975 for DDPM). When combined with a VAE on MNIST, it successfully generated crisp, coherent digit samples.

Limitations and Future Work

  • Bandwidth Sensitivity: Practical optimization relies on an isotropic Gaussian parameter $\epsilon$. Ablation studies show that setting $\epsilon$ too high introduces approximation bias, while setting it too small causes numerical instability.
  • Discrete-Time Bounds: Theoretical guarantees (Theorems 4.1 & 4.2) are proven in continuous time; finite-step discretization analysis remains open for future work.
  • Large-Scale Generative Validation: Experiments were limited to 1D/2D toys, low-dimensional tabular data, and latent MNIST. Full-scale image/video generation benchmarks were not evaluated, as the primary goal was enabling DGMs for MDPs.

Summary updated

Abstract

Deep Generative Models (DGMs), including Score-based Generative Models, have made significant progress in approximating complex continuous distributions. However, their application to Markov Decision Processes (MDPs), particularly in distributional Reinforcement Learning (RL), is underexplored. The field remains dominated by classical histogram-based methods, which suffer from discretization errors, leading to instability and slower convergence. This work highlights that this gap stems from the nonlinear operators used in modern DGM's modelings, which map neural network functions to the target distribution. These nonlinearities conflict with the linearity required by the Bellman equation, which relates the return distribution of a state to a linear combination of future states' return distributions. To address this, we introduce Bellman Diffusion, a new DGM that preserves the necessary linearity by modeling both the gradient and scalar fields. We propose a novel divergence-based training technique to optimize neural network proxies and introduce a new stochastic differential equation for sampling. With these innovations, Bellman Diffusion is guaranteed to converge to the target distribution. Our experiments show that Bellman Diffusion not only achieves accurate field estimations and serves as an effective image generator, but also converges $1.5\times$ faster than traditional histogram-based baselines in distributional RL tasks. This work paves the way for the effective integration of DGMs into MDP applications, enabling more advanced decision-making frameworks.
BibTeX
@misc{li2024bellman,
  author = {Yangming Li and Chieh-Hsin Lai and Carola-Bibiane Schönlieb and Yuki Mitsufuji and Stefano Ermon},
  title = {{Bellman Diffusion: Generative Modeling as Learning a Linear Operator in the Distribution Space}},
  year = {2024},
  eprint = {2410.01796},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2410.01796},
}
Figure