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

arXiv: https://arxiv.org/abs/2609.19135 · HTML: https://mlsanity.com/paper/2609.19135/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 5 references that are in the map.
- First posted on arXiv 16 Sep 2026.

## Builds on (most cited first, 5 of 5)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Future-Dependent Value-Based Off-Policy Evaluation in POMDPs](https://mlsanity.com/paper/2207.13081/) (2022)
- [On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation](https://mlsanity.com/paper/2402.14703/) (2024)
- [Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs](https://mlsanity.com/paper/2503.01134/) (2025)
- [A Covering Framework for Offline POMDPs Learning using Belief Space Metric](https://mlsanity.com/paper/2603.03191/) (2026)

## Built on by (most cited first, 1 of 1)

- [Revealing After Overwriting: An Exponential POMDP OPE Lower Bound under History-Dependent Logging](https://mlsanity.com/paper/2610.05063/) (2026)

## Abstract (arXiv)

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 ≥ 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 Theta((3/2)H log(1/δ)) logged episodes at confidence 1-δ, for 0 < δ ≤ 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.