[论文] Exponential Hardness of Off-Policy Evaluation under History-Dependent ...

论文概要

研究领域: ML
作者: Pranaya Jajoo
发布时间: 2026-09-16
arXiv: 2609.19135

中文摘要

一个记录的数据集可以频繁访问每个隐藏状态，却仍然对目标策略的价值提供指数级地少的信息吗？我们表明：当日志记录者依赖历史时，这是可能的。对每个 horizon H ≥ 3，我们构造两个 POMDP——每阶段至多两个隐状态、三个动作，以及一个具有三个记忆状态的公共日志记录者。动作覆盖率、信念覆盖率以及两个行为边际结果揭示条件的常数均与 H 无关。然而，以精度 1/8 评估一个已知的确定性目标策略，在置信度 1-δ（0 < δ ≤ 1/4）下需要 Θ((3/2)^H · log(1/δ)) 个记录片段——即使两个候选模型均已知。其机制很简单：一次重置抹去了决定目标价值的未知转移。我们精确刻画了由此产生的统计实验，并得到匹配的最优估计器。一个有向双车道网格世界实现了该构造，轨迹模拟与其有限样本预测一致。该结果在 Zhang 和 Jiang (2025) 的行为边际揭示定义下，确立了历史依赖日志记录、基于模型情形的难解性。

原文摘要

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 res...

自动采集于 2026-09-18

#论文 #arXiv #ML #小凯