Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret¶

会议: NeurIPS 2026
arXiv: 2605.11586
代码: https://github.com/khyu99/PD-LSCVI-UCB
领域: 强化学习
关键词: 约束马尔可夫决策过程, 弱通信结构, 强对偶性, 线性函数逼近, 截断值迭代

一句话总结¶

本文证明了有限状态动作空间下弱通信平均奖励约束马尔可夫决策过程在平稳策略类上的强对偶性，并基于此提出了首个结合有限时域近似与值函数截断的原对偶算法 PD-LSCVI-UCB，在线性 CMDP 下将遗憾与约束违背界从 $\widetilde{\mathcal{O}}(T^{3/4})$ 显著改进至 $\widetilde{\mathcal{O}}(T^{2/3})$。

研究背景与动机¶

安全强化学习在自动驾驶避障、机器人防撞、医疗决策安全边界以及大语言模型有害内容阻断等高风险场景中发挥着基础性作用。为了刻画系统的长期最优渐近行为，无限时域平均奖励约束马尔可夫决策过程（CMDP）被广泛研究，其目标是在满足长期平均安全约束的前提下最大化长期平均累积奖励。然而，平均奖励 CMDP 的学习难度与理论界极大程度取决于底层环境转移核的遍历结构假设。在强遍历（ergodic）或单链（unichain）假设下，占用测度集是一个凸多面体，能够等价转化为标准线性规划（LP），从而直接应用 LP 强对偶性等成熟工具获得最优或近最优保证。

在更现实且广泛的弱通信（weakly communicating）环境下，系统仅保证存在平稳策略诱导单一闭连通类以及一组在所有平稳策略下均为瞬态的瞬态状态集合。这一弱化假设导致平稳策略诱导的占用测度集合不再是多面体，且通常非凸并存在缺失的边界点，使得传统的 LP 等价重构彻底失效。由于缺乏强对偶性这一核心分析工具，弱通信平均奖励 CMDP 的在线算法设计极其困难，现有线性函数逼近算法（如 Ghosh et al., 2023）只能借道有限时域强对偶分析，付出了额外依赖时间步 $H$ 的乘性膨胀代价，导致遗憾界劣化至 $\widetilde{\mathcal{O}}(T^{3/4})$，远落后于表格型基准。

面对弱通信环境下的非凸几何结构与对偶工具缺失，本文从占用测度的几何边界分析切入。核心 idea：利用弱通信占用测度集包含外层多面体相对内部与极点的几何特性建立拉格朗日强对偶性，并将带有限时域近似的值函数截断机制扩展至原对偶框架，通过强对偶分解复合拉格朗日遗憾，在弱通信线性 CMDP 中实现 $\widetilde{\mathcal{O}}(T^{2/3})$ 遗憾与安全约束违背。

方法详解¶

整体框架¶

算法围绕弱通信平均奖励线性 CMDP 的在线学习展开，采用分幕有限时域近似（finite-horizon approximation）结构：将总交互步数 $T$ 划分为 $K = T^{2/3}$ 个长度为 $H = T^{1/3}$ 的幕（episode），从而保证 $T = HK$。在每一幕中，算法维护一个动态更新的对偶乘子 $\lambda_k$（针对约束函数 $g$ 的折算惩罚），并在复合奖励 $r + \lambda_k g$ 下运行带上置信界（UCB）的最小二乘截断值迭代（PD-LSCVI-UCB）。为了控制由于函数逼近带来的值估计方差，算法在逆向值迭代中强制引入跨状态跨度截断，最后基于幕内累积约束违背更新对偶变量。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["弱通信线性 CMDP 环境输入"] --> B["占用测度几何分解与强对偶保证"]
    B --> C["分幕有限时域框架与特征协方差维护"]
    C --> D["复合奖励构建与逆向值迭代评估"]
    D --> E["跨状态跨度值函数截断"]
    E --> F["贪心策略环境交互与轨迹收集"]
    F --> G["投影次梯度对偶变量更新"]
    G -->|下一幕循环更新| C
    G --> H["复合拉格朗日遗憾与违背界分解输出"]

关键设计¶

