Skip to content

VESPA: Verifiable Symbolic Policy Adaptation for Safe Reinforcement Learning

VESPA: Verifiable Symbolic Policy Adaptation for Safe Reinforcement Learning

arXiv: 其他 AI 安全论文· arXiv:2611.24083· Paul König, Sascha Marton, Stefan Lüdtke, Christian BarteltCOgnitive SoftwaRE (CORE), Clausthal University of Technology; Institute for Visual and Analytic Computing, University of RostockIndexed by this site · 13 hr ago· Originally publishedDefenses· Its place in the scan record →

Quick read

对齐/训练方法

Based on the paper PDF (AI-generated); refer to the original

The authors propose VESPA, which fine-tunes decision tree policies using counterexamples from formal verification; on MountainCarContinuous, 53 of 60 runs yielded safety proofs for all start states.

Questions
Safe reinforcement learning needs to guarantee that the policy does not violate safety constraints, but formal verification only gives a safe/unsafe verdict; when the policy is unsafe, the only option is to retrain from scratch and verify again, and both training and verification are costly, making the process inefficient.
Methods
VESPA alternates reachability verification and fine-tuning: it performs set-propagation verification on SYMPOL decision-tree policies, traces constraint-violating sets back along the action history to obtain counterexample regions, samples starting points from these regions with probability p for PPO fine-tuning, and repeats until safety is proven.
Experiments and results
On CartPole, the average verified safe steps rise from 63.8 to at least 92.7, with two rounds reaching the level of ten rounds of the Uninformed baseline, but return drops from 496 to 423; on MountainCarContinuous, 53 of 60 runs obtain a safety proof for all starting points, and return rises from 84 to 92.
Limitations and future work
The authors note that the proofs rely on known environment dynamics and cover only a bounded time horizon; verification cost grows with state dimension and policy size; on CP, proofs stop before 200 steps due to memory limits; and the experiments cover only two classic control environments and SYMPOL tree policies.
Experimental setupSYMPOL、VIPER · CartPole (CP)、MountainCarContinuous (MC-C) · verified safe steps (n⋆)、ratio of safe start state regions et al.
Evaluated models
SYMPOLVIPER
Benchmarks
CartPole (CP)MountainCarContinuous (MC-C)
Metrics
verified safe steps (n⋆)ratio of safe start state regionsaverage return
AI summaryThe VESPA framework targets safe reinforcement learning, using counterexamples from formal verification as fine-tuning training signals to make unsafe decision-tree policies safe or substantially close to safe. On CartPole, the mean number of verified safe steps rises from 63.8 to at least 92.7, reaching in two iterations the effect that takes ten iterations when no counterexamples are available. On MountainCarContinuous, 53 of 60 runs turn an unsafe policy into a safe one.

The VESPA framework targets safe reinforcement learning, using counterexamples from formal verification as fine-tuning training signals to make unsafe decision-tree policies safe or substantially close to safe. On CartPole, the mean number of verified safe steps rises from 63.8 to at least 92.7, reaching in two iterations the effect that takes ten iterations when no counterexamples are available. On MountainCarContinuous, 53 of 60 runs turn an unsafe policy into a safe one.

Paper analysis

