acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Offline reinforcement learning is typically analyzed under process-level reward supervision, yet many sequential decision datasets record only trajectory-level outcomes, such as task success, a final score, or a human preference between two trajectories. We develop a statistical theory of offline policy optimization from such feedback. For the cumulative-reward objective with one scalar outcome label per trajectory, we propose OPAC, a pessimistic actor-critic algorithm that learns a latent per-step reward together with the critic. OPAC finds an -optimal policy from trajectories under single-policy concentrability , and we prove a matching lower bound, characterizing the statistical cost of replacing process-level rewards with one trajectory-level label. The approach extends to pairwise trajectory preferences with comparable guarantees. We then study nonlinear aggregations of per-step rewards that serve as both the supervision and the objective. Here efficiency is not guaranteed: all-success outcomes can require exponentially many trajectories even with deterministic transitions and constant coverage. For structured aggregations affine in the continuation value, which admit Bellman-style dynamic programming, we identify two coefficients that quantify the information lost in outcome aggregation and Bellman updates, and show that generalized OPAC is sample-efficient when both are polynomially bounded.

Primary area:
reinforcement learning
Keywords:
Offline Reinforcement Learning, Trajectory-Level Supervision, Finite Sample Complexity

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_aJumOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies offline reinforcement learning with trajectory-level supervision instead of per-step rewards. It proposes OPAC, which jointly learns a reward model and a pessimistic critic before updating the policy. For additive returns, it establishes an upper bound under single-policy state-action coverage and a lower bound matching the explicit horizon and coverage dependence, up to function-class complexity factors. It also extends the analysis to preferences and studies nonlinear returns through an exponential hardness example and two conditioning coefficients.

Critical strengths
  1. The paper clarifies trajectory-level labels can support offline policy optimization under single-policy state-action coverage.

  2. The nonlinear analysis highlights that supervision granularity interacts strongly with the return objective.

Critical weaknesses
  1. Theorem 9 combines reward-class closure, uniform Bellman completeness, and a product critic class. These requirements can conflict even in a two-step multiplicative setting: if the maximum first-stage critic value is (M>0M>0) and continuation values include (0<vL<vU0<v_L<v_U), closure requires a reward (M/vLM/v_L), while exact completeness requires representing (MvU/vL>MMv_U/v_L>M). This raises concerns about the scope of the generalized guarantee.

  2. The contributions is concentrated on the theory analysis. The novelty of the proposed algorithm is limited in my opinion. Also, I think the performance of this algorithm may be not very good due to the joint optimization.

Questions for authors
  1. Could the authors also make the function-class complexity dependence explicit when comparing the additive upper and lower bounds?

  2. Could the authors work through one concrete scenario to explain how the formal assumptions apply and what actionable insight the theoretical results provide?

Reviewer_mMTBOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

In this manuscript, the authors studies the process-reward offline RL, in which setting is quite different from conventional step-reward RL. The authors studies several scenarios: including scalar outcome, pairwise preference and generalized objective. The authors propose the OPAC solution, a pessimistic actor‑critic which jointly learns latent step‑wise reward and critic. The authors further provide the upper bound and proves matching lower bound.

Critical strengths
  • The studied problem is interesting and practical. Many real‑world settings including LLM alignment, complex searching tasks have such scenarios, and it is common to see in practical situations.

  • The theoretical analysis are comprehensive, and the authors consider the cumulative‑return setting, pairwise‑preference supervision and nonlinear aggregation objectives.

  • The pessimistic actor‑critic OPAC method is appealing. It does not force exact recovery of ground‑truth step‑wise reward and only constrains return loss on trajectory level.

Critical weaknesses
  • This theoretical work is somehow not easy to understand. The problem is straightforward, however, the solution is not easy to follow.

  • All upper bounds and concentration inequalities apply finite‑set bounds. However, neural networks belong to infinite function classes. The theoretical results may not hold in practice.

  • Preferences are assumed to strictly follow BTL model. Real human preferences often violate BTL transitivity. Degradation guarantees under model misspecification are missing.

Questions for authors
  • The manuscript is a purly theoretical work, and there is no numerical/empirical studies. It is suggested to include some empirical studies demonstrating the effectiveness of the proposed method.

  • Discussion on nosiy outcome labels are suggested. Scalar outcomes are conditionally unbiased observations in theory. Real‑world trajectory labels suffer from systematic bias and label noise. Performance bounds under biased outcome supervision are missing.

  • Consequences of BTL preference model misspecification are not analyzed. It is unknown whether original sample‑complexity bounds survive when human preferences violate BTL.

1 comment

Dear Reviewer mMTB,

As the rebuttal period nears its end, we wanted to share a short update.

Following our discussion with Reviewer aJum, we added neural-network experiments in Appendix B.2.

All methods train on the same 2,000 complete, 1,000-step trajectories from simulated OGBench PointMaze-Medium, with only one outcome label per trajectory. We report cumulative 1,000-step returns: each seed's score averages five goal tasks and three fixed checkpoints, and the table gives the mean and sample SD across two training seeds. Higher is better.

