View PDF HTML (experimental)

Abstract: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^2\sqrt{C_{sa}(\pi^\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(2^H)$
trajectories even with deterministic transitions and constant concentrability. We then identify a tractable regime through two
structural coefficients, $\kappa_\mu(\sigma)$ and $\chi_\mu(\sigma)$, 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.

Submission history

From: Xuanfei Ren [view email]
[v1] Tue, 16 Jun 2026 22:55:45 UTC (68 KB)