PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging

Pranaya Jajoo

arXiv:2609.19135v1cs.LG

TL;DR

In partially observable off-policy evaluation, it is unclear whether coverage and observability conditions on a small state space suffice when the logger depends on history. The paper constructs two candidate POMDPs with a common history-dependent logger and reduces their logged data to an exact statistical experiment with a matching optimal estimator. For H ≥ 3 and 0 < δ ≤ 1/4, every (1/8, δ)-accurate estimator requires Θ((3/2)^H log(1/δ)) episodes.

  • Problem

    In partially observable off-policy evaluation, it is unclear whether coverage and observability conditions on a small state space suffice when the logger depends on history.

    Source: §1 · p. 1

  • Method

    The paper constructs two candidate POMDPs with a common history-dependent logger and reduces their logged data to an exact statistical experiment with a matching optimal estimator.

    Source: §1 · p. 1

  • Results

    For H ≥ 3 and 0 < δ ≤ 1/4, every (1/8, δ)-accurate estimator requires Θ((3/2)^H log(1/δ)) episodes.

    Source: §4 · p. 5

  • Takeaways & Limitations

    The construction separates state coverage from the information needed to evaluate a target policy, and positive guarantees need additional structure tying logger continuation to actual history.

    Source: §8 · p. 8

    The lower bound rules out the specified behavior-marginal guarantees, without characterizing all tractable POMDPs.

    Source: §8 · p. 8

Abstract

from arXiv · show

Can a logged dataset visit every hidden state frequently and still be exponentially uninformative about a target policy's value? We show that it can when the logger depends on history. For every horizon $H \ge 3$, we construct two POMDPs with at most two latent states per stage, three actions, and a common logger with three memory states. Action coverage, belief coverage, and two behavior-marginal outcome-revealing conditions all have constants independent of $H$. Nevertheless, evaluating a known deterministic target policy to accuracy $1/8$ requires $\Theta((3/2)^H \log(1/\delta))$ logged episodes at confidence $1-\delta$, for $0 < \delta \le 1/4$, even when both candidate models are known. The mechanism is simple: a reset erases the unknown transition that determines the target value. We characterize the resulting statistical experiment exactly and obtain a matching optimal estimator. A directed two-lane gridworld realizes the construction, and trajectory simulations agree with its finite-sample prediction. The result establishes intractability for the history-dependent-logging, model-based case posed by Zhang and Jiang (2025, arXiv:2503.01134), under their behavior-marginal definition of revealing.

1 Introduction

The paper asks whether coverage and observability can suffice for off-policy evaluation when the logger depends on history. It constructs an example where those conditions hold but the data remain exponentially uninformative about the target value.

1 Introduction

  • Strong coverage and revealing conditions can hold while the data are exponentially uninformative about the target value.The construction separates predicting the current state from identifying an earlier transition parameter.Source: §1 · p. 1
  • A gate resets the hidden lane, making the current state predictable from logger actions while erasing the initial transition that determines the never-resetting target’s return.The target always continues, unlike the logger’s resetting paths.Source: §1 · p. 1
  • The construction has constant coverage and revealing bounds, and an exact statistical reduction gives a matching optimal estimator and sample lower bound.Gridworld simulations reproduce the reduction’s finite-sample error.Source: §1 · p. 1
  • The result addresses Zhang and Jiang’s (2025) open model-based, history-dependent-behavior, multi-step-revealing case; it varies the environment and allows unrestricted target-policy queries.The stated lower bound concerns fixed offline data and behavior-marginal revealing, not stronger history-conditional observability or active interaction.Source: §1 · pp. 1–2

2 A two-lane construction

The construction uses two visually identical corridors whose hidden lane can be reset by gates. A common history-dependent logger sometimes erases the model difference, while the target always continues and retains it.

2.1 Two candidate environments

  • The two-lane gridworld has identical-looking corridors; the candidate models differ only in the first continue transition, and later gates reset the lane.The final noisy reward depends on the lane, while observations before termination are fixed blanks.Source: §2 · p. 2, §2.1 · p. 2

