OPAC: Offline RL from trajectory-level labels achieves near-optimal sample efficiency

A new paper by Xuanfei Ren and Tengyang Xie (UIUC) tackles a fundamental question in offline reinforcement learning: can we efficiently learn policies when we only observe a single outcome per trajectory (e.g., total reward or a win/loss label) instead of per-step rewards? The authors introduce OPAC (Outcome-based Pessimistic Actor-Critic), which learns a latent reward model from trajectory-level labels and then performs pessimistic policy optimization. They prove that OPAC achieves a sample complexity of Õ(H²√(Cₛₐ(π*)/n))—nearly matching the best known rates for per-step reward settings—and they provide a matching lower bound, showing the extra cost of using only one scalar label per trajectory is just a constant factor.

The paper goes further by extending the principle to preference-based feedback (e.g., pairwise comparisons between trajectories) and deriving similar guarantees. It then studies the hardest case: when both the supervision signal and the objective are nonlinear aggregations of per-step rewards (e.g., “all tasks completed” objectives). Here the authors prove a startling negative result: without additional structure, any offline learner may require Ω(2ᴴ) trajectories even with deterministic dynamics. However, they identify two structural coefficients—κ_μ (information loss in the outcome aggregation) and χ_μ (Bellman update gain)—that characterize when the problem becomes tractable. Under these conditions, a generalized version of OPAC achieves polynomial sample complexity. The work provides a sharp delineation of when trajectory-level supervision is sufficient for efficient offline RL and when missing per-step rewards create fundamental statistical barriers.