Research map / Bandits and online learning / RL theory and MDPs
Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation
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.
Introduces Bellman unbiasedness and proves moment functionals are the only sketches that are both Bellman unbiased and closed, then proposes SF-LSVI, a moment-based distributional RL algorithm with general value function approximation achieving Õ(d_E H^{3/2} √K) regret.
Problem
Distributional RL lacks a theory that accounts for the infinite dimensionality of return distributions and for exact, unbiased learnability of statistical functionals from finite samples, and existing regret analyses rely on distributional Bellman completeness that is intractable or leads to linear
Approach
Defines Bellman unbiasedness (finite-sample unbiased estimation of sketched Bellman targets), shows with Bellman closedness that only moment functionals qualify, and runs least-squares value iteration on normalized moments with a statistical-functional Bellman completeness assumption, yielding eluder-dimension regret bounds.
Key results
- SF-LSVI achieves regret Õ(d_E H^{3/2} √K), improving on V-EST-LSR's Õ(d_E H^2 √K) by √H under weaker assumptions.
- Theorem: the only finite sketches that are both Bellman unbiased and Bellman closed are linear spans of exponential-polynomial functionals (moments in the discounted setting).
- Quantile functionals cannot be Bellman closed under any additional sketch.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SF-LSVI with moment functionals instead of V-EST-LSR | Distributional RL with general value function approximation · Episodic MDP | regret upper bound: $\tilde{\mathcal{O}}(d_E H^2 \sqrt{K})$ -> $\tilde{\mathcal{O}}(d_E H^{\frac{3}{2}} \sqrt{K})$ | Helped |
| Use a finite-dimensional moment sketch and statistical functional Bellman completeness rather than distributional Bellman completeness | Distributional RL with general value function approximation · Episodic MDP | regret upper bound: $\tilde{\mathcal{O}}(d_E H^2 \sqrt{K})$ -> $\tilde{\mathcal{O}}(d_E H^{\frac{3}{2}} \sqrt{K})$ | Helped |
Surprising findings
- Median and quantile sketches are not mixture-consistent, so they cannot be exactly updated by Bellman operators.
- Distributional Bellman completeness with finite representations tends to cause linear regret through model misspecification.
Limitations
- Width function for general function classes requires solving a set-constrained optimization that is NP-hard.
- Regret is defined on expected return rather than distributional moments, so sample efficiency of distributional learning itself is not shown.
- No empirical experiments are reported.
Experimental setup
Metrics: regret
Baselines: O-DISCO V-EST-LSR
Builds on: Bellman closedness (Rowland et al.) LSVI-UCB / least-squares value iteration eluder dimension V-EST-LSR O-DISCO
Closest papers by meaning
- Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Model (NeurIPS 2024 · similarity 0.90)
- Distributional Bellman Operators over Mean Embeddings (ICML 2024 · similarity 0.88)
- Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation (ICML 2024 · similarity 0.88)
- A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximation (NeurIPS 2025 · similarity 0.88)
- More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning (ICML 2024 · similarity 0.88)
- Intrinsic Benefits of Categorical Distributional Loss: Uncertainty-aware Regularized Exploration in Reinforcement Learning (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.