# Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits

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

## 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.

## 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, 30 of 40)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHF](https://mlsanity.com/paper/2405.21046/) (2024)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Is RLHF More Difficult than Standard RL?](https://mlsanity.com/paper/2306.14111/) (2023)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2205.11140/) (2022)
- [Value-Incentivized Preference Optimization: A Unified Approach to Online and Offline RLHF](https://mlsanity.com/paper/2405.19320/) (2024)
- [Preference-based Reinforcement Learning with Finite-Time Guarantees](https://mlsanity.com/paper/2006.08910/) (2020)
- [Self-Exploring Language Models: Active Preference Elicitation for Online Alignment](https://mlsanity.com/paper/2405.19332/) (2024)
- [Dueling Posterior Sampling for Preference-Based Reinforcement Learning](https://mlsanity.com/paper/1908.01289/) (2019)
- [Provable Offline Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.14816/) (2023)
- [Making RL with Preference-based Feedback Efficient via Randomization](https://mlsanity.com/paper/2310.14554/) (2023)
- [Reinforcement Learning with Trajectory Feedback](https://mlsanity.com/paper/2008.06036/) (2020)
- [On the Complexity of Adversarial Decision Making](https://mlsanity.com/paper/2206.13063/) (2022)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [On the Theory of Reinforcement Learning with Once-per-Episode Feedback](https://mlsanity.com/paper/2105.14363/) (2021)
- [Adversarial Model for Offline Reinforcement Learning](https://mlsanity.com/paper/2302.11048/) (2023)
- [An efficient algorithm for learning with semi-bandit feedback](https://mlsanity.com/paper/1305.2732/) (2013)

## Built on by (most cited first, 7 of 7)

- [Improved Bounds for Private and Robust Alignment](https://mlsanity.com/paper/2512.23816/) (2025)
- [Offline and Online KL-Regularized RLHF under Differential Privacy](https://mlsanity.com/paper/2510.13512/) (2025)
- [Post-Training with Policy Gradients: Optimality and the Base Model Barrier](https://mlsanity.com/paper/2603.06957/) (2026)
- [Rethinking Reinforcement fine-tuning of LLMs: A Multi-armed Bandit Learning Perspective](https://mlsanity.com/paper/2601.14599/) (2026)
- [Demystifying Design Choices of Reinforcement Fine-tuning: A Batched Contextual Bandit Learning Perspective](https://mlsanity.com/paper/2601.22532/) (2026)
- [When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?](https://mlsanity.com/paper/2606.18531/) (2026)
- [Provable Test-Time Scaling for Beam Search in LLM Reasoning](https://mlsanity.com/paper/2609.38672/) (2026)

## 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.