Compositional Verification of Almost-Sure Büchi Objectives in MDPs

Marck van der Vegt, Kazuki Watanabe, Ichiro Hasuo, Sebastian Junges · 2025

Read Compositional Verification of Almost-Sure Büchi Objectives in MDPs by Marck van der Vegt, Kazuki Watanabe, Ichiro Hasuo, Sebastian Junges (2025) 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-2508-13087.txt.

Introduction

Marck van der Vegt and others verify long-run properties of probabilistic systems piece by piece, using the system's own compositional blueprint. The systems are Markov decision processes assembled as string diagrams. The question is whether some plan almost surely visits a target set infinitely often, a Buchi objective. Writing in twenty twenty-five, the team identifies the exact summary each component must export: its proper exit sets, plus reachability of a target state. That statistic is both sufficient and necessary for composition. The snag is that exit sets can multiply exponentially.

Two algorithms follow. One computes the statistic bottom-up, recursively and exactly. The other iterates plan refinement in polynomial time, never enumerating all exit sets. The pair gives verifiers a choice between completeness and speed on modular probabilistic systems.

Catalog record

CREATORMarck van der Vegt, Kazuki Watanabe, Ichiro Hasuo, Sebastian Junges
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE159 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-13087

Browse the full library · About the Tower of Babel

Full text

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

