离线策略优化新算法：全策略线性可实现下计算效率突破
Computationally Efficient Offline Policy Optimization with All-Policy Linear Realizability
离线强化学习理论的一篇硬核新论文：作者设计了每层只需一次凸回归的算法，在所有策略都线性可实现时样本量 O(ε^{-2})、计算量只随 log(B) 增长，还证明精度指数 2 已是下界。做 offline RL 理论或想了解覆盖假设能否放宽的研究者值得精读。
arXiv 论文（编号 2611.11423）研究有限时域 MDP 中的离线策略优化，假设每个确定性 Markov 策略的动作值函数在已知特征下线性可实现，系数范数上界为 B。
算法仅依赖单一未知行为策略的独立完整轨迹，在全策略占据覆盖条件下，样本复杂度为 O(ε^{-2})，计算复杂度对 log(2+B) 多项式级。机制上，算法每层只做一次凸回归，停止回报目标来自单一一致的 Markov 见证策略；
共享参考设计与有界预测约束将裁剪回归误差转为逐点置信区间，截断杠杆控制性能损失，无需在 B^{-2} 规模做经验协方差近似。向上取整置信半径可保留精确见证策略，并对有理数输入给出多项式时间的比特实现。
作者还给出协方差覆盖变体，在均匀近似可实现性下对 B 呈多项式依赖，并用双动作下界证明精度指数 2 不可改进。可实现性与覆盖条件仅需对确定性策略检验，且允许任意固定初始状态分布，降低了离线强化学习理论中的假设负担。
Computationally Efficient Offline Policy Optimization with All-Policy Linear Realizability
We study offline policy optimization in finite-horizon Markov decision processes where every deterministic Markov policy has an action-value function linear in known features, with coefficient norm at most $B$. From independent complete trajectories of one unknown Markov behavior policy, and under all-policy occupancy coverage, we give an algorithm with $\widetilde O(\varepsilon^{-2})$ sample dependence and computational complexity polynomial in $\log(2+B)$. The algorithm performs exactly one convex regression per layer. Its stopped-return targets are the values of a single consistent Markov witness policy. A shared reference design and bounded prediction constraints convert fast clipped-regression error into pointwise confidence for the raw linear predictions. Truncated leverage controls the performance loss without requiring empirical covariance approximation at scale $B^{-2}$. Rounding confidence radii upward preserves the exact witness and yields a polynomial-time bit implementation for rational numerical inputs. The guarantees allow any fixed initial-state distribution; realizability and coverage need only be checked for deterministic policies. We also establish a covariance-coverage variant with uniform approximate realizability and polynomial dependence on $B$. A two-action lower bound shows that the accuracy exponent $2$ is necessary.
This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include 离线强化学习, offline RL, 策略优化, 强化学习理论.
Source attribution: curated from arXiv cs.LG (@Zhijie Zheng).