# When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 24 of its 80 references that are in the map.
- First posted on arXiv 16 Jun 2026.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)
- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 24 of 24)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Offline Reinforcement Learning with Implicit Q-Learning](https://mlsanity.com/paper/2110.06169/) (2021)
- [OpenAI o1 System Card](https://mlsanity.com/paper/2412.16720/) (2024)
- [Solving math word problems with process- and outcome-based feedback](https://mlsanity.com/paper/2211.14275/) (2022)
- [Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning](https://mlsanity.com/paper/2410.08146/) (2024)
- [Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient](https://mlsanity.com/paper/2210.06718/) (2022)
- [Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximation](https://mlsanity.com/paper/2111.10919/) (2021)
- [Provable Offline Preference-Based Reinforcement Learning](https://mlsanity.com/paper/2305.14816/) (2023)
- [Foundations of Reinforcement Learning and Interactive Decision Making](https://mlsanity.com/paper/2312.16730/) (2023)
- [Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective](https://mlsanity.com/paper/2502.10581/) (2025)
- [A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalents](https://mlsanity.com/paper/2403.06323/) (2024)
- [Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Models](https://mlsanity.com/paper/2406.04274/) (2024)
- [Trajectory Bellman Residual Minimization: A Simple Value-Based Method for LLM Reasoning](https://mlsanity.com/paper/2505.15311/) (2025)
- [Maximum Reward Formulation In Reinforcement Learning](https://mlsanity.com/paper/2010.03744/) (2020)
- [Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2405.07637/) (2024)
- [To the Max: Reinventing Reward in Reinforcement Learning](https://mlsanity.com/paper/2402.01361/) (2024)
- [Directed Exploration in Reinforcement Learning from Linear Temporal Logic](https://mlsanity.com/paper/2408.09495/) (2024)
- [Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits](https://mlsanity.com/paper/2505.20268/) (2025)
- [Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2502.04004/) (2025)
- [Planning with Submodular Objective Functions](https://mlsanity.com/paper/2010.11863/) (2020)
- [The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2406.11686/) (2024)
- [Risk-sensitive Reinforcement Learning Based on Convex Scoring Functions](https://mlsanity.com/paper/2505.04553/) (2025)

## Abstract (arXiv)

Offline reinforcement learning is typically analyzed under process-level reward supervision, yet many sequential decision datasets record only trajectory-level outcomes. We develop a statistical theory for offline policy optimization from such outcome-level supervision. We first study the canonical setting where the target remains the expected cumulative reward, but each offline trajectory provides only a scalar label whose conditional mean is the cumulative return. We propose OPAC, a pessimistic actor-critic algorithm that learns a latent reward model and optimizes a policy from trajectory-level labels. We prove a high-probability guarantee of order widetilde O(H2√Csa(π^star)/n) and a matching lower bound, characterizing the sharp statistical cost of replacing process-level rewards with one trajectory-level label. We then extend the principle to preference-based feedback, preserving the leading horizon and concentrability dependence up to preference-model constants. Finally, we study generalized outcome-based offline RL, where both the supervision and the objective are trajectory-level quantities induced by a nonlinear aggregation of latent per-step rewards. This problem is not learnable in general: for all-success objectives, any offline learner may require Omega(2H) trajectories even with deterministic transitions and constant concentrability. We then identify a tractable regime through two structural coefficients, kappaμ(σ) and chiμ(σ), capturing information loss in outcome aggregation and generalized Bellman updates, under which generalized OPAC achieves polynomial sample complexity. Together, our results delineate when outcome-level supervision enables sample-efficient offline control and when missing process-level rewards create fundamental statistical barriers.