mlsanityData to 7 Oct 2026

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

arXiv 2606.18531 ↗First posted 16 Jun 2026stat.ML cs.LGcited by 0

On the map: LLM reasoning → Reinforcement learning for reasoning

also in 1 more
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.

Key facts. No citing papers in the map yet (data through 7 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.

Builds on

24 of 80 references.

Closest ancestors · 4

Same direction, newest first

  1. 2025Trajectory Bellman Residual Minimization: A Simple Value-Based Method for LLM Reasoning21 May
  2. 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective14 Feb
  3. 2024Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning10 Oct
  4. 2022Solving math word problems with process- and outcome-based feedback25 Nov

Other references · 20

  1. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  2. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,634
  3. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  4. 2021Offline Reinforcement Learning with Implicit Q-Learningcited by 1,245
  5. 2024OpenAI o1 System Cardcited by 1,220
  6. 2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
  7. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 69
  8. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  9. 2023Foundations of Reinforcement Learning and Interactive Decision Makingcited by 33
  10. 2024Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Modelscited by 16
  11. 2024A Reductions Approach to Risk-Sensitive Reinforcement Learning with Optimized Certainty Equivalentscited by 15
  12. 2020Maximum Reward Formulation In Reinforcement Learningcited by 10
8 more
  1. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  2. 2024To the Max: Reinventing Reward in Reinforcement Learningcited by 7
  3. 2024Directed Exploration in Reinforcement Learning from Linear Temporal Logiccited by 7
  4. 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limitscited by 7
  5. 2025Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedbackcited by 6
  6. 2020Planning with Submodular Objective Functionscited by 5
  7. 2024The Role of Inherent Bellman Error in Offline Reinforcement Learning with Linear Function Approximationcited by 4
  8. 2025Risk-sensitive Reinforcement Learning Based on Convex Scoring Functionscited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2023Harnessing Mixed Offline Reinforcement Learning Datasets via Trajectory Weighting
  2. 2024In-Dataset Trajectory Return Regularization for Offline Preference-based Reinforcement Learning
  3. 2022Semi-Supervised Offline Reinforcement Learning with Action-Free Trajectories
  4. 2023Beyond Uniform Sampling: Offline Reinforcement Learning with Imbalanced Datasets
  5. 2021Representation Matters: Offline Pretraining for Sequential Decision Making
  6. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward
  7. 2023Reward-Consistent Dynamics Models are Strongly Generalizable for Offline Reinforcement Learning
  8. 2026TOUR: A Trajectory-Level Unlearning Benchmark for Offline Reinforcement Learning