WorksComputer Science
VESPA: Verifiable Symbolic Policy Adaptation for Safe Reinforcement Learning
Abstract
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 (rifiable ymbolic olicy daptation), 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/
Introduction
Reinforcement learning (RL) has recently achieved remarkable progress in the areas of robotics and control [27]. Generally, both the training and evaluation of RL algorithms are based on expected return. However, solely optimizing the expected return for a given task is inadequate for safety-critical applications, because the environment or agent can impose safety constraints which must not be violated. For instance, in robotic applications it is insufficient to evaluate solely on average task performance. Instead, we need to guarantee that unsafe behaviors, such as a humanoid robot falling over, never occur. RL does not give such guarantees by default. In the area of safe RL, numerous approaches have been proposed to overcome this problem. As discussed by Zhao et al. (2023), some approaches provide proofs of safety, while others give probabilistic safety guarantees. We argue that any form of probabilistic safety guarantee is insufficient for deploying RL in safety-critical domains. In environments with high risks, a formal verification for the deployed policy is needed. Safety can either be enforced at runtime, during training or inference, as in shielding [1], or verified offline as a one-time proof for a fixed policy. Reachability analysis [2] is a versatile approach to offline verification, and issues a final verdict (either safe or unsafe) once for a fixed policy.
One challenge of applying reachability analysis in general is the gap between verifying whether a policy is safe and obtaining a safe policy. Formal verification only returns the verdict safe or unsafe. Since the final goal is to create a safe policy, one must train and verify many independent candidates, which is inefficient and in some cases infeasible.
To overcome this challenge, we introduce VESPA (VErifiable Symbolic Policy Adaptation) and show how to fine-tune a given policy based on the result of a formal verification. We focus on symbolic tree-based policies (SYMPOL, Marton et al. 2025), since their axis-aligned splits make them amenable to reachability analysis. For policies with an unsafe verdict, we natively obtain counterexamples, i.e., states that are reachable by the policy and violate the safety constraints. Those are then traced back to some predecessor state region and used as start states for fine-tuning the policy. This targeted policy adaptation teaches the policy to steer away from the unsafe counterexamples. In this way, VESPA utilizes the output of the reachability analysis as a training signal to fine-tune the current policy and obtain the next candidate policy. More specifically, our contributions are as follows:
We present a verifier for tree policies that scales to longer horizons than other approaches (Section 2.2).
We utilize failures extracted by the verifier for targeted fine-tuning, the core of VESPA (Section 2.4).
We show that VESPA obtains fully safe policies on MountainCarContinuous most of the time and makes considerable progress towards safe CartPole policies (Section 3.2).
On CartPole, our verifier scales to a mean horizon of at least 92.7 steps, more than the 10 steps verified by prior work on tree policies for CartPole [7, 28]. Our policy adaptation component then increases the proven steps by a mean of at least 29 steps.
On MountainCarContinuous, we prove in 53 of 60 runs that VESPA turns unsafe policies into safe policies for the full 200-step horizon from all start positions defined by the environment [19], whereas related proofs start from only 15–30% of these start positions [24, 15]. Our analysis also shows that expected return is a poor proxy for the safety of RL policies, even if the reward signal covers the safety constraint completely: On CartPole, none of the tested policies with near-maximal return is verified safe for 200 steps, and one is verified for only 27 steps.
VESPA: VErifiable Symbolic Policy Adaptation
We introduce VESPA, an alternating verification and fine-tuning loop (Figure 1) based on three main components:

Figure 1. Overview of VESPA. A hard, axis-aligned SYMPOL decision tree policy is pretrained with PPO. (1) Verify: starting from the start states , the reachable states in the state space are propagated step by step until the first violating step or the horizon . A single verification step is detailed in Figure 2. (2) Extract: each violating set is walked back for steps along its action history, giving a counterexample region . (3) Fine-tune: episode start states are sampled from the counterexample regions with probability and from otherwise, and the tree is fine-tuned with PPO up to step . The candidate policy is verified again. The loop ends with a proof of Eq. (1) once no violation occurs up to step .
Verification for symbolic tree-based policies through reachability analysis over a continuous state space (§ 2.2)
Counterexample extraction based on backtracking of unsafe state regions (§ 3.3)
Policy adaptation through mixing original start states and counterexample start states and fine-tuning on the remaining horizon (§ 3.4)
Background
Following Zhao et al. (2023), we distinguish between state-wise and cumulative safety constraints. State-wise constraints have to be met at each step, while cumulative constraints have to be met for an entire episode taking all steps into account. Within the former, we focus on invariance constraints, which force the agent to never leave a constraint-satisfying state region. Within the latter, we focus on reachability constraints, which describe a goal which has to be met at some step of the episode.
Reachability Analysis This approach to formal verification [2], here applied to RL policies, identifies the set of reachable states, which can then be checked against some safety constraint. The set of reachable states depends on the set of start states and the environment transition function , as well as the policy . Starting from , the set of reachable states at each step is determined by:
Tree-Based Policies The model type has great influence on the performance and interpretability of RL policies. While Deep Q-Network (DQN) policies and other neural network policies received much attention in recent years, tree-based policies [20, 12] achieved competitive results on several benchmarks. In addition to their better interpretability [20], tree-based policies naturally provide hard axis-aligned decision boundaries. We exploit this property within our verification algorithm, to make verification more efficient.
Reachability Analysis with Tree Policies
VESPA verifies policies with set-based reachability analysis [2], which has also been applied to tree policies before [24]: sets of states are propagated step by step through the closed loop of policy and environment and checked against the property. In our case, the policy acts at discrete time steps and selects one action per axis-aligned leaf, so the tree splits divide each set into pieces with a single action each (Figure 2).

