SOURCE-LINKED INTELLIGENCE

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

arXiv · AI, language, vision and robotics · article · Sep 16, 2026 · UTC

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 c

Read original source ↗ Open in workspace

recordType

paper

region

Global