mlsanityData to 14 Oct 2026

Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits

arXiv 2505.20268 ↗First posted 26 May 2025cs.LG cs.AI math.STcited by 7

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Reinforcement learning with outcome-based feedback faces a fundamental challenge: when rewards are only observed at trajectory endpoints, how do we assign credit to the right actions? This paper provides the first comprehensive analysis of this problem in online RL with general function approximation. We develop a provably sample-efficient algorithm achieving widetildeO(Crm cov H3/ε2) sample complexity, where Crm cov is the coverability coefficient of the underlying MDP. By leveraging general function approximation, our approach works effectively in large or infinite state spaces where tabular methods fail, requiring only that value functions and reward functions can be represented by appropriate function classes. Our results also characterize when outcome-based feedback is statistically separated from per-step rewards, revealing an unavoidable exponential separation for certain MDPs. For deterministic MDPs, we show how to eliminate the completeness assumption, dramatically simplifying the algorithm. We further extend our approach to preference-based feedback settings, proving that equivalent statistical efficiency can be achieved even under more limited information. Together, these results constitute a theoretical foundation for understanding the statistical properties of outcome-based reinforcement learning.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 40 of its 60 references that are in the map. First posted on arXiv 26 May 2025.

Builds on

40 of 60 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback13 May
  2. 2024Scalable Online Exploration via Coverability11 Mar

Other references · 38

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,720
  3. 2020Is Pessimism Provably Efficient for Offline RL?cited by 364
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  5. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  6. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 269
  7. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  8. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  9. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  10. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  11. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  12. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
26 more
  1. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 106
  2. 2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106
  3. 2020Batch Value-function Approximation with Only Realizabilitycited by 104
  4. 2023Is RLHF More Difficult than Standard RL?cited by 96
  5. 2022The Role of Coverage in Online Reinforcement Learningcited by 83
  6. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 81
  7. 2024Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHFcited by 73
  8. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  9. 2024Self-Exploring Language Models: Active Preference Elicitation for Online Alignmentcited by 63
  10. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  11. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  12. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  13. 2020Reinforcement Learning with Trajectory Feedbackcited by 40
  14. 2022On the Complexity of Adversarial Decision Makingcited by 33
  15. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  16. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  17. 2023Adversarial Model for Offline Reinforcement Learningcited by 31
  18. 2013An efficient algorithm for learning with semi-bandit feedbackcited by 21
  19. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  20. 2021Understanding the Eluder Dimensioncited by 19
  21. 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspectivecited by 17
  22. 2024Harnessing Density Ratios for Online Reinforcement Learningcited by 15
  23. 2022Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyondcited by 10
  24. 2025Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedbackcited by 6
  25. 2023What can online reinforcement learning with function approximation benefit from general coverage conditions?cited by 4
  26. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 5.

7 papers.

  1. 2025Improved Bounds for Private and Robust Alignmentcited by 5
  2. 2025Offline and Online KL-Regularized RLHF under Differential Privacycited by 4
  3. 2026Post-Training with Policy Gradients: Optimality and the Base Model Barriercited by 3
  4. 2026Rethinking Reinforcement fine-tuning of LLMs: A Multi-armed Bandit Learning Perspectivecited by 0
  5. 2026Demystifying Design Choices of Reinforcement Fine-tuning: A Batched Contextual Bandit Learning Perspectivecited by 0
  6. 2026When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?cited by 0
  7. 2026Provable Test-Time Scaling for Beam Search in LLM Reasoningcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  2. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation
  3. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  4. 2020On Reward-Free Reinforcement Learning with Linear Function Approximation
  5. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning
  6. 2026Mathematical methods of reinforcement learning
  7. 2025The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective
  8. 2025Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspective