mlsanityData to 7 Oct 2026

More Benefits of Being Distributional: Second-Order Bounds for Reinforcement Learning

arXiv 2402.07198 ↗First posted 11 Feb 2024cs.LGcited by 23

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

In this paper, we prove that Distributional Reinforcement Learning (DistRL), which learns the return distribution, can obtain second-order bounds in both online and offline RL in general settings with function approximation. Second-order bounds are instance-dependent bounds that scale with the variance of return, which we prove are tighter than the previously known small-loss bounds of distributional RL. To the best of our knowledge, our results are the first second-order bounds for low-rank MDPs and for offline RL. When specializing to contextual bandits (one-step RL problem), we show that a distributional learning based optimism algorithm achieves a second-order worst-case regret bound, and a second-order gap dependent bound, simultaneously. We also empirically demonstrate the benefit of DistRL in contextual bandits on real-world datasets. We highlight that our analysis with DistRL is relatively simple, follows the general framework of optimism in the face of uncertainty and does not require weighted regression. Our results suggest that DistRL is a promising framework for obtaining second-order bounds in general RL settings, thus further reinforcing the benefits of DistRL.

Key facts. Cited by 23 papers in the map (data through 7 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 44 of its 60 references that are in the map. First posted on arXiv 11 Feb 2024.

Builds on

44 of 60 references.

Closest ancestors · 6

Same direction, newest first

  1. 2022Learning Bellman Complete Representations for Offline Policy Evaluation12 Jul
  2. 2021Representation Learning for Online and Offline RL in Low-rank MDPs9 Oct
  3. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  4. 2021Conservative Offline Distributional Reinforcement Learning12 Jul
  5. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  6. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec

Other references · 38

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  3. 2017Rainbow: Combining Improvements in Deep Reinforcement Learningcited by 774
  4. 2017A Distributional Perspective on Reinforcement Learningcited by 743
  5. 2014OpenML: networked science in machine learningcited by 523
  6. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  7. 2017Distributional Reinforcement Learning with Quantile Regressioncited by 464
  8. 2018Implicit Quantile Networks for Distributional Reinforcement Learningcited by 362
  9. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  10. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  11. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  12. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
26 more
  1. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  2. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  3. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  4. 2018Practical Contextual Bandits with Regression Oraclescited by 92
  5. 2019Fully Parameterized Quantile Function for Distributional Reinforcement Learningcited by 87
  6. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  7. 2018An Analysis of Categorical Distributional Reinforcement Learningcited by 68
  8. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  9. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
  10. 2019A Comparative Analysis of Expected and Distributional Reinforcement Learningcited by 47
  11. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  12. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  13. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  14. 2022Spectral Decomposition Representation for Reinforcement Learningcited by 35
  15. 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
  16. 2023An Analysis of Quantile Temporal-Difference Learningcited by 30
  17. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 29
  18. 2019Quantile QT-Opt for Risk-Aware Vision-Based Robotic Graspingcited by 27
  19. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  20. 2013Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalizationcited by 19
  21. 2023Distributional Offline Policy Evaluation with Predictive Error Guaranteescited by 19
  22. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  23. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17
  24. 2023The Statistical Benefits of Quantile Temporal-Difference Learning for Value Estimationcited by 14
  25. 2021Provably Correct Optimization and Exploration with Non-linear Policiescited by 13
  26. 2022Conditionally Risk-Averse Contextual Banditscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 10; 2025: 8; 2026: 5.

23 papers.

Sort:

By area:

  1. 2024REBEL: Reinforcement Learning via Regressing Relative Rewardscited by 66
  2. 2024Diffusing States and Matching Scores: A New Framework for Imitation Learningcited by 16
  3. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 15
  4. 2025Qsharp: Provably Optimal Distributional RL for LLM Post-Trainingcited by 14
  5. 2025Value Flowscited by 12
  6. 2024Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Boundscited by 11
  7. 2024Second Order Bounds for Contextual Bandits with Function Approximationcited by 9
  8. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  9. 2024Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learningcited by 8
  10. 2024The Central Role of the Loss Function in Reinforcement Learningcited by 8
  11. 2025A Finite Sample Analysis of Distributional TD Learning with Linear Function Approximationcited by 5
  12. 2024Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processescited by 3
11 more
  1. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  2. 2025Instance-Dependent Continuous-Time Reinforcement Learning via Maximum Likelihood Estimationcited by 1
  3. 2025Rectifying Regression in Reinforcement Learningcited by 1
  4. 2025Variance-Aware Feel-Good Thompson Sampling for Contextual Banditscited by 1
  5. 2026Quantile-Coupled Flow Matching for Distributional Reinforcement Learningcited by 1
  6. 2026Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learningcited by 1
  7. 2024Finite Sample Bounds for Non-Parametric Regression: Optimal Sample Efficiency and Space Complexitycited by 0
  8. 2025Second-Order Bounds for [0,1]-Valued Regression via Betting Losscited by 0
  9. 2026Towards Efficient and Expressive Offline RL via Flow-Anchored Noise-conditioned Q-Learningcited by 0
  10. 2026Distributional Reinforcement Learning via the Cram'er Distancecited by 0
  11. 2026Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Setcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage
  2. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage
  3. 2023Selective Uncertainty Propagation in Offline RL
  4. 2022On Practical Reinforcement Learning: Provable Robustness, Scalability, and Statistical Efficiency
  5. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  6. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs
  7. 2026Distorted Distributional Policy Evaluation for Offline Reinforcement Learning
  8. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximation