Research map / Reinforcement learning / Policy gradient and actor-critic

Distributional Bellman Operators over Mean Embeddings

ICML 2024 · Reinforcement learning › Policy gradient and actor-critic · approach: Distributional value learning · 1 citations (OpenAlex)

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 distributional RL framework that learns finite-dimensional mean embeddings of return distributions and updates them directly with linear sketch Bellman operators (Sketch-DP/Sketch-TD), avoiding imputation, with error-propagation analysis and a DQN variant (Sketch-DQN).

Problem

Distributional RL methods based on statistical functionals (sketches) require an imputation strategy to convert sketch values back to distributions at every Bellman update, which is computationally costly and biologically implausible.

Approach

Represent return distributions by mean embeddings under a feature map and derive a linear Bellman operator on sketch values, using Bellman coefficients obtained from a least-squares regression of phi(r+gamma g) on phi(g), so that DP and TD updates operate entirely in sketch space without imputation.

Key results

• Sketch-DQN attains higher median and mean human-normalised Atari scores than C51 and QR-DQN over 200M frames, approaching IQN.
• Sketch-DP's mean embedding error and Cramer distance decrease as the number of features m increases; the proven error bound scales as O(1/m).
• Sketch-DP is substantially faster in wallclock run-time than imputation-based SFDP.

Measured effects reported in the paper

Surprising findings

• Bellman coefficient matrices B_r are not contractions in L2 norm, with singular values above 1, though dynamics converge to stable fixed points empirically.

Limitations

• Convergence theory for general sketches is left as future work; only error bounds neighbourhood results are given.
• Bellman coefficients require knowing the reward set in advance for DP; TD with unknown rewards needs just-in-time computation.
• Cubic cost of computing Bellman coefficients in feature dimension m and sensitivity to feature hyperparameters (slope, anchors).

Experimental setup

Datasets: Atari 57 Random chain Directed chain DC+Gaussian R

Benchmarks: Atari 57 Random chain MRP Directed chain MRP DC+Gaussian R MRP

Metrics: median human-normalised score mean human-normalised score mean embedding squared error Cramer distance excess Cramer distance wallclock run-time

Baselines: DQN C51 QR-DQN IQN categorical DP SFDP

Builds on: statistical functional dynamic programming QR-DQN categorical DP MMDRL

Closest papers by meaning

• 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)
• Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learning (NeurIPS 2026 · similarity 0.88)
• Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework (NeurIPS 2026 · similarity 0.86)
• Distributional Reinforcement Learning with Regularized Wasserstein Loss (NeurIPS 2024 · similarity 0.86)
• Epistemic Bellman Operators (AAAI 2025 · similarity 0.85)