VESPA:面向安全强化学习的可验证符号策略自适应
VESPA: Verifiable Symbolic Policy Adaptation for Safe Reinforcement Learning
作者提出 VESPA,用形式化验证的反例微调决策树策略;在 MountainCarContinuous 上 60 次运行中 53 次得到全起点安全证明。
- 安全强化学习需要保证策略不违反安全约束,但形式化验证只给出安全/不安全判定;策略不安全时只能从头重训再验证,训练和验证代价都高,流程低效。
- VESPA 交替进行可达性验证与微调:对 SYMPOL 决策树策略做集合传播验证,把违反约束的集合沿动作历史回溯得到反例区域,以概率 p 从这些区域采样起点用 PPO 微调,循环直至证明安全。
- 在 CartPole 上平均验证安全步数从 63.8 升至至少 92.7,两轮达到基线 Uninformed 十轮的水平,但回报从 496 降到 423;在 MountainCarContinuous 上 60 次运行中 53 次得到全起点安全证明,回报从 84 升到 92。
- 作者指出证明依赖已知环境动力学且只覆盖有界时域,验证开销随状态维度和策略规模增长,CP 上证明因内存限制止步于 200 步之前;实验仅覆盖两个经典控制环境和 SYMPOL 树策略。
- 被测模型
- SYMPOLVIPER
- 基准
- CartPole (CP)MountainCarContinuous (MC-C)
- 指标
- verified safe steps (n⋆)ratio of safe start state regionsaverage return
VESPA 框架面向安全强化学习,把形式验证的反例用作微调训练信号,让不安全的决策树策略变安全或大幅接近安全。在 CartPole 上,经验证的安全步数均值从 63.8 升至至少 92.7,两次迭代即达到无反例时十次迭代的效果。在 MountainCarContinuous 上,60 次运行中 53 次将不安全策略转为安全。
深度解读
这篇论文试图解决什么问题?
验证只给安全/不安全判定,策略不安全时只能从头重训;VESPA 把验证反例变成微调信号。
核心问题:形式化验证只能判定策略安全与否,无法指导如何修复不安全的策略,导致"重训—再验证"循环低效。
- 场景与重要性:安全强化学习要求智能体不采取危险动作,在机器人、自动驾驶等安全关键领域,作者认为任何概率性安全保证都不足以部署,需要对部署策略做形式化验证。
- 现有方法的不足:可达性分析等离线验证只对固定策略给出一次性的 safe/unsafe 判定;判定不安全后只能训练并验证多个独立候选,直到某个碰巧通过,作者称这一过程低效甚至不可行。
- 核心观察:对轴对齐分裂的符号树策略(SYMPOL)做可达性验证时,不安全判定天然附带反例(策略可达且违反约束的状态);把这些反例回溯到前驱状态区域并作为微调起点,可以定向教会策略避开违反约束的轨迹。
- 论文提出:VESPA(VErifiable Symbolic Policy Adaptation),一个交替进行验证与微调的框架,含三个组件:面向树策略的可达性验证器、基于回溯的反例提取、混合原始起点与反例起点的策略适配。作者称在 CartPole 上验证器可扩展到平均至少 92.7 步,多于先前工作的 10 步。
有哪些相关研究?
相关工作分三组:树策略验证、DNN 策略验证与修复、shielding;VESPA 的差异在回溯反例区域作微调起点。
决策树策略的验证
- Bastani, Pu, and Solar-Lezama (2018)——用 SMT 求解器验证从 DNN 蒸馏出的树策略,证明了 CartPole 策略前 10 步的正确性;论文称 VESPA 的验证确认了这一点,并在更晚的步数发现具体不安全状态。
- Jain et al. (2024) 与 Vinzent, Sharma, and Hoffmann (2023)——用树专用求解器 Veritas 和策略谓词抽象(PPA)构建无界时域的可达状态集。
- Schilling et al. (2023)——在连续时间下对树策略传播可达状态集;论文说明 VESPA 需要验证安全步数、反例区域及其发生步数,因此同样选择基于集合的表示。
DNN 策略的验证与修复
- Trainify(Jin et al. 2022)——把状态空间离散为抽象状态,在抽象状态上训练和验证 DNN 策略,并按违反约束的位置细化离散化、从头重训。
- Boetius, Leue, and Sutter (2023)、Yang et al. (2022)、Wu, Zhang, and Vorobeychik (2024)——用验证器反例修复 DNN 策略;论文指出它们在验证器找到反例的位置训练(加惩罚或对验证界加损失),而 VESPA 把反例区域沿时间回溯、只用作微调起点。
Shielding
- Alshiekh et al. (2018)——shielding 在运行时加一个静态组件限制或覆盖所学策略的动作;Anderson et al. (2020) 在该框架下交替训练 DNN 策略与可验证符号策略。论文指出 shielding 把验证问题转移给必须自身可证明安全、且部署时必须在场的 shield,而 VESPA 直接验证并适配所学策略本身。
基线与基准:实验基线是作者称为 Uninformed 的方法(同一循环、相同设置,但微调起点全部从标准初始分布采样,即 p = 0),另用相同验证设置验证 VIPER 提取的树;基准为 CartPole 与 MountainCarContinuous。作者将本文定位为:把验证输出(反例)用作微调训练信号,而非仅作判定或运行时屏蔽。
论文如何解决这个问题?
交替循环:集合传播验证树策略→回溯提取反例区域→以概率 p 从反例区域采样起点用 PPO 微调→再验证。
整体思路:VESPA 把可达性验证的输出当作训练信号,对预训练的轴对齐决策树策略做"验证—提取反例—定向微调"的交替循环,直到策略被证明安全或达到迭代上限(Figure 1)。
问题设定与安全定义
- 考虑状态空间 S ⊆ R^d、确定性转移函数 f、初始状态集 S0 的 MDP;给定已预训练的轴对齐决策树策略 π,不假设其获得方式。
- 不变式(invariance)安全定义为 ∀ s0 ∈ S0 ∀ t ≤ n: st ∈ Ssafe,即 n 步内不离开安全集;有界可达式(reachability)要求 n 步内某步进入目标集 Sgoal。
- 论文聚焦不变式约束(CP)与可达式约束(MC-C),时域 n = 200。
可达性验证(Section 2.2)
- 用 d 维 box 或 zonotope 表示状态集,逐步传播:树策略的 L 个叶区域把每个集合切成单一动作的片段,box 下切分精确,zonotope 下需外包过近似;环境动作用区间算术过近似为 fˆ。
- 安全判定恒为证明,不安全判定可能不精确;用 Eq. 6 的两种无损归约(丢弃完全重复、丢弃被同动作集合包含的集合)降低碎片化。
- 不变式属性下,首个违反步 n⋆ + 1 处离开 Ssafe 的集合即反例;可达式属性下,时域结束仍未进入 Sgoal 的集合为反例。
反例提取(Section 2.3)
- 不直接用违反集合本身(违反已发生、无法挽回),而是沿每个集合记录的动作历史用逆转移 fˆ−1 回溯 n_lookback 步,得到前驱状态区域,称为反例区域 b̂,全体记为 B̂。
- n_lookback 依属性类型选取:可达式属性需要更大的值,因为未达目标在时域末尾才被发现,可能源于任意更早步。
策略适配(Section 2.4)
- 修改初始状态分布:Dmix = (1−p) D0 + p/(|B̂|) ∑b̂ U(b̂),即以概率 p 均匀取自各反例区域、以 1 − p 取自环境标准起点分布;作者称这既聚焦困难边缘情形又防止遗忘。
- 微调支持任意 on-policy 算法;实验用 PPO,critic 从头重初始化(数据分布已变),每个 episode 在剩余时域结束时截断。
- 候选策略只有在验证深度不更低(CP)、或被证安全或安全起点区域比例严格更高(MC-C)时才替换当前策略;随后再验证,循环至证明安全或迭代上限。
论文做了哪些实验?
在 CP 与 MC-C 上对比 VESPA 与 Uninformed:CP 验证步数两轮抵十轮但回报下降,MC-C 53/60 次全证明。
实验设置
- 被测策略:SYMPOL 配置的深度 7 轴对齐树(PPO 预训练,CP 50M 步、MC-C 1M 步);CP 用 12 个评估种子 × 剪枝/未剪枝 = 24 个输入策略,MC-C 用 6 个种子 × 2 = 12 个(Table 4);另验证 21 棵 VIPER 蒸馏树(附录 F)。
- 环境:CartPole(CP,不变式约束,box 表示)与 MountainCarContinuous(MC-C,可达式约束,zonotope 表示,S0 均分为 2^14 = 16384 个起点区域分别验证),时域 n = 200(Table 5)。
- 基线:Uninformed,同一循环与设置,仅微调起点全部来自标准初始分布(p = 0)。
- 指标:CP 主指标为验证安全步数 n⋆(内存耗尽时报下界);MC-C 为安全起点区域比例;另报告获得安全策略的运行数与 30 个贪心 episode 的平均回报。
- 运行数与迭代:CP 每方法 48 次运行(24 策略 × 2 微调种子),至多 11 轮;MC-C 每方法 60 次(12 策略 × 5 种子),至多 5 轮;每轮 10^5 环境步。
- 关键超参:p = 0.5(VESPA)/ 0(Uninformed);n_lookback:CP 为 10(在 2、6、10、14 中随机搜索 25 组选出),MC-C 为 200(附录 E)。
主结果
据 Table 1(CP,48 对运行)与 Table 2(MC-C,60 对运行):
表格较宽,可左右滑动
环境 指标 初始 VESPA 最终 Uninformed 最终 CP 验证安全步数(均值) 63.8 ≥92.7(+28.9) ≥85.2(+21.4) CP 平均回报 496 423 477 MC-C 安全起点区域比例 55.7% 99.6% 99.2% MC-C 全起点证安全的运行数 0 53/60 46/60 MC-C 平均回报 84 92 92 - 作者称 VESPA 的优势出现得早:CP 上两轮后平均至少 85.1 步,Uninformed 需十轮才达到同一值(Figure 4)。
- 配对比较:3 轮后 VESPA 在 48 对中 26 对验证更深、5 对更浅;最后一轮后 14 对领先、2 对落后,其余相等或不可比(均为下界)。
- MC-C 上 42 对双方都得证的运行中,VESPA 平均需 2.2 轮、Uninformed 2.7 轮;作者指出 MC-C 的证明不损失回报。
回报与安全解耦(Figure 3)
- 测了什么:3 棵 VIPER 树(d3、d9、d10)与 3 个 SYMPOL 策略(深度 7),平均回报均接近上限(≥490/30 episodes)。
- 结果:6 个策略无一被验证 200 步安全,其中一个仅验证 27 步;d10 在 108 个采样起点中仅 12 个导致违反,1000 episode 的评估难以发现。
- 作者解读:即使奖励完全覆盖安全约束,平均回报也是安全的差代理;短时域验证(如先前工作的 10 步)下 6 个策略全部被证安全,会掩盖这些违反。
过近似的影响(附录 B)
- 测了什么:验证中集合传播相对精确可达集的过近似程度。
- 结果:CP 上 18,581 个 box 单步过近似的中位数不超过精确像宽度的 0.02%;MC-C 上 2,737 个无证明起点区域中 98.6% 含有具体未达标轨迹,安全区域比例至多被低估 1.8 个百分点。
- 作者解读:理论上部分反例可能是过近似的产物,但因反例明显改善了微调(Figure 4),作者认为该效应要么不存在、要么小到不影响微调。
其他消融与分析
- 内存限制:CP 上 48 次 VESPA 运行中 40 次、Uninformed 中 26 次因验证内存耗尽提前结束,无运行获得全 200 步安全判定(Table 1)。
- 剪枝:CP 上 VESPA 的剪枝/未剪枝组平均增益 +31.9/+25.9 步,MC-C 上 26/30 与 27/30 次得证;作者称未见剪枝的系统性影响(Table 3)。
- VIPER 树:21 棵 VIPER 蒸馏树无一被验证 200 步安全,其中 20 棵找到 200 步前违反约束的具体 episode(附录 F)。
- 回报下降的解释:CP 微调 episode 在 200 步结束而回报按 500 步计,作者称这可以解释微调后 CP 策略回报偏低(附录 E)。
有什么可以进一步探索的点?
作者指出证明依赖已知动力学、有界时域且验证开销随维度增长;后续方向是更省内存的表示与树集成。
作者指出的局限与后续方向
- 证明针对策略和环境模型,因此动力学必须已知,且只覆盖有界时域 n(Section 3.2 Limitations)。
- 可达性分析的开销随状态维度数和策略规模增长;CP 上证明因此在 200 步前终止(Section 3.2 Limitations)。
- CP 上未证明全时域安全,限制因素是验证所需内存而非策略适配;后续可研究更省内存的状态表示(Section 5)。
- 后续可把 VESPA 扩展到树集成,如 GRANDE(Section 5;附录 F 亦称树集成策略是未来工作)。
实验覆盖范围
- 被测环境为 CartPole 与 MountainCarContinuous 两个经典控制基准,时域 n = 200(Section 3.1)。
- 被测策略为 SYMPOL 深度 7 树(CP 24 个、MC-C 12 个输入策略),另验证了 21 棵 VIPER 蒸馏树;微调仅用 PPO(Section 3.1、附录 F)。
- 基线只有 Uninformed(同一循环、仅起点分布不同),未与其他修复或验证方法做实验对比(Section 3.1)。
- 运行规模:CP 每方法 48 次、MC-C 每方法 60 次;回报按 30 个贪心 episode 计(Figure 3 用 1000 个)(Section 3.1)。
- 论文未报告微调单次运行的耗时或总训练开销;验证耗时仅给出中位数(CP 180 s、MC-C 23 s,Table 5)。
总结一下论文的主要内容
VESPA 把可达性验证的反例回溯后用作微调起点,CP 验证深度两轮抵十轮,MC-C 53/60 次获得全起点安全证明。
一篇安全强化学习论文,针对"验证只给判定、不给修复路径"的问题:策略被判定不安全后,只能从头重训再验证,代价高。
- 方法:VESPA 对轴对齐决策树策略(SYMPOL)做集合传播可达性验证,把违反约束的集合沿动作历史回溯 n_lookback 步得到反例区域,以概率 p = 0.5 从这些区域采样起点、用 PPO 在剩余时域上微调,候选通过验证才替换当前策略,循环至证明安全。
- 验证器:利用树策略的轴对齐分裂精确切分状态集,CP 用 box、MC-C 用 zonotope;安全判定恒为证明。作者称 CP 上验证深度达平均至少 92.7 步,多于先前树策略验证工作的 10 步。
- CP 结果:平均验证安全步数从 63.8 升至至少 92.7,两轮达到基线 Uninformed 十轮的水平;代价是平均回报从 496 降到 423(Uninformed 降到 477),且 48 次运行中 40 次因验证内存耗尽提前结束,无运行获得全 200 步证明。
- MC-C 结果:12 个输入策略初始平均仅 55.7% 起点区域可证达标;5 轮内 VESPA 在 60 次运行中 53 次得到全起点安全证明(Uninformed 46 次),平均回报从 84 升到 92。
- 另一发现:6 个平均回报接近上限的 CP 策略无一被验证 200 步安全;作者据此认为平均回报是安全的差代理,即使奖励完全覆盖安全约束。
- 作者结论:验证反例是有效的训练信号,可系统性提升树策略安全性;局限在于证明依赖已知动力学、有界时域,验证开销随维度与策略规模增长,后续方向包括更省内存的表示和扩展到树集成。