NeurIPS2026（任务队列归属；全文为 arXiv v1）强化学习机会约束贝尔曼分布证书逆向 KL 置信集方差缩减策略梯度选择后安全认证

Learning Chance-Constrained MDPs with Bellman Distributional Certificates¶

会议: NeurIPS2026（任务队列归属；全文为 arXiv v1）
arXiv: 2609.30856v1
领域: 强化学习
关键词: 机会约束、贝尔曼分布证书、逆向 KL 置信集、方差缩减策略梯度、选择后安全认证

一句话总结¶

论文将累计成本超标事件改写为剩余预算上的贝尔曼递推，在有界后继支持与认证规划预言机条件下得到近匹配的确定性策略样本复杂度，并为随机策略提供局部近似 KKT 优化与独立安全验证，合成及电网仿真实验展示了统计保守性与期望成本替代约束的区别。

研究背景与动机¶

传统约束马尔可夫决策过程常限制累计成本的期望，但较低的平均成本并不排除少量高成本轨迹。机会约束直接限制累计成本超过阈值的概率，更接近可靠性要求。两者并非简单换一个损失函数：期望成本可以逐步相加，超标概率却取决于整条轨迹，以及已经消耗了多少预算。

已知模型下，剩余预算扩展、分布动态规划和搜索可以处理这类事件；未知模型下，还必须解决数据驱动的策略选择问题。分别模拟每个候选策略会浪费样本，而在同一批数据上选出看起来安全的策略，再把固定策略的误差界直接套上去，也不能自动保证选择后的安全性。与此同时，机会约束规划本身的非凸与组合困难，不必然意味着统计上要为每个预算格、每个时刻或每个策略重新付费。

核心 idea：先把无限时域超标事件保守地压成有限预算事件，再用原始状态—动作行上的共享置信集认证所有候选策略；另一条无模型路线直接优化轨迹超标概率，但把最终安全判断交给独立验证数据。

方法详解¶

整体框架¶

输入是有限状态、折扣型环境，已知且有界的即时奖励与成本，以及每条机会约束的成本阈值和允许超标概率。输出可以是通过认证的策略，也可以是无法确认的 unresolved。原始目标是最大化累计奖励，同时限制每项累计成本的超标概率：

\[ q_{P,i}(\pi)=\mathbb{P}_{P,\pi,\mu}\!\left(\sum_{t=0}^{\infty}\gamma^{t}c_i(s_t,a_t)>d_i\right)\leq\delta_i,\qquad J_P(\pi)=\mathbb{E}_{P,\pi,\mu}\!\left[\sum_{t=0}^{\infty}\gamma^t r(s_t,a_t)\right]. \]

论文先建立共同的保守预算表示，然后给出两条替代路线，而不是先训练有模型方法、再训练无模型方法。有模型路线用生成模型采样原始转移行，后向计算鲁棒超标概率，并由认证规划器挑选策略。无模型路线用轨迹指示变量、似然比梯度和方差缩减更新生成候选，再独立验证。时间和剩余预算是策略可使用的轨迹参数，不表示环境突然变成了新的、必须独立采样的巨型状态空间。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境与机会约束"] --> B["保守预算表示"]
    B -->|生成模型采样| C["共享模型认证"]
    B -->|训练轨迹| D["轨迹梯度优化"]
    D -->|候选固定后使用新数据| E["独立安全验证"]
    C --> F["认证策略或无法确认"]
    E --> F
    F -->|返回策略时| G["执行时跟踪<br/>时间与剩余预算"]

图中的训练采样和执行数据流不同：认证使用训练模型或新验证轨迹，执行阶段只按策略及预算更新采取动作，不在每一步重新完成规划认证。合成实验采用平稳策略子类，所以其中的执行策略不必显式依赖预算。

关键设计¶

1. 保守预算表示：让有限超标事件覆盖无限时域风险

直接截断累计成本可能漏掉截断点之后的超标。作者先预留一个折扣尾部额度，再把初始预算向下取整、每步折扣成本向上取整。尾部额度不是超标概率，而是累计成本上界的一部分；网格宽度也不是统计置信半径。二者负责把原始事件包进可计算的有限事件。