6 questions; open one to read the full answer

  1. What problem does this paper attempt to solve?

    Verification gives only a safe/unsafe verdict, and when a policy is unsafe one can only retrain from scratch; VESPA turns verification counterexamples into a fine-tuning signal.

    Core problem: formal verification can only determine whether a policy is safe or not, and cannot guide how to repair an unsafe policy, making the "retrain—re-verify" loop inefficient.

    • Setting and importance: Safe reinforcement learning requires agents not to take dangerous actions; in safety-critical domains such as robotics and autonomous driving, the authors argue that any probabilistic safety guarantee is insufficient for deployment, and the deployed policy needs formal verification.
    • Shortcomings of existing methods: Offline verification such as reachability analysis gives only a one-time safe/unsafe verdict for a fixed policy; once a policy is judged unsafe, one can only train and verify multiple independent candidates until one happens to pass, a process the authors call inefficient or even infeasible.
    • Core observation: When reachability verification is performed on symbolic tree policies with axis-aligned splits (SYMPOL), an unsafe verdict naturally comes with counterexamples (states that are reachable by the policy and violate the constraints); tracing these counterexamples back to predecessor state regions and using them as fine-tuning starting points can teach the policy in a targeted way to avoid constraint-violating trajectories.
    • Paper proposes: VESPA (VErifiable Symbolic Policy Adaptation), a framework that alternates verification and fine-tuning, with three components: a reachability verifier for tree policies, backtracking-based counterexample extraction, and policy adaptation that mixes original starting points with counterexample starting points. The authors state that on CartPole the verifier scales to an average of at least 92.7 steps, more than the 10 steps of prior work.
  2. What related research exists?

    Related work falls into three groups: tree policy verification, DNN policy verification and repair, and shielding; VESPA's difference lies in backtracking counterexample regions as fine-tuning starting points.

    Verification of decision-tree policies

    • Bastani, Pu, and Solar-Lezama (2018)—verify tree policies distilled from DNNs using an SMT solver, proving correctness of a CartPole policy for the first 10 steps; the paper states that VESPA's verification confirms this and finds specific unsafe states at later steps.
    • Jain et al. (2024) and Vinzent, Sharma, and Hoffmann (2023)—use tree-specific solvers Veritas and policy predicate abstraction (PPA) to construct reachable state sets over an unbounded time horizon.
    • Schilling et al. (2023)—propagate reachable state sets for tree policies in continuous time; the paper explains that VESPA needs the number of safe steps verified, the counterexample regions, and the steps at which they occur, and therefore likewise chooses a set-based representation.

    Verification and repair of DNN policies

    • Trainify (Jin et al. 2022)—discretizes the state space into abstract states, trains and verifies a DNN policy on the abstract states, and refines the discretization at constraint-violating locations and retrains from scratch.
    • Boetius, Leue, and Sutter (2023), Yang et al. (2022), Wu, Zhang, and Vorobeychik (2024)—repair DNN policies using verifier counterexamples; the paper notes that they train at the locations where the verifier finds counterexamples (adding a penalty or adding a loss on the verification bound), whereas VESPA traces counterexample regions back along time and uses them only as fine-tuning starting points.

    Shielding

    • Alshiekh et al. (2018)—shielding adds a static component at runtime that restricts or overrides the actions of the learned policy; Anderson et al. (2020) alternate training of a DNN policy and a verifiable symbolic policy under this framework. The paper notes that shielding shifts the verification problem to a shield that must itself be provably safe and must be present at deployment, whereas VESPA directly verifies and adapts the learned policy itself.

    Baselines and benchmarks: The experimental baseline is the method the authors call Uninformed (the same loop and the same settings, but all fine-tuning starting points are sampled from the standard initial distribution, i.e., p = 0); VIPER-extracted trees are additionally verified with the same verification settings; the benchmarks are CartPole and MountainCarContinuous. The authors position this paper as using verification output (counterexamples) as a fine-tuning training signal, rather than only as a verdict or runtime shielding.

  3. How does the paper address this problem?

    Alternating loop: set-propagation verification of the tree policy → backtrack to extract counterexample regions → sample starting points from the counterexample regions with probability p and fine-tune with PPO → verify again.

    Overall idea: VESPA treats the output of reachability verification as a training signal, running an alternating loop of "verify—extract counterexamples—targeted fine-tuning" on a pretrained axis-aligned decision tree policy until the policy is proven safe or an iteration limit is reached (Figure 1).

    Problem setup and safety definition

    • Consider an MDP with state space S ⊆ R^d, deterministic transition function f, and initial state set S0; given a pretrained axis-aligned decision tree policy π, with no assumption about how it was obtained.
    • Invariance safety is defined as ∀ s0 ∈ S0 ∀ t ≤ n: st ∈ Ssafe, i.e., not leaving the safe set within n steps; bounded reachability requires entering the target set Sgoal at some step within n steps.
    • The paper focuses on the invariance constraint (CP) and the reachability constraint (MC-C), with time horizon n = 200.

    Reachability verification (Section 2.2)

    • State sets are represented as d-dimensional boxes or zonotopes and propagated step by step: the L leaf regions of the tree policy cut each set into single-action fragments, with exact splitting under boxes and required outer over-approximation under zonotopes; environment dynamics are over-approximated as fˆ using interval arithmetic.
    • A safe verdict is always a proof, while an unsafe verdict may be imprecise; two lossless reductions from Eq. 6 (discarding exact duplicates and discarding sets contained in a set with the same action) reduce fragmentation.
    • Under invariance properties, the set leaving Ssafe at the first violating step n⋆ + 1 is a counterexample; under reachability properties, sets that have not entered Sgoal by the end of the time horizon are counterexamples.

    Counterexample extraction (Section 2.3)

    • Rather than using the violating set itself (the violation has already occurred and cannot be undone), the action history recorded for each set is backtracked n_lookback steps using the inverse transition fˆ−1 to obtain predecessor state regions, called counterexample regions b̂, with the whole set denoted B̂.
    • n_lookback is chosen by property type: reachability properties need a larger value, because failure to reach the target is only discovered at the end of the time horizon and may originate from any earlier step.

    Policy adaptation (Section 2.4)

    • The initial state distribution is modified: Dmix = (1−p) D0 + p/(|B̂|) ∑b̂ U(b̂), i.e., with probability p uniformly from each counterexample region and with 1 − p from the environment's standard starting distribution; the authors say this both focuses on hard edge cases and prevents forgetting.
    • Fine-tuning supports any on-policy algorithm; the experiments use PPO, with the critic reinitialized from scratch (the data distribution has changed), and each episode truncated at the end of the remaining time horizon.
    • A candidate policy replaces the current policy only if the verification depth is not lower (CP), or if it is proven safe or the proportion of safe starting regions is strictly higher (MC-C); verification then repeats, looping until safety is proven or the iteration limit is reached.
  4. What experiments did the paper conduct?

    Comparing VESPA with Uninformed on CP and MC-C: on CP, verified steps in two rounds match ten rounds but return decreases; on MC-C, 53/60 runs are fully proven.

    Experimental setup

    • Policies tested: SYMPOL-configured depth-7 axis-aligned trees (PPO pretrained, CP 50M steps, MC-C 1M steps); CP uses 12 evaluation seeds × pruned/unpruned = 24 input policies, MC-C uses 6 seeds × 2 = 12 (Table 4); additionally 21 VIPER distilled trees are verified (Appendix F).
    • Environments: CartPole (CP, invariance constraint, box representation) and MountainCarContinuous (MC-C, reachability constraint, zonotope representation, S0 evenly divided into 2^14 = 16384 starting regions verified separately), time horizon n = 200 (Table 5).
    • Baseline: Uninformed, same loop and settings, except that all fine-tuning starting points come from the standard initial distribution (p = 0).
    • Metrics: CP's main metric is verified safe steps n⋆ (reported as a lower bound when memory is exhausted); MC-C's is the proportion of safe starting regions; also reported are the number of runs obtaining a safe policy and the average return over 30 greedy episodes.
    • Runs and iterations: CP 48 runs per method (24 policies × 2 fine-tuning seeds), at most 11 rounds; MC-C 60 per method (12 policies × 5 seeds), at most 5 rounds; 10^5 environment steps per round.
    • Key hyperparameters: p = 0.5 (VESPA) / 0 (Uninformed); n_lookback: 10 for CP (selected by random search over 25 configurations among 2, 6, 10, 14), 200 for MC-C (Appendix E).

    Main results

    According to Table 1 (CP, 48 paired runs) and Table 2 (MC-C, 60 paired runs):

    Swipe horizontally to read the table

    EnvironmentMetricInitialVESPA finalUninformed final
    CPVerified safe steps (mean)63.8≥92.7 (+28.9)≥85.2 (+21.4)
    CPAverage return496423477
    MC-CProportion of safe starting regions55.7%99.6%99.2%
    MC-CRuns proving safety for all starting points053/6046/60
    MC-CAverage return849292
    • The authors claim VESPA's advantage appears early: on CP, after two rounds the average is at least 85.1 steps, and Uninformed needs ten rounds to reach the same value (Figure 4).
    • Paired comparison: after 3 rounds, VESPA verifies deeper in 26 of 48 pairs and shallower in 5; after the final round, 14 pairs lead and 2 trail, with the rest equal or incomparable (all are lower bounds).
    • In the 42 MC-C runs where both sides obtain proofs, VESPA needs 2.2 rounds on average and Uninformed 2.7 rounds; the authors note that MC-C proofs do not cost return.

    Return and safety decoupling (Figure 3)

    • What was measured: 3 VIPER trees (d3, d9, d10) and 3 SYMPOL policies (depth 7), all with average return close to the upper limit (≥490/30 episodes).
    • Results: none of the 6 policies is verified safe for 200 steps, and one is verified for only 27 steps; d10 violates in only 12 of 108 sampled starting points, which a 1000-episode evaluation would hardly detect.
    • Authors' interpretation: even when the reward fully covers the safety constraint, average return is a poor proxy for safety; under short-horizon verification (such as the 10 steps of prior work) all 6 policies are proven safe, which would mask these violations.

    Effect of over-approximation (Appendix B)

    • What was measured: the degree of over-approximation of set propagation relative to the exact reachable set during verification.
    • Results: on CP, the median single-step over-approximation of 18,581 boxes is no more than 0.02% of the exact image width; on MC-C, 98.6% of the 2,737 unproven starting regions contain concrete trajectories that fail the target, and the safe region proportion is underestimated by at most 1.8 percentage points.
    • Authors' interpretation: in theory some counterexamples could be artifacts of over-approximation, but since the counterexamples clearly improve fine-tuning (Figure 4), the authors believe this effect is either absent or too small to affect fine-tuning.

    Other ablations and analyses

    • Memory limits: on CP, 40 of 48 VESPA runs and 26 Uninformed runs end early due to verification memory exhaustion, and no run obtains a safety verdict for all 200 steps (Table 1).
    • Pruning: on CP, the average gain for VESPA's pruned/unpruned groups is +31.9/+25.9 steps, and on MC-C proofs are obtained in 26/30 and 27/30 runs; the authors report no systematic effect of pruning (Table 3).
    • VIPER trees: none of the 21 VIPER distilled trees is verified safe for 200 steps, and for 20 of them a concrete episode violating the constraint before 200 steps is found (Appendix F).
    • Explanation for the return drop: CP fine-tuning episodes end at 200 steps while return is counted over 500 steps, which the authors say can explain the lower return of CP policies after fine-tuning (Appendix E).
  5. What are some points that can be further explored?

    The authors note that the proofs rely on known dynamics and a bounded time horizon, and that verification cost grows with dimension; future directions are more memory-efficient representations and tree ensembles.

    Limitations and future directions noted by the authors

    • The proof targets the policy and the environment model, so the dynamics must be known, and it covers only a bounded time horizon n (Section 3.2 Limitations).
    • The cost of reachability analysis grows with the number of state dimensions and the policy size; on CP the proof therefore terminates before 200 steps (Section 3.2 Limitations).
    • Safety over the full time horizon is not proven on CP; the limiting factor is the memory required for verification rather than policy adaptation; future work could study more memory-efficient state representations (Section 5).
    • Future work could extend VESPA to tree ensembles such as GRANDE (Section 5; Appendix F also states that tree-ensemble policies are future work).

    Experimental scope

    • The environments tested are two classic control benchmarks, CartPole and MountainCarContinuous, with time horizon n = 200 (Section 3.1).
    • The policies tested are SYMPOL depth-7 trees (24 input policies for CP, 12 for MC-C), and 21 VIPER-distilled trees were additionally verified; fine-tuning uses only PPO (Section 3.1, Appendix F).
    • The only baseline is Uninformed (the same loop with only the starting-point distribution different); no experimental comparison with other repair or verification methods is made (Section 3.1).
    • Run scale: 48 runs per method on CP and 60 runs per method on MC-C; returns are computed over 30 greedy episodes (Figure 3 uses 1000) (Section 3.1).
    • The paper does not report the wall-clock time of a single fine-tuning run or the total training cost; verification time is given only as a median (CP 180 s, MC-C 23 s, Table 5).
  6. Summarize the main content of the paper

    VESPA backtracks counterexamples from reachability verification and uses them as fine-tuning starting points; on CP, two rounds of verification match ten rounds, and MC-C obtains a safety proof for all starting points in 53/60 runs.

    A safe reinforcement learning paper addressing the problem that "verification only gives a verdict, not a repair path": once a policy is judged unsafe, the only option is to retrain from scratch and verify again, which is costly.

    • Method: VESPA performs set-propagation reachability verification on axis-aligned decision tree policies (SYMPOL), backtracks the constraint-violating sets along the action history for n_lookback steps to obtain counterexample regions, samples starting points from these regions with probability p = 0.5, fine-tunes with PPO over the remaining time horizon, and replaces the current policy with a candidate only if it passes verification, looping until safety is proven.
    • Verifier: exploits the axis-aligned splits of tree policies to partition state sets exactly, using boxes for CP and zonotopes for MC-C; a safe verdict is always a proof. The authors claim that on CP the verification depth reaches an average of at least 92.7 steps, more than the 10 steps of prior tree-policy verification work.
    • CP results: average verified safe steps rise from 63.8 to at least 92.7, with two rounds reaching the level of ten rounds of the Uninformed baseline; the cost is that average return drops from 496 to 423 (Uninformed drops to 477), and 40 of 48 runs end early due to verification memory exhaustion, with no run obtaining a proof for all 200 steps.
    • MC-C results: the 12 input policies initially have only 55.7% of the starting region provably meeting the target on average; within 5 rounds VESPA obtains a safety proof for all starting points in 53 of 60 runs (Uninformed 46), and average return rises from 84 to 92.
    • Another finding: none of 6 CP policies whose average return is close to the upper limit is verified safe for 200 steps; the authors therefore argue that average return is a poor proxy for safety, even when the reward fully covers the safety constraint.
    • Authors' conclusion: verification counterexamples are an effective training signal that can systematically improve the safety of tree policies; limitations are that the proofs rely on known dynamics and a bounded time horizon, verification cost grows with dimension and policy size, and future directions include more memory-efficient representations and extension to tree ensembles.
Read originalarxiv.org