1. 占用测度几何包含性与拉格朗日强对偶性证明：克服无 LP 重构下的非凸对偶缺失 在弱通信假设下，平稳策略诱导的占用测度集合 $\widehat{\mathcal{P}}(s_1) = \{q_{s_1}^\pi : \pi \in \Pi\}$ 通常非凸且无法用有限线性约束完全闭合。为了建立强对偶性，本文深入剖析了 $\widehat{\mathcal{P}}(s_1)$ 与由概率归一化和流守恒约束定义的外层紧凸多面体 $\mathcal{P}$ 的几何关系，严格证明了两个关键包含关系： $$\mathrm{relint}(\mathcal{P}) \subseteq \widehat{\mathcal{P}}(s_1) \subseteq \mathcal{P}, \quad \mathrm{ext}(\mathcal{P}) \subseteq \widehat{\mathcal{P}}(s_1)$$ 其中 $\mathrm{relint}(\mathcal{P})$ 是相对内部，$\mathrm{ext}(\mathcal{P})$ 是极点集。由于任何线性规划在线性目标下的最大值必在极点处取得，且由相对内部的可达性可使开集极限逼近原 LP 最优值，因此原非凸规划 $\sup_{q \in \widehat{\mathcal{P}}(s_1)} r^\top q \ \text{s.t.} \ g^\top q \geq b$ 与多面体 LP $\max_{q \in \mathcal{P}} r^\top q \ \text{s.t.} \ g^\top q \geq b$ 拥有完全相同的最优目标值。在此几何等价性基础上，结合 LP 强对偶性与极点包含性，证明了存在有界最优对偶乘子 $\lambda^* \geq 0$ 使得原问题最优值与对偶函数最小值严格相等，即 $J_r^*(s_1) = D(\lambda^*) = \min_{\lambda \geq 0} \sup_{\pi \in \Pi} \mathcal{L}(\pi, \lambda)$。

2. 跨状态跨度值函数截断：切断有限时域步数对值函数估计的乘性放大 在线性 MDP 下无法直接估计状态转移张量 $P$，通常采用逆向值迭代估计各步值函数 $\{V_h^*\}_{h=1}^H$。然而以往方法受限于平凡上界 $\|V_h^*\|_\infty \le H$，导致探索奖励 bonus 必须引入随时域 $H$ 线性增长的置信半径，带来严重的误差累积。根据弱通信平均奖励偏差函数跨度（span）的固有性质，最优值函数在任意两状态间的波动被严格限制。算法定义依赖已知最优偏差跨度的截断参数： $$\zeta \triangleq \mathrm{sp}(v_r^*) + \frac{2}{\gamma}\mathrm{sp}(v_g^*)$$ 在每一幕的逆向倒推步骤中，算法对最小二乘回归得到的未截断价值 $\widetilde{V}_h^k(s)$ 施加硬截断： $$V_h^k(s) \leftarrow \widetilde{V}_h^k(s) \wedge \left(\min_{s'} \widetilde{V}_h^k(s') + 2\zeta\right)$$ 由于理论证明了真实最优复合价值函数的跨度满足 $\mathrm{sp}(V_{r,h}^* + \lambda_k V_{g,h}^*) \leq 2\zeta$，截断操作在完全保留高概率乐观高估（optimism）特性的同时，将估计函数的范围从 $\mathcal{O}(H)$ 强制收敛到与时域 $H$ 无关的常数 $\mathcal{O}(\zeta)$，彻底消除了估计半径中不利的 $H$ 乘子。

3. 对偶稳定化有限时域分幕与投影更新：避免折扣逼近导致的对偶震荡 此前在无约束环境下使用截断值迭代的工作（如 Hong et al., 2024）依赖基于加倍法（doubling trick）的折扣因子逼近，这使得单阶段有效视界可随步数激增至 $\mathcal{O}(T)$。在约束环境下，若时域达到 $\mathcal{O}(T)$，对偶变量的步进变化量 $|\lambda_{k+1} - \lambda_k|$ 将放大至 $\mathcal{O}(\eta T)$，导致对偶乘子剧烈振荡甚至发散。本文选择固定幕长 $H = T^{1/3}$ 的有限时域逼近，在每幕结束后基于幕内总安全违背量进行投影次梯度更新： $$\lambda_{k+1} \leftarrow \left[\lambda_k + \eta \left(Hb - \sum_{h=1}^H g(s_h^k, a_h^k)\right)\right]_{\left[0, \frac{2}{\gamma}\right]}$$ 基于 Slater 条件导出的对偶最优值有界性（$\lambda^* \le 1/\gamma$），截断区间设置为 $[0, 2/\gamma]$。当步长配置为 $\eta = \frac{2}{\gamma\sqrt{KH^2}} = \frac{2}{\gamma T^{2/3}}$ 时，对偶迭代既维持了单幕内有界的漂移，又保证了在线对偶遗憾上界的紧致性。