\[ H=\left\lceil\frac{\log(1/((1-\gamma)\alpha_{\rm tail}))}{1-\gamma}\right\rceil,\qquad b_i^0=\left\lfloor\frac{d_i-\alpha_{\rm tail}}{\eta_i}\right\rfloor,\qquad w_{i,h}(s,a)=\left\lceil\frac{\gamma^h c_i(s,a)}{\eta_i}\right\rceil. \]

每步将整数预算减去相应收费；一旦负数就置为失败值并保持失败。初始预算为负时直接从失败值开始。策略可依赖当前状态、预算向量和时刻，因此给定这些量以后，未来有限超标概率不再需要完整历史。附录 B 用后向归纳证明这种充分性：终点只看预算是否失败，前一时刻再对下一状态求期望。

附录 C 的安全论证是逐轨迹的：若整数预算一直未失败，则真实前缀成本不超过预留尾部后的阈值；折扣尾部又不超过预留额度。因此原始无限轨迹超标必定意味着有限预算失败。这个方向很重要，证书允许误拒绝安全策略，却不能靠向下取整成本来获得虚假的安全性。

保守性也有代价。预算网格的舍入损失随证书长度累积，原始阈值附近的概率质量可能被算成失败。因此原始安全最优策略不一定属于舍入后的可行集；即便模型已知且确定，也不能自动消除这部分差异。

2. 共享模型认证：用同一批原始转移行覆盖选择后的策略

有模型路线对每个原始状态—动作行抽取独立后继样本，形成一个共享经验转移核。即时奖励和成本已知。置信集使用经验行到候选行的逆向 KL，而不是要求所有可能后继都已被观察到；后者在罕见后继存在时会过早排除真实模型。

\[ \kappa_n=\frac{(d_0-1)\log(n+1)+\log(|\mathcal{S}||\mathcal{A}|/\zeta)}{n},\qquad \mathcal{C}_{s,a}=\{p\in\Delta(\mathcal{S}):\mathrm{KL}(\widehat{P}_{s,a}\|p)\leq\kappa_n\},\qquad \overline q_i^\pi(s,b,h)=\sup_{p\in\mathcal{C}_{s,a}}p^\top\overline q_i^\pi(\cdot,B_h(s,a,b),h+1),\quad a=\pi_h(s,b). \]

超标表在终点取预算失败指示值，随后从后往前递推。因为表里存的是失败概率，安全认证必须对置信集中的转移做最大化，而不是采用乐观最小值。奖励排名则使用普通经验贝尔曼求值；安全与奖励的角色不对称，不能把奖励高解释为证书强。

附录 D 先通过有界支持上的类型计数获得所有原始行同时覆盖的事件，只对原始行做联合界。固定这个事件后，真实行处处在置信集中，贝尔曼单调性保证鲁棒表高于真实舍入失败概率。于是证明对整个策略类同时成立，包括看过数据才选出的策略；复用的是转移行数据与置信集，不是声称每个策略共享一张数值完全相同的表。

附录 E 的关键不是把每一步误差线性累加，而是将行 KL 沿整条增广轨迹用链式法则合并，再用 Pinsker 不等式转成事件概率误差。矩形置信集的鲁棒后向最大化可以由随时刻和预算变化的对抗转移实现；它与经验轨迹之间也满足同样的 KL 控制。两次转移界夹住真实失败概率和鲁棒证书：

\[ r_n=\sqrt{H\kappa_n/2},\qquad 0\leq\overline q_{i,H,\eta}(\pi)-q_{P,i}^{\rm rnd}(\pi)\leq2r_n,\qquad |\widehat J(\pi)-J_{P,H}(\pi)|\leq R_Hr_n,\quad R_H=\sum_{h=0}^{H-1}\gamma^h. \]

因此不必对全部策略或时间—预算表条目做联合界，预算空间大小也不进入行覆盖事件。不过预算向量的笛卡尔积仍可能使规划非常昂贵，这个统计结论不消除计算开销。

算法实际将证书阈值收紧为 \(\delta_i-3\rho/4\)。定理比较的是采样前固定有限策略类中的非空舍入内点集合，而不是不受限制的原始机会约束最优值：

\[ V_\rho^\star=\max_{\pi\in\Pi_{\mathcal O}:\ q_{P,i}^{\rm rnd}(\pi)\leq\delta_i-\rho\ \forall i}J_P(\pi),\qquad D=\widetilde O\!\left(d_0|\mathcal S||\mathcal A|\left[\frac{1}{(1-\gamma)^3\varepsilon^2}+\frac{1}{(1-\gamma)\rho^2}\right]\right),\qquad J_P(\widehat\pi)\geq V_\rho^\star-\varepsilon-\xi. \]

