History-dependent logging can make policy evaluation exponentially hard even with good state coverage, because resets can erase critical information about transitions that determine policy value.
This paper proves that even when a logged dataset visits all hidden states frequently, it can still require exponentially many episodes to evaluate a policy's performance if the logger depends on history. The authors construct specific environments where standard coverage conditions hold, yet accurate policy evaluation needs Θ((3/2)^H) episodes—exponential in horizon H.