4. 基于强对偶性的拉格朗日遗憾解耦：打通复合遗憾向纯遗憾与违背的转化 在原对偶 CMDP 分析中，通常只能直接控制包含对偶变量权衡的复合拉格朗日遗憾 $\mathrm{Regret}(T) + \lambda \mathrm{Violation}(T)$。通过选取 $\lambda = 0$，可以直接得到纯奖励遗憾的 $\widetilde{\mathcal{O}}(T^{2/3})$ 上界；但为了约束安全违背 $\mathrm{Violation}(T) \leq \frac{\gamma}{2}(\Delta - \mathrm{Regret}(T))$，必须寻找 $\mathrm{Regret}(T)$ 紧致的理论下界。本文利用建立的强对偶性 $J_r^*(s_1) = J_{\lambda^*}^*(s_1)$ 与弱通信无约束贝尔曼最优条件，证明了： $$\mathrm{Regret}(T) \geq -\lambda^* \mathrm{Violation}(T) - \mathrm{sp}(v_{\lambda^*}^*) \sqrt{2T\log(1/\delta)} - \mathrm{sp}(v_{\lambda^*}^*)$$ 将此下界代入复合目标并在选取 $\lambda = 2/\gamma$ 时展开，剩余违背项的前序系数变为 $(2/\gamma - \lambda^*) \geq 1/\gamma > 0$，成功将复合拉格朗日界转化为对约束违背的强有力约束，最终完全解耦出纯约束违背的 $\widetilde{\mathcal{O}}(T^{2/3})$ 上界。

损失函数 / 训练策略¶

在每一幕 $k \in [K]$，特征协方差矩阵按历史访问特征累加：$\mathbf{\Sigma}_k = I + \sum_{\tau=1}^{k-1}\sum_{j=1}^H \phi(s_j^\tau, a_j^\tau)\phi(s_j^\tau, a_j^\tau)^\top$。从 $h = H$ 逆向推导至 $h = 1$： 1. 计算去中心化岭回归权重向量： $$\mathbf{w}_{h+1}^k \leftarrow \mathbf{\Sigma}_k^{-1} \sum_{\tau=1}^{k-1}\sum_{j=1}^H \phi(s_j^\tau, a_j^\tau)\left(V_{h+1}^k(s_{j+1}^\tau) - \min_{s'} V_{h+1}^k(s')\right)$$ 2. 构建乐观动作价值函数（配探索置信半径 $\beta = \widetilde{\mathcal{O}}((\zeta+1)d)$）： $$Q_h^k(s, a) \leftarrow \left(r(s,a) + \lambda_k g(s,a) + \phi(s,a)^\top \mathbf{w}_{h+1}^k + \min_{s'} V_{h+1}^k(s') + \beta\|\phi(s,a)\|_{\mathbf{\Sigma}_k^{-1}}\right) \wedge \left(1 + \frac{2}{\gamma}\right)H$$ 3. 取贪心值 $\widetilde{V}_h^k(s) \leftarrow \max_a Q_h^k(s, a)$，并实施值函数跨度截断 $V_h^k(s) \leftarrow \widetilde{V}_h^k(s) \wedge (\min_{s'} \widetilde{V}_h^k(s') + 2\zeta)$。

实验关键数据¶

主实验¶

在由 He et al. (2022) 构造并扩展为无限时域约束环境的基准弱通信环境（状态空间大小 $|\mathcal{S}|=8$，动作空间维数 $|\mathcal{A}|=2$，$d = |\mathcal{S}||\mathcal{A}| = 12$，约束阈值 $b = 0.7$）上，进行 $K = 1000$ 幕的在线交互学习，对比各算法在理论界阶数与经验表现上的综合指标：

算法	理论遗憾界 $\mathrm{Regret}(T)$	理论违背界 $\mathrm{Violation}(T)$	经验遗憾收敛性 ($K=1000$)	经验违背表现 ($K=1000$)
Random Agent	$\mathcal{O}(T)$（线性增长）	$\mathcal{O}(T)$（严重超标）	线性发散（无学习能力）	持续违背约束
Ghosh et al. (2023) [Alg. 2]	$\widetilde{\mathcal{O}}(T^{3/4})$	$\widetilde{\mathcal{O}}(T^{3/4})$	接近随机（探索过大）	接近随机策略水平
PD-LSCVI-UCB (本文)	$\mathbf{\widetilde{\mathcal{O}}(T^{2/3})}$	$\mathbf{\widetilde{\mathcal{O}}(T^{2/3})}$	快速达到亚线性收敛	有效满足约束并平稳收敛

消融实验¶

针对算法中各关键机制的理论与算法属性对比：

