首页 > AI前沿 > Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging

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

arXiv机器学习 2026-09-17 01:56 2 阅读 查看原文

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.