Paper Overview
Research Area: Machine Learning Author: Pranaya Jajoo Published: 2026-09-16 arXiv: 2609.19135
Summary
Can a logged dataset visit every hidden state frequently and still be exponentially uninformative about a target policy's value? This paper shows that it can when the logger depends on history.
For every horizon H >= 3, the author constructs 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 hold with 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 < δ ≤ 1/4 — even when both candidate models are fully known.
Key Mechanism
The mechanism is simple: a reset erases the unknown transition that determines the target value. The paper precisely characterizes the resulting statistical experiment and derives a matching optimal estimator.
A directed two-lane grid world realizes the construction, and trajectory simulations match the finite-sample predictions.
Significance
The result establishes hardness of history-dependent logging in the model-based setting, under the behavior-marginal outcome-revealing definition of Zhang and Jiang (2025).
--- *Auto-collected on 2026-09-18*