acceptodds
Under review as a conference paper at ICLR 2027

Offline Policy Learning from Outcome-Only Feedback: Identification and the Price of Logging Memory

Abstract

We study offline reinforcement learning when each logged episode records the full trajectory but only one noisy scalar outcome, with no per-step rewards. Under history-dependent logging, state–action coverage alone may not determine whether a target policy can be evaluated, because the data reveal rewards only through sums along logged trajectories. With known dynamics, we show that a policy value is identified when its occupancy lies in the span of logged trajectory features; for interior tabular rewards, this condition is also necessary, and when point identification fails the value admits a sharp identified interval. The coefficient is the exact additive change-of-measure constant and quantifies finite-sample difficulty. History-dependent logging separates this trajectory geometry from ordinary state–action coverage. Two loggers can have identical one-step occupancies while combining those visits into different trajectories, changing both identification and . We quantify this effect through an order-necessary distortion factor and a target-specific refinement . With known dynamics, we propose a projected, box-constrained pessimistic learner whose expected regret depends on of an optimal policy without requiring a global minimum-eigenvalue threshold; block splitting gives a corresponding high-probability guarantee. On a temporal direct-sum family, exactly, with complementary Gaussian and missing-exposure lower-bound mechanisms. For general even horizons, a parallel-state construction gives the minimax rate for the stated high-dimensional tabular class with under the non-clipping conditions. Matched-marginal experiments on compiler-derived additive geometry and at the Markov logging boundary confirm that changing cross-time dependence changes outcome geometry and learning difficulty.

Primary area:
reinforcement learning
Keywords:
offline reinforcement learning, trajectory-level supervision, partial identification, history-dependent logging, pessimistic learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_bcZXOpenReview ↗
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, CoutC_\mathrm{out}; this can be related to standard coverage in terms of their quantity, κ(μ)\kappa(\mu). 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 CoutC_\mathrm{out} 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.

