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

Luca Marzari, Enrico Marchesini · 2026

Read Probabilistic Verification of Recurrent Neural Networks for Single and Multi-Agent Reinforcement Learning by Luca Marzari, Enrico Marchesini (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14758.txt.

Introduction

Marzari and Marchesini propose RNN-ProVe, a probabilistic framework for verifying recurrent neural network policies. Such policies act where only part of the state is seen, and hidden state dynamics make checks hard. Existing tools lean on narrow assumptions or coarse over-approximations of hidden states. Policy-driven sampling instead maps the feasible hidden states under a trained policy. Error bounds then yield high-confidence estimates of violations. Tests on single-agent and team tasks claim stronger guarantees than rivals.

Catalog record

CREATORLuca Marzari, Enrico Marchesini
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50303
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.14758

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Probabilistic Verification of Recurrent Neural Networks for Single and Multi-Agent Reinforcement Learning Luca Marzari, Enrico Marchesini Abstract History-dependent policies induced by recurrent neural networks (RNNs) rely on latent hidden state dynamics, making verification in partially observable reinforcement learning (RL) challenging. Existing RNN verification tools typically rely on restrictive modeling assumptions or coarse over-approximations of the hidden state space, which can lead to overly conservative or inconclusive results. We propose RNN Pro babilistic Ve rification ( RNN-ProVe ), a probabilistic framework that estimates the likelihood of undesired behaviors in RNN-based policies. RNN-ProVe uses policy-driven sampling to approximate the set of hidden states that are feasible under a trained policy, and derives statistical error bounds to produce bounded-error, high-confidence estimates of behavioral violations. Experiments on partially observable single-agent and cooperative multi-agent tasks show that RNN-ProVe yields more quantitative, feasibility-aware probabilistic guarantees than existing tools, while scaling to recurrent and multi-agent settings. 1 Introduction Recurrent neural networks (RNNs) are widely used in reinforcement learning (RL) to handle partial observability and multiple agents ( 4 ; 21 ) . Such RNN-based policies learn hidden-state dynamics that encode past observations and actions, making decision-making depend on the interaction history rather than only the current input. Verifying such policies is challenging, as most existing verification tools are designed for feedforward neural networks ( 20 ; 40 ) . When applied to RNNs, verification is typically restricted to robustness analysis, where networks are checked over a single transition by bounding the effect of perturbations to a fixed input on the corresponding output. While effective for local robustness, this abstraction fails to capture the sequential and history-dependent nature of recurrent RL agents. In particular, assessing whether an RNN-based policy performs unsafe or undesired actions (or behaviors, interchangeably) requires reasoning about which hidden states can arise from feasible, policy-induced histories , that is, interactions the agent can actually encounter during execution (Fig. 1 ). Existing approaches addressing this challenge typically rely on explicit transition models to reason about recurrent policies, and verification remains computationally challenging even under these assumptions ( 1 ; 7 ; 10 ) . Moreover, these methods are limited in both scalability and expressivity: they fail to scale to multiple agents or high-dimensional spaces ( 23 ; 22 ) , and often yield only binary certificates (e.g., safe or unsafe ). Such binary outcomes are frequently uninformative in practice, as policies may differ substantially in how often violations occur across different feasible histories. In principle, sound verification of RNN-based policies would require enumerating all reachable hidden-state configurations during execution and checking whether any of them lead to undesired behavior. However, this requirement is equivalent to computing neural network preimage measures for which a desired behavior holds ( 19 ; 43 ) , a problem that is #P-hard due to the nonlinearity and nonconvexity of neural networks ( 27 ) . Hence, under standard complexity assumptions, obtaining an exact characterization of the feasible-history space is computationally infeasible. This observation suggests that, for recurrent policies in RL, exact worst-case verification is not only computationally prohibitive but also misaligned with the structure of history-dependent decision making. Figure 1: (a) Interval-based verification over-approximates the hidden state space, admitting infeasible histories. (b) RNN-ProVe assesses policies over probabilistically feasible histories, yielding more precise and informative certificates. These limitations motivate a probabilistic and quantitative perspective on verification for RNN-based policies. Rather than enumerating all feasible hidden states exactly, we aim to estimate the likelihood of undesired behavior by quantifying how much of the feasible-history space leads to behavioral violations under a trained policy. To this end, we introduce RNN Pro babilistic Ve rification ( RNN-ProVe ), a probabilistic framework that approximates the policy-induced feasible hidden state space using policy-driven sampling with explicit statistical error bounds, and produces bounded-error, high-confidence verification certificates. At its core, RNN-ProVe learns a feasibility oracle that distinguishes feasible from infeasible hidden state representations with respect to the distribution of histories induced by the policy during training. The oracle is implemented as a classifier trained on feasible representations encoded by the policy. RNN-ProVe then performs quantitative verification over probabilistically feasible histories identified by the classifier. Additionally, we derive statistical confidence bounds to determine the required sample sizes for verification, ensuring that the resulting certificates have provable error bounds and high statistical confidence. We evaluate RNN-ProVe on single-agent and cooperative multi-agent partially observable tasks, demonstrating that the framework scales to settings in which existing verification tools become overly conservative or inapplicable, while providing informative probabilistic assessments of behavioral risk. Our results suggest that probabilistic verification over feasible histories is not merely a heuristic relaxation, but a principled response to fundamental computational barriers. These outcomes motivate the following contributions: • We formulate the problem of probabilistic verification of recurrent RL policies under partial observability, explicitly accounting for the set of hidden states that are feasible under a trained policy. • We propose RNN-ProVe , a policy-driven probabilistic verification framework that combines feasibility learning with Monte Carlo estimation to quantitatively assess behavioral violations in RNN-based policies. • We extend the problem to fully cooperative multi-agent RL (MARL) and derive bounded-error, high-confidence guarantees for feasible-history identification and violation estimation, yielding a tractable approximation to an otherwise #P-hard verification problem. More broadly, this work advocates probabilistic verification over feasible histories as a principled foundation for reasoning about safety and reliability in history-dependent decision-making systems. 2 Preliminaries and Related Work At time t , an RNN produces an output y_{t} by using a hidden state representation h_{t} of an input sequence \mathbf{x}=(x_{1},\dots,x_{t}) . Figure 2: An explanatory RNN transition. Following the illustration of Fig. 2 , the transition function for a vanilla RNN is h_{t}=\sigma(W_{x}x_{t}+W_{h}h_{t-1}+b_{h}) , where W_{x},W_{h} are the input and recurrent weight matrices, b_{h} is a bias vector, and \sigma is typically a non-linear activation function. The output is derived via a linear transformation as y_{t}=W_{y}h_{t}+b_{y} , where W_{y} is the output weight matrix and b_{y} is another bias vector. This recursive structure enables RNNs, as well as gated variants such as LSTMs ( 12 ) and GRUs ( 8 ) , to model temporal dependencies over input sequences. RNNs in RL. In partially observable RL, an agent typically learns a policy \pi:\mathcal{H}\rightarrow\Delta(\mathcal{A}) ; where \mathcal{H} denotes the agent’s action-observation history (o_{0},a_{0},\ldots,o_{t-1}) , \mathcal{A} is the set of actions modeling the RNN’s output y , and o\in\mathcal{O} are observations (i.e., RNN’s input x ) distributed following a stochastic transition function T_{\mathcal{O}}:\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{O}) (where \mathcal{O},\mathcal{S} are the finite sets of observations and states, respectively) ( 3 ) . In practice, at time t , \pi uses the RNN’s hidden state h_{t} as a compressed history representation that depends on: (i) the previous hidden state h_{t-1} ; and (ii) the current observation o_{t} , to output an action. 1 1 1 For simplicity, we use h,\mathcal{H} for both histories and hidden states. When tackling problems with \mathcal{N} agents, we consider the setting where each agent i\in\mathcal{N} has a local observation space \mathcal{O}^{i} and conditions its policy on the local action-observation history ( 35 ) . To achieve this decentralization, centralized training with decentralized execution (CTDE) is the de facto standard paradigm ( 2 ; 5 ) . In CTDE, agents leverage privileged information during training (including the

Read the complete text