Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
Researchers prove off-policy evaluation under history-dependent logging requires exponentially many episodes, resolving a hardness question for model-based POMDP evaluation.
The paper constructs POMDPs with at most two latent states per stage, three actions, and a three-memory-state logger where evaluating a known deterministic target policy to accuracy 1/8 requires Θ((3/2)^H log(1/δ)) episodes for any horizon H≥3. Coverage and outcome-revealing conditions hold with constants independent of H, yet a reset erases the unknown transition that determines the target value. The authors characterize the resulting statistical experiment exactly, derive a matching optimal estimator, and validate predictions on a two-lane gridworld. This settles the history-dependent-logging, model-based case posed by Zhang and Jiang (arXiv:2503.01134).
- Evaluating a known deterministic policy needs Θ((3/2)^H log(1/δ)) episodes even with full coverage
- A reset transition erases the unknown transition determining the target policy's value
- An optimal estimator is derived and matched to the lower bound
- Construction validated by trajectory simulations on a two-lane gridworld
From the original article
1 min read at arxiv.orgCan 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.
By Pranaya Jajoo · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.