技术摘要：具有对抗性损失的线性约束马尔可夫决策过程的对偶策略优化

问题设定

本文解决了在必须满足安全约束的环境中，尽管存在对抗性扰动，安全强化学习（RL）所面临的挑战。具体而言，作者考虑了有限时域对抗性线性约束马尔可夫决策过程（CMDPs）。

该设定由元组 $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, \{P_h\}, \{f^k\}, \{g^k\}, s_1, b)$ 定义，其中：

• 对抗性损失：损失函数 $f^k = \{f^k_h\}$ 由对手在每个回合 $k$ 开始时任意选择（全信息反馈）。这些损失并非来自固定分布。
• 随机成本：成本函数 $g^k = \{g^k_h\}$ 从固定分布 $G$ 中独立同分布采样（bandit 反馈），代表安全约束。
• 线性结构：转移核、损失函数和成本函数相对于已知特征映射 $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$ 具有线性结构。
• 目标：智能体寻求一种策略，以最小化累积期望损失，同时确保期望累积成本不超过预算 $b$。

性能通过遗憾值（与最优策略相比的累积损失差异）和约束违反（超过预算的累积超额成本）来衡量。目标是使这两个指标均达到次线性界。

方法论

作者提出了一种对偶策略优化算法（算法 1），旨在处理线性函数近似设定中对抗性损失与随机约束之间的相互作用。该算法集成了四个主要组件：

1. 阶段初始化与特征收缩：
   算法以阶段（epochs）为单位运行。当设计矩阵 $\Lambda^k_h$ 的行列式增加一个倍数因子时，一个新阶段开始。初始化时，策略重置为均匀策略，对偶变量重置为零。关键在于，算法采用特征收缩，使用 sigmoid 函数收缩原始特征 $\phi$，以防止 Q 函数估计无控制地膨胀。该技术改编自 Cassel & Rosenberg (2024)，简化了用于覆盖数论证的策略表示。

2. 策略执行与估计：
   在每个回合中，智能体根据当前策略执行动作，观察对抗性损失和随机成本，并更新设计矩阵。随后，它估计损失函数和成本函数的参数，并使用收缩后的特征和乐观奖励项计算 Q 函数估计值（$\hat{Q}$）和价值函数估计值（$\hat{V}$）。

3. 周期性策略混合：
   核心创新在于周期性策略混合。算法并非在每个回合都混合策略（即向均匀策略扰动），而是每 $K^B$ 个回合（其中 $B=3/4$）应用一次混合。

   • 动机：频繁混合对于界定对偶变量（通过漂移分析）是必要的，但会增加策略类的复杂度（覆盖数）。周期性混合平衡了这些相互竞争的需求。
   • 机制：每 $K^{3/4}$ 个回合，当前策略 $\hat{\pi}^k$ 通过凸组合与均匀策略 $\pi_{unif}$ 混合：$\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$。

4. 正则化对偶更新：
   对偶变量 $Y^k$（与成本约束相关）使用正则化梯度上升步骤进行更新：
   $$Y^{k+1} \leftarrow \left[ (1 - 4\alpha\eta H^3)Y^k + \eta(\hat{V}^k_{g,1}(s_1) - b - 4\alpha H^3 - 4\theta H^2) \right]_+$$
   正则化项（$-4\alpha\eta H^3 Y^k$ 和常数项）旨在将对偶变量拉向零，从而启用Lyapunov 漂移分析来界定 $Y^k$，而无需依赖在对抗性设定中失效的强对偶假设。

5. 加权 LogSumExp Softmax 策略：
   生成的策略类是加权 LogSumExp softmax。由于周期性混合，该策略并非 Q 函数之和的简单指数，而是 Q 函数估计值部分和的指数的加权和。这种结构使得策略能够适应对抗性选择的损失，同时保持可处理的覆盖数。

主要贡献

1. 对抗性线性 CMDPs 的首个次线性界：
   本文提出了首个在具有对抗性损失和随机成本的线性 CMDP 设定中实现次线性遗憾值和约束违反界的算法。这些界为 $\tilde{O}(K^{3/4})$，其中 $K$ 是回合数。

2. 新的覆盖数论证：
   作者为加权 LogSumExp softmax 策略建立了一种新颖的覆盖数论证。与权重均匀的标准 softmax 策略不同，混合过程引入了变化的权重参数 $\zeta_i$。作者证明，该类策略的覆盖数对数增长为 $\tilde{O}(n^2 d^2)$，其中 $n$ 是混合步数，$d$ 是特征维度。这一结果非同寻常，因为权重参数同时依赖于混合参数和 Q 函数估计值。

3. 用于控制的算法组件：
   本文引入了两个新颖组件，以联合控制覆盖数和对偶变量：

   • 周期性策略混合：调节混合频率，防止覆盖数增长过大（若进行 $O(K)$ 次混合步则会发生），同时仍频繁发生以界定对偶变量。
   • 正则化对偶更新：一种新的更新规则，引入正则化项以促进基于漂移的分析，从而在缺乏强对偶的情况下实现对偶变量的界定。

结果

理论保证：
在 Slater 条件（假设 1）下，并假设 $H^2 \leq K$，以至少 $1-\delta$ 的概率，该算法实现：

• 遗憾值：$\tilde{O}\left(\sqrt{d^3}H^4 K^{3/4} + dH^3 K^{3/4} + d^3 H^4 K^{1/2} + \frac{H^6}{\gamma^2} K^{1/4} + \frac{dH^6}{\gamma^2}\right)$
• 约束违反：$\tilde{O}\left(\frac{dH^5}{\gamma} K^{3/4} + \sqrt{d^3}H^4 K^{3/4} + d^3 H^4 K^{1/2}\right)$

这两个指标均随 $K$ 呈次线性增长（具体为 $K^{3/4}$），表明随着回合数的增加，平均遗憾值和平均约束违反收敛于零。

数值实验：
该算法在具有对抗性损失的修改版工作调度 CMDP 上进行了评估。在 $100,000$ 个回合中：

• 遗憾值：呈次线性增长，证实了理论界。
• 约束违反：最初迅速增长，但在约 45,000 个回合后收敛至零，验证了该算法在长期内满足安全约束的能力。

意义与主张

本文声称这是对抗性设定下具有线性函数近似的安全 RL 的首个可证明高效的算法。其意义在于弥合了以下两者之间的差距：

1. 表格型对抗性 CMDPs：先前的工作（例如 Qiu 等人，2020）处理了对抗性设定，但仅限于小型有限状态空间。
2. 线性随机 CMDPs：先前的工作（例如 Ghosh 等人，2022）处理了大型状态空间，但假设环境是平稳的（随机的）。

通过引入加权 LogSumExp softmax 策略和周期性混合策略，作者证明了同时处理大型状态空间（通过线性近似）和对抗性损失是可行的。本文谦逊地指出，虽然实现了 $\tilde{O}(K^{3/4})$，但最优的 $\tilde{O}(\sqrt{K})$ 界对于该特定设定仍然是一个未解决的问题，特别是关于混合步数与覆盖数之间的权衡。该工作还强调了将基于占用度量的对偶更新扩展到对抗性线性 CMDPs 中的基于策略的方法的困难性，从而证明了所提出的对偶策略优化方法的合理性。