Global Optimality for Constrained Exploration via Penalty Regularization¶
会议: NeurIPS 2026
arXiv: 2604.28144
代码: https://github.com/Flo-Wo/penalty-based-constrained-exploration
领域: 强化学习
关键词: 强化学习, 受约束探索, 状态占用度量熵, 罚正则化, 全局最后迭代收敛
一句话总结¶
针对受安全或模仿约束的最大熵探索问题，本文提出基于二次罚函数的单循环策略梯度算法 PGP，利用伪奖励构造规避复合非凸项的估计偏差，并证明了首个非渐近全局最后迭代多项式样本复杂度。
研究背景与动机¶
在无外在奖励信号的强化学习中，高效探索是获取环境全面状态表征的核心基石，经典理论通常将其形式化为最大化状态-动作占用度量（State-Action Occupancy Measure）的香农熵。然而在真实工业与机器人系统中，纯粹的无约束探索往往伴随着极大的安全隐患与物理损耗；实际场景要求智能体在探索未访问状态的同时，必须遵守安全界限、资源预算或对专家轨迹的模仿约束（如保证状态占用度量与参考分布的 KL 散度在阈值内）。这类受约束最大熵探索问题（Constrained Maximum-Entropy Exploration, CME）具有根本性的优化难度：由于占用度量熵以及广义凸约束不具备时间上的可加 Bellman 结构，经典的动态规划与价值函数迭代框架彻底失效。
为了使算法能够扩展至高维乃至连续控制场景，必须对策略进行参数化表示（如 Softmax 策略或神经网络）；但策略参数化会将占用度量空间原有的凸结构扭曲为参数空间中高度非凸的目标函数与非凸约束集。现有解决受约束凸强化学习的方案陷入了两难困境：基于模型的占用度量显式计数方法（如基于强 Slater 条件或 KL 正则化的原始-对偶算法）受限于离散网格与模型表征，无法向复杂连续场景扩展；而此前唯一面向通用策略参数化的免模型策略梯度基线（如 Ying 等人的原始-对偶 PDPG）仅能提供弱遗憾（Weak Regret）与遍历时间平均（Ergodic Average）保证。在实际部署中，策略参数网络的几何平均没有物理意义，且对偶乘子的振荡会导致各步策略在可行域边界反复横跳，无法保证最终输出的单批单体策略达到近乎可行且近似最优。
面对非凸参数化与无 Bellman 可加性的双重困境，本文选择另辟蹊径：不使用带对偶延迟更新的双循环或原始-对偶框架，而是直接在策略空间采用二次罚正则化构建无约束单循环目标。核心 idea：利用策略梯度定理将占用度量凸泛函的目标与二次罚函数梯度重构为统一的“伪奖励”（Pseudo-Rewards），借助单批次轨迹实现无偏导交互的梯度估计，并依托隐式凸性（Hidden Convexity）与强对偶性建立首个针对非凸参数化策略的全局最后迭代（Last-Iterate）收敛保证。
方法详解¶
整体框架¶
本文考虑有限折现马尔可夫决策过程 \(\mathbb{M} = (\mathcal{S}, \mathcal{A}, r, \mathbb{P}, \gamma, \mu_0)\)。令 \(\lambda^{\pi_\theta}(s,a) = (1-\gamma)\sum_{t=0}^\infty \gamma^t \mathbb{P}_{\mu_0, \pi_\theta}(s_t=s, a_t=a)\) 为策略 \(\pi_\theta\) 诱导的折现状态-动作占用度量，受约束最大熵探索问题形式化为： $$ \max_{\theta \in \Theta} F_1(\theta) \coloneqq \mathcal{H}(\lambda^{\pi_\theta}) = -\sum_{s,a} \lambda^{\pi_\theta}(s,a) \log \lambda^{\pi_\theta}(s,a) \quad \text{s.t.} \quad F_2(\theta) \coloneqq \mathcal{R}(\lambda^{\pi_\theta}) \le 0 $$ 其中 \(\mathcal{R}\) 为占用度量上的光滑凸泛函（如累积代价约束或模仿学习中的 KL 散度约束）。PGP 方法将其转化为二次罚函数无约束最小化问题： $$ \min_{\theta \in \Theta} P(\theta) \coloneqq -F_1(\theta) + \beta \mathcal{L}(F_2(\theta)), \quad \text{其中 } \mathcal{L}(\cdot) = [\cdot]_+^2 = (\max{0, \cdot})^2 $$ 整个算法遵循单循环流程：在每轮迭代 \(k\)，环境采集一批轨迹后，首先估计当前的经验占用度量 \(\lambda^{(k)}\)；随后利用反向传播分别计算目标项与约束罚项关于占用度量的泛函导数，将其作为伪奖励；进而利用 REINFORCE 风格的策略梯度定理一次性估计出罚目标的复合梯度，直接执行随机投影梯度下降步。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["当前策略采样轨迹批次"] --> B["占用度量经验估计<br/>单批次蒙特卡洛 / GMM-MLE 估计"]
B --> C["双分支伪奖励反向传播生成<br/>计算目标与二次罚泛函梯度"]
C --> D["单批次轨迹策略梯度估计<br/>复用轨迹与伪奖励避免跨项偏差"]
D --> E["隐式凸性单循环投影更新<br/>步长自适应收缩保证最后迭代收敛"]关键设计¶
1. 双分支伪奖励反向传播生成：将泛函复合导数无缝映射为标准策略梯度
在通用的非凸随机优化中，针对复合罚函数 \(\beta [\mathcal{R}(\lambda(\theta))]_+^2\) 求导时，根据链式法则会展开为外层乘子项 \(2\beta [\mathcal{R}(\lambda)]_+\) 与内层雅可比项 \(\nabla_\theta \mathcal{R}(\lambda(\theta))\) 的乘积。若采用常规随机估计算法，分别对函数值和梯度进行蒙特卡洛独立估计，两者的随机耦合会引入不随批次增大的交叉偏差（Cross-term Bias），迫使以往方法不得不借助双重嵌套采样、极高频函数评估或动量方差追踪技术。本文利用强化学习的特定结构，将目标与约束对策略参数 \(\theta\) 的梯度通过策略梯度定理建立桥梁： $$ \nabla_\theta F(\lambda(\theta)) = [\nabla_\theta \lambda(\theta)]^\top \nabla_\lambda F(\lambda(\theta)) = \nabla_\theta V^{\pi_\theta}(r)\Big|{r = \nabla\lambda F(\lambda(\theta))} $$ 算法在步骤 5 中显式构造两组伪奖励（Pseudo-Rewards）：目标伪奖励 \(g_O^{(k)} = \nabla_\lambda (-\mathcal{H}(\lambda))\big|_{\lambda = \lambda^{(k)}}\) 以及约束罚伪奖励 \(g_C^{(k)} = \nabla_\lambda (\mathcal{L} \circ \mathcal{R}(\lambda))\big|_{\lambda = \lambda^{(k)}} = 2[\mathcal{R}(\lambda^{(k)})]_+ \nabla_\lambda \mathcal{R}(\lambda^{(k)})\)。这使得外层非线性与内层导数的复杂计算完全收敛在占用度量维度，无需嵌套采样即可利用标准自动微分反向传播精确求出。
2. 单批次轨迹策略梯度估计：单批共享与复用消解非独立估计偏差
为了避免多次独立轨迹采样带来的样本复杂度膨胀，PGP 采用激进的单批次估计策略：在同一迭代中采集大小为 \(B\)、截断步长为 \(H\) 的轨迹批次 \((\tau_b^{(k)})_{b=1}^B\)。算法首先利用该批次所有轨迹计算出归一化经验占用度量 \(\lambda^{(k)} = \frac{1-\gamma}{B}\sum_{b=1}^B \sum_{t=0}^{H-1} \gamma^t \delta_{s_t^{(b)}, a_t^{(b)}}\)；随后以此经验分布求出伪奖励 \(g_O^{(k)}\) 和 \(g_C^{(k)}\)；最后在相同的轨迹集合上执行加权策略梯度计算： $$ \hat{g}{H,B}(r, \theta, (\tau_b) \gamma^k r(s_k, a_k)\right) \nabla_\theta \log \pi_\theta(a_t|s_t) $$ 虽然外层伪奖励与内层轨迹梯度共享同一批数据构成了强统计依赖，但作者严密证明了占用度量的集中不等式能够有效束缚该偏差，其偏差界为 }^B) = \frac{1}{B} \sum_{b=1}^B (1-\gamma) \sum_{t=0}^{H-1} \left(\sum_{k=t}^{H-1\(\mathcal{O}(\gamma^H + B^{-1/2})\)，方差界为 \(\mathcal{O}(B^{-1})\)。这不仅免去了维护额外值函数网络或双重采样的开销，还为有偏随机梯度下降（Biased SGD）奠定了数学可控性。
3. 隐式凸性单循环投影更新：依托局部反转与强对偶保证最后迭代全局收敛
尽管 Softmax 参数化诱导了高度非凸的参数空间曲面，但状态-动作占用度量空间本身是一个紧致多面体，且目标函数在占用度量空间保持严格隐式凸（Hidden Convex）。在锚定 Softmax（Anchored Tabular Softmax）参数化下，局部逆映射存在且具有 Lipschitz 连续性。本文进一步证明，将平滑凸约束 \(\mathcal{R}\) 复合二次罚函数 \([\cdot]_+^2\) 后，整体罚目标依然能够保持弱凸性与有界梯度平滑性（\(L_{P,\theta}\) 平滑度与罚参数 \(\beta\) 呈线性关系）。依托优化理论中的一阶压缩不等式，单循环投影更新步： $$ \theta^{(k+1)} \leftarrow \operatorname{proj}_\Theta \left[\theta^{(k)} - \eta (\hat{g}_O^{(k)} + \beta \hat{g}_C^{(k)})\right] $$ 能够单调压低罚目标间隙 \(P^{\mathsf{opt}}_{2,\beta}(\theta^{(k)}) \le \varepsilon\)。在比 Slater 条件更弱的强对偶性假设（允许可行域仅有边界或存在等式约束）下，理论设定罚参数 \(\beta = \mathcal{O}(\varepsilon^{-1})\)，即可将罚间隙无损翻译为目标误差 \(|F_1(\theta^{(N)}) - F^*| \le \varepsilon\) 和绝对约束违背 \(\mathbb{E}[[F_2(\theta^{(N)})]_+] \le \varepsilon\)。此设计从根本上规避了传统拉格朗日乘子在迭代后期的震荡，确保算法具备最后迭代全局收敛性质。
损失函数 / 训练策略¶
算法最终输出单批单体策略 \(\theta^{(N)}\)。对于给定的目标容差 \(\varepsilon > 0\)，理论确定的超参数调度关系为： - 学习率设为 \(\eta = \mathcal{O}(\varepsilon)\)（与罚平滑常数倒数匹配）； - 罚参数设为 \(\beta = \mathcal{O}(\varepsilon^{-1})\)，根据对偶乘子 \(\nu^*\) 理论标定为 \(\beta(\varepsilon) = (\nu^* + 1) \frac{\nu^* + \sqrt{(\nu^*)^2 + 2}}{\varepsilon}\)； - 采样截断步长 \(H = \mathcal{O}(\log(1/\varepsilon))\)，单批样本量 \(B = \mathcal{O}(\varepsilon^{-4})\)； - 总迭代轮数 \(N = \widetilde{\mathcal{O}}(\varepsilon^{-2})\)，从而获得总轨迹采样复杂度 \(\widetilde{\mathcal{O}}(\varepsilon^{-6})\)。在连续控制中，离散占用度量估计平滑迁移为基于 16 个高斯混合分量（GMM）的最大似然估计器。
实验关键数据¶
主实验¶
论文在两类代表性场景中验证性能：一是理论涵盖的离散网格世界（FrozenLake，含线性危险冰窟窿约束）；二是连续控制基准 SafeCartpole（车杆摆起受对称位置边界 \([-2.0, 2.0]\) 约束）与 PointMass（带参考策略的 KL 模仿约束）。在基准测试中，PGP 与当前代表性的策略级原始-对偶方法 PDPG（Ying et al., 2025）进行最后迭代稳定性对比。
下表统计了训练后期检查点的可行性达标比例（Grid World 为最后 1000 个 Epoch，SafeCartpole 为最后 500 个 Epoch）：
| 实验环境 | 评估指标 | PGP (本文方法) | PDPG 基线 | 提升幅度 |
|---|---|---|---|---|
| Grid World (离散 10 种子) | 约束违背 \(\mathcal{R} \le 0.1\) 达标率 | 97.21% | 65.33% | +31.88% |
| Grid World (离散 10 种子) | 严苛违背 \(\mathcal{R} \le 0.01\) 达标率 | 92.43% | 51.01% | +41.42% |
| SafeCartpole (连续 5 种子) | 摆起持续时间 SU > 1 步 | 87.23% | 59.47% | +27.76% |
| SafeCartpole (连续 5 种子) | 稳定摆起时间 SU > 60 步 | 86.11% | 41.64% | +44.47% |
| SafeCartpole (连续 5 种子) | 约束违背 \(\mathcal{R} \le 0.1\) 达标率 | 96.89% | 70.03% | +26.86% |
| SafeCartpole (连续 5 种子) | 严苛违背 \(\mathcal{R} \le 0.01\) 达标率 | 94.49% | 53.33% | +41.16% |
消融实验¶
针对罚系数 \(\beta\) 的敏感性，作者在 Grid World 与 SafeCartpole 任务上进行了宽范围检查点消融分析（探索收敛所需 Epoch 数以及最终收敛性能）：
| 任务配置 | 罚系数 \(\beta\) | 收敛 Epoch 数 | 最终熵指标 \(\mathcal{H}\) | 最终约束值 \(\mathcal{R}\) |
|---|---|---|---|---|
| Grid World | \(5 \times 10^{-3}\) | 2200 | 接近理论无约束上界 | 严格可行 (\(\le 0\)) |
| Grid World | \(10^{-2}\) | 2800 | 接近理论无约束上界 | 严格可行 (\(\le 0\)) |
| Grid World | \(10^{-1}\) | 3500 | 接近理论无约束上界 | 严格可行 (\(\le 0\)) |
| Grid World | \(1.0\) | 5000 | 接近理论无约束上界 | 严格可行 (\(\le 0\)) |
| Grid World | \(10.0\) | 7000 | 接近理论无约束上界 | 严格可行 (\(\le 0\)) |
| Grid World | \(100.0\) | 10000 | 接近理论无约束上界 | 严格可行 (\(\le 0\)) |
| SafeCartpole | \(10\) | 2500 | \(798.22 \pm 214.13\) | \(-12.78 \pm 8.42\) |
| SafeCartpole | \(50\) | 3500 | \(825.82 \pm 211.10\) | \(-13.94 \pm 8.67\) |
| SafeCartpole | \(100\) | 10000 | \(787.29 \pm 246.31\) | \(-12.50 \pm 7.82\) |
| SafeCartpole | \(200\) | 14000 | \(817.61 \pm 235.52\) | \(-13.72 \pm 8.12\) |
关键发现¶
- 对罚系数 \(\beta\) 极度鲁棒：实验表明，只要 \(\beta\) 跨越可行性阈值，在横跨多个数量级的变化范围内，策略最终收敛的熵值和安全约束水平保持高度一致，并不会损害纯探索能力；过高估计 \(\beta\) 带来的主要代价仅仅是线性的收敛速度放缓，无需精细调参。
- 解决对偶震荡难题：PDPG 等原始-对偶方法在训练后期对偶变量持续高频震荡，导致策略在安全区与违规区之间交替波动，导致后期检查点可行率极差（仅 50%~70% 达标）；而 PGP 作为纯原始单循环方法，后期检查点可行性超过 94%，展现了极强的最后迭代可靠性。
- 动态探索对称性与相变：在 SafeCartpole 连续任务中，策略呈现出从最初的粗糙随机摆起、过渡到利用对称性扩展全状态覆盖，再到后期逼近安全边界以最短时间完成摆起的清晰演变，最终学到了理想的 bang-bang 控制模式。
亮点与洞察¶
- 伪奖励机制消解复合导数偏差：将高维外层罚函数与占用度量导数转化为环境交互中的虚拟标量奖励，复用单批轨迹即实现了策略梯度的端到端计算。这种巧妙构造成型了纯原始单循环优化，规避了传统非凸罚优化中必须使用的双重循环或多重函数评估。
- 突破弱遗憾与时间平均的局限：在理论上首次为通用参数化策略给出了受约束凸探索的全局最后迭代非渐近保证。这在工程上具备极高价值，意味着训练结束时的最新单体网络可以直接上线，摆脱了以往参数空间难以求平均的部署死穴。
- 弱化几何假设至强对偶：理论不再依赖限制性极强的严格 Slater 内部可行性条件，允许包含等式约束或仅具边界可行域的复杂安全边界，拓宽了凸强化学习的应用边界。
局限与展望¶
- 样本复杂度上界偏保守：为严格压制蒙特卡洛占用度量估计在有偏策略梯度中的误差传播，理论推导给出了 \(B = \mathcal{O}(\varepsilon^{-4})\) 的单批规模与 \(\widetilde{\mathcal{O}}(\varepsilon^{-6})\) 的总样本复杂度；尽管消融实验表明在实际小批次下算法依然收敛稳健，但理论上引入方差缩减（Variance Reduction）以紧化复杂度仍是未决问题。
- 连续空间理论缺失：当前的隐式凸收敛定理依赖于离散状态动作空间中锚定 Softmax 的紧致多面体可逆映射，连续控制中依靠高斯混合模型（GMM）最大似然估计的泛化理论尚待补全。
- 约束非光滑性扩展：目前分析主要针对 \(L\)-光滑的占用度量泛函，对于具备不可导拐角或分段线性的非光滑硬约束，尚需发展基于精确罚（Exact Penalty）与近端算子（Proximal Point）的进阶理论。
相关工作与启发¶
- vs Ying et al. (2025) [PDPG]: 该工作是先前唯一针对通用策略参数化求解受约束凸 MDP 的方法，但采用原始-对偶机制，仅能给出弱遗憾与时间遍历平均界，训练过程频繁发生约束振荡；本文采用二次罚正则化单循环架构，实现了最后迭代强收敛且无震荡。
- vs Zhang et al. (2020) [Variational PG]: 该工作开创了无约束通用效用 RL 的变分策略梯度分析，但局限于无约束环境且假设拥有精确 \(Q\) 价值函数预知；本文将隐式凸拓展至带约束罚系统，并严谨刻画了截断与经验蒙特卡洛的双重随机偏差。
- vs Fatkhullin et al. (2023): 该工作在优化理论层面建立了隐式凸无约束随机优化的基础，但依赖无偏一阶预言机；本文解决了复合罚函数引入的有偏估计，建立了强对偶下罚参数缩放与最后迭代精度的定量映射。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 巧妙利用伪奖励将非凸策略参数下的复合罚项化解为单批次策略梯度，设计极富洞察力。
- 实验充分度: ⭐⭐⭐⭐☆ 覆盖网格离散与连续物理仿真，消融与对比充实，若增加高维视觉任务则更佳。
- 写作质量: ⭐⭐⭐⭐⭐ 数学证明严密自洽，从隐式凸机制到样本复杂度演化的逻辑链条极具说服力。
- 价值: ⭐⭐⭐⭐⭐ 填补了非凸受约束强化学习无最后迭代可部署策略的理论空白，对安全探索具有重大指导意义。