Compositional Verification of Almost-Sure Büchi Objectives in MDPs Thanks: I.H. was supported by ERATO HASUO Metamathematics for Systems Design Project (JST, No. JPMJER1603). I.H. and M.V. were supported by the ASPIRE grant (JST, No. JPMJAP2301). K.W. was supported by ACT-X grant (JST, No. JPMJAX23CU). Marck van der Vegt, Kazuki Watanabe, Ichiro Hasuo, Sebastian Junges Abstract This paper studies the verification of almost-sure Büchi objectives in MDPs with a known, compositional structure based on string diagrams. In particular, we ask whether there is a strategy that ensures that a Büchi objective is almost-surely satisfied. We first show that proper exit sets — the sets of exits that can be reached within a component without losing locally — together with the reachability of a Büchi state are a sufficient and necessary statistic for the compositional verification of almost-sure Büchi objectives. The number of proper exit sets may grow exponentially in the number of exits. We define two algorithms: (1) A straightforward bottom-up algorithm that computes this statistic in a recursive manner to obtain the verification result of the entire string diagram and (2) a polynomial-time iterative algorithm which avoids computing all proper exit sets by performing iterative strategy refinement. 1 Introduction Markov decision processes (MDPs) are a ubiquitous model to describe systems with uncertain action outcomes. Their efficient verification is hindered by typical state space explosion problems, see e.g., [ 1 , 12 ] . To overcome this state space explosion, a promising research direction to overcome scalability concerns is to explicitly capture and utilize the (compositional) structure of the MDP [ 5 , 13 , 16 ] . Concretely, we consider sequentially composed MDPs (potentially with loops), that is, we consider MDPs whose state space is partitioned into components . Specifically, we study the setting in which these components and their interaction is specified as string diagrams [ 19 ] : That is, components are MDPs with entrance and exit states and their composition is defined by a number of operations that glue these components together to obtain the monolithic MDP (see e.g., Fig. 1 ). The key concept in compositional verification is then to verify objectives without constructing the monolithic MDP, but rather, by (iteratively or exhaustively) analyzing the components and combining the result of their analysis. This has been done for quantitative reachability in [ 19 , 22 ] , but not for almost-sure Büchi objectives. Although the analysis of Büchi objectives on a monolithic MDP can be done in polynomial time in the number of states of the MDP, the size of the MDPs is often prohibitively large. Compositional approaches avoid the necessity to handle the monolithic MDP. The key question this paper answers affirmatively is whether such a compositional approach can work for almost-sure Büchi objectives. We study MDPs with a set of marked states, called the Büchi states , and algorithmically answer whether given an entrance it is possible to win the almost-sure Büchi objective, that is, can we visit a Büchi state infinitely often with probability one. In this paper, we first discuss what information is necessary to sufficiently describe the behavior of the components exhaustively . We call this information the solution . The solution should include for each entrance the set of exits that can be reached using strategies that we call no-lose , that is, a strategy which avoid surely violating the Büchi objective in the component. We call the set of reachable exits the proper exit set . Intuitively, after playing a no-lose strategy, we can reach a proper exit which is connected to an entrance of another component, after which we play another no-lose strategy. However, constantly playing no-lose strategies is not sufficient to satisfy the Büchi objective. In the solution, beside the proper exit set we must therefore also include whether there is a positive probability of reaching a Büchi state. If for a given entrance, there exists a no-lose strategy that can reach a Büchi state, then reaching this entrance infinitely often implies satisfaction of the Büchi objective. We call the combination of the proper exit set and the positive reachability of a Büchi state the effect of the strategy and it is the essential information for our compositional solution . The characterization of the problem in terms of a compositional solution gives rise to a natural (exhaustive) algorithm in the spirit of [ 19 , 21 ] : Consider the abstract syntax tree of the string diagram, first analyze the leafs of this tree exhaustively by computing its solution, and then compose the analysis results. The exhaustive analysis is exponential in the number of exits, but polynomial in the number of components. Compared to the quantitative reachability case [ 19 , 21 ] , this is already good news, because in the quantitative case, the computation can be superpolynomial even with a constant number of exits per component. Our second (iterative) algorithm avoids computing all possible effects by taking the context of each component into account, inspired by a compositional formulation of value iteration in [ 22 ] . In contrast to existing work, this algorithm can limit the amount of iterations necessary by determining that certain entrances may not be reached by any winning strategy. In particular, we start with a strategy that reaches as many entrances as possible, and refine this strategy by pruning entrances from which we cannot avoid losing. Our iterative algorithm mimics the classical Büchi algorithm [ 7 , 6 , 4 ] on the level of components. We show that the sets of possible effects computed by the exhaustive algorithm exhibit a join semilattice structure, which the iterative algorithm uses to prevent computing all effects, yielding a polynomial time algorithm. In conclusion, the contributions of this work are a characterization of the necessary and sufficient information about the behavior of a component in order to prove satisfaction of a Büchi objective globally, an exponential-time bottom-up algorithm that computes this information on individual components and composes them according to the structure of the string diagram, and an iterative approach that avoids the exponential influence of the number of exits. 2 Preliminaries For n\in{\mathbb{N}} , [n] denotes the set \{1,2,\dots,n\} . We denote the disjoint union by \uplus . We use \nu and \mu to denote the greatest and least fixpoint operators, respectively. A (directed) graph \mathcal{G}=\langle V,E\rangle is a tuple with finitely many vertices V and edges E\subseteq V\times V . The successors of x\in V are \mathrm{Post}(x)\vcentcolon=\{y\in V\mid\langle x,y\rangle\in E\} . Similarly, \mathrm{Pre}(y)\vcentcolon=\{x\in V\mid\langle x,y\rangle\in E\} are the predecessors of y\in V . We lift \mathrm{Post} and \mathrm{Pre} to sets: \mathrm{Post}(X)\vcentcolon=\bigcup_{x\in X}\mathrm{Post}(x) , \mathrm{Pre}(X)\vcentcolon=\bigcup_{x\in X}\mathrm{Pre}(x) . We are interested in almost-sure acceptance in Markov decision processes [ 2 , 11 ] (MDPs). Then, the amplitude of probabilities is irrelevant—a non-zero probability, however small it is, can break almost-sure acceptance. Therefore, we study the following abstraction of MDPs (see, e.g. [ 3 ] ), which preserves all results. Definition 1 (MDP graph and strategy) An MDP graph {{M}}\vcentcolon=\langle V_{1},V_{P},E\rangle is a graph \langle V,E\rangle where V\vcentcolon=V_{1}\uplus V_{P} . V_{1} are the player-1 vertices and V_{P} are the probabilistic vertices . A strategy \sigma\colon V_{1}\to\mathcal{P}\left\lparen V_{P}\right\rparen maps player-1 vertices to successor vertices, such

Read the complete text