- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
Authors consider offline RL with only outcome rewards measured, under non-Markovian loggers. They identify conditions for policy evaluation at the population level, since this cannot necessarily be uniquely done. They identify a case where a non-Markovian logger has good marginal coverage but learning is impossible; learning from such data is actually governed by the visitation norm in the geometry of its covariance, ; this can be related to standard coverage in terms of their quantity, . Authors’ Algorithm 2 is a pessimism-based learner that takes the worst-case plausible linear fit for the reward function, and then plans based on that reward; it enjoys minimax sample complexity as a function of and other problem parameters.
Critical strengths
Both non-Markovian logging procedures and outcome-only rewards are important in practice. Although elementary, the counterexample serves to highlight how these can interact negatively in the worst case. The lower bound constructions are nontrivial and, to my knowledge, new. Although the work covers only tabular MDPs, the methodology seems like it could be extended to linear MDPs, and their Appendix provides work in this direction.
Critical weaknesses
Because the work’s primary contribution is to handle the conjunction of outcome only rewards with non-Markov loggers, this work appears quite incremental. In particular, the outcome-only setting has already been extensively covered with related techniques [1, 2] (both cited by them).
Although the analysis for non-Markovian loggers is technically new, Algorithm 2 is of limited novelty compared to [1]. The upper bound analysis does not appear to be substantially novel. That said, the lower bound analysis appears more novel.
can depend on and across examples; or be large independently of all of these (due to the logger). This makes it hard to give it an appealing interpretation in terms of qualitative aspects of the MDP/logger. Are there classes of problem instances where admits insightful upper bounds, or can be said to be independent of certain problem quantities?
The writing/exposition quality of this paper is poor. As mentioned in their AI Use Statement, AI was used for writing the manuscript, and the text itself does not feel very human-friendly.
[1] Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective, Jia et al 2025. [2]Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward, Xu et al 2022.
Questions for authors
See weaknesses
3 comments
Concern 3: Contribution of the upper-bound analysis
We agree that the upper-bound proof uses familiar tools, including confidence-set pessimism, linear estimation, and Cauchy–Schwarz. Its purpose is not to introduce a new concentration technique, but to establish achievability under the information conditions identified in Section 3.
The important distinction is that the analysis works directly with the optimal policy’s outcome-information coefficient . It uses a trajectory-level representer whose second moment equals , rather than relying on a change-of-measure bound through one-step state–action coverage. This allows the guarantee to hold even when the logger is history-dependent and the trajectory covariance is singular.
The upper bound also separates the effects of outcome noise and missing exposure. The regret scales, up to logarithmic factors, with and . Theorem 5.1 shows that both contributions are necessary in the stated even-horizon, non-clipped tabular minimax class, including the missing-exposure difficulty that remains when the outcome noise is zero.
Thus, the role of the upper bound is to show that the information difficulty characterized by our lower bounds is achievable, completing the minimax characterization. We also clarify that avoiding global spectral burn-in distinguishes our analysis from eigenvalue-based approaches such as PARTED, but not from the burn-in-free guarantees of Jia et al. or Ren and Xie under their respective assumptions.
Concern 4: Interpretation and structural bounds for the coverage coefficients
We agree that the coefficients are more useful when we can relate them to recognizable properties of the logger and the problem, rather than treating them as abstract matrix quantities.
The coefficient measures how much information the logged trajectory outcomes contain about a particular policy's value. Proposition 2.1 gives a statistical interpretation: it is the minimum second moment of a trajectory reweighting that reconstructs the target occupancy. A large means that the reward combinations needed to evaluate the target are poorly represented in the logged outcomes, even if individual state–action pairs are frequently observed.
The memory factor describes a different effect. It compares a history-dependent logger with a Markov logger having identical one-step occupancies, and measures how much their trajectory-level information can differ. For Markov loggers, and Theorem 3.3 recovers the familiar marginal-coverage bound.
We also provide several examples showing when these quantities have simpler interpretations:
- Dependence on logging behavior: In the two-step XOR family, while standard coverage remains 2. The difficulty is determined by how rarely the logger produces the relevant action combinations, rather than by the problem dimension.
- Dependence on horizon: The temporal XOR construction gives , whereas the temporal-gating family keeps fixed as increases. Thus, horizon dependence is not inevitable.
- Dependence on dimension: The neutral-padded construction in Appendix E shows that learning difficulty can depend on the number of active reward directions rather than the ambient dimension, under the stated structural assumptions.
We additionally examined a natural sticky logger that tends to repeat its previous action. In the numerical experiments in Appendix H, grows slowly with the horizon and approaches a finite level determined by the switching probability over the tested range . We do not claim a horizon-independent theorem for this family.
Finally, these effects are target-specific. Figure 18 shows that logging memory can even improve the outcome information for a particular target, despite a diverging global memory factor. This motivates the refined coefficient in Proposition C.7.
Together, these results explain why cannot generally be bounded by problem size alone, while identifying several structured settings in which its dependence on logging behavior, horizon, or dimension can be characterized.
Concern 5: Writing and exposition
We understand the reviewer’s concern about the readability of the original manuscript. One of its main problems was that the mathematical results were presented before the reader had enough intuition for why they were needed. We have substantially revised the paper to address this.
The Introduction now develops the study through a sequence of questions, using the two-stage XOR example to explain why outcome-only feedback and logging memory create an information problem that standard coverage may not capture. Section 2 motivates the trajectory second-moment matrix directly from the observation model, and Sections 3–5 explain the role of each theorem before presenting its formal statement. We have also added short proof intuitions, clarified the distinction between classical tools and new contributions, and included a notation table and an appendix guide.
We hope the revised Introduction and main results are easier to follow, and we would appreciate any further feedback on passages that remain unclear.
Thank you for recognizing that the lower-bound constructions are nontrivial and new, and for acknowledging the practical relevance of both non-Markov logging and outcome-only feedback. We appreciate the careful assessment of the remaining novelty and interpretation questions.
Concern 1: Novelty beyond existing outcome-only RL results
Our contribution is not the introduction of outcome-only feedback itself, but showing that allowing the logger to depend on past decisions changes what can be learned from such feedback.
This distinction is illustrated by the two-stage XOR example in Theorem 3.2. Even though every action is observed equally often at each stage and standard state–action coverage is bounded by 2, two reward functions can generate exactly the same logged outcomes while requiring opposite optimal policies. Consequently, every learner incurs nonvanishing worst-case regret, regardless of the number of logged episodes.
This matters for prior guarantees. The change-of-trajectory-measure argument of Jia et al. [1], also used in related work, relies on the Markov structure of the data-collecting policy. Our construction shows why a guarantee depending only on marginal coverage cannot be extended to arbitrary history-dependent logging. PARTED [2] takes a different approach, requiring trajectory-level and per-step feature coverage. In the canonical tabular one-hot representation, its trajectory-level eigenvalue condition cannot hold for H≥2 because of structural null directions (Proposition C.9). This is a separate limitation of that representation, rather than a consequence of logging memory.
We then go beyond the impossibility example. Theorem 3.3 quantifies the effect of memory through κmem, and Corollary E.3 establishes that this dependence is necessary in general. Theorem 4.2 gives an achievable learning guarantee under general history-dependent logging, while Theorem 5.1 establishes the matching minimax rate for the specified tabular class.
We therefore view the contribution as identifying a limitation of existing coverage-based learning guarantees, explaining the additional information cost, and characterizing what can still be achieved under history-dependent logging.
Concern 2: Novelty of Algorithm 2
We agree that Algorithm 2 builds on an established pessimistic learning principle, as also used by Jia et al. [1, Appendix B, Algorithm 2/Theorem 11]. Our approach adapts this principle by constructing a projected, box-constrained confidence set directly over the additive reward vector, leading to a tractable formulation with polynomial-time optimization through a second-order cone programming oracle (Theorem D.11). More importantly, this formulation supports a learning guarantee for general history-dependent loggers. Rather than relying on Markov state–action concentrability to control trajectory-level uncertainty, our analysis works directly with the exact outcome coefficient Cout of an optimal policy. As Theorem 3.2 shows, this distinction matters because marginal coverage alone cannot guarantee learnability when the logger depends on history.
The assumptions also differ. Jia et al. allow unknown dynamics and provide a one-shot high-probability guarantee, whereas our main result assumes known dynamics and gives an expected-regret bound, with a high-probability variant obtained through block splitting.
We do not claim a new pessimism paradigm or superiority over the algorithm of [1]. Rather, Algorithm 2 provides a concrete, computationally tractable approach to achieving an outcome-information guarantee under the general logging setting studied here. We have clarified this distinction and added the comparison with Jia et al. in the revised Introduction and Table 1.