VESPA: Verifiable Symbolic Policy Adaptation for Safe Reinforcement Learning

Paul König, Sascha Marton, Stefan Lüdtke, Christian BarteltarXiv 2026 · arXiv

TL;DR

VESPA (VErifiable Symbolic Policy Adaptation) is a novel framework that uses formal verification as a training signal to fix unsafe reinforcement learning (RL) agents. By extracting "counterexample regions" from failed safety proofs and using them for targeted fine-tuning, VESPA can transform unsafe decision tree policies into provably safe ones significantly faster than standard retraining.

What Problem Does This Paper Address?

Reinforcement learning agents are notoriously difficult to deploy in safety-critical environments like robotics or autonomous driving because they prioritize expected return over absolute safety. While formal verification (like reachability analysis) can prove whether a policy is safe, it usually provides a binary verdict: "safe" or "unsafe."

If a policy is found to be unsafe, the standard approach is to retrain from scratch with different parameters and hope the next candidate passes. This "guess-and-verify" loop is incredibly inefficient. The authors identify a critical gap: the lack of a mechanism to use the reasons for a verification failure to systematically improve the policy.

Methods

The authors introduce VESPA, which focuses on symbolic, tree-based policies (specifically SYMPOL). These policies are highly interpretable and use axis-aligned decision boundaries, making them uniquely suited for efficient reachability analysis.

The VESPA loop consists of three main stages:

  1. Verify: The framework uses set-based reachability analysis (propagating "boxes" or "zonotopes" through the environment dynamics) to find states that violate safety constraints.
  2. Extract: When a violation is found, VESPA backtracks from the failure point to identify a "counterexample region"—a set of predecessor states that inevitably lead to the safety breach.
  3. Fine-tune: Instead of retraining from scratch, VESPA performs targeted fine-tuning using PPO. It modifies the initial state distribution to sample heavily from these counterexample regions, effectively creating a "curriculum" that teaches the agent how to navigate its most dangerous failure modes.
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.

Datasets

The framework was evaluated on two classic continuous control benchmarks:

  • CartPole (CP): The agent must balance a pole on a cart without falling over or exiting a defined area.
  • MountainCarContinuous (MC-C): The agent must drive a car up a steep hill, requiring it to build momentum through swing-ups.

Key Insights and Ideas

  • Return $\neq$ Safety: One of the most striking findings is that a high average return is a poor proxy for safety. Policies with near-perfect scores can still fail verification because they harbor rare, catastrophic failure modes that standard evaluation episodes never encounter.
  • Counterexamples as Training Signals: The "aha moment" is treating the output of a formal verifier not just as a grade, but as a map. By pinpointing exactly where the policy fails, the verifier provides a high-density training signal that is far more efficient than undirected exploration.
  • Efficiency Gains: VESPA reached safety milestones in just two iterations that an "uninformed" baseline (fine-tuning without counterexample sampling) took ten iterations to achieve.
Comparison showing that high return does not guarantee safety. Even policies with maximal return can fail verification early.

Key Results

  • CartPole: VESPA increased the mean number of verified safe steps from 63.8 to over 92.7. It scaled to horizons nearly ten times longer than those verified in prior work on this benchmark.
  • MountainCarContinuous: VESPA successfully turned unsafe policies into fully provably safe ones in 53 out of 60 runs. On average, it required only 2.2 fine-tuning iterations to reach a full safety proof.
  • Speed: The targeted approach is significantly faster than uninformed fine-tuning, as shown in the rapid convergence of verified safe steps over iterations.
Verified safe steps on CartPole over fine-tuning iterations, showing VESPA's rapid improvement over the uninformed baseline.

Limitations and Future Work

The primary limitations of VESPA stem from the inherent challenges of formal verification:

  • Model Dependency: It requires a known, deterministic model of the environment dynamics.
  • State Explosion: Reachability analysis is memory-intensive. On CartPole, the verifier often ran out of memory before reaching the full 200-step horizon, though it still outperformed previous methods.
  • Policy Scope: Currently, the method is tailored to single decision trees. The authors suggest that extending this to tree ensembles (like Gradient-Based Decision Tree Ensembles) is a promising next step to handle more complex tasks while maintaining verifiability.

Summary updated

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 ($\textbf{VE}$rifiable $\textbf{S}$ymbolic $\textbf{P}$olicy $\textbf{A}$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/
BibTeX
@misc{konig2026vespa,
  author = {Paul König and Sascha Marton and Stefan Lüdtke and Christian Bartelt},
  title = {{VESPA: Verifiable Symbolic Policy Adaptation for Safe Reinforcement Learning}},
  year = {2026},
  eprint = {2611.24083},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.24083},
}
Figure