Neurosymbolic Reinforcement Learning with Formally Verified Exploration

Greg Anderson, Abhinav Verma, Isil Dillig, Swarat Chaudhuri

Abstract

Reinforcement learning (RL) agents typically learn through a process of trial and error, which poses significant risks in safety-critical applications such as autonomous driving and robotics. While "Safe RL" methods exist, they often provide only probabilistic safety or rely on static, overly restrictive symbolic rules. This paper presents REVEL, a neurosymbolic framework that guarantees worst-case safety during exploration in continuous state and action spaces. REVEL utilizes a hybrid policy consisting of a deep neural network for performance and a verifiable symbolic shield for safety. Through a novel functional mirror descent algorithm, the symbolic shield is iteratively updated to remain provably safe while adapting to the agent's learned behavior. Evaluation across ten benchmarks shows that REVEL eliminates safety violations entirely while achieving competitive or superior performance compared to state-of-the-art safe RL algorithms.

Introduction

The deployment of reinforcement learning (RL) in the real world is hindered by the lack of formal safety guarantees. In environments where a single failure can be catastrophic—such as a robot colliding with a human or an autonomous vehicle veering off-road—the standard exploration-exploitation trade-off is unacceptable. Existing approaches to safe RL generally fall into two categories: constrained optimization, which minimizes the expected cost of violations but lacks worst-case guarantees, and formal verification, which is often too computationally expensive to integrate into the training loop of deep neural networks.

REVEL (REinforcement learning with VERifiable Exploration) bridges this gap. It introduces a neurosymbolic approach that provides formal, worst-case safety guarantees without the need to verify complex neural networks at every training step. By combining the flexibility of neural networks with the rigor of formal methods, REVEL ensures that the agent never violates safety constraints during the learning process.

The REVEL Framework

The core innovation of REVEL is its hybrid policy architecture. The policy is composed of two distinct parts:

  1. The Neural Component ($f$): A standard deep neural network designed to optimize for high performance and handle complex environmental features.
  2. The Symbolic Shield ($g$): A simpler, piecewise-linear function that is mathematically tractable and easy to verify using formal methods.

During execution, a safety monitor oversees the neural network's proposed actions. If the monitor determines that a neural action could lead to a violation of safety constraints (based on a worst-case dynamics model), it intercepts the action and instead executes the symbolic shield. This "shielding" mechanism ensures that the overall system remains safe, regardless of the neural network's internal state. This approach creates a "verification loophole": you do not need to verify the complex neural network if you have a verifiable fallback that is guaranteed to keep the system safe.

Neurosymbolic Mirror Descent

To ensure that the safety shield does not become a bottleneck for performance, REVEL employs a functional mirror descent algorithm to update the policy. This process involves three key stages:

  • Lift: The current safe symbolic shield is "lifted" into the neurosymbolic space by initializing a neural network to mimic its behavior.
  • Update: The neural component is trained using standard gradient-based RL methods (e.g., DDPG) to maximize rewards. The safety monitor ensures zero violations during this phase by switching to the shield whenever necessary.
  • Project: The improved neural behavior is "projected" back into the symbolic space. Using imitation learning (specifically the DAgger algorithm), REVEL finds a new symbolic shield that approximates the neural network's performance while remaining provably safe via abstract interpretation.

This iterative process allows the shield to evolve, becoming less conservative as the agent learns safer ways to navigate the environment.

Experimental Evaluation

The authors evaluated REVEL on ten continuous control benchmarks, ranging from classic tasks like Pendulum and Mountain-car to complex navigation and driving scenarios like Obstacle2 and Adaptive Cruise Control. These environments were augmented with formal safety properties and worst-case dynamics models (e.g., defining the maximum possible acceleration a lead car might take).

Figure 4: Detailed training progress in the obstacle2 navigation task, showing REVEL's ability to maintain high rewards while adhering to safety constraints.

Key Results

REVEL demonstrated a remarkable ability to balance safety and performance. In tasks where unconstrained DDPG and probabilistic CPO incurred thousands of safety violations (e.g., over 4,900 for DDPG in Car-racing), REVEL maintained a perfect record of zero violations throughout the entire training process.

Figure 6: Performance comparison of REVEL against DDPG, Revel, CPO, and Static Shielding across various benchmark environments.

Furthermore, REVEL's dynamic shielding allowed it to outperform static shields in 4 out of 10 benchmarks and achieve competitive rewards in 7 out of 10 cases. Qualitative assessments in the "Obstacle2" task showed that while static shields often caused "jerky" movements due to frequent interventions, REVEL learned smooth, safe paths that avoided the need for emergency overrides.

Discussion and Limitations

While REVEL represents a significant step forward, it has limitations. The framework relies on an accurate "worst-case" model of environment dynamics; if this model is too conservative, the agent's performance may be unnecessarily restricted. Additionally, the computational cost of symbolic shield synthesis is high, accounting for approximately 87% of the total training time on average. Future work aims to reduce this overhead through incremental verification and by exploring more expressive symbolic languages for the shields.

Summary updated

BibTeX
@inproceedings{anderson2020neurosymbolic,
  author = {Greg Anderson and Abhinav Verma and Isil Dillig and Swarat Chaudhuri},
  title = {{Neurosymbolic Reinforcement Learning with Formally Verified Exploration}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=MerKL6cENAq},
}
Figure