acceptodds
Under review as a conference paper at ICLR 2027

REVEALING AFTER OVERWRITING: AN EXPONENTIAL POMDP OPE LOWER BOUND UNDER HISTORY-DEPENDENT LOGGING

Abstract

Multi-step revealing can make off-policy evaluation tractable under memoryless logging. With history-dependent logging, state decodability and target-relevant evidence can separate. For every horizon , we construct two exactly realizable POMDPs with four actions, at most four states per layer, a known logger, and a memoryless target. Action overlap, history coverage, and observation-only revealing remain bounded independently of , yet the target values differ by and the KL divergence between the logged laws is , forcing exponential sample complexity. Logger memory makes states distinguishable, while reset erases the model-distinguishing evidence preserved by the target. A separate construction retains this barrier with common, known observation-only revealing operators. Under action and history coverage, we give a finite-class OPE guarantee using common observable value representations that remain valid at every history. The sample bound depends polynomially on their second-moment cost. In the common-operator construction, the same value direction has constant marginal decoding cost but exponential history-conditioned cost. Finally, on a fixed four-action continuum, we derive matching passive and budgeted readout rates. With one known channel and unit read cost, early reads are optimal. With unknown sensor bias, early reads alone remain exponentially costly. Combining them with post-reset calibration gives sample complexity independent of when both read types receive fixed positive expected budgets per trajectory.

Primary area:
reinforcement learning
Keywords:
Off-policy evaluation, Partially observable Markov decision processes, History-dependent logging, Multi-step revealing, Overwrite--reveal mismatch, Sample complexity

Reviews

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

This paper studies the limits of off-policy evaluation in partially observable Markov decision processes under history-dependent behavior policies. The paper shows that standard coverage and multi-step revealing conditions can hold while evaluation still requires exponentially many trajectories, even for a memoryless target, resolving an open question in prior work. it claims to show that revealing hidden states does not necessarily preserve the information needed to evaluate the target policy. The paper strengthens this impossibility result, establishes a sufficient condition for sample-efficient evaluation through history-conditioned value representations, and analyzes how additional measurements and sensor calibration can overcome the information barrier within a specified family of models.

Critical strengths
  1. The main lower bound addresses an open question under carefully controlled conditions. Theorem 1 establishes exponential sample complexity despite exact realizability, a known history-dependent logger, and constant state and action spaces per layer. The coverage and revealing coefficients remain bounded independently of the horizon. The rare-survival argument is clear. The coverage and revealing calculations substantiate the nontrivial part of the construction.

  2. The common-operator construction makes the distinction between revealing and evaluation convincing. Proposition 1 shows that the lower bound persists even when the two models share known observation-only revealing operators. Proposition 4 establishes an exponential separation between marginal and history-conditioned representation costs for the same scalar continuation value.

Critical weaknesses
  1. The general applicability and distinct contribution of the positive result are not sufficiently established. Theorem 2 relies on Eq. (19), which requires a single observable representation of each candidate's continuation value to remain conditionally correct under every generating model and every reachable history. This is stronger than the existence of a valid representation under the true model. Its feasibility also depends on the alignment of latent-state coordinates across candidates, although the observable evaluation problem is invariant to candidate-specific relabelings.

    For example, consider a two-step problem with a binary terminal state and observed reward R2=O2R_2=O_2. Let the first action induce state-one probabilities 1/4 and 3/4, respectively, in both models. Suppose O2=S2O_2=S_2 in one model and O2=1−S2O_2=1-S_2 in the other. Both states are possible after either first-action history. A common representation of the first candidate’s terminal value V2(s)=sV_2(s)=s would then have to assign incompatible values to the same observation under the two generating models. Nevertheless, the target value is readily estimable from observed terminal rewards with bounded first-action importance weights.

    The paper correctly presents Eq. (19) as sufficient, so this example does not contradict Theorem 2. It limits the interpretation of the representation cost as a general explanation of statistical difficulty. Moreover, memory-dependent future-value functions and conditional Bellman moments already appear in Uehara et al. (2023). The paper identifies differences in its assumptions and analysis, but a precise comparison showing when the new theorem provides a distinct tractability guarantee is missing.

  2. The recovery results are sharp within a restricted experiment, but add limited general guidance beyond the constructed family. Theorems 3–5 concern a specific seed-parameter family with the remaining kernels fixed, and the unknown-bias extension adds a single nuisance parameter. The restriction to at most one measurement per trajectory is particularly consequential. Under the stated sensor model, two conditionally independent early measurements of the same bit satisfy Cov(Y1,Y2∣K=k)=1/4pθ,k(1−pθ,k)Cov(Y_1,Y_2 | K=k) = 1/4 p_{\theta,k}(1-p_{\theta,k}), which is independent of the unknown additive sensor bias. For k=0k=0, pθ,0∈[0.2,0.3]p_{\theta,0}\in[0.2,0.3], so this covariance identifies the seed parameter. Taking two measurements only when the first action is c0c_0 has expected cost 2(1/8)=1/4 per trajectory.

    This alternative changes the permitted protocol and therefore does not invalidate the theorem. It shows that the role of post-reset calibration is specific to the single-read restriction. Appendix K.2 acknowledges this issue, but the broader statements about early measurements in the abstract and conclusion should be qualified accordingly. The restrictions of Theorem 2 is also a concern.