MethodCumulative return
OPAC876.30 ± 2.85
Reward regression + ATAC (two-stage)864.11 ± 1.45
RRD-style + ATAC836.84 ± 46.01
Reward regression + IQL815.18 ± 49.84
OPAC without pessimism757.26 ± 101.19
Equal credit + ATAC560.45 ± 94.23

OPAC has the highest aggregate mean among the tested methods, including the two-stage baseline using the same actor–critic. These results support joint learning with neural networks in this setting. Appendix B.2 describes the methods and exploratory simulator tuning.

For the concerns in your review:

  • Presentation: We added an explanatory example (Section 3.1) and simplified the generalized proof.
  • Experiments: Appendix B now includes tabular simulations and neural-network experiments on PointMaze to test OPAC's effectiveness.
  • Infinite classes: We extended Theorem 1 through covering numbers, keeping its other assumptions (Appendix L.1).
  • Label noise and bias: Unbiased noise is already allowed; we quantified the extra error from systematic bias (Appendix L.2).
  • BTL misspecification: We bounded the extra error from misspecified preferences, relative to a reference reward (Appendix L.3).

Please let us know if any concerns remain. We hope you will reconsider your assessment in light of these revisions and results.

Thank you for your time and consideration.

Best regards,
The Authors

Reviewer_Jdf2OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies offline RL with trajectory-level feedback, where rewards at individual steps are not observed. For cumulative returns, the authors propose OPAC, which combines latent reward estimation with pessimistic policy evaluation without requiring the true per-step rewards to be identified. Under realizability, completeness, and single-policy coverage assumptions, they obtain upper and lower bounds with matching dependence on the horizon, coverage, and accuracy, up to logarithmic and function-class complexity factors. The approach is also extended to pairwise preferences. For nonlinear trajectory objectives, the results are quite different. An all-success objective can require exponentially many samples even with constant state-action coverage. The authors also provide sufficient conditions for polynomial sample complexity for certain structured objectives, using two coefficients that measure different sources of information loss. The paper is theoretical, with proofs and explicit constructions supporting its main results.

Critical strengths
  1. For cumulative returns, the authors give both an upper bound for OPAC and a lower bound with the same dependence on the horizon, coverage, and accuracy, up to logarithmic factors. The analysis also does not require recovering individual step rewards from trajectory outcomes, which may not uniquely identify them. I see this as the main strength of the paper.

  2. The all-success lower bound shows that constant state–action coverage does not rule out exponential sample complexity. The generalized analysis further separates information loss from trajectory aggregation and Bellman updates, with examples showing that the two coefficients are incomparable. This provides useful insight into the difficulty of learning from nonlinear trajectory objectives.

Critical weaknesses
  1. The lower bound for cumulative returns uses labels of the form Y=HBernoulli⁡(p)Y=H\operatorname{Bernoulli}(p), with conditional variance of order H2H^2. This is allowed by the model, but it is not clear whether the same H4H^4 dependence would hold if exact trajectory returns were observed. The result therefore does not fully distinguish the difficulty caused by missing stepwise rewards from that caused by noisy outcome labels.
  2. It is not clear how broadly Theorem 9 applies. Besides realizability and completeness, Assumption 4 requires that every policy–critic pair be exactly Bellman-consistent under some reward in the candidate class. The appendix examines the two information-loss coefficients in several examples, but none is shown to satisfy all the assumptions for a nontrivial nonlinear objective. This makes it difficult to assess the scope of the generalized upper bound.
Questions for authors
  1. The lower bound in Theorem 2 uses outcome labels with conditional variance of order H2H^2. Would the same H4H^4 dependence hold if the exact trajectory return were observed? The current construction does not seem to separate the effect of aggregation from the noise in the labels.

  2. Can the authors give a concrete nonlinear example satisfying all the assumptions of Theorem 9? Appendix H calculates the information-loss coefficients for several objectives, but does not verify closure and completeness for the corresponding reward and critic classes.

  3. The proof of Theorem 1 chooses β\beta based on Csa(π⋆)C_{\mathrm{sa}}(\pi^\star), which is generally unknown in offline RL. Is this an oracle-tuned guarantee, or can β\beta be chosen without knowing this quantity? Does the tuning in Theorem 9 similarly require knowledge of the information-loss coefficients?

2 comments

Dear Reviewer Jdf2,

As the rebuttal period is coming to a close, we wanted to briefly recap our responses:

  • Label noise: We clarified how noise affects the lower bound and what remains unresolved for exact returns.
  • Nonlinear assumptions: We removed closure and verified all remaining assumptions in a concrete nonlinear example (Appendix I).
  • Parameter choice: We added a constrained variant whose thresholds do not require the unknown coverage or information-loss coefficients (Appendix K).

Please let us know whether these responses address your concerns or if any questions remain. We would be happy to clarify.

Thank you for your time and consideration.

Best regards,
The Authors

Thank you for the detailed responses. The points I raised have been sufficiently clarified, and I have no further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.