研究揭示历史依赖日志下离线评估的指数级难度
Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
这是篇关于强化学习离线评估难度的学术论文，对研究强化学习算法的工程师或研究者可能有参考价值。
这篇论文研究了在历史依赖日志的情况下，离线评估（Off-Policy Evaluation）的难度问题。作者证明了对于任意时间步数H≥3，存在两个部分可观察马尔可夫决策过程（POMDPs），它们最多有两个隐藏状态，三个动作，以及一个具有三个记忆状态的共同日志器。尽管满足行动覆盖、信念覆盖和两个行为边缘结果揭示条件，但评估一个已知的确定性行为策略（target policy）到精度1/8需要Θ((3/2)^H log(1/δ))个日志化轨迹，在置信水平1-δ下（0<δ≤1/4），即使候选模型已知。这个机制很简单：重置会擦除决定目标值的不确定性转移。作者精确地刻画了由此产生的统计实验，并得到了匹配的最优估计量。一个有向双车道网格世界实现了这个构造，轨迹模拟与有限样本预测一致。该结果确立了由张和江（2025年arXiv:2503.01134）提出的基于模型的历史依赖日志、基于行为边缘定义揭示的情况下的不可行性。
Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
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.