When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?
Authors: name: Xuanfei Ren, name: Tengyang Xie
Organization: University of Wisconsin - Madison

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(H^2C_{sa(π^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 Ω(2^H)
  trajectories even with deterministic transitions and constant concentrability. We then identify a tractable regime through two
  structural coefficients, κ_μ(σ) and χ_μ(σ), 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.