κ(μ)\kappa(\mu) can depend on H,SH, S and AA 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 κ\kappa 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

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≥2H\ge 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\kappa_{\mathrm{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 CoutC_{\mathrm{out}} 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.

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 CoutC_{\mathrm{out}}. It uses a trajectory-level representer whose second moment equals CoutC_{\mathrm{out}}, 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 σdC/n\sigma\sqrt{dC/n} and dHC/n\sqrt{dHC/n}. 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 CoutC_{\mathrm{out}} 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 CoutC_{\mathrm{out}} 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 κmem\kappa_{\mathrm{mem}} 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, κmem=1\kappa_{\mathrm{mem}}=1 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, Cout=1+1/εC_{\mathrm{out}}=1+1/\varepsilon 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 Cout−1=HκmemC_{\mathrm{out}}-1=H\kappa_{\mathrm{mem}}, whereas the temporal-gating family keeps Cout=CC_{\mathrm{out}}=C fixed as HH 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, κmem\kappa_{\mathrm{mem}} grows slowly with the horizon and approaches a finite level determined by the switching probability over the tested range H≤16H\le16. 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 κrep\kappa_{\mathrm{rep}} in Proposition C.7.

Together, these results explain why CoutC_{\mathrm{out}} 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.

Reviewer_AguZOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper explores offline RL from outcome-only feedback, where every logged episode records the full trajectory but only one noisy scalar outcome, and the logger can be history dependent within an episode. The paper shows that a policy’s value can be identified when its occupancy lies in the span of the logged trajectory features, and otherwise gives an interval for the value. They also show that two loggers with same one step occupancies can have different outcome coefficient and the difference is measured by a memory factor, which compares the logger to a Markov logger with the same occupancies. The work purposes a pessimistic algorithm whose regret depends on the outcome coefficient of an optimal policy, and does not need a burn in condition. It also gives a minimal rate on a constructed class. The claims are tested on synthetic XOR examples and gcc compiler data.

Critical strengths

The problem is well motivated and important, there is a very clear gap in the current trajectory feedback literature which assumes Markov logging. The XOR example shows this as well, that the one step coverage is fine but the value can still not be identified. The paper proposes an algorithm which does not need the outcome coefficient or the memory factor as inputs, and also does not need a burn-in condition, and provide the necessary bounds. The theory seems correct, although I did not read the appendix thoroughly. The authors elaborate on the limitations, and also provide the necessary info to reproduce the experiments.

Critical weaknesses

w1: The contributions do not seem sufficiently novel, the identification results mostly follow from classical linear model theory, (the authors cite Elfving Pukelsheim). The novelty seems to limited to the history dependent logging part mainly.

w2: The price of logger memory depends on the chosen representation, and if the logger memory is added to the state, the logger becomes Markov. In this case the outcome coefficient does not change, and only the one step coverage changes, so the gap between them depends a bit on the representation. Since this gap is one of the main claims of the paper, it should be discussed more clearly.

w3: The paper is quite dense to read, would benefit from a notation table, and a more concise appendix.

Questions for authors

q1: Can you elaborate a bit more on the exact novelty of the paper? q2: see w2. q3: Do the experiments show the burn-in-free advantage? All the methods in Fig 13 seem to have near zero regret.

2 comments

Thank you for recognizing the importance of the problem and the gap between existing Markov-logging analyses and more general data collection. We appreciate the specific questions, which helped us clarify the scope of our contributions and strengthen the revised manuscript.

Q1: What exactly is novel?

The main novelty of our work is in understanding what changes when trajectory-level outcomes are collected by a history-dependent logger, rather than a Markov behavior policy.

The key distinction is that good state–action coverage may no longer imply that policy learning is possible. This is illustrated by the two-stage XOR example in Theorem 3.2, where the logger has uniform action marginals, yet two reward functions produce identical logged outcomes while requiring opposite optimal policies. As a result, no learner can distinguish these reward functions, even with unlimited data. This shows why marginal-coverage guarantees developed for Markov logging cannot be directly extended to general history-dependent logging.

Our subsequent results address what happens beyond this impossibility example. Theorem 3.3 quantifies the effect of logging memory through κmem\kappa_{\mathrm{mem}}, while Corollary E.3 shows that the dependence on this factor is unavoidable in general. Theorem 4.2 establishes that learning is still possible when an optimal policy has finite outcome coverage CoutC_{\mathrm{out}}, without a global eigenvalue condition. Finally, Theorem 5.1 characterizes the minimax rate in the stated tabular class, matching the noise-driven and missing-exposure terms of the upper bound.

We agree that the linear-span identification criterion and its pseudoinverse characterization are classical, as are the basic tools of pessimistic optimization. Existing work, including Jia et al. and Ren and Xie, also provides burn-in-free guarantees under Markov logging. We have clarified these connections in the revised Introduction and related-work comparison.

Thus, our contribution is not a new linear-estimation technique or a new pessimism paradigm. It is the characterization of how history-dependent logging changes learnability, how much information can be lost, and what statistical guarantees remain achievable.

Q2: Representation dependence and state augmentation

You are right that the effect of logging memory depends on the chosen state representation. If the logger's relevant memory is observed and included in the state, the logger becomes Markov in the augmented representation, and the explicit memory factor κmem\kappa_{\mathrm{mem}} becomes 1.

However, this does not mean that state augmentation makes the underlying outcome-information problem disappear. When we preserve the original additive reward class, observed trajectory-outcome law, and target value, augmentation does not provide any additional observations, and CoutC_{\mathrm{out}} remains unchanged. What changes is the one-step coverage certificate, which may become much more conservative.

To examine this directly, we added an exact population analysis using the XOR and flag-budget loggers. The results are reported in Section 6 (Table 3), with details in Appendix H.

For the flag-budget logger, the original CoutC_{\mathrm{out}} is 8.222 for two-flag targets and 9.778 for three-flag targets, while their augmented one-step bounds range from 17.625 to 143.428 and from 20.292 to 282.200, respectively. More strikingly, for the four-flag target, the augmented bound is infinite even though CoutC_{\mathrm{out}} remains finite at 18.296.

The reason is that augmented marginal coverage must account for detailed memory states, whereas identifying the value of an additive policy may only require information about reward combinations already present in other logged trajectories.

We therefore agree that κmem\kappa_{\mathrm{mem}} and standard coverage are representation-dependent. Our point is narrower: augmenting the state can remove the explicit memory factor, but it need not produce a useful marginal-coverage certificate for the original outcome-learning problem.

Q3: Does the experiment demonstrate a burn-in-free advantage?

The original Figure 13 (Figure 11 in the revision) was designed to illustrate the applicability of the theoretical guarantee, rather than to compare empirical performance. As an irrelevant direction in the logged data becomes increasingly rare, the sufficient sample-size threshold for the ridge population guarantee grows from 556 to nearly 100,000 episodes. Meanwhile, the optimal policy's CoutC_{\mathrm{out}} remains between 2 and 3, so Theorem 4.2 continues to apply. Importantly, failing to satisfy a sufficient condition does not imply that ridge must perform poorly, which explains why all methods achieve nearly zero regret in this experiment. We have made this distinction explicit in the revision.

To investigate empirical differences, we added experiments in settings where regret is not already close to zero (Figures 12–13). We compared projected pessimism (Algorithm 2), ridge pessimism (Algorithm 1), and plug-in least squares on the same datasets, including different ridge regularization parameters.

In the 12-MDP family (Figure 13), Algorithm 2 has lower interquartile-mean (IQM) regret than the primary ridge-pessimistic baseline (λ=1\lambda=1) at all seven tested sample sizes. At n=125n=125, the IQM regrets are 0.294 for Algorithm 2, 0.426 for ridge, and 0.014 for plug-in least squares. The paired Algorithm-2-minus-ridge difference is −0.132-0.132 (95% bootstrap CI [−0.165,−0.095][-0.165,-0.095]). Smaller ridge regularization narrows the gap, while plug-in least squares performs better than both pessimistic methods across all seven sample sizes.

The broader XOR comparisons require numerical qualification. Across 53 primary paired comparisons, 49 confidence intervals favor Algorithm 2, but 26 of these differences—all in the XOR family of Figure 12—do not exceed the reported numerical solver gap. We do not treat those cases as solver-resolved improvements. Appendix H also reports 24 failures to obtain numerical certificates among 36,000 Algorithm 2 solves.

Our claim is therefore limited: Theorem 4.2 does not require global spectral burn-in, and Algorithm 2 improves on the tested primary ridge-pessimistic baseline in the 12-MDP experiments. This is not a claim of superiority over tuned ridge, plug-in least squares, or other estimators. In particular, a sufficient ridge proof condition being unmet does not imply that ridge must fail. We have made these distinctions explicit in Section 6 and the Limitations.

Additional weaknesses

Identification results. We agree that the span condition and pseudoinverse characterization follow from classical linear-model theory. Theorem 3.1 provides the identification framework for the subsequent results, rather than claiming a new mathematical estimability principle. As discussed in our response to Q1, the new findings concern the consequences of history-dependent logging for policy learnability, information distortion, and minimax difficulty. We have made this distinction explicit in the revised contribution list and related-work discussion.

Readability and appendix. Thank you for these suggestions. We substantially revised the main text to explain the questions motivating each result before presenting the mathematics. We also added a notation table (Table 4), an appendix guide, and a table mapping experiments to the results they illustrate (Table 5). Two appendices that were peripheral to the main contributions have been removed.

We have retained the full proofs and the additional experimental results, so the appendix remains substantial. Our aim was to make it easier to navigate and understand, rather than shorten it at the expense of important details.

Reviewer_ZLVNOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies offline RL where the offline dataset records the full trajectory and only one noisy scalar outcome.

The authors studied when policy-value identification is possible. With known dynamics, the authors propose a pessimistic algorithm with polynomial-time running time and regret bound which does not rely on global minimum eigenvalue condition.

Critical strengths

The paper studies an interesting setting where the offline dataset records only one noisy scalar outcome instead of all rewards. Such setting could be of practical interest compared to existing offline RL settings.

Critical weaknesses

The paper was written in an extremely poor way.

In the introduction, the authors introduce the outcome-only feedback setting, without any justification why such a setting deserves to be studied. Then, the authors claim that we should study the second moment of logged trajectory features, again without any justification. After that, a list new results in this setting are given, none which are motivated in a satisfying manner.

The technical parts are also poorly written. For example, at the beginning of Section 2, the authors say ``finite-horizon MDP with known (P,ρ), horizon H, and tabular reward r ∈ [0,1]^d, d= HSA.''. What are the definitions of P and ρ? Why d= HSA?

In short, the writing quality of the paper is not satifying, and it clearly does not meet the bar of ICLR.

Questions for authors

See weaknesses above.

1 comment

Thank you for recognizing the practical interest of the outcome-only setting and for your detailed feedback. We agree that the original presentation made the paper harder to follow than it needed to be. We have substantially revised the manuscript to address these issues.

Motivation and overall structure. We reorganized the Introduction around the questions that motivate our study, starting from what can be learned when only a single outcome is observed for each trajectory, and then explaining why seemingly sufficient state–action coverage may still fail to support policy learning. For example, suppose a logger only records action sequences (a,a)(a,a) and (b,b)(b,b). Although both actions are observed equally often at each stage, their total outcomes may not tell us which crossing sequence, (a,b)(a,b) or (b,a)(b,a), is better. This illustrates why outcome-only feedback can make policy learning impossible despite apparently good state–action coverage. We now use these questions to motivate the analysis and guide readers through the subsequent results, rather than introducing the mathematical results without first explaining the problems they address.

Regarding the specific points raised in your review:

Why trajectory second moments matter. We revised Section 2 to explain where the central information quantity comes from. Each observed outcome is a noisy sum of rewards along a trajectory. Therefore, what matters is not only how frequently each state–action pair is visited, but also which visits occur together. The trajectory second-moment matrix captures these relationships, whereas one-step coverage alone does not. We now explain this distinction before introducing the identification and coverage results.

Connecting the results. The revised Sections 3–5 follow a more explicit progression: when a policy value can be identified (Theorem 3.1), why marginal coverage may still fail to guarantee learning (Theorem 3.2), how logging memory changes the available information (Theorem 3.3), and what learning guarantees and statistical limits follow (Theorems 4.2 and 5.1). We have also added short proof intuitions to help readers understand the role of each result without having to consult the appendix immediately.

Notation and appendices. We moved the definitions of PP, ρ\rho, and d=HSAd=HSA into Section 2, added a notation table (Table 4), and reorganized the appendices with a short guide to their contents.

We hope these changes make the main argument easier to follow. We would particularly appreciate your feedback on whether the revised Introduction and Sections 2–3 address the difficulties you encountered in the original submission.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.