mlsanityData to 14 Oct 2026

The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning

arXiv 2305.15703 ↗First posted 25 May 2023cs.LG cs.AI math.OCcited by 27

Not on the map. Why?

Abstract (arXiv)

While distributional reinforcement learning (DistRL) has been empirically effective, the question of when and why it is better than vanilla, non-distributional RL has remained unanswered. This paper explains the benefits of DistRL through the lens of small-loss bounds, which are instance-dependent bounds that scale with optimal achievable cost. Particularly, our bounds converge much faster than those from non-distributional approaches if the optimal cost is small. As warmup, we propose a distributional contextual bandit (DistCB) algorithm, which we show enjoys small-loss regret bounds and empirically outperforms the state-of-the-art on three real-world tasks. In online RL, we propose a DistRL algorithm that constructs confidence sets using maximum likelihood estimation. We prove that our algorithm enjoys novel small-loss PAC bounds in low-rank MDPs. As part of our analysis, we introduce the ℓ1 distributional eluder dimension which may be of independent interest. Then, in offline RL, we show that pessimistic DistRL enjoys small-loss PAC bounds that are novel to the offline setting and are more robust to bad single-policy coverage.

Key facts. Cited by 27 papers in the map (data through 14 Oct 2026). Builds on 65 of its 100 references that are in the map. First posted on arXiv 25 May 2023.

Builds on

65 of 100 references.

References · 65

  1. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  2. 2017Rainbow: Combining Improvements in Deep Reinforcement Learningcited by 786
  3. 2017A Distributional Perspective on Reinforcement Learningcited by 765
  4. 2020MOReL : Model-Based Offline Reinforcement Learningcited by 590
  5. 2014OpenML: networked science in machine learningcited by 526
  6. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  7. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  8. 2017Distributional Reinforcement Learning with Quantile Regressioncited by 474
  9. 2018Implicit Quantile Networks for Distributional Reinforcement Learningcited by 369
  10. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  11. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  12. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
38 more
  1. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 279
  2. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
  3. 2013Learning to Optimize Via Posterior Samplingcited by 256
  4. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  5. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  6. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  7. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  8. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  10. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  11. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  12. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  13. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 164
  14. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 136
  15. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  16. 2020Neural Thompson Samplingcited by 128
  17. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  18. 2022Adversarially Trained Actor Critic for Offline Reinforcement Learningcited by 111
  19. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 110
  20. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  21. 2020Information Theoretic Regret Bounds for Online Nonlinear Controlcited by 90
  22. 2019Fully Parameterized Quantile Function for Distributional Reinforcement Learningcited by 88
  23. 2022The Role of Coverage in Online Reinforcement Learningcited by 83
  24. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  25. 2021Conservative Offline Distributional Reinforcement Learningcited by 79
  26. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  27. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 71
  28. 2018An Analysis of Categorical Distributional Reinforcement Learningcited by 68
  29. 2018Offline Multi-Action Policy Learning: Generalization and Optimizationcited by 65
  30. 2019Being Optimistic to Be Conservative: Quickly Learning a CVaR Policycited by 63
  31. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  32. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  33. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  34. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  35. 2019A Comparative Analysis of Expected and Distributional Reinforcement Learningcited by 47
  36. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  37. 2021Instabilities of Offline RL with Pre-Trained Neural Representationcited by 38
  38. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38

50 most cited of 65 All 65 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 13; 2025: 7; 2026: 6.

27 papers.

Sort:

By area:

  1. 2024Stop Regressing: Training Value Functions via Classification for Scalable Deep RLcited by 144
  2. 2024REBEL: Reinforcement Learning via Regressing Relative Rewardscited by 69
  3. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  4. 2024More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learningcited by 23
  5. 2025Bigger, Regularized, Categorical: High-Capacity Value Functions are Efficient Multi-Task Learnerscited by 23
  6. 2024Diffusing States and Matching Scores: A New Framework for Imitation Learningcited by 16
  7. 2025Qsharp: Provably Optimal Distributional RL for LLM Post-Trainingcited by 15
  8. 2025Value Flowscited by 15
  9. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  10. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  11. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  12. 2024Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learningcited by 8
15 more
  1. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  2. 2024Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Modelcited by 7
  3. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 6
  4. 2024Provable Risk-Sensitive Distributional Reinforcement Learning with General Function Approximationcited by 3
  5. 2024Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processescited by 3
  6. 2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximationcited by 3
  7. 2026Eluder dimension: localise it!cited by 3
  8. 2025Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learningcited by 2
  9. 2026Towards Efficient and Expressive Offline RL via Flow-Anchored Noise-conditioned Q-Learningcited by 2
  10. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
  11. 2026Quantile-Coupled Flow Matching for Distributional Reinforcement Learningcited by 1
  12. 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learningcited by 1
  13. 2024Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximationcited by 0
  14. 2026From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Modelcited by 0
  15. 2026Distributional Reinforcement Learning via the Cram'er Distancecited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs
  2. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage
  3. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  4. 2022Settling the Communication Complexity for Distributed Offline Reinforcement Learning
  5. 2025A Differential Perspective on Distributional Reinforcement Learning
  6. 2026Decoupling Time and Risk: Risk-Sensitive Reinforcement Learning with General Discounting
  7. 2024A Robust Quantile Huber Loss With Interpretable Parameter Adjustment In Distributional Reinforcement Learning
  8. 2026Multivariate Distributional Reinforcement Learning Using Sliced Divergences