Efficient Strategy Synthesis for MDPs via Hierarchical Block Decomposition

Alexandros Evangelidis, Gricel Vázquez, Simos Gerasimou · 2025

Read Efficient Strategy Synthesis for MDPs via Hierarchical Block Decomposition by Alexandros Evangelidis, Gricel Vázquez, Simos Gerasimou (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-2506-17792.txt.

Introduction

Alexandros Evangelidis, Gricel Vazquez, and Simos Gerasimou present, in a 2025 paper, a faster way to compute good strategies for large decision problems under uncertainty. Such problems, modeled as Markov decision processes, capture sequential choices in systems from software product lines to robots. Standard strategy synthesis fails to scale when the state space grows huge.

Their approach breaks the problem into blocks and refines them step by step. At each round, it picks the most fragile regions of the model for finer treatment, and leaves the rest coarse. That balance keeps accuracy where it matters and saves work elsewhere. They prove the combined strategy is near optimal under standard assumptions. Across cases with up to a million states, the method ran up to twice as fast as a leading tool.

Catalog record

CREATORAlexandros Evangelidis, Gricel Vázquez, Simos Gerasimou
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE56 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-17792

Browse the full library · About the Tower of Babel

Full text

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

Efficient Strategy Synthesis for MDPs via Hierarchical Block Decomposition Thanks: Identify applicable funding agency here. If none, delete this. Alexandros Evangelidis, Gricel Vázquez, Simos Gerasimou Abstract Software-intensive systems, such as software product lines and robotics, utilise Markov decision processes (MDPs) to capture uncertainty and analyse sequential decision-making problems. Despite the usefulness of conventional policy synthesis methods, they fail to scale to large state spaces. Our approach addresses this issue and accelerates policy synthesis in large MDPs by dynamically refining the MDP and iteratively selecting the most fragile MDP regions for refinement. This iterative procedure offers a balance between accuracy and efficiency, as refinement occurs only when necessary. Through a comprehensive empirical evaluation comprising diverse case studies and MDPs up to 1M states, we demonstrate significant performance improvements yielded by our approach compared to the leading probabilistic model checker PRISM (up to 2x), thus offering a very competitive solution for real-world policy synthesis tasks in larger MDPs. Accelerating Policy Synthesis in Large MDPs via Dynamic Refinement I Introduction Modern software-intensive systems, ranging from cloud microservices [ 1 , 2 ] with frequent deployments to self-adaptive systems and autonomous robots that navigate dynamic warehouses [ 3 , 4 , 5 ] must reason rigorously about uncertainty [ 6 , 7 ] . Markov decision processes (MDPs) allow capturing both nondeterminism and stochasticity, making them an expressive and powerful mathematical framework for sequential decision-making under uncertainty [ 8 ] . In software engineering (SE), MDPs support the continuous verification of self-adaptive systems [ 9 ] , dynamic QoS management and optimisation of service-based applications [ 10 ] , and variability-aware model checking of software product lines [ 11 ] , and robotic software stacks for task and motion planning [ 12 ] . However, despite the widespread adoption of MDPs to support decision-making in these complex, software-intensive systems, their practical application is often hindered by the so-called state-space explosion problem [ 13 ] . This is because as the systems modelled grow, the corresponding MDP can expand to an unmanageable size. This explosion in the number of states and transitions renders standard policy synthesis algorithms, which determine optimal actions, computationally prohibitive due to excessive time and memory requirements [ 9 , 14 ] . For engineering teams that rely on MDP-based analysis to ensure safety requirements (e.g., “the robot never becomes stuck”) or the achievement of performance targets (e.g., “the task must be completed time within T time steps”), the state-space explosion problem can significantly undermine the adoption of verification techniques for real-world software systems [ 15 ] . Large models can stall verification pipelines and delay releases. For example, even adjusting a single parameter (such as shelf layout) might force re-verification of the entire MDP, escalating development costs and turnaround time [ 16 ] . Despite significant research, the scalability of MDP solution methods remains a fundamental challenge [ 17 ] . Recent benchmark studies [ 18 ] report that state-of-the-art probabilistic verification tools, such as the widely used probabilistic model checkers PRISM [ 19 ] and Storm [ 20 ] , still timeout on large MDP benchmarks. This holds for various underlying techniques. Symbolic approaches , which excel in non-probabilistic settings, often fail to scale for MDPs [ 21 ] , while explicit state engines that rely on static partitioning and secondary storage can require hours of computation as the state space grows [ 22 ] . Similarly, sampling-based methods may need millions of simulation traces until convergence is achieved [ 23 ] . To address this challenge, we introduce S calable H ierarchical A daptive R efinement for P olicy synthesis ( SHARP ). The core of our approach is based upon a “refine-where-needed” principle, which focuses computational effort only on the most critical regions of the state space. SHARP begins with a coarse abstraction of the MDP and iteratively improves it by subdividing and solving state space partitions, yielding a refined and more detailed analysis. Through this iterative and selective partitioning, SHARP balances solution accuracy with execution efficiency, accelerating verification for large MDPs. The key contributions of our work comprise: (i) the SHARP hierarchical adaptive refinement framework combining hierarchical decomposition with adaptive refinement for efficient large-scale MDP policy synthesis; (ii) algorithms for iterative refinement with region identification criteria, local sub-MDP construction with boundary conditions, and efficient bottom-up value propagation; (iii) an open-source tool, SHARP, supporting reachability probabilities/rewards with configurable refinement strategies; (iv) a comprehensive evaluation on diverse robotic inspection scenarios (up to 1M states) showing up to 2\times speedup over PRISM’s standard policy synthesis solvers. II Preliminaries II-A Probabilistic Modelling Markov decision process (MDP) . An MDP is a tuple \ \mathcal{M}\;=\;(S,\bar{s},A,\delta,r,AP,L), where S is a finite set of states; \bar{s}\in S is an initial state; A is a finite set of actions; \delta:(S\times A)\to\mathit{Dist}(S) is a probabilistic transition function mapping each (s,a) pair to a probability distribution over S ; r:S\to\mathbb{R}_{\geq 0} is a reward structure; AP is a set of atomic propositions; and L:S\to 2^{AP} is a labelling function. MDPs support nondeterministic actions as each state s\in S can have multiple enabled actions for which \mathit{Dist}(s,a) is defined, given by A(s) . An MDP policy is a possible resolution of nondeterminism. Resolving this nondeterminism enables to probabilistically reason about MDPs and synthesise memoryless deterministic policies , i.e., policies where the action chosen in a state depends solely on the current state. Formally, a (deterministic memoryless) policy of an MDP is a function \sigma:S\rightarrow A mapping each state s\in S to an action in A(s) . Probabilistic Computation Tree Logic (PCTL). PCTL [ 24 , 25 ] specifies properties over MDPs. State formulae: \Phi::=\textit{true}\mid a\mid\neg\Phi\mid\Phi_{1}\land\Phi_{2}\mid\mathtt{P}_{\bowtie p}[\varphi]\mid\mathtt{R}^{r}_{\bowtie q}[\rho] , with a\!\in\!AP , \bowtie\!\in\!\{<,\leq,>,\geq\} , p\!\in\![0,1] , q\!\geq\!0 . Path formulae: \varphi::=\mathsf{X}\,\Phi\mid\Phi_{1}\,\mathsf{U}^{\leq k}\Phi_{2}\mid\Phi_{1}\,\mathsf{U}\,\Phi_{2} . Reachability is the shorthand \mathsf{F}\Phi\equiv\textit{true}\,\mathsf{U}\,\Phi . Typical query: \mathtt{P}_{\max}[\mathsf{F}\,\textit{goal}] which asks the maximum probability of eventually reaching a goal state. II-B Probabilistic Model Checking Probabilistic Model Checking (PMC) [ 15 ] is a well-known technique for the verification of stochastic systems Given a probabilistic model, PMC evaluates if the system satisfies a specification expressed in temporal logic (e.g., PCTL). Probabilistic model checkers (e.g., PRISM [ 19 ] , Storm [ 20 ] ) automate the verification process. Quantitative reachability. Let M=(S,\bar{s},A,\delta,r,AP,L) be the MDP defined above and T\subseteq S a set of target states. We denote by \mathsf{F}\ T the event that T is eventually reached. For any state s\in S and policy \sigma , let \Pr^{\sigma}_{s} (and the associated expectation \mathbb{E}^{\sigma}_{s} ) denote the probability measure on infinite state sequences \pi=\pi_{0}\pi_{1}\ldots with \pi_{0}=s such that, at every step i , an action a_{i}=\sigma(\pi_{i}) is taken and \delta(\pi_{i},a_{i})(\pi_{i+1})>0 . The minimum reachability probability is \mathtt{P}_{\min}(s,\mathsf{F}\ T)=\inf_{\sigma}\Pr^{\sigma}_{s}(\mathsf{F}\ T) , and the maximum reachability probability is \mathtt{P}_{\max}(s,\mathsf{F}\ T)=\sup_{\sigma}\Pr^{\sigma}_{s}(\mathsf{F}\ T) . The minimum expected reachability reward is \mathtt{R}_{\min}(s,\mathsf{F}T)=\inf_{\sigma}\mathbb{E}^{\sigma}_{s}\bigl[\sum_{k<k_{T}}r(\pi_{k})\bigr] , and the maximum expected reachability reward is \mathtt{R}_{\max}(s,\mathsf{F}T)=\sup_{\sigma}\mathbb{E}^{\sigma}_{s}\bigl[\sum_{k<k_{T}}r(\pi_{k})\bigr] , where k_{T}=\min\{j\mid\pi_{j}\in T\} is the first step index at which a state in T is reached. Value Iteration (VI). VI [ 8 , 26 ] is a widely used dynamic programming technique [ 27 ] that repeatedly applies the Bellman operator to approximate both optimal reachability probabilities and rewards. Let V^{(k)}(s) (resp. W^{(k)}(s) ) be the probability (resp. expected reward) obtained

Read the complete text