定理 1 还要求已知且固定的后继支持数量上界，不随状态规模、精度或折扣变化；后继身份与概率可以未知。网格与尾部额度取 \(\min\{\varepsilon/8,(1-\gamma)/128\}\)，规划器需返回证书可行且经验价值距最优至多求解误差的策略。样本足够时证书误差至多内点裕量的一部分，比较器仍通过收紧测试，所以高概率下不会返回无法确认，并且对原始机会约束安全。

与原始最优值建立进一步联系，需要比较器在舍入影响的阈值邻域内没有过多概率质量；附录 E 明确提出了这一附加边界条件。不能省去它，直接宣称获得原始全局最优策略。附录 F 分别构造奖励辨识与安全边界辨识困难实例，两者每行至多两个后继，通过自适应 Bernoulli 测试给出匹配的两项下界；把两个困难族合并，得到同阶的和，而不是要求一个实例同时承担两种难度。

认证规划器是预言机假设。附录 G 用确定性链上的选择/跳过动作编码背包问题，说明已知确定模型下精确规划仍是 NP-hard。因此论文的近匹配结论是统计样本复杂度结果，不是多项式时间求解保证。

3. 轨迹梯度优化：直接估计机会事件，但只保证局部近似 KKT

无模型路线不拟合转移核。每条长度固定的轨迹维护完整预算向量，终点失败指示变量同时提供所有约束的样本。固定轨迹的预算与失败指示值不随策略参数求导，策略参数只改变动作概率；所以失败指示值乘整条轨迹的动作对数概率梯度之和，给出超标概率的无偏梯度。

\[ \chi_i=\mathbb I\{b_{i,H}<0\},\qquad \widehat{\nabla g_i^H}(\theta)=\chi_i\sum_{t=0}^{H-1}\nabla_\theta\log\pi_\theta(a_t\mid s_t,t,b_t),\qquad g_i^H(\theta)=q_{P,i}^H(\theta)+2\rho-\delta_i,\qquad f_H(\theta)=-(1-\gamma)J_P(\pi_\theta). \]

奖励梯度用几何停止轨迹估计归一化的无限时域收益，而不是悄悄把奖励也截成有限时域目标。无模型训练收紧原始允许超标概率，为优化误差与最终验证误差留空间。约束与奖励采样长度不同，论文样本界计数的是期望环境转移量，不能把梯度调用次数直接当成交互步数。

优化器引入非负松弛变量，使用固定二次罚函数与近端更新，近端操作只约束松弛变量；参数迭代被假设留在开放参数域内的紧凸集合。大批次周期性刷新梯度，小批次则估计相邻迭代的梯度差。轨迹分布随策略变化，差分必须乘似然比校正，不能直接复用旧轨迹梯度当成无偏差分。

罚函数梯度中的约束 Jacobian 与约束值乘积使用独立样本，避免相关性导致乘积偏差。附录 H.8 的差分对这两个独立因子分别做换测度校正。正的动作概率、受控的似然比矩、得分及其导数矩、均方光滑差分和有限方差都是实质条件，不由“策略梯度”这个名称自动满足。

尤其要注意假设 3 的残差支配条件：固定罚函数的一阶驻点并不一般等同于约束问题的 KKT 点。作者额外假设，访问点的参数驻点残差、松弛驻点残差和约束残差之和，被罚函数的复合驻点残差乘一个有限常数控制。再结合松弛误差界、可行初始化、有限初始目标差、有界乘子和松弛量，才能将方差缩减的驻点界转成 KKT 残差界。

这里的 KKT 残差同时衡量拉格朗日梯度、正约束违反量和互补性，且对一个有界非负乘子集合取最小值。定理给的是随机候选的期望残差不超过容忍度，优化部分对容忍度呈三次逆幂依赖；不是每次运行都获得严格可行点，更不是全局收益最优。局部常数可依赖策略类、证书长度、网格、裕量及访问集合，不能将它们理解成普适小常数。

4. 独立安全验证：认证被接受的候选，而不是承诺一定返回策略

完成训练后，算法从已经算出的后更新迭代中均匀随机选一个候选，随后用新轨迹验证。理论对应的不是最后一个迭代，也不是根据真实模型选出的最高收益迭代。独立性使得条件于训练数据后，候选固定，验证失败指示值就是固定 Bernoulli 均值的估计。

