💻 computer science

Probabilistic Verification of Recurrent Neural Networks for Single and Multi-Agent Reinforcement Learning

The paper introduces RNN-ProVe, a probabilistic framework that estimates the likelihood of undesired behaviors in recurrent neural network-based policies for single and multi-agent reinforcement learning by using policy-driven sampling to overcome the limitations of existing verification tools in partially observable environments.

Original authors: Luca Marzari, Enrico Marchesini

Published 2026-05-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Luca Marzari, Enrico Marchesini

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are training a robot to navigate a maze. This robot has a special "memory" (a Recurrent Neural Network, or RNN) that helps it remember where it has been, so it doesn't just react to what it sees right now, but makes decisions based on its entire journey so far.

The problem is: How do we know this robot won't accidentally crash into a wall?

The Old Way: The "Worst-Case" Guess

Traditional safety checkers try to prove the robot is safe by looking at every possible thing that could ever happen. They imagine every possible memory the robot might have, even the ones that are impossible in real life (like the robot remembering a wall that doesn't exist).

Because they have to check every single possibility, including the impossible ones, they often get stuck. It's like trying to find a specific needle in a haystack by checking every single piece of straw, even the ones that were never in the barn to begin with. This makes the process incredibly slow, and often, they just give up and say, "We can't be sure," or they assume the robot is unsafe just to be safe, which isn't very helpful.

The New Way: RNN-ProVe (The "Real-Life" Detective)

The authors of this paper, Luca Marzari and Enrico Marchesini, created a new tool called RNN-ProVe. Instead of checking every impossible fantasy, they ask a smarter question: "What are the actual memories this robot has built up while it was learning?"

Here is how it works, using a simple analogy:

1. The "Feasibility Oracle" (The Memory Filter)

Imagine the robot went through thousands of training runs. During this time, it built up a specific set of "real" memories.

Old tools look at the entire library of all possible memories (including fake ones).
RNN-ProVe trains a special "Memory Filter" (a classifier). This filter learns to distinguish between a real memory (one the robot actually experienced) and a fake memory (one that could never happen).

Think of it like a bouncer at a club. The bouncer (the filter) checks your ID. If your ID says you were actually at the party (a feasible history), you get in. If your ID is fake (an impossible history), you are turned away. RNN-ProVe only checks the safety of the people who actually made it past the bouncer.

2. The "Probability" Check (The Risk Meter)

Once the filter separates the real memories from the fake ones, RNN-ProVe doesn't try to check every single real memory (which is still too hard). Instead, it takes a random sample of the real memories.

It asks: "Out of 1,000 real memories we picked, how many led to a crash?"

If 10 out of 1,000 led to a crash, it doesn't say "The robot is unsafe."
It says: "There is a 1% chance the robot will crash in this specific situation, and we are 99% confident that this number is accurate."

This is like a weather forecaster. Instead of saying "It will definitely rain" or "It will definitely not rain," they say, "There is a 30% chance of rain, based on the data we have." This gives a much more useful, quantitative answer.

Why This Matters

The paper tested this on two types of games:

Single Agent: One robot navigating a grid.
Multi-Agent: Two robots working together to push a box.

The Results:

Speed: The old tools took minutes or hours to check small grids and gave up on larger ones. RNN-ProVe did the same checks in milliseconds.
Accuracy: The old tools often found "fake" problems (false alarms) because they checked impossible memories. RNN-ProVe ignored the impossible ones and found the real risks.
Teamwork: The old tools couldn't handle teams of robots working together. RNN-ProVe handled the multi-agent team perfectly, checking if any of the team members might make a mistake.

The Bottom Line

RNN-ProVe is a new way to verify AI safety that stops trying to check every impossible scenario. Instead, it focuses on what actually happens during training. By filtering out the impossible and sampling the real, it gives us a fast, reliable, and mathematical "risk percentage" for how often a smart robot might make a mistake.

It turns a scary, unsolvable math problem into a manageable, statistical estimate that tells us exactly how safe our history-dependent AI really is.

Technical Summary: RNN Probabilistic Verification (RNN-ProVe)

Problem Statement

Recurrent Neural Networks (RNNs) are widely employed in Reinforcement Learning (RL) to handle partial observability and multi-agent coordination by maintaining latent hidden states that encode interaction history. Verifying these policies is fundamentally challenging because the decision-making process depends on the entire history of observations and actions, not just the current input.

Existing verification tools for RNNs primarily focus on robustness analysis against bounded input perturbations over a fixed horizon. These methods typically rely on coarse geometric over-approximations (e.g., intervals or hyperrectangles) of the hidden state space. In the context of RL, this approach admits spurious hidden states—combinations of neuron values that are mathematically possible within the network's bounds but are infeasible given the specific policy and environment dynamics. Consequently, these tools often produce overly conservative results or false positives.

Furthermore, exact verification of RNN-based policies requires enumerating all reachable hidden-state configurations to check for undesired behaviors. This problem is equivalent to computing neural network preimage measures, which is #P-hard due to the nonlinearity and nonconvexity of neural networks. Exact characterization is computationally infeasible for non-trivial policies, and existing methods fail to scale to multi-agent settings or high-dimensional spaces.

Methodology: RNN-ProVe

The authors propose RNN Probabilistic Verification (RNN-ProVe), a framework that shifts from exact worst-case verification to probabilistic verification over feasible histories. Instead of attempting to enumerate all possible hidden states, RNN-ProVe estimates the likelihood of undesired behaviors by quantifying the volume of the feasible hidden state space that leads to violations.

The framework operates through three main phases:

Feasibility Oracle Learning:
- During the RL training phase, the agent explores the environment, generating a dataset of state-hidden state pairs $(s, h)$ .
- RNN-ProVe trains a feasibility classifier $C: S \times H \to \{0, 1\}$ on this dataset. This classifier learns to distinguish between hidden states that are actually reachable under the trained policy (feasible) and those that are not (infeasible).
- This step leverages the universal approximation theorem to approximate the complex, lower-dimensional manifold of feasible histories within the high-dimensional hidden state space.
Policy-Driven Sampling and Verification:
- For a specific state of interest, the method samples candidate history vectors from the hidden state domain.
- The trained classifier $C$ acts as an oracle, filtering out infeasible samples and retaining only those hidden states $h^*$ that correspond to valid interaction histories leading to the current state.
- The policy is then evaluated on these validated histories to determine if they result in a violation (e.g., selecting an unsafe action).
Statistical Estimation with Error Bounds:
- The framework computes the ratio of violating validated histories to the total number of validated histories to estimate the violation volume.
- Crucially, RNN-ProVe derives statistical confidence bounds using Hoeffding's inequality. It decomposes the total error tolerance $\epsilon$ $ϵ$ and confidence parameter $\delta$ $δ$ into two components:
  - Classifier Error: The accuracy of the feasibility oracle.
  - Sampling Variance: The statistical error from the Monte Carlo estimation.
- This allows the framework to produce bounded-error, high-confidence certificates regarding the probability of behavioral violations.

Key Contributions

The paper makes the following specific contributions:

Problem Formulation: It formally defines the problem of probabilistic verification for recurrent RL policies under partial observability, explicitly accounting for the set of feasible hidden states induced by a trained policy.
RNN-ProVe Framework: It introduces a novel framework combining feasibility learning with Monte Carlo estimation to quantitatively assess behavioral violations in RNN-based policies.
Multi-Agent Extension: It extends the verification problem to fully cooperative Multi-Agent RL (MARL). It derives bounded-error, high-confidence guarantees for feasible-history identification and violation estimation in decentralized settings, providing a tractable approximation to an otherwise #P-hard problem.
Theoretical Guarantees: It provides a theoretical proof (Theorem 2) that the estimated violation volume satisfies specific error and confidence bounds, contingent on the sample sizes of the classifier validation and the verification sampling.

Experimental Results

The authors evaluated RNN-ProVe on single-agent navigation tasks and cooperative multi-agent "BoxPushing" (BP) tasks using DRQN policies.

Scalability: RNN-ProVe demonstrated significant scalability advantages. In navigation tasks, baseline linearization-based methods required minutes to hours for small environments (4x4, 8x8) and timed out on larger environments (16x16). In contrast, RNN-ProVe produced quantitative results in milliseconds across all tested grid sizes.
Accuracy vs. Baselines:
- Compared to naive Monte Carlo (uniform sampling without feasibility filtering), RNN-ProVe provided accurate estimates. Naive sampling yielded significantly inflated violation rates (e.g., ~23% vs. ~1.6% in 4x4) because it tested infeasible hidden states that do not occur in practice.
- Compared to exact linearization baselines (where feasible), RNN-ProVe produced comparable violation estimates (e.g., ~1.42% vs. ~1.44% in 4x4) but with probabilistic guarantees and orders of magnitude less computation time.
Multi-Agent Performance: The framework successfully verified cooperative policies in the BP domain (10x10 and 20x20 grids), identifying mean violation rates of approximately 1.18% and 1.7%, respectively. Existing tools could not be directly applied to these cooperative settings.
Insight: The experiments revealed that even policies with high average returns exhibit non-uniform generalization across feasible hidden states, with specific sensitivities near obstacles that standard empirical evaluations miss.

Significance and Claims

The paper argues that exact worst-case verification for recurrent RL policies is not only computationally prohibitive but also misaligned with the structure of history-dependent decision-making. The authors claim that probabilistic verification over feasible histories is not merely a heuristic relaxation but a principled response to fundamental computational barriers.

By focusing on the set of hidden states that are actually reachable under a policy, RNN-ProVe provides quantitative, feasibility-aware probabilistic guarantees. This approach yields more informative certificates than binary "safe/unsafe" outcomes or overly conservative robustness checks, enabling a better understanding of policy reliability and generalization in complex, partially observable, and multi-agent environments. The work advocates for this probabilistic perspective as a foundational approach for reasoning about safety in history-dependent systems.