2.2 A common logger with three memory labels

  • The common logger uses three memory labels: I before a reset, then the value of the latest reset, with action probabilities conditioned on that label.It chooses each action with probability 1/3 initially, uses an independent uniform action at H, and does not depend on the model or hidden state.Source: §2.2 · p. 2
  • The target always continues, preserving bit θ and yielding JMθ(πe) = 1/4 + θ/2; a logged episode is informative about the initial transition only if it continues at every step.After a gate, the latest gate determines the lane and subsequent observations have the same distribution under both candidates.Source: §2.2 · pp. 2–3

3 Setup and coverage conditions

The setup defines finite-horizon POMDP off-policy evaluation from complete trajectories logged by a known behavior policy. Its coverage and revealing conditions concern physical states and logged futures, with revealing defined by averaging over logger histories conditional on state.

3 Setup and coverage conditions

  • A layered finite-horizon POMDP has hidden states, observations, actions, known observation-based rewards, and transition kernels before the final stage.Policies may depend on observable history and current observation, while a memoryless policy depends only on stage and observation.Source: §3 · p. 3
  • The learner receives n independent complete trajectories from the logger and can inspect candidate models and query the target policy, but gets no further samples from the unknown environment.The estimator’s accuracy probability includes its own randomization.Source: §3 · p. 3
  • Action coverage rules out negligible logging probabilities, belief coverage asks whether histories span physical states, and outcome revealing asks whether logged futures distinguish them.These are properties of each candidate model, not privileged information given to the estimator.Source: §3 · p. 4
  • The behavior-marginal definition averages the logger’s past memory conditional on the physical state rather than fixing a history; the displayed bounds are common to both candidates.The conditions use stage range h < H, and the paper notes uniform-prior revealing at h = H with constant four.Source: §3 · p. 4

4 Main result

The theorem constructs two small POMDPs whose coverage and behavior-marginal revealing constants remain bounded, yet evaluating the known target policy requires exponentially many logged episodes. The proof isolates a rare no-reset trajectory that retains the information needed to distinguish the models.

4 Main result

  • Each candidate has at most two latent states per stage, three actions, a three-label unconfounded logger, and a deterministic memoryless target.The logger assigns every action probability at least 1/6; the two target values are 1/4 and 3/4.Source: §4 · pp. 4–5
  • Both candidates satisfy the stated coverage and behavior-marginal outcome-revealing conditions with horizon-independent constants.The reported constants are C_A = 6, C_H = 3, C_F = 35/9, and eC_F = 9.Source: §4 · p. 4
  • N_H(δ) = Θ((3/2)^H log(1/δ)) episodes are necessary and sufficient for accuracy 1/8, uniformly for H ≥ 3 and 0 < δ ≤ 1/4.The lower bound applies even with both candidate models known and unrestricted computation and target-policy queries.Source: §4 · p. 5

4.1 Proof outline

  • Every episode containing a gate has the same observable law under both candidates; only the no-reset fraction p_H carries a terminal bit distributed as Ber(1/4) or Ber(3/4).The resulting divergence is D_KL(P_0∥P_1) = p_H log(3)/2, yielding the exponential testing lower bound.Source: §4.1 · p. 5

5 The optimal estimator and its exact error

The section reduces each trajectory to a three-symbol observation that preserves all information for testing the candidate models. A fair-tie likelihood-ratio test then gives the exact optimal estimator and risk.

5 The optimal estimator and its exact error

  • The optimal estimator discards reset episodes, compares terminal zeros and ones among the rest, and selects the corresponding model, flipping a fair coin at a tie.It returns the selected model’s target value; the likelihood ratio is 3^S_n, making the fair-tie test minimax.Source: §5 · pp. 5–6
  • The three-symbol reduction preserves the full-data optimal testing risk because a common reconstruction kernel recovers trajectories conditional on the reduced observation.A reset maps to erasure ⊥; otherwise the terminal bit is retained.Source: §5 · pp. 5–6
  • The reduced distributions are Q_0 = (1 − p_H, 3p_H/4, p_H/4) and Q_1 = (1 − p_H, p_H/4, 3p_H/4), in order (⊥, 0, 1).Their shared erasure probability reflects that reset trajectories have identical likelihood under both candidates.Source: §5 · p. 5

