ICLR 2026 | 在确定性转移和Linear Q^π Realizability假设下的高效强化学习算法

关键词：强化学习理论，策略迭代，线性函数近似

导读

本文是 ICLR 2026 会议接收论文 Frozen Policy Iteration: Computationally Efficient RL under Linear Q^π Realizability for Deterministic Dynamics 的解读。该工作由北京大学计算机学院王若松课题组完成，论文第一作者柯怿憬是北京大学图灵班本科生，合作者包括香港科技大学助理教授张子函。

论文地址：

https://arxiv.org/abs/2603.00716

引言

本文研究了基于函数近似的强化学习中的理论问题。在强化学习理论中，如何实现既样本高效又计算高效的算法，一直是学术界关注的核心问题。

在在线强化学习的设定中，算法在每一回合根据观察到的状态，选择执行特定动作，接着获得一定的收益并观察到转移后的状态，直到回合结束。我们使用遗憾值 $R(T)=\sum^T_{t=1}(r^*_t-r_t)$ 来衡量算法的有效性，即 $T$ 回合中采取最优策略与当前策略期望收益的差距。

为了证明算法的有效性，通常需要对环境或函数类做出结构性假设。Linear $Q^\pi$ Realizability 是一个常见的假设，它假定对于任意策略 $\pi$ ，其 $Q$ 函数 $Q^\pi(s,a)$ 都可以表示为某个给定的状态-动作特征向量 $\phi(s,a)\in\mathbb{R}^d$ 的线性函数。该假设常见于对策略迭代类算法的理论分析中。

然而，在此假设下，现有算法大多存在明显局限：要么需要解决计算上难以处理的非凸优化问题^[1]，要么依赖于能够从历史状态重启的模拟器^[2,3]，而这在在线学习的设定下是无法实现的。

传统策略迭代算法的困境

策略迭代通常循环进行策略评估和策略改进。一旦策略被更新，之前收集的历史轨迹数据就变成了 off-policy 数据。直接利用这些数据来评估新策略会产生偏差，甚至导致学习发散。

结果

本文提出的 Frozen Policy Iteration（FPI）算法，首次在转移确定性且 Linear $Q^\pi$ Realizability 假设成立的环境中实现了计算高效的强化学习。在具有确定性转移、随机初始状态与随机奖励、动作数量为 $A$ 、特征维数为 $d$ 的 $H$ 步的 Markov 决策过程（MDP）中，FPI 算法能以高概率实现 $T$ 回合后 $\tilde{O}(\sqrt{d^2H^6T})$ 的遗憾值上界，时间复杂度为 $\tilde{O}(HT^2A\text{poly}(d))$ 。

算法

FPI 算法通过两个关键机制，确保了学习的有效性与高效性。

只用高置信度轨迹片段

在每一回合中，算法仅将轨迹中最后一个“未被充分探索”的状态-动作对加入数据集，丢弃其余所有数据。这保证了数据集中每条记录对应的后续状态都位于已充分探索的区域。

冻结已探索状态的策略

一旦某个状态的所有动作都被数据集“以高置信度覆盖”，算法就冻结该状态处策略的更新。后续对该状态价值函数的估计仅使用冻结前的历史数据，从而确保了整个学习过程中所有数据在分布上始终保持一致。

简化版算法

为了突出 FPI 算法的核心思想，我们先介绍该算法的简化版本 FPI-PAC。该算法具有 PAC（Probably Approximately Correct）保证，即以高概率找到一个 $\epsilon$ -近似的最优策略。

数据集与覆盖检测

算法在 MDP 的每一步 $h\in[H]$ 维护一个数据集 $D_h$ 。 $D_h$ 是一个有序序列，按时间顺序记录了历史数据。对于一个状态-动作对 $(s,a)$ ，如果在特征空间中 $\phi(s,a)$ 关于数据集 $D_h$ 协方差矩阵的置信椭圆半径 $\left \| \phi(s,a) \right \|_{\sum^{-1}}$ 小于阈值 $\epsilon$ ，则称该状态-动作对被 $D_h$ 覆盖。

探索机制

在每一个回合 $t$ ，算法按如下策略选择动作。对于当前状态 $s$ ，如果状态 $s$ 的所有动作都被数据集 $D_h$ 覆盖，说明该状态已充分探索，算法就基于 $D_h$ 估计特定的 $Q$ 函数 $Q_t(s,\cdot)$ ，然后采取贪心策略。否则，算法任意选择一个未被覆盖的动作进行探索。

选择性更新数据集

该回合结束后，我们收集到了一条轨迹，接下来用这条轨迹更新数据集。FPI 算法与传统策略迭代算法的核心区别就在于如何更新数据集，以及如何基于它估计 $Q$ 函数 $Q_t$ 。

算法只将轨迹数据的高置信部分加入数据集。具体来说，我们找到轨迹中最后未被覆盖的一步 $h$ ，只将 $(s_h,a_h)$ 加入对应的数据集 $D_h$ ，舍弃轨迹中其他部分的数据。

冻结策略

