Off-Policy Evaluation Gets Harder Than You Think
Off-policy evaluation estimates what a new policy would achieve using data collected by a different policy. In reinforcement learning, this matters because you cannot always deploy a policy to test it: a medical treatment protocol, a trading strategy, or a robotics controller might be too dangerous or expensive to try in the real world. You collect data with a behavior policy (the logger), then use that data to estimate the value of a target policy without running it. The question is how much data you need.
For fully observable MDPs, the answer depends on the number of states and the behavior policy's coverage of the target policy's action distribution. In partially observable MDPs (POMDPs), the situation is harder because the learner does not observe the hidden state. Recent work has shown that future-dependent value functions can exploit latent-state structure, using future observations and actions as proxies for the current state, and that coverage conditions on the small latent state space can make off-policy evaluation tractable.
Pranaya Jajoo from the University of Alberta shows that these positive results break down when the logger depends on history. For every horizon H >= 3, he constructs two POMDPs with at most two latent states per stage, three actions, and a common logger with three memory states, where every standard coverage condition holds with constants independent of H. Yet evaluating a known deterministic target policy to accuracy 1/8 requires Theta((3/2)^H log(1/delta)) logged episodes. The sample complexity is exponential in the horizon, even when both candidate models are completely known, the target policy is known, and the learner has unrestricted computation. This resolves the open problem posed by Zhang and Jiang (2025) about the model-based, history-dependent-behavior case under their behavior-marginal definition of revealing.
The Two-Lane Construction: Same Corridors, Different Secrets
The construction is a directed two-lane grid. Every nonterminal action advances one column. The action set has three elements: continue (hold the lane), upper gate (reset to lane zero), and lower gate (reset to lane one). The initial state is a singleton; every later state is a bit (0 or 1). In model M_theta, the first transition is deterministic and depends on theta: if the first action is continue, the lane becomes theta; if it is an upper gate, the lane becomes 0; if it is a lower gate, the lane becomes 1. For all subsequent stages, both models have the same transitions: continue preserves the lane, and the gates reset to their respective lanes.
The observations before the terminal stage are blank time tags. The learner sees identical corridors in both models. The terminal observation Y is drawn from a noisy channel: P(Y=1 | s_H = 0) = 1/4 and P(Y=1 | s_H = 1) = 3/4. The reward is zero before the terminal stage and equals Y at the end. The target policy always continues (never resets). Its lane remains theta from stage 2 onward, so its expected return is 1/4 + theta/2. In M_0 the target value is 1/4; in M_1 it is 3/4.
The two models differ only in the first transition. The learner's job is to figure out which model is true. But a gate resets the lane, erasing the information about the initial transition. After any gate, the remaining observations have the same distribution under both candidates. A logged episode is informative about the unknown first transition only if it continues at every step, never triggering a gate. This event has probability p_H = (1/3)(2/3)^(H-2), which shrinks exponentially with the horizon.
Why Coverage Conditions Are Not Enough
The paper defines four coverage conditions from the Zhang and Jiang (2025) framework. Action coverage asks that the logger assigns probability at least 1/C_A to every action at every stage and history. Belief coverage asks that the belief second-moment matrix has minimum eigenvalue at least 1/C_H. Uniform-prior outcome revealing asks that the outcome matrix Gram has bounded inverse norm at most C_F. Prior-weighted outcome revealing asks the same for a prior-weighted variant.
In the two-lane construction, all four conditions hold with constants independent of H. Action coverage holds with C_A = 6, since every action has probability at least 1/6. Belief coverage holds with C_H = 3, because the two reset-memory labels have equal probability and every physical state has mass at least 1/3. The two revealing conditions hold with C_F = 35/9 and tilde{C}_F = 9, established by direct eigenvalue computation on the 2x2 outcome matrices.
These are strong conditions. They certify that the logger visits every physical state frequently, that the logged futures distinguish the states, and that the data-collection law provides enough information about the current state to support off-policy evaluation. In the Zhang and Jiang framework, these conditions are exactly what you need for tractability.
But they are not enough. The construction exploits a gap between what the conditions certify and what the learner actually needs. The revealing conditions are behavior-marginal: they average the logger's future law over histories conditional on the physical state. They do not require that the physical state is sufficient for the logger's continuation. In the two-lane grid, two histories can lead to the same physical state but different logger behavior. After a first continue and after a first upper gate, both place the agent in lane zero, but the logger's next-action laws are (2/3, 1/6, 1/6) and (1/6, 2/3, 1/6) respectively. The physical state alone cannot reproduce both continuation laws.
The Mechanism: Resets Erase the Unknown
The exponential hardness comes from a simple structural feature. The logger's resets erase the lane, making the current state predictable from the logger's memory but destroying the information about the initial transition that determines the target value. After a reset, the lane equals the last reset value, regardless of theta. The remaining observations have the same distribution under both candidates.
Only episodes that never trigger a gate are informative. The target follows this informative path in every episode. But the logger triggers a gate with high probability. The fraction of informative episodes is p_H = (1/3)(2/3)^(H-2), which is exponentially small. The KL divergence between the two trajectory laws is D_KL(P_0 || P_1) = p_H log(3) / 2. By the standard testing reduction, any estimator that distinguishes the two target values with error at most delta needs at least 2 kl(1-delta, delta) / (p_H log 3) episodes.
This lower bound is exponential in H. The construction has only 2H-1 latent states across all layers, so the exponential cost is not a consequence of a large state space. It comes from the logger's history dependence erasing the information that matters.
The Optimal Estimator and Its Exact Error
The paper characterizes the resulting statistical experiment exactly. A complete trajectory maps to a three-symbol statistic: reset (bot) if a gate occurs before the terminal observation, 0 if no gate and Y=0, 1 if no gate and Y=1. Under M_0, the distribution is Q_0 = (1-p_H, 3p_H/4, p_H/4). Under M_1, it is Q_1 = (1-p_H, p_H/4, 3p_H/4). There exists a reconstruction kernel, common to both candidates, that generates the full trajectory conditional on the three-symbol statistic. The full-data and three-symbol experiments have the same optimal testing risk.
The optimal estimator counts terminal rewards among non-reset episodes. Let S_n be the sum of +1 for ones, -1 for zeros, and 0 for erasures. The optimal worst-case failure probability for accuracy 1/8 is e_n = P_0(S_n > 0) + (1/2) P_0(S_n = 0). The lower bound is (1/2)(1-p_H)^n, from the probability that all episodes are erasures. The upper bound uses the Bhattacharyya affinity: e_n <= (1/2)(1 - (1-sqrt(3)/2)p_H)^n.
The likelihood ratio is 3^(S_n). Symmetry makes the fair-tie test minimax. Returning the selected model's target value equates testing and estimation risk. The exponential cost persists for this explicit optimal estimator, independent of representation or optimization.
Gridworld Experiments: Theory Matches Practice
The construction is realized as a directed two-lane gridworld and simulated at horizons H in {4, 8, 12, 16, 20, 24}. For each horizon, 256 independent datasets are generated per candidate and 512 per budget level. The estimator receives observable evidence only; it does not sample from the reduced three-symbol law. Each gate counts as one transition in the directed grid.
The analytically chosen 90%-success thresholds range from 43 episodes at H=4 to 143,982 at H=24. These are computed from the exact risk, not fitted to simulation data. At these thresholds, observed failures range from 8.6% to 10.2%, and every 95% Wilson interval contains its analytic prediction. The simulated errors follow the predicted (3/2)^H horizon dependence.
Population diagnostics confirm that the coverage constants remain bounded. At H=24, the actual worst-stage norms are C_F approximately 3.094 and tilde{C}_F approximately 4.218, both below their proved bounds. The construction is not pathological in the sense of having degenerate coverage; it achieves exponential hardness with well-behaved, constant coverage conditions.
Information Controls: What Would Make It Easy
The paper includes two information controls that isolate what makes the original problem hard. In the first control, fresh target-policy episodes are collected instead of logger episodes. Every episode is now informative because the target never triggers a gate. The 90%-success budget drops to seven episodes, independent of H. In the second control, the lane is revealed at stage 2 while keeping the logger. A first continue identifies the model exactly, giving risk (1/2)(2/3)^n. The 90%-success budget is four episodes, also independent of H.
These controls change the information available and fall outside the original lower bound. They illustrate the core mechanism: the exponential cost comes specifically from the logger's resets erasing information that the target does not erase. If the logger did not reset, or if the lane were observable, the problem would be easy.
Why Current-State Information Is Insufficient
A natural reaction is to augment the state with logger memory, making the process memoryless on the augmented state. This works in principle but exposes a rare state: the never-reset state, which has probability w_h = (1/3)(2/3)^(h-2) at stage h. The belief second-moment eigenvalue for this augmented state is w_h, so the coverage cost is at least 1/w_h = 3(3/2)^(h-2), which grows exponentially with the stage.
A constant number of memory labels also does not give a uniformly short history window. For any fixed suffix length L, arbitrarily long common hold suffixes can retain different states or different logger laws. Histories beginning with reset-zero and reset-one, followed by L holds, share the same last L action-observation pairs but retain belief distance 2 in l_1. The number of logger memory states can be constant while the window needed to reproduce its continuation grows with the horizon.
This explains why positive results with forgetting and additional coverage conditions, such as those of Zhu and Lu (2026), need not apply. The present family admits no uniformly short forgetting window across horizons at the fixed accuracies above.
What This Means for Off-Policy Evaluation
The result establishes a fundamental barrier. Behavior-marginal coverage conditions, which are the standard notion in the POMDP off-policy evaluation literature, are not sufficient for tractability when the logger depends on history. The gap between what the conditions certify (state coverage averaged over histories) and what the learner needs (information about the specific transition that determines the target value) can be exponential.
This does not mean that off-policy evaluation in POMDPs is always hard. Positive guarantees need additional structure tying the logger's continuation to the actual history, through joint state coverage, forgetting, or informative controlled futures. The theorem rules out the specified behavior-marginal guarantees without characterizing all tractable POMDPs.
For practitioners, the message is cautionary. If your data-collection policy depends on the history of observations and actions (which it often does in practice, since policies condition on what they have seen), and if the environment is partially observable, standard coverage diagnostics can be misleading. The data might visit every hidden state frequently and still be exponentially uninformative about the target policy's value. The two-lane construction is not an exotic edge case; it is a minimal example that separates state coverage from information, using only two latent states per stage, three actions, and three memory labels.
The proofs have been formalized and verified in Lean 4, and the formalization is available at github.com/pranayajajoo/pomdp-logging-hardness. The gridworld simulations, exact risk computations, and all experimental code are released as well.
Read the paper on arXiv