知识卡片：历史依赖日志下离策略评估的指数级硬度

英文标题：Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging

英文关键词（从标题/摘要提取）：Off-Policy Evaluation; History-Dependent Logging; POMDP; Exponential Hardness; Coverage; Behavior-Marginal Revealing; Model-Based OPE; Optimal Estimator.

一句话结论

在日志记录器依赖历史时，一个已记录数据集可以频繁访问每个隐藏状态并满足多种覆盖/揭示条件，却仍对目标策略价值指数级无信息；评估已知确定性目标策略到精度 $1/8$ 需要 $\Theta((3/2)^H \log(1/\delta))$ 条日志回合。

事件概述或研究问题

论文提出的问题是：日志数据集能否频繁访问每个隐藏状态，却仍然对目标策略的价值指数级无信息？作者证明，当 logger 依赖 history 时，这是可能的。对每个 horizon $H \ge 3$，论文构造两个 POMDP，它们每阶段至多有两个隐状态、三个动作，并共享一个具有三个记忆状态的 logger。即使 action coverage、belief coverage 和两个 behavior-marginal outcome-revealing conditions 都满足，且相关常数不随 $H$ 变化，离策略评估仍可能极其困难。

方法/产品要点

• 本条为学术理论结果，无产品。
• 核心方法是构造性下界：构造两个 POMDP，共享 logger，使覆盖类条件看似充分。
• 构造满足 action coverage、belief coverage，以及两个 behavior-marginal outcome-revealing conditions，且这些条件的常数独立于 $H$。
• 关键机制是简单 reset：它擦除了决定目标价值的未知转移。
• 论文精确刻画了由此产生的统计实验，并得到一个匹配的最优估计器。
• 一个有向双车道 gridworld 实现了该构造，轨迹模拟与有限样本预测一致。

主要结果或产业意义

• 对每个 $H \ge 3$，评估一个已知的确定性目标策略到精度 $1/8$，在置信度 $1-\delta$ 下，需要 $\Theta((3/2)^H \log(1/\delta))$ 条 logged episodes，其中 $0 < \delta \le 1/4$。
• 该下界即使在两个候选模型都已知时仍成立。
• 结果确立了对 Zhang and Jiang (2025, arXiv:2503.01134) 提出的 history-dependent-logging、model-based case 的 intractability，且是在其 behavior-marginal definition of revealing 下。
• 产业意义/启示：在离线强化学习与离策略评估中，仅报告动作覆盖、信念覆盖或行为边际揭示条件，可能不足以证明数据“可评估”。日志记录机制本身可能决定数据是否包含足够统计信息。

为什么重要

• 它直接挑战“覆盖充分即可评估”的直觉：隐藏状态访问频繁并不保证目标策略价值可识别。
• 它把评估困难从经验观察推进到指数样本复杂度下界，并给出匹配最优估计器，说明困难不是分析松弛。
• 对离线 RL 数据采集、日志系统设计和 OPE 诊断指标有警示：需要审计 logger 是否历史依赖，以及 reset 等机制是否抹除了关键转移。
• 在已有强调评估指标可能掩盖脆弱性的卡片脉络中，本条增量是：在 OPE 场景下，覆盖/揭示条件满足仍可能指数级无信息，并给出理论下界与估计器匹配结果。

局限与不确定性

• 本卡片只基于 arXiv 摘要与元数据；完整证明、定理的精确假设、实验细节和代码/数据可用性均待核实。
• 构造针对特定 POMDP 规模、horizon 范围、logger 记忆状态数和 behavior-marginal 揭示定义；对更一般模型、随机目标策略、其他揭示定义是否成立，待核实。
• gridworld 的具体参数、模拟规模、有限样本预测细节待核实。
• 该理论结果对真实离线 RL 系统影响的量级与普适性待核实。
• 作者单位、资助信息、是否经过同行评审等元数据未在材料中提供，待核实。

可用于图书/PPT/简报的角度

• “覆盖不等于可评估”：覆盖率指标全部通过，目标价值仍可能指数级不可学。
• 日志记录机制是统计信息的一部分：history-dependent logger 与 reset 可抹去决定目标值的未知转移。
• 理论下界可视化：随着 $H$ 增长，样本需求按 $(3/2)^H$ 增长。
• 离线 RL 数据评估清单：不只看状态/动作覆盖，还要审计 logger、行为策略与结果揭示条件。
• “难解但可刻画”：论文得到精确统计实验刻画与匹配最优估计器，适合讲解下界与最优性。

与既有脉络的关系

本条与已有卡片没有重复同一事实。若将已有脉络概括为“评估困难、聚合指标或覆盖指标可能掩盖脆弱性”，本条提供的增量是：在历史依赖日志的离策略评估中，覆盖与 behavior-marginal 揭示条件满足仍可能导致指数级硬度，并给出匹配最优估计器。

原始材料

• 英文标题：Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
• 作者：Pranaya Jajoo
• arXiv ID：2609.19135v1
• 发布日期（材料标注）：2026-09-16T17:56:12Z
• 更新日期（材料标注）：2026-09-16T17:56:12Z
• Primary category：cs.LG
• Categories：cs.LG
• Abstract URL：https://arxiv.org/abs/2609.19135v1
• PDF URL：https://arxiv.org/pdf/2609.19135v1
• 摘要中提及的相关工作：Zhang and Jiang (2025, arXiv:2503.01134)