6 Gridworld experiments

Gridworld simulations reproduce the predicted horizon-dependent evaluation error and bounded population diagnostics. Information controls sharply reduce the required episode budget, but alter what information the learner receives.

6 Gridworld experiments

  • The simulations use shared dataset prefixes across budgets and pointwise 95% Wilson intervals over 512 datasets, rather than simultaneous bands.The reported experiment concerns the specified worst-case family, not typical navigation tasks or a general ranking of learned OPE methods.Source: §6 · p. 6
  • At the six analytic 90%-success thresholds, observed failures range from 8.6% to 10.2%, while the threshold rises from 43 episodes at H = 4 to 143,982 at H = 24.Each interval contains the exact-risk prediction; the thresholds are computed from exact risk, not fitted to simulation data.Source: §6 · p. 6, Figure 2 · p. 7
  • At H = 24, the actual worst-stage norms are C_F ≈ 3.094 and eC_F ≈ 4.218, below their proved bounds; C_A = 6 and C_H = 3 throughout.The experiments simulate the construction action by action, using observable evidence only and counting each gate as one grid transition.Source: §6 · p. 6
  • The target-policy and lane-observation controls have analytic 90%-success budgets of seven and four episodes, respectively, independent of H.Every target-policy episode is informative; revealing the lane at stage 2 makes a first continue identify the model, and each episode still costs order H steps.Source: §6 · p. 6

7 Why current-state information is insufficient

The revealing condition establishes a state–future correlation under the logger’s marginal law, but does not make physical state sufficient for its continuation. Logger memory can restore a memoryless representation while exposing a rare state that drives coverage costs.

7 Why current-state information is insufficient

  • Histories ending in the same physical lane can induce different logger continuation laws, so one state-conditioned future matrix cannot represent both.In M0, a first continue and a first upper gate both reach lane zero, but their next-action laws differ.Source: §7 · p. 8
  • The behavior-marginal revealing assumption certifies state–future correlation, not that physical state is sufficient for the logger’s continuation.Augmenting state with logger memory restores a memoryless representation but exposes the rare never-reset state; its belief second-moment eigenvalue is w_h = 1/[3(2/3)^(h−2)].Source: §7 · p. 8
  • A constant number of logger-memory labels does not guarantee a uniformly short history window across horizons.Arbitrarily long common hold suffixes can retain different states or different logger laws.Source: §7 · p. 8

8 Discussion

The construction shows that constant physical-state coverage and behavior-marginal revealing bounds do not remove the information loss caused by history-dependent logging. The appendix establishes these coverage and revealing properties under uniform and prior-weighted normalizations.

8 Discussion

  • Exponential sample complexity persists despite constant state coverage and both behavior-marginal revealing bounds; positive guarantees need additional structure tying logger continuations to history.The discussion identifies joint state coverage, forgetting, or informative controlled futures as possible additional structure, without characterizing all tractable POMDPs.Source: §8 · p. 8

A.1 Uniform belief coverage

  • Every physical state has belief-matrix diagonal entries at least 1/3, although the model-dependent posterior used to establish coverage is not supplied to the learner.The never-reset label persists only through hold, with probability 2/3, and cannot be re-entered.Source: §A.1 · p. 10

A.2 Uniform-prior outcome revealing

  • The uniform-prior revealing bound has induced 1-norm at most 35/9 before the terminal stage, and uniform-prior revealing on every layer has common bound 4.The revealing event can depend on the candidate under consideration and is not supplied to the estimator.Source: §A.2 · p. 11

A.3 Prior-weighted outcome revealing

  • Changing the latent-state prior in the revealing matrix does not remove the information loss under the prior-weighted normalization.The proof uses state probabilities in [1/3, 2/3].Source: §A.3 · pp. 11–12

A.4 Information in a logged trajectory

The logged trajectory distinguishes the candidate models only when every nonterminal action is hold. Because estimator randomization and candidate simulations operate as a common kernel on observed data and known inputs, they do not alter the information bound.

