- 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
-
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.
-
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
-
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 . Let the first action induce state-one probabilities 1/4 and 3/4, respectively, in both models. Suppose in one model and in the other. Both states are possible after either first-action history. A common representation of the first candidate’s terminal value 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.
-
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 , which is independent of the unknown additive sensor bias. For , , so this covariance identifies the seed parameter. Taking two measurements only when the first action is 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
-
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.
-
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?
-
Do the authors agree that paired independent early measurements can identify the seed parameter through their covariance at a constant expected budget?