Figure 2. One verification step of VESPA. Both rows show the same step from to , with boxes (top) and zonotopes (bottom) as state representation. Representation: the reachable states 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 . This is exact for boxes, while each zonotope piece is over-approximated by an enclosing zonotope. Step: each piece is propagated through . 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 (Eq. (3)). Check: every set that leaves is captured as with its action history at the first violating step (Eq. (4)). Otherwise, becomes the next frontier, and after step the verification returns a proof of Eq. (1).
We consider a Markov Decision Process with state space , action set , deterministic transition function and initial states . We assume that a pretrained axis-aligned decision tree policy already exists. VESPA does not make any assumptions on how this policy was obtained. Given a safe set (or a goal set ) and a verification horizon , a safe policy is defined as [5, 8]:
for invariance properties, and:
for bounded reachability properties, where is the state reached after policy steps from .
Exploiting Hard Axis-Aligned Decision Boundaries
As a default, we use -dimensional boxes to represent a subset region of a continuous state space. A decision tree policy with leaves induces subset regions, one for each leaf. Each region corresponds to a single action that is selected for that region. We then intersect the start state region with every leaf region and obtain at most parts of . We apply the transition function to each part individually, obtaining the results of one policy step for all start states . This process is repeated for each resulting box recursively along the verification horizon (Figure 2). Formally, let be the axis-aligned leaf regions of the tree and the action of leaf . Starting from , one policy step maps the set of boxes to
where is the over-approximated environment step described below and Reduce applies the reduction techniques in Eq. (6).
For invariance properties, each box in is intersected with the complement of the safe set, . The verdict is unsafe if this intersection is non-empty, i.e. some box leaves the safe set, with the number of verified safe steps
and safe otherwise. The boxes with are the counterexamples (§ 3.3).
Naturally, only exists for invariance properties. For reachability properties, the reachable set is intersected with the complement of the goal set, , at every step. A box that lies entirely inside has satisfied Eq. (2) and is absorbed. Only the remaining boxes
are propagated, i.e., Eq. (3) is applied to in place of . The verdict is unsafe if some box has still not reached the goal at the horizon, , and safe otherwise. The boxes in are the counterexamples (§ 3.3). In both cases, invariance and reachability, verifying the constraint is an efficient intersection, done in constant time per box. Since the leaf regions are axis-aligned, the intersections are exact. over-approximate the environment dynamics with by interval arithmetic [23]. A safe verdict is always a proof, while an unsafe verdict may be inaccurate. Combining these properties with Counterexample Extraction (§ 3.3) and Policy Adaptation (§ 3.4), we are able to fine-tune and then prove a safe policy.
Zonotopes as an Alternative State Representation
Instead of boxes, VESPA can represent each element of as a zonotope [13], i.e., a centrally symmetric set with center and generator matrix . We use zonotopes as an alternative representation of the observed state space: Eq. (3), the counterexample extraction and the policy adaptation step remain unchanged. Their main advantage is that affine state transitions are exact, so correlations between state dimensions are preserved and the transitions do not need to be over-approximated as with boxes. However, the axis-aligned tree splits are no longer exact, since is in general not a zonotope and has to be over-approximated [14]. Which representation is tighter depends on the environment: zonotopes are preferable when the environment dynamics strongly couple state dimensions, boxes when the fragmentation by the tree dominates (Appendix § 12). As with boxes, a safe verdict obtained with zonotopes is a proof, while an unsafe verdict may be inaccurate.
Scaling to Many Environment Steps
The computational effort of verification within VESPA depends on two main factors: the structure of the pretrained policy, with larger trees leading to more fragmentation, and the number of observed dimensions as defined by the environment. The computational effort also grows with higher verification depth, i.e., more verified steps. Most environments define a step limit, after which an episode is either terminated or truncated.
To reduce the computational effort, we introduce two reduction techniques aimed at reducing the fragmentation of the reachable state space. First, exact duplicates are dropped. Second, if a state region is contained in another region, it can be safely dropped. In both cases, their corresponding actions need to match. Formally, with the action under which zonotope or box was propagated in the current step, and the set of zonotopes or boxes after dropping exact duplicates,
Both reduction techniques are used for both box and zonotope representations. Applying those reduction techniques is lossless and does not impact the verdict.
Counterexample Extraction
An unsafe verification verdict comes with at least one violating set , i.e., a reachable box or zonotope that leaves at the first violating step . We then extract the predecessor state regions of every violating set.
Extracting Predecessor State Regions Naively using the violating set itself as a counterexample for policy adaptation would be a poor choice. Since the violation has already occurred, it would be impossible to recover. The counterexample extraction of VESPA therefore returns a part of some predecessor set, which we call a counterexample region . The set of all extracted counterexample regions is . To accomplish this, we keep a record of the action history for each set, which we then use to backtrack its predecessors. The length of the action history, and thus the number of backtracked steps, is denoted by . Starting from only the violating part of each violating box , we apply the inverse transition once per recorded action, from the most recent to the oldest, each time obtaining the box one step earlier. The appropriate value of depends on the property class. Reachability properties naturally require substantially larger values, since a failure to reach the goal is only detected at the horizon and may originate at any earlier step.
Policy Adaptation
The VESPA verification issues either a safety proof or counterexamples, which are regions reachable by the current policy from which a future violation is inevitable. Since the main goal is to train a safe policy, these counterexamples are valuable: they pinpoint states that lead to potentially very rare trajectories in which the constraint is violated. Standard RL training would encounter such states only by chance during exploration, and may never sample them at all. Without targeted guidance, finding a safe solution is hard. We therefore utilize the counterexamples for an informed policy adaptation, directing training exactly to these hard cases instead of relying on undirected exploration.
Initial-State Distribution The initial-state distribution defines the sampling of training start states and thereby which episodes the policy is trained on [26]. During standard pretraining, it is defined by the environment and usually covers the range of possible start states uniformly. In policy adaptation, we focus the fine-tuning on the hard regions that lead to violations. Therefore, we modify the initial-state distribution to sample with probability from the extracted counterexample regions and with probability from the standard start state region, i.e.,
where is the initial-state distribution of the environment and the uniform distribution over region . Every counterexample region is thus drawn with equal probability, independent of its volume. The mixture thus focuses on the hard edge cases while preventing forgetting [11, 16].
Standard Fine-Tuning for the Remaining Horizon Our fine-tuning supports any on-policy optimization algorithm. In the case of actor-critic methods such as PPO [25], we reinitialize the critic from scratch, since the training data distribution has changed. We then run the standard formulation of the optimizer, but truncate each episode at the end of the remaining horizon. Depending on the unsafe step and the parameter, we may start a training episode in the middle of the horizon, far away from the start state region. Therefore, it is natural to run those episodes only for the remaining horizon.
Evaluation
We evaluate whether VESPA turns pretrained SYMPOL trees [20] that fail verification into policies that are verified safe over the full horizon on two classic control benchmarks. Moreover, we show that the average return of a policy and its verified safe steps are decoupled.
Experimental Setup
Environments and Safety Constraints We carry out our evaluation on the CartPole (CP) [6] and MountainCarContinuous (MC-C) [22] control environments (Appendix § 12). Solving CP requires the policy to balance a pole on a cart while controlling the movement of the cart. An episode fails if either the pole falls over or the cart exits the allowed area. Solving MC-C requires a car to gain energy from multiple swing-ups to escape a valley and finally reach the goal position at the top of the right hill. For both environments, pretraining and the reported average return follow the standard formulation, while both constraints use the horizon , the episode limit of the original CartPole-v0 and MountainCar-v0 specifications [10, 29].
Pretraining VESPA does not make any assumptions on how the pretrained axis-aligned tree policy was obtained. We focus on the SYMPOL configurations of Marton et al. [20] for both CP and MC-C (Appendix § 11).
Pruning We apply the pruning of the SYMPOL implementation [20] and evaluate both the pruned and the unpruned pretrained policies. Pruning does not change the actions of a policy, but the pruned tree has fewer nodes that the fine-tuning can adjust. We therefore treat the pruned and the unpruned tree of a pretraining seed as two separate runs, although they are not independent. We provide an analysis of pruned and unpruned policies in Appendix § 9, which shows no evidence of any impact.
Verification and Counterexample Extraction We verify CP with boxes and MC-C with zonotopes (§ 2.2, Appendix § 12). For MC-C, we additionally divide into start state regions of equal width along the position and verify each region separately. For the counterexample extraction (§ 3.3), we use for CP and for MC-C (Appendix § 13).
Policy Adaptation In both environments, fine-tuning uses the PPO hyperparameters of Marton et al. [20] with few changes (Appendix § 13), and we sample fine-tuning start states from the counterexample regions with probability (Eq. (7)). Each run consists of at most 11 fine-tuning iterations for CP and at most 5 for MC-C. A candidate replaces the current policy only if it is verified at least as deep (CP), or if it is safe or its ratio of safe start state regions is strictly higher (MC-C). We stop either after the verdict is safe, after the last iteration, or, for CP, when the verification of a candidate runs out of memory beyond the depth of the current policy.
Metrics For CP, our main metric is the number of verified safe steps (Eq. (4)). If the verification runs out of memory before a verdict, we report the steps verified so far as a lower bound on (Appendix § 13). For MC-C, we report the ratio of safe start state regions. A start state region is safe if all trajectories provably reach the goal within steps (Eq. (2)). For both environments, we additionally report the number of runs in which VESPA obtains a safe policy and, as a secondary metric, the average return over 30 episodes with greedy action selection (1000 episodes in Figure 3).

