← All papers
First page of Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging

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

Pranaya Jajoo

cs.LG Sep 16, 2026 · v1
The main exponential lower bound, the finite-sample minimax error characterization, and the matching sample-complexity bounds are formalized and verified in Lean 4.
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 $Θ((3/2)^H \log(1/δ))$ logged episodes at confidence $1-δ$, for $0 < δ\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.

Whether coverage and outcome-revealing conditions suffice for sample-efficient off-policy evaluation in POMDPs when the logging policy depends on history. This is the model-based, history-dependent-logging case posed by Zhang and Jiang (2025).

Two POMDPs are built for every horizon H ≥ 3, with at most two latent states per stage, three actions, and a three-memory-state logger. Gates reset the hidden lane and erase the unknown first transition that determines the target policy's value. An exact reduction to a three-symbol experiment yields a matching optimal estimator. The main proofs are formalized in Lean 4, and a two-lane gridworld simulation checks the finite-sample predictions.

Action coverage, belief coverage, and both revealing constants stay independent of H. Even so, evaluating the target to accuracy 1/8 needs Θ((3/2)^H log(1/δ)) episodes. In simulations, observed failure rates at the analytic 90%-success thresholds range from 8.6% to 10.2%. These thresholds grow from 43 episodes at H=4 to 143,982 at H=24.