机制配置	理论遗憾率	对偶稳定性	计算复杂度	说明
本文完整模型 (PD-LSCVI-UCB)	$\mathbf{\widetilde{\mathcal{O}}(T^{2/3})}$	稳定有界（区间截断）	$\mathcal{O}(d^2	\mathcal{S}
无值函数截断（消去 Line 7）	$\widetilde{\mathcal{O}}(T^{3/4})$	稳定	$\mathcal{O}(d^2	\mathcal{S}
折扣因子近似（替换为 Hong et al. 方案）	理论失效	剧烈发散（$\mathcal{O}(\eta T)$ 漂移）	$\mathcal{O}(d^2	\mathcal{S}
无强对偶解耦机制	无法单独解耦	无法评估	无影响	无法从复合拉格朗日界推导出纯违背上界

关键发现¶

截断机制对实际探索的巨大影响：Ghosh et al. (2023) 的 UCB 探索置信参数随时域线性设定为 $\beta = dH$，由于未引入跨度截断，探索红利被严重放大，导致策略频繁陷入过度乐观的次优动作选择，表现几乎接近随机探索；而本文利用跨度 $\zeta$ 将探索半径收紧为 $\beta = \widetilde{\mathcal{O}}((\zeta+1)d)$，展现出优异的学习稳定性。
对偶变量约束的重要性：通过强对偶性引出的 $\lambda^* \le 1/\gamma$ 上界将对偶变量动态范围严格限制在 $[0, 2/\gamma]$ 内，杜绝了乘子在初始阶段因随机噪声导致数值爆炸并破坏策略价值估计的问题。

亮点与洞察¶

多面体相对内部与极点的几何巧用：在非凸且存在边界缺失的弱通信占用测度集合中，精准抓住其与外层闭凸多面体共享相对内部与极点的性质，以极度精妙的方式绕过了无法建立等价 LP 的理论死结，首次在平稳策略类上确立了强对偶性。
有限时域近似与值截断的适配衔接：敏锐指出了无约束平均奖励方法中折扣加倍法用于约束环境时的“对偶失稳”致命缺陷，转向 $H=T^{1/3}$ 的有限时域切片，成功让截断值迭代在 CMDP 中稳定着陆。
纯正的强对偶分析工具链：不仅将强对偶性用于概念证明，更将其作为贝尔曼最优方程对齐的数学支点，为纯违背界的推导开辟了简洁且极富技巧性的分析范式。

局限与展望¶

计算复杂度对状态空间大小的依赖：算法在执行值函数截断（第 7 行）时必须显式计算 $\min_{s'} \widetilde{V}_h^k(s')$，这引入了对原始状态空间基数 $|\mathcal{S}|$ 的线性依赖，在超大规模或连续状态空间下计算不可行。
非最优遗憾阶数 $\widetilde{\mathcal{O}}(T^{2/3})$：尽管改进了现有界，但弱通信平均奖励 CMDP 下的遗憾下界通常预期为 $\widetilde{\mathcal{O}}(\sqrt{T})$；如何通过更精细的方差减少技术或双边对偶平滑抹平此理论鸿沟仍是悬而未决的公开问题。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次建立弱通信平稳策略下平均奖励 CMDP 的强对偶性，理论突破意义显著。
实验充分度: ⭐⭐⭐⭐ 包含合成环境对照与数值收敛性验证，但受限于理论算法的理论属性，缺乏大规模真实物理任务验证。
写作质量: ⭐⭐⭐⭐⭐ 数学证明严谨完整，动机与推导脉络清晰流畅。
价值: ⭐⭐⭐⭐⭐ 为安全强化学习中极具挑战的弱通信非遍历环境提供了核心理论工具与新基准界。

算法	理论遗憾界 \(\mathrm{Regret}(T)\)	理论违背界 \(\mathrm{Violation}(T)\)	经验遗憾收敛性 (\(K=1000\))	经验违背表现 (\(K=1000\))
Random Agent	\(\mathcal{O}(T)\)（线性增长）	\(\mathcal{O}(T)\)（严重超标）	线性发散（无学习能力）	持续违背约束
Ghosh et al. (2023) [Alg. 2]	\(\widetilde{\mathcal{O}}(T^{3/4})\)	\(\widetilde{\mathcal{O}}(T^{3/4})\)	接近随机（探索过大）	接近随机策略水平
PD-LSCVI-UCB (本文)	\(\mathbf{\widetilde{\mathcal{O}}(T^{2/3})}\)	\(\mathbf{\widetilde{\mathcal{O}}(T^{2/3})}\)	快速达到亚线性收敛	有效满足约束并平稳收敛