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

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 Bellman 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, SF-LSVI, that achieves a tight regret bound of Õ(d E H 1. Related Work 1 We ignore poly-log terms in H, S, A, K in the Õ(•) notation. 2 In Chen et al. (2024), the regret bound is written as Õ(dEL∞(ρ)H √ K), where L∞(ρ) represents the lipschitz constant of the risk measure ρ, i.e., |ρ(Z) -ρ(Z ′ )| ≤ L∞(ρ)∥FZ -F Z ′ ∥∞. Since L∞(ρ) ≥ H in risk-neutral setting, we translate the regret bound into Õ(dEH 2 √ K).