Questions for authors
  1. Is Eq. (19) assuming a meaningful correspondence between latent states across candidate models, beyond a common index set? How should the interpretation of $C_V consider its dependence on candidate-specific state relabelings? Please clarify whether this is an intended modeling restriction or whether the certificate should be considered over equivalent state alignments.

  2. Can the authors give a more precise comparison between Theorem 2 and the memory-dependent future-value framework of Uehara et al. (2023)? Do have a setting in which the proposed guarantee is polynomial while the earlier guarantee fails or becomes exponential?

  3. Do the authors agree that paired independent early measurements can identify the seed parameter through their covariance at a constant expected budget?

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

I've ask Claude to read the paper and explain to me. I did not understand much of it.

I looks solid. They proved a bunch of stuff related to the question "can a POMDM agent learn from the trajectories of another agent". H is the length of the trajectories and they prove things relating H with the number of trajectories we need to infer if another policy (agent) can do well or not.

Critical strengths

It's math and it has been backed up by AI, so I trust it. Also my Claude ran some independent numerical simulation and it was happy.

Critical weaknesses

I don't see any critical weakness

Questions for authors

I don't have any question.

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

The paper studies off-policy evaluation in POMDPs with history-dependent logging. It constructs small, realizable model pairs with uniformly bounded action coverage, history coverage, and marginal revealing coefficients, yet exponentially small divergence between their logged distributions and a constant target-value gap. The separation persists with common, known observation-only operators. The paper also establishes a finite-class upper bound using history-conditioned value representations and derives matching, family-specific sample-complexity rates for optional readouts and sensor calibration.

Critical strengths

The central distinction between marginal state decodability and preservation of target-relevant evidence is insightful. The lower bound is stronger than simply exhibiting rare informative trajectories: the construction simultaneously maintains bounded coverage and revealing coefficients, and the common-operator extension rules out uncertainty about the marginal decoder as the sole explanation. The exponential separation between marginal and history-conditioned representation costs for the same value direction further clarifies the mechanism. The readout analysis adds a constructive perspective, particularly the distinction between preserving evidence and calibrating the sensor needed to interpret it. Detailed proofs and reported exact-arithmetic checks strengthen the presentation.

Critical weaknesses
  1. Equation (19) imposes a strong cross-model requirement: each candidate’s value representation must remain conditionally calibrated under every generating model and every supported history. Beyond the constructed examples, structural conditions ensuring a manageable representation cost are unclear. The role of shared latent-state coordinates also deserves more explanation.

  2. The positive result provides a sufficient statistical condition, not a general tractability characterization or computationally efficient procedure. Checking the representation condition may require exponentially large programs, and the dependence on horizon and representation cost is not generally shown to be optimal. These limitations should be distinguished more prominently from the family-specific matching rates.

  3. The readout results rely on a restricted measurement model: one read per trajectory, an unchanged logger, known reset distributions, and a fixed sensor gain with a shared additive bias. The horizon-independent recovery guarantee is therefore family-specific; robustness to unknown gain, sensor drift, or measurement-dependent logging remains unresolved.

  4. The examples and simulations remain within the designed overwrite mechanism. They do not quantify sensitivity to imperfect overwriting or weak preterminal observations of the preserved bit. Such perturbations could introduce additional evidence outside the all-preserve event; analyzing them would clarify the range of settings in which the exponential bottleneck remains relevant.

  5. The uploaded submission does not discuss Jajoo (2026), which addresses the same open question using a smaller reset construction. The public preprint already acknowledges this concurrent work; that comparison should be incorporated into the reviewed version, clearly separating the overlapping hardness result from the common-operator, representation-cost, and calibration contributions.

Jajoo, P. (2026). Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging. arXiv:2609.19135.

Questions for authors
  1. How does the common-representation condition behave under independent relabelings of latent states across candidate models? Is a known cross-model alignment essential to Theorem 2?

  2. Can Theorem 2 accommodate approximate conditional calibration, with an explicit error term? Which dependencies on horizon, history coverage, and representation cost are believed to be tight?

  3. How do the lower bound and representation-cost separation change when resets only partially erase the bit, or hidden states provide a small amount of preterminal information?

  4. Which readout conclusions survive an unknown sensor gain or repeated measurements? Is the need for post-reset calibration specific to the single-read, fixed-gain protocol?

  5. Please clarify the contribution relative to Jajoo (2026) and incorporate the comparison already present in the public preprint. Given the broad AI-use disclosure, please also describe the independent verification undertaken for the central proofs.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.