Figure 3. High return does not imply safety on CP. Mean and minimum return over 1000 greedy episodes and verified safe steps at 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 over 30 episodes. A minimum return of 500 means that no episode violated the constraint. It does not show that the policy is safe. : the verifier ran out of memory, so is a lower bound.
Baselines We compare VESPA against a baseline that we call Uᴜɴɪғᴏʀᴍᴇᴅ. Uᴜɴɪғᴏʀᴍᴇᴅ runs the same loop with identical settings, including the verification and the acceptance of candidates, but samples all fine-tuning start states from the standard initial-state distribution ( in Eq. (7)). The two methods thus differ only in the start states of the fine-tuning episodes, which isolates the contribution of the counterexample start states. In addition, we verify decision trees extracted with VIPER [7] using the same verification settings (Appendix § 14).
Results
Average return as a performance metric fails for CartPole We first trained 21 trees as described by VIPER, and 32 tree ensembles as described by SYMPOL. We then selected 3 of each with high return and verified them with VESPA. The reward issued by the CP environment covers the safety constraint completely: every step is rewarded until an unsafe state is reached. Nevertheless, the average return and the verified safety are decoupled (Figure 3): all six policies obtain a near-maximal average return, yet none is verified safe for . The average return therefore neither indicates whether a policy is safe, nor does it rank policies by their safety. The reason is that the return averages over sampled start states: the many episodes with high return hide the few start states that lead to an unsafe trajectory. An unsafe verdict may be inaccurate (§ 2.2), but for d3 and d10 we found concrete episodes that violate the safety constraint before step 200 (Appendix § 14). For d10, this is the case for only 2 of sampled start states, which an evaluation on 1000 episodes is unlikely to reveal. These violations also remain hidden for a short verification horizon, such as the 10 steps considered by Bastani, Pu, and Solar-Lezama [7], for which all six policies are verified.
VESPA counterexamples represent concrete failures A safe verdict of VESPA is a proof (§ 2.2). An unsafe verdict, in contrast, is conservative, because the propagated sets can be larger than the exact reachable states. Per step, this over-approximation is small: the median excess of a propagated CP box over its exact image is at most 0.02% of the image width in every dimension. Over many steps, the excess accumulates, because a set that slightly overlaps a neighboring leaf region is split into an additional piece with a different action. In theory, some counterexamples could therefore be mere artifacts of the over-approximation. However, since the counterexamples clearly improve the fine-tuning (Figure 4), we conclude that this effect either does not occur or is too small to impair the fine-tuning.

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).
For MC-C, the effect stays small: 98.6% of the start state regions without a proof contain a concrete episode that misses the goal, so the ratio of safe start state regions is underestimated by at most 1.8 percentage points (Appendix § 10).
VESPA for CP makes considerable progress towards a full safety proof Starting from a mean of 63.8 verified safe steps, VESPA verifies a mean of at least 85.1 steps after two fine-tuning iterations, while Uninformed needs ten iterations to reach the same value (Figure 4). After the last iteration, the means are at least 92.7 and 85.2 steps, respectively. Most runs end because the verifier runs out of memory, which happens for 40 of 48 VESPA runs and 26 of 48 Uninformed runs. The advantage of VESPA shows early. On the same input policy and fine-tuning seed, VESPA is verified for more steps than Uninformed in 26 of 48 pairs after three fine-tuning iterations and for fewer steps in 5 (Table 1 in Appendix § 9). Afterwards, more and more runs reach the memory limit and end with a lower bound, and two lower bounds cannot be ordered. After the last iteration, VESPA is therefore ahead in 14 pairs and behind in 2, while the remaining 32 pairs are equal or cannot be ordered. Because of the memory limit, no run obtains the verdict safe for all 200 steps, and the reported gains are lower bounds. As discussed above, VESPA still verifies substantially more steps than prior verifiers for tree policies on CP ([7, 28]). The deeper proofs come at the cost of return: the mean return of the final policies drops from 496 to 423 for VESPA and to 477 for Uninformed (medians 492 and 500). A likely reason is that fine-tuning episodes end at step 200, while the return counts 500 steps (Appendix § 13).
| It. | Return VESPA | Return Uninf. | Verified safe steps VESPA | Verified safe steps # | Verified safe steps Uninf. | Verified safe steps # | Pairs W | Pairs E | Pairs L |
| 0 | 0 | 0 | 0 | 48 | 0 | ||||
| 1 | 17 | 10 | 18 | 24 | 6 | ||||
| 2 | 26 | 14 | 24 | 17 | 7 | ||||
| 3 | 30 | 15 | 26 | 17 | 5 | ||||
| 4 | 34 | 15 | 25 | 18 | 5 | ||||
| 5 | 37 | 16 | 23 | 22 | 3 | ||||
| 6 | 39 | 18 | 20 | 25 | 3 | ||||
| 7 | 40 | 18 | 21 | 24 | 3 | ||||
| 8 | 40 | 23 | 17 | 28 | 3 | ||||
| 9 | 40 | 25 | 15 | 31 | 2 | ||||
| 10 | 40 | 26 | 14 | 32 | 2 | ||||
| 11 | 40 | 26 | 14 | 32 | 2 |
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 iterations. Return: mean std of 30 greedy episodes. Verified safe steps: row 0 gives the absolute value of the input policies, rows 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.
VESPA for MC-C reliably obtains a safe policy None of the 12 input policies for MC-C is safe: on average, only 55.7% of the start state regions provably reach the goal within steps (Figure 5). Within five fine-tuning iterations, VESPA obtains a policy that is proven safe on the entire start region in 53 of 60 runs, compared to 46 of 60 runs for Uninformed (Table 2 in Appendix § 9). In the 42 pairs in which both runs end with a proof, VESPA needs 2.2 fine-tuning iterations until the proof on average and Uninformed 2.7. In contrast to CP, the proof does not cost return: the mean return increases from 84 to 92 for both methods. Since , all counterexample regions lie in . For MC-C, VESPA therefore draws half of the fine-tuning episodes from exactly those start states for which the proof still fails. Whether the input policy is pruned or unpruned has no systematic effect on the results in either environment (Table 3 in Appendix § 9).

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).
| It. | Return VESPA | Return Uninf. | Safe start state regions (%) VESPA | Safe start state regions (%) #safe | Safe start state regions (%) Uninf. | Safe start state regions (%) #safe | Pairs W | Pairs E | Pairs L |
| 0 | 0 | 0 | 0 | 60 | 0 | ||||
| 1 | 20 | 13 | 28 | 10 | 22 | ||||
| 2 | 36 | 23 | 30 | 16 | 14 | ||||
| 3 | 45 | 32 | 25 | 23 | 12 | ||||
| 4 | 49 | 39 | 20 | 32 | 8 | ||||
| 5 | 53 | 46 | 13 | 42 | 5 |
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 environment steps each. Each value describes the accepted policy after 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 within steps. #safe: runs proven safe on all of . 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 | ||||
| steps | ||||
| 19 | 9 | 21 | 17 | |
| Return | ||||
| W/E/L | 10/14/0 | 4/18/2 | ||
| MC-C, 30 runs per cell, after 5 iterations | ||||
| Input (%) | ||||
| Safe reg. (%) | ||||
| #safe | 26 | 25 | 27 | 21 |
| Iterations | 74 | 82 | 76 | 111 |
| Return | ||||
| W/E/L | 4/23/3 | 9/19/2 |
Table 3. Results split by pruned and unpruned input policies.
Limitations
The limitations of VESPA are largely those of formal verification in general. A proof refers to a policy and a model of the environment, so the dynamics have to be known, and it covers a bounded horizon . The effort of a reachability analysis grows with the number of state dimensions and the size of the policy. On CP, this is why our proofs end before step 200. They still reach about nine times further than prior work on this benchmark ([7, 28]), and on MC-C they cover the full horizon.
Related Work
Verification of Decision Tree Policies As discussed in § 2.1, decision tree policies are well suited for formal verification. For instance, Bastani, Pu, and Solar-Lezama [7] distill deep neural network (DNN) policies into tree policies and then verify them with an SMT solver. They proved correctness of distilled CartPole policies for the first 10 steps. Our verification confirms this, while finding concrete unsafe states at later steps (§ 4.2, Figure 3). Similarly, Jain et al. [17] verify tree policies with a tree-specific solver called Veritas and use policy predicate abstraction (PPA) (Vinzent, Sharma, and Hoffmann 2023) to build the reachable state set for an unbounded horizon. Schilling et al. [24] instead propagate sets of reachable states through tree policies in continuous time. For VESPA, we require the number of verified safe steps and counterexample regions together with the step at which they occur, and thus also choose a set-based representation (§ 2.1).
Verification and Repair of Deep Neural Network Policies In contrast to tree ensembles, verifying DNN policies faces additional challenges, especially because their decision boundaries are not axis-aligned. For instance, Trainify (Jin et al. [18]) discretizes the state space into finitely many abstract states and then trains and verifies a DNN policy on those abstract states. It then refines the discretization based on where the safety constraint is violated and retrains the DNN policy from scratch.
Closest to the adaptation step of VESPA are methods that repair DNN policies with counterexamples from a verifier ([9] (Yang et al. 2022; Wu, Zhang, and Vorobeychik 2024)). They train on the counterexamples where the verifier finds them, with an added penalty or a loss on verified bounds, whereas VESPA walks the counterexample regions back in time and uses them only as start states for fine-tuning.
Shielding As described by Alshiekh et al. [1], shielding adds a static component that restricts or overrides the actions of the learned policy at runtime. Following the general framework of shielding, Anderson et al. [3] propose to alternate between training a DNN policy and a verifiable symbolic policy. Shielding thus shifts the verification problem to the shield, which must itself be provably safe and remain in place at deployment, whereas VESPA verifies and adapts the learned policy itself.
Conclusion and Future Work
In this paper, we introduced VESPA, a verification and fine-tuning loop that turns counterexamples from reachability analysis into a training signal for fine-tuning. VESPA exploits the hard axis-aligned decision boundaries of tree policies to compute the reachable states, extracts a counterexample region from every violating set, and fine-tunes the policy from these regions. Our evaluation shows that the average return does not indicate whether a tree policy is safe, and that counterexamples from the verification are an effective training signal. On CP, VESPA reaches in two iterations the verified safe steps that UNINFORMED reaches in ten. On MC-C, it obtains a fully proven policy in 53 of 60 runs.
While VESPA does not yet prove a CP policy safe for the full horizon, the limiting factor is the memory required by the verification and not the policy adaptation. Even though our verifier scales to significantly more steps than other approaches, future work could still investigate more memory-efficient state representations. Furthermore, one could extend VESPA to tree ensembles, such as GRANDE (Marton et al. [21]). We expect that safety-critical applications will ask for a proof before a policy is deployed, and our results show that for tree policies such proofs are within reach.
Acknowledgments
This research was supported in part by the German Federal Ministry for Economic Affairs and Climate Action of Germany (BMWK) and by the German Federal Ministry for Research, Technology, and Space (BMFTR).
Detailed Results
Tables 1 and 2 report the results per fine-tuning iteration for CP and MC-C, including the average return and the paired comparison of VESPA and Uninformed.
Pruned and Unpruned Input Policies Table 3 splits the results of Tables 1 and 2 by pruned and unpruned input policies. The number of input safe steps for CP differs slightly, because of rounding errors near the splits, which depend on the tree layout. For VESPA, the two groups behave alike: on CP the mean gain in verified safe steps is and at a standard deviation of about 23, and on MC-C 26 and 27 of 30 runs are proven safe. Uninformed varies more. On CP, more of its unpruned runs are verified up to the memory limit (17 vs. 9 of 24), whereas on MC-C fewer of its unpruned runs are proven safe (21 vs. 25 of 30). These two shifts point in opposite directions, and neither is significant after correction for multiple comparisons. We therefore find no systematic effect of pruning.
Measuring the Over-Approximation
This section describes how we measured the values reported in § 4.2.
CP, per Step We drew 18,581 boxes at random from the verifications of 7 input policies and propagated each of them through . We compared the result with the smallest box around the exact image, which we approximated from inside by dense sampling, so that the measured excess is an upper bound. Its median lies between 0.001% and 0.02% of the width of the exact image, depending on the dimension.
MC-C, over the Full Horizon We verified the 6 distinct input policies (the pruned and the unpruned tree of a seed are the same policy) with start state regions, a coarser partition than in our experiments, and simulated 1024 concrete episodes from every region. Of the 2,737 regions without a proof, 2,698 (98.6%) contain an episode that misses the goal within steps. Only the remaining 39 regions can be affected by over-approximation. Per policy, these are at most 18 of the 1024 regions, i.e., 1.8 percentage points of the ratio of safe start state regions.
Finer Start Partition For 18 pretrained CP policies, we split the part of that leads to the first violation into 16 sub-boxes and verified every sub-box separately. In 16 of 21 cases, the two groups behave alike: on CP the mean gain in verified safe steps is and at a standard deviation of about 23, and on MC-C 26 and 27 of 30 runs are proven safe. Uninformed varies more. On CP, more of its unpruned runs are verified up to the memory limit (17 vs. 9 of 24), whereas on MC-C fewer of its unpruned runs are proven safe (21 vs. 25 of 30). These two shifts point in opposite directions, and neither is significant after correction for multiple comparisons. We therefore find no systematic effect of pruning.
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.
all sub-boxes are verified beyond the original first violating step, so the over-approximation does have an influence on the verified safe steps. As discussed in § 4.2, it does not impair the fine-tuning.
Pretrained Policies
We pretrain a single axis-aligned tree of depth 7 with the SYMPOL configurations (Marton et al. [20]), which use PPO (Schulman et al. [25]), for 50M environment steps on CP and 1M on MC-C. For CP, we use the checkpoint with the best evaluation return. For MC-C, we keep the best of 5 random trials per seed. The pruning of the SYMPOL implementation removes branches whose split thresholds lie outside the state space and, for discrete actions, merges leaves with the same action.
| 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 |
Table 4. Number of pretrained policies and runs. Every seed contributes a pruned and an unpruned policy.
Table 4 lists the number of policies. Tuning policies are used only for the hyperparameter optimization, and all reported results are obtained on the evaluation policies. For CP, the evaluation seeds are those whose initial verification ends with an unsafe verdict before it runs out of memory, which is not the case for 13 seeds. Three further seeds were excluded because their pretraining was incomplete or one of their two variants was missing. For MC-C, we only accept a pretrained policy if it reaches the goal within steps in at least 10% of the episodes.
| CP | MC-C | |
| Actions | discrete | continuous |
| Episode limit (steps) | 500 | 999 |
| Start region | ||
| Unsafe region | ||
| Goal region | ||
| Horizon | 200 | 200 |
| State representation | boxes | zonotopes |
| Start partition | 1 box | zonotopes |
| GPU (NVIDIA) | H200 | RTX PRO 6000 |
| Median time per verification | 180 s | 23 s |
Table 5. Environments and verification settings. CP follows the CartPole-v1 specification, MC-C the MountainCarContinuous-v0 specification of gymnax (Lange [19]). CP: cart position and pole angle (rad). MC-C: car position and velocity .
Verification Settings
Table 5 lists the environments and the verification settings. We verify CP with boxes and MC-C with zonotopes (§ 2.2), since the MC-C dynamics strongly couple position and velocity, whereas the CP policies switch actions frequently, so that the fragmentation by the tree dominates. Two sets are never merged into a larger enclosing set. The number of generators of a zonotope is limited to 24 by the order reduction of Girard [13], which replaces the smallest generators by an axis-aligned box that encloses them. All sets are propagated in 32-bit floating-point arithmetic with every bound rounded outwards, so that a safe verdict is also a proof with respect to floating-point effects. The reward of MC-C favors policies that reach the goal quickly (i.e., far below 200 steps).
Policy Adaptation and Hyperparameter Optimization
Loop Settings A candidate replaces the current policy if it is verified at least as deep (CP), or if it is safe or its ratio of safe start state regions is strictly higher (MC-C). A CP candidate whose verification runs out of memory beyond the depth of the current policy is accepted with its verified depth as a lower bound and ends the run. A rejected candidate is discarded, and the current policy is fine-tuned again with a different seed. VESPA and UNIFORMED use identical settings and seeds and differ only in (Eq. (7)). UNIFORMED still uses the verification, but only as a metric and to accept or reject candidates. On CP, fine-tuning episodes end at the verification horizon , while the reported return uses episodes of up to 500 steps, which can explain the lower return of the fine-tuned CP policies.
| Hyperparameter | CP | MC-C |
| Learning rate, split thresholds | ||
| Learning rate, split features | ||
| Learning rate, leaves | ||
| Learning rate, tree weights | ||
| Learning rate, action log-std | – | |
| Upper bound of action log-std at start | – | |
| Learning rate, critic | ||
| Entropy coefficient | ||
| Discount factor | ||
| GAE | ||
| Clipping coefficient | ||
| Value loss coefficient | ||
| Gradient norm clipping | ||
| Parallel environments | ||
| Steps per rollout | ||
| Update epochs | ||
| Minibatch size | ||
| Fine-tuning iterations per run (max.) | ||
| Environment steps per iteration | ||
| Reward at the first unsafe state | – | |
| Mixing probability | 0.5 (VESPA), 0 (Uninf.) |
Table 6. Fine-tuning hyperparameters of VESPA and UNINFORMED.
Hyperparameters Table 6 lists the fine-tuning hyperparameters. For CP, they follow Marton et al. [20] with two exceptions: a single learning rate of for all tree parameters, which is a common default for PPO (Schulman et al. [25]; Andrychowicz et al. [4]), and neither weight averaging nor learning rate reduction. A fine-tuning episode on CP ends at the first unsafe state with an additional reward of for both methods, whereas pretraining and the fine-tuning on MC-C use the standard reward. We chose among the values 2, 6, 10 and 14 in a random search over 25 configurations on the tuning policies. For MC-C, we compared 7 configurations on the tuning policies, separately for VESPA and UNINFORMED, and the same configuration ranks first for both. was fixed, since whether the goal is reached depends heavily on the actions taken at the beginning of an episode.
Verification of Alternative Pretraining Methods
VESPA does not make any assumptions on how the decision tree policy was obtained. In addition to SYMPOL, we therefore verified 21 decision trees extracted with VIPER (Bastani, Pu, and Solar-Lezama [7]) from a DQN teacher (maximum leaf counts of 2, 4, 8, 16, 32, 64 and 128 with 3 seeds each), using the settings of Appendix § 12. Figure 3 shows the three trees with an average return of at least 490 over 30 episodes. None of the 21 trees is verified safe for 200 steps. For 20 of them, we found concrete episodes that violate the safety constraint before step 200 among sampled start states.
Tree ensemble policies are future work, with Gradient-Based Decision Tree Ensembles (GRANDE) (Marton et al. [21]) being the natural extension of SYMPOL trees.
References
- [1]Alshiekh, M.; Bloem, R.; Ehlers, R.; Könighofer, B.; Niekum, S.; and Topcu, U. 2018. Safe Reinforcement Learning via Shielding. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2669–2678.arxiv.org/abs/1708.08611
- [2]Althoff, M.; Frehse, G.; and Girard, A. 2021. Set Propagation Techniques for Reachability Analysis. Annual Review of Control, Robotics, and Autonomous Systems, 4: 369–395.DOI
- [3]Anderson, G.; Verma, A.; Dillig, I.; and Chaudhuri, S. 2020. Neurosymbolic Reinforcement Learning with Formally Verified Exploration. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 6172–6183.arxiv.org/abs/2009.12612
- [4]Andrychowicz, M.; Raichuk, A.; Stańczyk, P.; Orsini, M.; Girgin, S.; Marinière, R.; Hussenot, L.; Geist, M.; Pietquin, O.; Michalski, M.; Gelly, S.; and Bachem, O. 2021. What Matters for On-Policy Deep Actor-Critic Methods? A Large-Scale Study. In International Conference on Learning Representations (ICLR).
- [5]Baier, C.; and Katoen, J.-P. 2008. Principles of Model Checking. Cambridge, MA: MIT Press.
- [6]Barto, A. G.; Sutton, R. S.; and Anderson, C. W. 1983. Neuronlike Adaptive Elements That Can Solve Difficult Learning Control Problems. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13(5): 834–846.DOI
- [7]Bastani, O.; Pu, Y.; and Solar-Lezama, A. 2018. Verifiable Reinforcement Learning via Policy Extraction. In Advances in Neural Information Processing Systems (NeurIPS), volume 31.arxiv.org/abs/1805.08328
- [8]Biere, A.; Cimatti, A.; Clarke, E.; and Zhu, Y. 1999. Symbolic Model Checking without BDDs. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS), volume 1579 of Lecture Notes in Computer Science, 193–207. Springer.
- [9]Boetius, D.; Leue, S.; and Sutter, T. 2023. A Robust Optimisation Perspective on Counterexample-Guided Repair of Neural Networks. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, 2712–2737. PMLR.arxiv.org/abs/2301.11342
- [10]Brockman, G.; Cheung, V.; Pettersson, L.; Schneider, J.; Schulman, J.; Tang, J.; and Zaremba, W. 2016. OpenAI Gym. arXiv preprint arXiv:1606.01540.arxiv.org/abs/1606.01540
- [11]Florensa, C.; Held, D.; Wulfmeier, M.; Zhang, M.; and Abbeel, P. 2017. Reverse Curriculum Generation for Reinforcement Learning. In Proceedings of the 1st Annual Conference on Robot Learning (CoRL), volume 78 of Proceedings of Machine Learning Research, 482–495. PMLR.arxiv.org/abs/1707.05300
- [12]Fuhrer, B.; Tessler, C.; and Dalal, G. 2025. Gradient Boosting Reinforcement Learning. In Proceedings of the 42nd International Conference on Machine Learning (ICML), volume 267 of Proceedings of Machine Learning Research, 17960–17985. PMLR.arxiv.org/abs/2407.08250
- [13]Girard, A. 2005. Reachability of Uncertain Linear Systems Using Zonotopes. In Hybrid Systems: Computation and Control (HSCC), volume 3414 of Lecture Notes in Computer Science, 291–305. Springer.
- [14]Girard, A.; and Le Guernic, C. 2008. Zonotope/Hyperplane Intersection for Hybrid Systems Reachability Analysis. In Hybrid Systems: Computation and Control (HSCC), volume 4981 of Lecture Notes in Computer Science, 215–228. Springer.
- [15]Huang, C.; Fan, J.; Chen, X.; Li, W.; and Zhu, Q. 2022. POLAR: A Polynomial Arithmetic Framework for Verifying Neural-Network Controlled Systems. In Automated Technology for Verification and Analysis (ATVA), volume 13505 of Lecture Notes in Computer Science, 414–430. Springer.arxiv.org/abs/2106.13867
- [16]Ivanovic, B.; Harrison, J.; Sharma, A.; Chen, M.; and Pavone, M. 2019. BaRC: Backward Reachability Curriculum for Robotic Reinforcement Learning. In 2019 International Conference on Robotics and Automation (ICRA), 15–21. IEEE.arxiv.org/abs/1806.06161
- [17]Jain, C.; Cascioli, L.; Devos, L.; Vinzent, M.; Steinmetz, M.; Davis, J.; and Hoffmann, J. 2024. Safety Verification of Tree-Ensemble Policies via Predicate Abstraction. In European Conference on Artificial Intelligence (ECAI), volume 392 of Frontiers in Artificial Intelligence and Applications, 1189–1197. IOS Press.DOI
- [18]Jin, P.; Tian, J.; Zhi, D.; Wen, X.; and Zhang, M. 2022. Trainify: A CEGAR-Driven Training and Verification Framework for Safe Deep Reinforcement Learning. In Computer Aided Verification (CAV), volume 13371 of Lecture Notes in Computer Science, 193–218. Springer.
- [19]Lange, R. T. 2022. gymnax: A JAX-based Reinforcement Learning Environment Library. https://github.com/RobertTLange/gymnax.
- [20]Marton, S.; Grams, T.; Vogt, F.; Lüdtke, S.; Bartelt, C.; and Stuckenschmidt, H. 2025. Mitigating Information Loss in Tree-Based Reinforcement Learning via Direct Optimization. In International Conference on Learning Representations (ICLR).arxiv.org/abs/2408.08761
- [21]Marton, S.; Lüdtke, S.; Bartelt, C.; and Stuckenschmidt, H. 2024. GRANDE: Gradient-Based Decision Tree Ensembles for Tabular Data. In International Conference on Learning Representations (ICLR).arxiv.org/abs/2309.17130
- [22]Moore, A. W. 1990. Efficient Memory-based Learning for Robot Control. Technical Report UCAM-CL-TR-209, University of Cambridge, Computer Laboratory.DOI
- [23]Moore, R. E.; Kearfott, R. B.; and Cloud, M. J. 2009. Introduction to Interval Analysis. Philadelphia, PA: SIAM.DOI
- [24]Schilling, C.; Lukina, A.; Demirović, E.; and Larsen, K. G. 2023. Safety Verification of Decision-Tree Policies in Continuous Time. In Advances in Neural Information Processing Systems (NeurIPS), volume 36, 14750–14769.DOI
- [25]Schulman, J.; Wolski, F.; Dhariwal, P.; Radford, A.; and Klimov, O. 2017. Proximal Policy Optimization Algorithms. arXiv preprint arXiv:1707.06347.arxiv.org/abs/1707.06347
- [26]Sutton, R. S.; and Barto, A. G. 2018. Reinforcement Learning: An Introduction. Cambridge, MA: MIT Press, second edition.
- [27]Tang, C.; Abbatt ematteo, B.; Hu, J.; Chandra, R.; Martín-Martín, R.; and Stone, P. 2025. Deep Reinforcement Learning for Robotics: A Survey of Real-World Successes. Annual Review of Control, Robotics, and Autonomous Systems, 8: 153–188.
- [28]Vasić, M.; Petrović, A.; Wang, K.; Nikolić, M.; Singh, R.; and Khurshid, S. 2022. MöeT: Mixture of Expert Trees and its Application to Verifiable Reinforcement Learning. Neural Networks, 151: 34–47.DOI
- [29]Verma, A.; Murali, V.; Singh, R.; Kohli, P.; and Chaudhuri, S. 2018. Programmatically Interpretable Reinforcement Learning. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, 5045–5054. PMLR.arxiv.org/abs/1804.02477