Fixed Point Certificates for Reachability and Expected Rewards in MDPs
Krishnendu Chatterjee, Tim Quatmann, Maximilian Schäffeler, Maximilian Weininger, Tobias Winkler, Daniel Zilken · 2025
Read Fixed Point Certificates for Reachability and Expected Rewards in MDPs by Krishnendu Chatterjee, Tim Quatmann, Maximilian Schäffeler, Maximilian Weininger, Tobias Winkler, Daniel Zilken (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-2501-11467.txt.
Introduction
Krishnendu Chatterjee and five co-authors build proof slips that let anyone check a model checker's answer cheaply. Checkers can err, and a wrong pass on a safety claim is a grave risk. Their 2025 work gives slips for chance-based models that mix choice and odds, the Markov decision processes.
The slips rest on plain fixed-point math and work for any finite model of the kind. Stock methods can mint them with little extra cost. The team proved the slips sound in a proof assistant and built a checked checker for them. A standard checker was taught to mint slips too. The first formal check of a known benchmark set caps the work. Trust can now be earned line by line.
Catalog record
| CREATOR | Krishnendu Chatterjee, Tim Quatmann, Maximilian Schäffeler, Maximilian Weininger, Tobias Winkler, Daniel Zilken |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 154 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-11467
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Fixed Point Certificates for Reachability and Expected Rewards in MDPs Thanks: This project has received funding from the ERC CoG 863818 (ForM-SMArt), the Austrian Science Fund (FWF) 10.55776/COE12, a KI-Starter grant from the Ministerium für Kultur und Wissenschaft NRW, the DFG RTG 378803395 (ConVeY), the EU’s Horizon 2020 research and innovation programmes under the Marie Sklodowska-Curie grant agreement Nos. 101034413 (IST-BRIDGE) and 101008233 (MISSION), and the DFG RTG 2236 (UnRAVeL). Experiments were performed with computing resources granted by RWTH Aachen University under project rwth1632. Krishnendu Chatterjee, Tim Quatmann, Maximilian Schäffeler, Maximilian Weininger, Tobias Winkler, Daniel Zilken Abstract The possibility of errors in human-engineered formal verification software, such as model checkers, poses a serious threat to the purpose of these tools. An established approach to mitigate this problem are certificates —lightweight, easy-to-check proofs of the verification results. In this paper, we develop novel certificates for model checking of Markov decision processes (MDPs) with quantitative reachability and expected reward properties. Our approach is conceptually simple and relies almost exclusively on elementary fixed point theory. Our certificates work for arbitrary finite MDPs and can be readily computed with little overhead using standard algorithms. We formalize the soundness of our certificates in Isabelle/HOL and provide a formally verified certificate checker . Moreover, we augment existing algorithms in the probabilistic model checker Storm with the ability to produce certificates and demonstrate practical applicability by conducting the first formal certification of the reference results in the Quantitative Verification Benchmark Set. 1 Introduction Markov decision processes (MDPs) [ 48 , 7 , 5 ] are the model for sequential decision making in probabilistic environments. Their many applications [ 53 , 32 ] frequently require computing reachability probabilities towards an (un-) desired system state, as well as the expected rewards (or costs) accumulated until doing so. MDP model checking amounts to computing (approximations of) these quantities in a mathematically rigorous way, with a formal guarantee of their correctness and precision. Various mature MDP model checking tools such as PRISM [ 42 ] , mcsta [ 28 ] , and Storm [ 33 ] exist. Figure 1 shows an example MDP. Who checks the model checker? The possibility of errors in complex, human-engineered formal verification tools is a delicate issue: How formal is a verification result produced by an informal , i.e., unverified implementation? We highlight four sources of errors: (i) classic implementation bugs, (ii) unintentionally unsound algorithms [ 8 , 23 ] , optimizations, and heuristics, (iii) numerical errors due to floating point arithmetic [ 27 ] , and (iv) errors in third-party back end libraries or tools, e.g., commercial LP solvers [ 29 ] . Certifying algorithms [ 44 ] are a paradigm for establishing trust in implementations. A certifying algorithm produces a concise, easily verifiable proof—a certificate —of its result. The certificate can be checked independently, possibly even by an external, simpler program amenable to formal verification, or by a third party. Formally verified certificate checkers are already employed in tool competitions on software verification [ 12 ] or SAT-solving [ 9 ] . Existing proposals for certifying MDPs [ 34 , 21 , 35 ] , however, have some drawbacks (detailed further below) hindering wider adoption in the community and its competitions [ 25 , 15 , 3 ] . The goal of this paper is to establish a new standard for certified MDP model checking, with a focus on applicability and extensibility. Our contributions towards this goal are as follows: • We present fixed point certificates for two-sided bounds on extremal reachability probabilities and expected rewards (Tables 1 , 2 ). Our certificates are sound and complete for arbitrary finite MDPs without structural restrictions. • We formalize the theory in Isabelle/HOL [ 46 ] , proving soundness of our certificates, and generate a formally verified certificate checker implementation . • We implement a certifying variant of [ 29 ] Interval Iteration [ 8 ] with floating point arithmetic in Storm [ 33 ] . Using this, we give certified reference results for the Quantitative Verification Benchmark Set [ 32 ] . s \frac{1}{2} \frac{1}{2}\mid 1 t 1 1\mid 0 z 0 0\mid\infty s Certificate for upper bounds: Certificate for lower bounds: \frac{1}{3} \frac{1}{3} \frac{1}{3} Figure 1: An MDP with states S=\{z,s,t\} , two actions (distinguished by solid and dashed edges), uniform probabilities, and target set T=\{t\} . The annotations above and below each state are a certificate for upper and lower bounds on \mathbb{P}^{\min}(\lozenge T) , resp. Extensibility towards further properties is enabled by our simple, clean theory summarized as four guiding principles : (GP 2 ) We characterize the quantities of interest as a fixed point of basic, easy-to-evaluate Bellman-type operator [ 11 ] . The fundamental certification mechanism is to use fixed point induction for proving bounds on the least or greatest fixed point. (GP 3 ) We certify qualitative reachability properties using ranking functions which are amenable to fixed point induction, too. (GP 4.2 ) As the basic Bellman operators frequently have undesired, spurious fixed points [ 13 , 23 , 39 ] (often related to end components [ 2 ] ), we consider slight modifications requiring qualitative reachability information which we certify following GP 3 . (GP 4.3 ) When GP 4.2 is insufficient or not applicable, we implicitly include a witness strategy in our certificate. Technical challenges still arise in concretely applying these guiding principles. For instance, a key novelty of our paper is a ranking-function type certificate for not almost sure reachability ( Proposition 2 ), which is surprisingly involved. Table 1: Our reachability certificates. Sound and complete for arbitrary finite MDPs. Certificate Condition(s) Explanation Upper bounds on minimal reachability probabilities: \forall s\in S\colon\mathbb{P}^{\min}_{s}(\lozenge T)\leq x(s) [ Proposition 3 ] x\in[0,1]^{S} \mathcal{B}^{\min}(x)\leq x min -Bellman operator decreases value of all states Upper bounds on maximal reachability probabilities: \forall s\in S\colon\mathbb{P}^{\max}_{s}(\lozenge T)\leq x(s) [ Proposition 3 ] x\in[0,1]^{S} \mathcal{B}^{\max}(x)\leq x max -Bellman operator decreases value of all states Lower bounds on minimal reachability probabilities: \forall s\in S\colon\mathbb{P}^{\min}_{s}(\lozenge T)\geq x(s) [ Proposition 4 ] x\in[0,1]^{S} \mathcal{B}^{\min}(x)\geq x min -Bellman operator increases value of all states r\in{\overline{\mathbb{N}}}^{S} \mathcal{D}^{\max}(r)\leq r r upper bounds maximal distances to T x(s){>}0\implies r(s){<}\infty positive reachability necessitates finite distance Lower bounds on maximal reachability probabilities: \forall s\in S\colon\mathbb{P}^{\max}_{s}(\lozenge T)\geq x(s) [ Proposition 6 ] x\in[0,1]^{S} \mathcal{B}^{\max}(x)\geq x max -Bellman operator increases value of all states r\in{\overline{\mathbb{N}}}^{S} \mathcal{D}^{\min}_{x\uparrow}(r)\leq r r upper bounds min. distances to T via x -incr. actions x(s){>}0\implies r(s){<}\infty positive reachability necessitates finite distance Related work. Closest to our work are the previous proposals for certificates in MDP model checking: [ 34 , Sec. 4] formally verifies a theory of certificates for reachability objectives, which is however limited to upper bounds on maximal and lower bounds on the minimal probabilities. [ 21 ] presents so-called “Farkas certificates” for reachability; however, it does not offer a formally verified certificate checker, is limited to MDPs without end components (ECs), and does not address certificate generation explicitly. With similar limitations, [ 6 ] provides Farkas certificates for multiple reachability or mean payoff objectives, which can be computed via linear programming. [ 35 ] suggests lifting the EC assumptions from [ 21 ] by certifying the full maximal EC