Safe reinforcement learning (RL) aims to prevent agents from taking actions that are dangerous or destructive to their environment. This is especially important for safety-critical domains, such as robotics or autonomous driving. Formal verification can be used to prove agent safety through safety constraints. However, in practice, many policies do violate safety constraints, and thus are verified to be unsafe. Since the goal is to obtain a safe policy, we would need to retrain a new policy from scratch and then verify it again until a candidate happens to pass. Both training and verification are usually not cheap, which makes this process inefficient. We introduce VESPA (VErifiable Symbolic Policy Adaptation), a framework for targeted fine-tuning of decision tree policies. We show that using counterexamples for policy adaptation can make existing unsafe policies safe, or at least make considerable progress towards safety. Targeted fine-tuning of the existing policy on those counterexamples enables it to learn how to avoid violating safety constraints. We thus use the result of a formal verification as a training signal for fine-tuning. On CartPole, VESPA raises the mean number of verified safe steps from 63.8 to at least 92.7, reaching after two iterations what the same loop without counterexamples reaches after ten. On MountainCarContinuous, VESPA turns an unsafe policy into a safe policy in 53 of 60 runs. We conclude that counterexamples from a verifier are an effective training signal, which can be utilized to systematically improve the safety of policies. Our implementation is available at: https://anonymous.4open.science/r/VESPA-Submission/
Figures & tables
Figure 1: Overview of VESPA. A hard, axis-aligned SYMPOL decision tree policy π0 is pretrained with PPO. (1) Verify: starting from the start states S0 , the reachable states in the state space S are propagated step by step until the first violating step n⋆+1 or the horizon n . A single verification step is detailed in Fig. 2 . (2) Extract: each violating set b⋆ is walked back for n_lookback steps along its action history, giving a counterexample region b^ . (3) Fine-tune: episode start states are sampled from the counterexample regions with probability p and from S0 otherwise, and the tree is fine-tuned with PPO up to step n . The candidate policy πk+1 is verified again. The loop ends with a proof of Eq. 1 once no violation occurs up to step n .
Figure 2: One verification step of VESPA. Both rows show the same step from Si to Si+1 , with boxes (top) and zonotopes (bottom) as state representation. Representation: the reachable states Si are represented as a set of boxes or zonotopes, each carrying its action history. Partition: the axis-aligned splits of the policy divide each set into pieces, each with a single action aj . This is exact for boxes, while each zonotope piece is over-approximated by an enclosing zonotope. Step: each piece is propagated through f^(⋅,aj) . For boxes, interval arithmetic over-approximates by an enclosing box, while affine transitions of zonotopes are exact. Reduce: exact duplicates and sets contained in another set with equal action are dropped (Eq. 6 ), giving Si+1 (Eq. 3 ). Check: every set that leaves Ssafe is captured as b⋆ with its action history at the first violating step n⋆+1 (Eq. 4 ). Otherwise, Si+1 becomes the next frontier, and after step n the verification returns a proof of Eq. 1 .
Figure 3: High return does not imply safety on CP. Mean and minimum return over 1000 greedy episodes and verified safe steps at n=200 for three VIPER trees, labeled by their depth (d3, d9, d10), and three SYMPOL policies of depth 7 (s1–s3). All six were selected by a return ≥490 over 30 episodes. A minimum return of 500 means that no episode violated the constraint. It does not show that the policy is safe . ≥d : the verifier ran out of memory, so d is a lower bound.
Figure 4: Verified safe steps on CP over the fine-tuning iterations. Mean (solid) and median (dashed) over 48 runs per method (24 input policies × 2 fine-tuning seeds) of the verified depth of the current policy. Iteration 0 is the input (pretrained) policy. Uninformed samples all fine-tuning start states from the standard initial-state distribution. A run whose verification runs out of memory keeps its depth as a lower bound ( ≥ ), and also ends early (visualized at the bottom).
Figure 5: Safe start state regions on MC-C over the fine-tuning iterations. Mean (solid) and median (dashed) over 60 runs per method (12 input policies × 5 fine-tuning seeds) of the ratio of safe start state regions of the current policy. Iteration 0 is the input (pretrained) policy. A run that is proven safe ends early (visualized at the bottom).
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Return
Δ Verified safe steps
Pairs
It.
VESPA
Uninf.
VESPA
# ≥
Uninf.
# ≥
W
E
L
0
496 ± 9
496 ± 9
63.8 ± 22.3
0
63.8 ± 22.3
0
0
48
0
1
459 ± 95
487 ± 43
+15.2 ± 17.4
17
+6.9 ± 14.7
10
18
24
6
2
445 ± 100
473 ± 66
+21.3 ± 19.9
26
+10.7 ± 16.5
14
24
17
7
3
436 ± 108
467 ± 75
+22.4 ± 19.0
30
+13.1 ± 17.4
15
26
17
5
4
439 ± 101
462 ± 80
+24.7 ± 21.0
34
+14.3 ± 17.3
15
25
18
5
Appendix
Table 1: CP results over the fine-tuning iterations. 24 input policies × 2 fine-tuning seeds = 48 paired runs per method, at most 11 iterations. Each value describes the accepted policy after k iterations. Return: mean ± std of 30 greedy episodes. Verified safe steps: row 0 gives the absolute value of the input policies, rows k≥1 the change with respect to the run’s own input policy (mean ± std). Runs whose verification ran out of memory enter with their verified depth as a lower bound. # ≥ : number of such runs. W/E/L: on the same input policy and seed, VESPA is verified for more steps than Uninformed (W), for fewer steps (L), or the two are equal or cannot be ordered (E). A lower bound counts as more steps only if it exceeds the exact value of the other run, and two lower bounds cannot be ordered.
Return
Safe start state regions (%)
Pairs
It.
VESPA
Uninf.
VESPA
#safe
Uninf.
#safe
W
E
L
0
84 ± 11
84 ± 11
55.7 ± 18.0
0
55.7 ± 18.0
0
0
60
0
1
80 ± 21
82 ± 15
87.2 ± 16.2
20
85.9 ± 12.2
13
28
10
22
2
89 ± 9
88 ± 11
94.5 ± 11.8
36
92.8 ± 9.7
23
30
16
14
3
91 ± 4
90 ± 7
98.0 ± 6.8
45
96.5 ± 6.5
32
25
23
12
4
91 ± 7
90 ± 7
99.0 ± 3.8
49
97.8 ± 5.8
39
20
32
8
Appendix
Table 2: MC-C results over the fine-tuning iterations. 12 input policies × 5 fine-tuning seeds = 60 paired runs per method, at most 5 iterations of 105 environment steps each. Each value describes the accepted policy after k iterations. A run that is proven safe keeps its policy. Return: mean ± std of 30 greedy episodes. Safe start state regions: mean ± std of the ratio of start state regions proven to reach Sgoal within n=200 steps. #safe: runs proven safe on all of S0 . W/E/L: VESPA has a higher, equal or lower ratio than Uninformed on the same input policy and seed.
Pruned
Unpruned
VESPA
Uninf.
VESPA
Uninf.
CP, 24 runs per cell, after 11 iterations
Input
63.5 ± 22.6
64.1 ± 22.5
Δ steps
+31.9 ± 22.5
+20.6 ± 22.8
+25.9 ± 22.7
+22.3 ± 18.4
# ≥
19
9
21
17
Return
432 ± 102
462 ± 77
414 ± 116
492 ± 18
Appendix
Table 3: Results split by pruned and unpruned input policies. Every pretraining seed contributes one pruned and one unpruned input policy, and pruning does not alter the policy. CP: 12 seeds × 2 fine-tuning seeds = 24 runs per cell. MC-C: 6 seeds × 5 fine-tuning seeds = 30 runs per cell. Input: verified safe steps (CP) or ratio of safe start state regions (MC-C) of the input policies, mean ± std. All other rows describe the final accepted policy. Δ steps, # ≥ , return and W/E/L for CP are defined as in Table 1 . Safe reg., #safe, return and W/E/L for MC-C are defined as in Table 2 . Iterations: total number of fine-tuning iterations, where a run without a proof counts with all 5.
CP
MC-C
Tuning seeds (policies)
4 (8)
4 (8)
Evaluation seeds (policies)
12 (24)
6 (12)
Fine-tuning seeds per policy
2
5
Runs per method
48
60
Appendix
Table 4: Number of pretrained policies and runs. Every seed contributes a pruned and an unpruned policy.
CP
MC-C
Actions
discrete
continuous
Episode limit (steps)
500
999
Start region S0
[−0.05,0.05]4
x∈[−0.6,−0.4] , v=0
Unsafe region S∖Ssafe
∣x∣>2.4∨∣θ∣>0.2094
–
Goal region Sgoal
–
x≥0.45
Horizon n
200
200
Appendix
Table 5: Environments and verification settings. CP follows the CartPole-v1 specification, MC-C the MountainCarContinuous-v0 specification of gymnax ( Lange 2022 ) . CP: cart position x and pole angle θ (rad). MC-C: car position x and velocity v .
Hyperparameter
CP
MC-C
Learning rate, split thresholds
3⋅10−4
1.67⋅10−4
Learning rate, split features
3⋅10−4
1.46⋅10−4
Learning rate, leaves
3⋅10−4
4⋅10−3
Learning rate, tree weights
3⋅10−4
1.23⋅10−4
Learning rate, action log-std
–
1⋅10−2
Upper bound of action log-std at start
–
−1
Appendix
Table 6: Fine-tuning hyperparameters of VESPA and Uninformed .