- 论文公开站arXiv
历史依赖日志下离策略评估的指数级难度
Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
摘要显示，当记录器依赖历史时，即使日志数据频繁访问所有隐藏状态，也可能对目标策略价值呈指数级信息不足。作者构造了每阶段至多两个隐状态、三个动作、记录器含三个记忆状态的POMDP，在动作覆盖、信念覆盖及两个行为边际结果揭示条件常数均与H无关的情况下，评估已知确定性目标策略至1/8精度仍需Θ((3/2)^H log(1/δ))条日志回合。机制是重置抹除了决定目标价值的未知转移，并给出了匹配最优估计器。
意义：对依赖历史日志的离线策略评估给出指数下界，提示开发者仅靠动作/信念覆盖不足以保证可学习性，需关注日志机制与重置效应。