A.4 Information in a logged trajectory

  • Only all-hold action sequences distinguish the models: on that event, terminal outcomes are Ber(1/4) under M0 and Ber(3/4) under M1.After any reset, the conditional terminal-outcome law is the same under both candidates; the final independent action contributes no divergence.Source: §A.4 · p. 12
  • The observable-trajectory laws have the same support, while every nonterminal action has positive probability and both terminal emissions have positive probability at either bit.The common-support property is distinct from the differing terminal laws on all-hold sequences.Source: §A.4 · p. 12
  • Even adaptive simulations in the supplied candidate models cannot evade the information bound, because estimator randomization is a common stochastic kernel applied to the data and known inputs.Data processing applies regardless of the estimator’s computational cost.Source: §A.4 · p. 12

B Proofs for the optimal estimator

The appendix characterizes an optimal test for the logged-data experiment and clarifies why physical-state coverage, short logger memory, and compressed futures do not remove the construction’s limitations. It also gives a deterministic-terminal variant with a distinct observation property.

B Proofs for the optimal estimator

  • The likelihood-ratio test is minimax optimal, and testing risk equals the minimax risk of estimating value within 1/8.The test selects the model with the larger likelihood, randomizing fairly at ties; the value estimate succeeds exactly when the corresponding test is correct.Source: B Proofs for the optimal estimator · p. 13

C.1 The same lane can lead to different logged futures

  • Histories with identical physical-state beliefs can have different logger futures, so a belief-based factorization cannot reproduce all conditional future laws.In M0 the compared next-action distributions have total variation distance 1/2.Source: §C.1 · pp. 13–14

C.2 Including logger memory makes a rare state explicit

  • Augmenting physical state with logger memory makes the logger memoryless, but constant physical-state coverage does not imply constant augmented-state coverage.The reachable augmented-state second-moment matrix has diagonal entries w_h, (1−w_h)/2, and (1−w_h)/2.Source: §C.2 · p. 14

C.3 Three memory labels do not imply a short observation window

  • Three logger-memory labels do not imply a uniformly short observation window: for fixed suffix length, histories can retain belief distance two in ℓ1 across sufficiently long horizons.For an individual finite horizon, keeping the entire history remains possible.Source: §C.3 · p. 14

D A compact outcome matrix for exact calculations

  • Compressing the future to the first reset’s time and value, or the terminal outcome if no reset occurs, preserves both revealing Gram matrices exactly.The compressed statistic has 2L + 2 possible symbols.Source: D A compact outcome matrix for exact… · p. 15

E A deterministic-terminal variant

  • In the deterministic-terminal variant, one non-erased observation identifies the model, while candidates remain indistinguishable conditional on all erasures.The non-erased observations are singular across candidates; the main noisy theorem instead has common observable support and finite KL.Source: E A deterministic-terminal variant · pp. 15–16

F.1 Experimental protocol

The section specifies the trajectory-simulation protocol, exact finite-sample risk calculations, and a secondary comparison with importance-sampling estimators.

F.1 Experimental protocol

  • Simulated trajectories record observations and terminal reward without latent-state information, while the behavior policy depends on past actions and the target always continues.Each protocol, horizon, and candidate uses 256 independent datasets; population coverage matrices are computed in exact rational arithmetic.Source: §F.1 · p. 16

F.2 Computing the exact risk and confidence intervals

  • The exact risk calculation uses the binomial count of informative episodes and conditional positive-bit count, with no Poisson approximation.For the target-policy control, every episode contributes a noisy bit, and Hoeffding's inequality gives a horizon-independent episode bound.Source: §F.2 · p. 16

F.3 Rescaling and importance-sampling comparisons

  • Exact and simulated errors nearly align when plotted against expected informative episodes, but this is not an exact finite-sample collapse.The distribution of Bin(n, pH) depends on both parameters.Source: §F.3 · p. 17
  • The self-normalized estimator's midpoint choice when its denominator is zero fails at accuracy 1/8 in both candidates; Figure 4(b) compares specified estimators, not general superiority.The ordinary estimate is not clipped.Source: §F.3 · p. 17, Figure 4 · p. 17
Loading 2609.19135v1…