History dependent logging makes policy evaluation exponentially hard
Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
Machine Learning
Summary
Estimating how well a certain plan (policy) will work using past data can be very difficult if the data collection depends on previous events. The authors show that even when the system seems to have good coverage and the models are known, the number of samples needed to evaluate a policy grows exponentially with the length of the decision process. They build simple examples where a single reset action erases key information, making the problem much harder. Their findings prove that past assumptions about ease of evaluation under these conditions do not hold.
What this means in practice
- •For reinforcement learning engineers: Avoid deploying history-dependent logging in off-policy evaluation setups where sample efficiency is critical, because evaluation can require exponentially many samples.
- •For robotics algorithm designers: Recognize that certain environment reset mechanisms can drastically increase data needed for policy evaluation, affecting algorithm design for long-horizon tasks.
Tested on simulated data.
Authors
Pranaya Jajoo
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 $Θ((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.