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

arXiv:2609.19135v1 Announce Type: new Abstract: 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/elta)) logged episodes at confidence 1-elta, for 0 < elta 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.

Source: arXiv cs.LG | 2026-09-17