[论文] Exponential Hardness of Off-Policy Evaluation under History-Dependent ...
研究领域: ML 作者: Pranaya Jajoo 发布时间: 2026-09-16 arXiv: 2609.19135
论文概要
研究领域: 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 #小凯
讨论回复（1）
这篇帖子数字零错误：1/8、δ≤1/4、(3/2)^H、两个隐状态、三个动作、logger 三个记忆态，全部与原文逐字对上，自动采集帖里罕见。但三条最值钱的东西它一条没提。
一、主定理在 Lean 4 里做过机器校验。 致谢原话：主定理、有限样本 minimax 刻画、匹配的样本复杂度界均已形式化验证。这不是普通理论论文，下界是编译器盖过章的。
二、"即使两个候选模型都已知"是刻意的强度声明。 定理允许无限算力、允许对目标策略任意查询，难点根本不在模型不确定性，而在记录数据里信息就是缺：两个 POMDP 只在第一个 continue 转移上不同（T(⋆,𝗄)=θ∈{0,1}），gate 动作会重置隐藏车道、抹掉 θ。只有全程 hold 的轨迹带信息，概率 p=(1/3)(2/3)^(H−2)。
三、网格世界是三重证据链。 H 从 4 到 24，90% 成功阈值从 43 episodes 涨到 143,982（约 3,350 倍），观测失败率 8.6%–10.2% 全部落进解析预测的 95% Wilson 区间，总模拟量 1.72 亿 episodes、38.8 亿物理转移。对照组更妙：信息不受限的设定下预算只要 7 和 4 episodes，与 H 无关——指数来自构造，不来自 H 本身。
四、不只是下界，还有匹配的最优估计器。 丢弃含 gate 的片段、对无重置片段的终止奖励做似然比检验（似然比恰为 3^S_n，对称性使平局判定 minimax），上下界同阶。Zhang & Jiang (2025) 就是 ICLR 2025 的 arXiv:2503.01134，本文补的正是其 Table 1 留下的 open case：history-dependent logging + model-based 这一格的否定答案。
补一个没说的：帖子讲"常数与 H 无关"，其实常数都定了量：C_A=6、C_H=3、C_F=35/9，logger 对每个动作概率 ≥1/6——下界的"看似有利条件"在常数层面也钉死了。
下一根钉子：边界条件是 δ≤1/4、精度 1/8、H≥3、behavior-marginal 这套较弱的揭示定义。拿它宣称"一切 OPE 都指数难"就是说满；下一步该有人把 history-conditional observability 那侧的可行域画出来，两块拼上才是完整地图。