\[ M_{\rm val}=\left\lceil\frac{2\log(2m/\zeta)}{\rho^2}\right\rceil,\qquad \widehat q_{i,\rm val}^H(\theta_{\rm cand})+\rho/2\leq\delta_i\quad\forall i. \]

Hoeffding 界与约束间联合界控制验证误差，再利用保守预算的逐轨迹包含关系，把验证通过转成原始无限时域安全。这个安全证明不依赖训练是否达到局部 KKT 点；但期望 KKT 保证本身也不能替代验证。

定理 3 的准确陈述是：高概率下，算法要么接受一个真正安全的候选，要么返回 unresolved。若候选的真实舍入风险已低于允许风险至少一个验证裕量，同一事件上保证接受。未通过测试只表示数据或候选不足以认证，不等于已经证明它不安全，更不保证换一批数据就会通过。

一个完整示例¶

附录 I.1 的合成环境只有坏状态产生一次单位成本，折扣为 \(\gamma=0.95\)，阈值为 \(d=0.50\)。因为第十三时刻的折扣成本仍大于阈值、第十四时刻则小于阈值，原始超标事件恰好是到第十三时刻为止访问坏状态。环境有自环，吸收时间并无固定上界，但这项机会事件可精确用有限递推计算，不需要把整个环境硬改成固定时域。

在这个环境上，有模型实验枚举平稳确定性策略，用缓冲失败概率筛选后再排名奖励；无模型实验则训练每个决策状态一个 logit 的 Bernoulli 策略。独立验证最终检验的是随机抽到的候选，而不是训练曲线的终点。这也说明“优化曲线看起来安全”和“指定策略获得独立认证”是两个不同结论。

损失函数 / 训练策略¶

无模型实验使用归一化负收益加二次松弛罚项，固定罚系数为 80，步长为 0.01；风险裕量为 0.0035，训练风险阈值为 0.123。每 20 次更新用 2,048 个独立轨迹三元组刷新，其余更新使用 128 个三元组及似然比校正，共执行 250,000 次更新。

每个三元组分别提供独立奖励梯度、风险梯度与风险值样本，松弛变量投影到非负半轴。实验累计使用 168 million 条训练轨迹；这不是用少量轨迹就完成优化的证据，也不是对所有局部理论假设的逐项数值验证。

实验关键数据¶

主实验¶

合成任务有 8 个决策状态、1 个坏状态、1 个吸收终点，两个动作都有 0.06 自环概率。安全动作奖励为 0.45、坏转移概率为 0.002；机会约束允许风险为 0.13。所有方法在同一个 256 策略类内比较，每个预算使用 150 次独立经验模型抽样，不同预算不是同一数据流的嵌套前缀。下表的收益是选出策略后在真实核下精确计算的平均值。

总转移样本	贝尔曼缓冲选择器收益	Markov-CMDP 收益	同类机会约束预言机	安全试验数：缓冲 / Markov
8,000	3.562	4.026	4.404	150/150 / 148/150
800,000	4.391	3.928	4.404	150/150 / 150/150

低预算时缓冲策略更保守，收益反而更低；论文报告从测试预算 32,000 起其平均收益超过替代方法。缓冲方法每个测试预算均出现 150/150 安全，但这只是有限重复实验；相应逐点双侧 95% Clopper–Pearson 区间约为 [0.9757,1]，不能解释为真实失败概率恰为零。

无模型结果需区分随机候选、最后迭代以及参考最优值。下表保留原文精度；训练与显示使用 seed 11，随机候选选择是训练后另一次抽样。

策略 / 参考	迭代	真实收益	真实风险	独立验证
初始随机策略	0	4.16658	未单独报告	未执行
随机选中候选	59,611	4.29506	0.12601	通过
最后迭代	250,000	4.36245	0.12769	不是被验证候选
枚举确定性可行参考	不适用	4.40376	未单独报告	不适用
多起点随机策略数值参考	不适用	4.50970	0.13	不适用

候选使用 602,267 条新验证轨迹，风险估计为 0.126168，加 0.00175 裕量得到 0.127918，低于 0.13 因而接受。最后迭代收益更高，但不能把其数值替换进候选认证结果；多起点随机参考也不是已证明的全局最优值。确定性参考的 4.40376 与上表 4.404 是同一参考的不同报告精度。

