# Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation

arXiv: https://arxiv.org/abs/2407.21260 · HTML: https://mlsanity.com/paper/2407.21260/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 29 of its 45 references that are in the map.
- First posted on arXiv 31 Jul 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 29 of 29)

- [A Distributional Perspective on Reinforcement Learning](https://mlsanity.com/paper/1707.06887/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Distributional Reinforcement Learning with Quantile Regression](https://mlsanity.com/paper/1710.10044/) (2017)
- [Implicit Quantile Networks for Distributional Reinforcement Learning](https://mlsanity.com/paper/1806.06923/) (2018)
- [Revisiting the Arcade Learning Environment: Evaluation Protocols and Open Problems for General Agents](https://mlsanity.com/paper/1709.06009/) (2017)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach](https://mlsanity.com/paper/1506.02188/) (2015)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [An Analysis of Categorical Distributional Reinforcement Learning](https://mlsanity.com/paper/1802.08163/) (2018)
- [Statistics and Samples in Distributional Reinforcement Learning](https://mlsanity.com/paper/1902.08102/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation](https://mlsanity.com/paper/2212.06069/) (2022)
- [Efficient Risk-Averse Reinforcement Learning](https://mlsanity.com/paper/2205.05138/) (2022)
- [On Lower Bounds for Regret in Reinforcement Learning](https://mlsanity.com/paper/1608.02732/) (2016)
- [Quantile QT-Opt for Risk-Aware Vision-Based Robotic Grasping](https://mlsanity.com/paper/1910.02787/) (2019)
- [The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning](https://mlsanity.com/paper/2305.15703/) (2023)
- [Regret Bounds for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2210.05650/) (2022)
- [Trust Region-Based Safe Distributional Reinforcement Learning for Multiple Constraints](https://mlsanity.com/paper/2301.10923/) (2023)
- [Bridging Distributional and Risk-sensitive Reinforcement Learning with Provable Regret Bounds](https://mlsanity.com/paper/2210.14051/) (2022)
- [Beyond Average Return in Markov Decision Processes](https://mlsanity.com/paper/2310.20266/) (2023)
- [Pitfall of Optimism: Distributional Reinforcement Learning by Randomizing Risk Criterion](https://mlsanity.com/paper/2310.16546/) (2023)
- [Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2402.18159/) (2024)

## Abstract (arXiv)

Distributional reinforcement learning improves performance by capturing environmental stochasticity, but a comprehensive theoretical understanding of its effectiveness remains elusive. In addition, the intractable element of the infinite dimensionality of distributions has been overlooked. In this paper, we present a regret analysis of distributional reinforcement learning with general value function approximation in a finite episodic Markov decision process setting. We first introduce a key notion of textitBellman unbiasedness which is essential for exactly learnable and provably efficient distributional updates in an online manner. Among all types of statistical functionals for representing infinite-dimensional return distributions, our theoretical results demonstrate that only moment functionals can exactly capture the statistical information. Secondly, we propose a provably efficient algorithm, textttSF-LSVI, that achieves a tight regret bound of tildeO(dE H^frac32√K) where H is the horizon, K is the number of episodes, and dE is the eluder dimension of a function class.