对抗性MDP策略优化：正则化Q函数消除Horizon差距

在强化学习理论中，策略优化（Policy Optimization）与占用度量（Occupancy-Measure）方法长期存在一道被称为"Horizon差距"的鸿沟。近期一篇理论研究给出了突破性的解法：通过正则化Q函数，在对抗性MDP下将策略优化的遗憾界提升了整整一个$H$因子。

问题背景：为什么Horizon差距如此顽固

考虑在线情景式表格MDP（tabular MDP），损失函数是**对抗性（adversarial）**的——即环境可以在每一轮选择任意损失，甚至针对算法历史做对抗选择，同时反馈是bandit式的（只能观测到所选动作的损失）。这是比随机损失更严苛的设定。

策略优化之所以受欢迎，是因为它在每个状态局部更新策略，不需要对整个占用度量多面体做全局优化，计算和实现上都更简洁。代价是：已有的遗憾界比基于占用度量的算法大出$H$倍。直观地看，这是因为局部更新只保证了单个状态下的稳定性，而全局算法可以统一控制所有状态-动作对的误差累积。

占用度量（Occupancy Measure） 是刻画策略在MDP中访问状态-动作对频率的分布：对于策略 $\pi$，其占用度量 $d^\pi(s,a)$ 表示在 $\pi$ 下状态-动作对 $(s,a)$ 的期望访问次数（或归一化后的分布）。在情景式MDP中，占用度量同时编码了策略的长期行为。基于占用度量的算法（如线性规划或镜像下降）把整个策略优化问题重写为在占用度量多面体上的凸优化，从而可以全局地控制所有状态-动作对上的误差累积，这正是其遗憾界少一个 $H$ 因子的根本原因。然而，这类方法需要显式维护或优化整个多面体，计算和实现都比逐状态局部更新的策略优化复杂得多，这构成了本文试图弥合差距的动机。

对抗性MDP（Adversarial MDP） 是相较于随机损失 MDP 更严苛的设定：在每一回合 $t$，环境可以选择任意损失函数 $\ell_t(s,a)$（可能依赖于算法历史），而非从固定分布中独立采样。由于损失可随时间任意变化，算法必须对不确定性具有更强鲁棒性。同时反馈是 bandit式 的——算法只能观测到实际执行动作的损失，而无法获知其他动作的损失。对抗性设定下，标准的乐观或置信上界方法不再直接适用，遗憾分析通常需要借助在线学习中的对抗性技巧（如跟随正则化领导者 FTRL）以及更精细的稳定性论证。本文正是在此更难的设定下证明了策略优化可以达到与占用度量方法相同的 horizon 依赖。

核心方法：联合控制状态-动作对的稳定性

论文的关键洞察是：改用正则化Q函数而非仅依赖局部策略梯度，可以把稳定性控制从"逐状态独立"升级为"所有状态-动作对联合"。这样一来，局部更新带来的额外误差不再随 horizon 线性膨胀，$H$的差距被彻底消除。

最终算法达到的遗憾界为：

• 已知转移：$\widetilde O(\sqrt{HS(H+A)T})$
• 未知转移：$\widetilde O(HS\sqrt{AT})$

其中$S$为状态数，$A$为动作数，$T$为回合数。两个结果都改进了已有策略优化界的 horizon 依赖；后者更是匹配了已知最优界——意味着策略优化在这一设定下不再有任何理论劣势。

正则化Q函数 指在Q函数更新中引入一个凸正则项（例如熵正则或 $L_2$ 正则），使得每个状态-动作对的Q值更新不仅依赖当前局部梯度，还通过正则项与全局策略分布耦合。在本文的分析中，正则化Q函数的作用是充当一个"全局稳定器"：它让所有状态-动作对的策略更新步长受到统一约束，从而把逐状态独立分析中会线性累积的误差转化为联合可控的量。直观上，标准策略梯度只在当前状态执行局部更新，不同状态间的误差无法相互抵消；而正则化Q函数通过全局正则项将各状态的更新耦合起来，使得误差在 horizon 维度上不再放大，最终消除了 $H$ 因子的差距。

意义与延伸：线性混合MDP同样受益

作者进一步把算法扩展到对抗性线性混合MDP（adversarial linear-mixture MDPs），并获得了相同的 horizon 依赖改进。这说明正则化Q函数的思路并非只适用于表格情形，在函数近似场景下也具有推广潜力。

对强化学习理论社区而言，这项工作回答了一个悬而未决的问题：策略优化是否天生比占用度量方法差一个$H$？答案是否定的——差距来自分析工具的局限，而非算法范式本身。这为后续在更一般的函数近似、多智能体等设定下设计紧遗憾界的策略优化算法提供了新路径。

线性混合MDP（Linear-Mixture MDP） 是一类函数近似设定：转移概率被假设为若干已知基特征的线性组合，即 $P(s'|s,a) = \sum_{i=1}^d \phi_i(s'|s,a) \theta_i$，其中 $\phi_i$ 是已知特征，$\theta$ 是未知参数。它介于表格MDP（特征为指示函数）与一般函数近似之间，允许状态空间巨大甚至连续，同时仍保留可学习的线性结构。在对抗性设定下，损失仍可每轮任意选择，但转移的线性结构为算法提供了可估计的参数。本文把正则化Q函数方法扩展到这一设定并保持相同的 horizon 依赖改进，表明该技术不依赖于表格的有限性，为更一般的函数近似场景提供了可行方向。