消融实验¶

论文没有标准神经模块移除表；以下是原文支持的机制与协议分析，不将不同数据协议伪装成同一算法的严格消融。

配置 / 协议	定量设置	分析边界
合成贝尔曼缓冲	固定 log 项 2；尺度 0.75；16 个采样行	共享模型；实用缓冲不是定理常数
合成 Markov-CMDP	期望成本阈值 0.065	经验替代约束无额外不确定性缓冲
IEEE 14-bus 策略类	176 状态；5 动作；145 策略；60 次试验	同类比较，不能外推全部控制策略
IEEE 有限预算证书	折扣 0.85；成本阈值 0.30；风险阈值 0.15；尾部 0.005；网格 0.0015；长度 48；整数预算 196	保守舍入与统计缓冲是不同来源
IEEE 采样与评估	每行 25, 50, 100, 200, 500, 1000 样本；评估 50,000 条 100 步轨迹	安全批次跨阶段独立；奖励模型另采
IEEE 实用缓冲	尺度 0.20/H；置信参数 0.05；替代成本阈值 0.045	校准常数；未使用定理的风险裕量收紧

IEEE 14-bus 实验将储能荷电状态、时间块和负荷区间离散化，设备位于 bus 14。动作控制充电、放电或闲置，奖励是归一化运行收益，安全成本是线路过载严重程度。145 个候选包含 144 个阈值策略和始终闲置策略；不是任意连续电网控制器的比较。

其安全数据在各贝尔曼阶段之间独立，奖励排名还使用另一份独立经验模型。这与定理 1 复用同一个原始行模型的协议不同，不能直接把图中每行样本数理解成定理的总采样预算。缓冲的 0.20/H 系数经过校准，也未施加理论风险裕量收紧，所以图 1 展示机制，而非验证定理覆盖常数。

关键发现¶

合成实验区分了随数据增加而减少的统计保守性，与 Markov 不等式替代条件自带的结构保守性；更多数据不会让后者自动等于机会约束。
合成不同预算独立抽样，因此单次试验的收益不必单调提升；曲线均值趋势不能转成每条样本路径的单调保证。
IEEE 图示风险由真实核下有限 Monte Carlo 估计，收益与期望成本由已知有限核求值；正文没有列出的图上收益或风险数值不作猜测。

亮点与洞察¶

安全认证与奖励优化使用不同贝尔曼对象。失败概率要悲观上界，奖励只负责在已认证集合中排名，避免把“看起来高收益”与“有风险证据”混为一谈。
共享行置信事件把选择后安全问题转成确定性的策略一致论证。轨迹 KL 控制让预算表的计算规模不必变成额外统计维度，这比逐表条目叠加置信缓冲更重要。
两条路线提供不同的安全接口：有模型方法在共同覆盖事件上认证任意候选，无模型方法则以新验证数据认证指定候选。可以迁移的是认证边界与数据独立性，而不是随意复用验证集筛选许多策略。

局限与展望¶

有模型主定理限于固定有界后继支持、生成模型访问、已知奖励成本及认证规划器；对复杂环境、在线安全探索或未知成本学习没有直接保证。预算组合与 NP-hard 规划仍是实现瓶颈。
收益比较器必须具有舍入后的内点裕量。若真实累计成本在阈值附近集中，网格变细也需要另外分析边界概率质量，不能只凭原始安全性替代这项条件。
无模型理论依赖强局部残差支配、正策略概率、似然比矩与可行初始化等条件；只给期望近似 KKT，不给全局最优，验证还可能无法确认。更可检验的正则条件与明确求解器是重要后续方向。
实验有合成诊断、无模型训练和电网仿真，不能称为纯理论论文；但大规模训练轨迹开销与校准缓冲也限制了样本效率的经验说服力。IEEE 风险是有限轨迹估计，不是临床证据或真实电网部署安全认证。

评分¶

新颖性: 4/5 — 共享逆向 KL 行证书与策略一致轨迹转移论证是主要贡献。
实验充分度: 3/5 — 有机制诊断和电网仿真，但实用协议与定理不同，训练开销较大。
写作质量: 4/5 — 附录明确交代比较器、局部假设和实验边界，理解时需细读这些条件。
价值: 4/5 — 清楚区分机会约束的统计难度、计算难度与最终认证责任。