为了防止策略更新导致旧数据变成 off-policy 数据，算法不是使用数据集中所有数据来估计 $Q$ 函数。一旦数据集能够覆盖某个状态 $s$ 的所有动作，算法就冻结对状态 $s$ 处策略的更新。定义 $k(s)$ 为数据集增长到足以覆盖 $s$ 的所有动作时的大小，那么 $Q_t(s,\cdot)$ 的估计仅使用数据集中的前 $k(s)$ 个数据点。

这意味着，一旦一个状态认定为被充分探索，其 $Q$ 函数估计所依赖的数据就被冻结了。由于环境是确定性的，该状态的后续策略也随之冻结，从而保证了后续学习过程中数据分布的一致性。

理论保证

注意到算法每次向一个数据集中添加新的数据点时，该数据点都不能被以前的数据覆盖。由 Elliptical Potential Lemma^[4]可知，所有数据集的大小都一定有一个 $\text{poly}(d,\epsilon^{-1})$ 级别的上界。这为算法的探索次数与计算复杂度提供了理论保证。

完整算法

精度层级

FPI-PAC 算法使用了固定的精度 $\epsilon$ ，不足以实现低遗憾值。FPI 算法在此基础上引入了多层精度架构。算法引入了层级 $l\in\{1,...,L\}$ ，每一层对应一个精度 $\epsilon_l=2^{-l}$ 。对于每个层级 $l$ ，算法类似地在 MDP 的每一步 $h\in[H]$ 维护一个数据集 $D^{(l)}_h$ 。

动态调整精度层级

在每个回合 $t$ 开始时，精度层级 $l$ 被初始化为最大值 $L$ 。对于每一步，如果当前状态 $s$ 存在一个动作 $a$ 使得 $(s,a)$ 不能被更低层级 $l'\le l$ 的数据集 $D^{(l)}_h$ 以精度 $\epsilon_{l'}$ 覆盖，就将层级 $l$ 降级到 $l'$ ，并执行一个探索性的动作。否则，保持 $l$ 不变并采取贪心策略。

精度层级约束下的探索

FPI 算法的一个微妙之处在于如何选择探索性动作。与 FPI-PAC 算法中可以选择任意未被覆盖的动作不同，这里算法还需要确保所选探索性动作带来的损失不能远大于 $\epsilon_l$ ，以控制该回合的遗憾值。

为此，算法将可选动作限定在一个子集 $A^{(l)}_t(s)$ 中，只保留损失不超过 $\Delta_l=\tilde\Theta(\epsilon_l)$ 的动作。为了估计损失，算法使用更低层级 $l-1$ 下的数据集估计 $Q$ 函数。在决定是否冻结状态 $s$ 处的策略时，算法也只检测 $A^{(l)}_t(s)$ 中动作能否被该层数据集覆盖。

总结

本文提出了 Frozen Policy Iteration 算法，通过锁定已探索区域的策略，算法确保了用于学习的历史数据始终与生成它们的策略保持一致。通过引入多精度层级，算法能够动态调整探索的精度，在探索与利用之间取得平衡。最终实现了在 Linear $Q^\pi$ Realizability 和确定性转移的设定下，首个具有理论保证的、计算高效的在线强化学习算法。

参考文献

[1] Gellert Weisz, Andras Gyorgy, and Csaba Szepesvari. Online RL in linearly qπ-realizable MDPs is as easy as in linear MDPs if you learn what to ignore. Advances in Neural Information Processing Systems, 36:59172–59205, 2023.

[2] Dong Yin, Botao Hao, Yasin Abbasi-Yadkori, Nevena Lazic, and Csaba Szepesvari. Efficient local planning with linear function approximation. In International Conference on Algorithmic Learning Theory, pp. 1165–1192. PMLR, 2022.

[3] Gellert Weisz, Andras Gyorgy, Tadashi Kozuno, and Csaba Szepesvari. Confident approximate policy iteration for efficient local planning in qπ-realizable MDPs. Advances in Neural Information Processing Systems, 35:25547–25559, 2022.

[4] Tor Lattimore and Csaba Szepesvari. Bandit algorithms. Cambridge University Press, 2020.

图文 | 柯怿憬

北京大学王若松课题组

课题组PI简介

王若松博士，现任北京大学前沿计算研究中心助理教授，博士生导师，于2024年1月正式加入中心。他于2017年在清华大学交叉信息研究院获学士学位，于2022年在卡内基梅隆大学获博士学位，之后在华盛顿大学计算机科学与工程学院担任博士后研究员。他的研究兴趣是机器学习理论，目前的主要研究方向为：（1）设计有理论保证的强化学习算法，（2）证明强化学习问题的采样复杂度下界，（3）在理论研究的基础上，设计更高效、更鲁棒的强化学习系统和更合理的强化学习算法评估框架。王若松博士已在 STOC，FOCS，SODA，ICML，NeurIPS，ICLR 等国际顶级会议发表三十余篇论文。

中心近期科研动态

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点击“阅读原文”转论文链接

内容中包含的图片若涉及版权问题，请及时与我们联系删除

ICLR 2026 | 在确定性转移和Linear Q^π Realizability假设下的高效强化学习算法

评论列表

评论