🤖 AI

Accelerating Policy Synthesis in Large-Scale MDPs via Hierarchical Adaptive Refinement

This paper presents a hierarchical adaptive refinement approach that accelerates policy synthesis in large-scale Markov decision processes by dynamically targeting fragile regions, achieving up to a 2x speedup over PRISM while maintaining near-optimal accuracy.

Original authors: Alexandros Evangelidis, Gricel Vázquez, Simos Gerasimou

Published 2026-05-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexandros Evangelidis, Gricel Vázquez, Simos Gerasimou

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 trying to find the absolute best route for a robot to navigate a massive, complex warehouse filled with shelves, moving obstacles, and slippery floors. The robot needs to make decisions at every single step: "Should I go left? Right? Forward?" Because the floor is slippery, there's a chance it might slip, and because the shelves might block paths, the robot has to plan for many different "what-if" scenarios.

In computer science, this problem is modeled as a Markov Decision Process (MDP). Think of the MDP as a giant map where every possible position of the robot is a dot, and every possible move is a line connecting the dots.

The Problem: The "State-Space Explosion"

The problem is that for a real-world warehouse, this map becomes astronomically huge. If the warehouse is just 50 steps by 50 steps, the number of possible situations (states) the robot could be in is in the millions.

Traditional methods for finding the best route (called policy synthesis) try to look at every single dot on the map, calculate the best move for each one, and update the whole map over and over again. It's like trying to solve a jigsaw puzzle by staring at every single piece individually, one by one, even the ones in the middle of a blue sky that are all exactly the same color. This takes forever and requires a massive amount of computer memory. It's like trying to count every grain of sand on a beach to find the best path to the water.

The Solution: SHARP (The Smart Refiner)

The authors of this paper created a new method called SHARP (Scalable Hierarchical Adaptive Refinement). Instead of treating the whole warehouse the same way, SHARP uses a "divide and conquer" strategy with a twist: it only zooms in where it's actually necessary.

Here is how SHARP works, using a simple analogy:

1. The Coarse Map (The Big Picture)

Imagine you have a low-resolution photo of the entire warehouse. You divide it into nine large squares (like a tic-tac-toe board).

The Safe Zones: Some squares are empty, open floors. The robot can move freely there.
The Danger Zones: Other squares are right next to the shelves where the robot might get stuck or slip.

SHARP looks at these nine squares. It realizes, "Hey, the open floor squares are pretty simple. I don't need to look at every single grain of sand there. I can just give them a rough estimate."

2. The Adaptive Refinement (Zooming In)

However, SHARP notices that the square near the shelves (let's call it "Block 9") is messy. The values (how good or bad a spot is) change wildly within that one square. One spot is right next to the goal (very good), and the spot next to it is blocked by a shelf (very bad).

Because the values are so different, SHARP says, "This square is too messy to be a single block. I need to refine it." It cuts that one square into four smaller squares and solves the problem for those smaller pieces. It keeps doing this, cutting the messy areas into smaller and smaller pieces, but leaving the simple, open areas as big, coarse blocks.

3. The "Boundary" Check

When SHARP solves a small block, it needs to know what's happening just outside its borders. It checks the "boundary values" (the estimates from the neighboring blocks).

If the neighbors change their minds significantly, SHARP knows it needs to re-solve the current block to stay accurate.
If the neighbors are stable, SHARP leaves the block alone.

This is like a team of surveyors. Instead of every surveyor measuring every inch of the whole country, they only measure the areas where the terrain is changing rapidly (like a cliff). If the terrain is flat, they just assume it's flat. They only go back and re-measure if the map changes nearby.

The Results: Faster and Smarter

The paper tested SHARP on warehouse models with up to 1 million states (dots on the map).

Speed: SHARP was up to 2 times faster than the standard tools (like PRISM) used by engineers today.
Accuracy: It didn't just guess; it produced a route that was mathematically proven to be almost as good as the perfect route. The error was tiny, bounded by how much the "neighbor" estimates drifted.
Memory: It used more memory than the old tools (because it keeps track of the different-sized blocks), but the authors argue that modern computers have plenty of RAM, so the speed gain is worth the extra memory.

When Does It Work Best?

The paper notes that SHARP is like a specialized tool.

It shines on "spatial" problems (like the warehouse robot) or "staged" problems (where you move from one level to the next), because these have natural areas that are simple and areas that are complex.
It struggles on tightly connected systems (like complex communication protocols) where every part depends heavily on every other part. In those cases, the "divide and conquer" approach adds too much overhead, and the old "look at everything" method is still better.

The Bottom Line

SHARP is a new way to teach robots (or software) how to make decisions in huge, uncertain worlds. Instead of wasting time calculating the obvious, it focuses its brainpower only on the tricky, dangerous, or uncertain parts of the map. This makes it possible to solve problems that were previously too big to handle, getting the robot to its goal faster without losing its way.

1. Problem Statement

Modern software-intensive systems (e.g., autonomous robotics, cloud microservices, software product lines) rely on Markov Decision Processes (MDPs) to model uncertainty and synthesize optimal decision-making policies. However, these systems often suffer from the state-space explosion problem, where the number of states and transitions becomes too large for conventional policy synthesis algorithms (like Value Iteration) to handle within reasonable time and memory limits.

Standard tools like PRISM and Storm often time out on large instances (e.g., models with $>10^6$ states). Existing abstraction-refinement techniques (like CEGAR) are primarily designed for verification (checking bounds) rather than policy synthesis (generating an executable controller). Aggregating states for abstraction can degrade the resulting policy if states requiring different actions are merged. Furthermore, treating all regions of an MDP with the same level of granularity is inefficient, as many regions (e.g., open spaces in a warehouse) may not require fine-grained analysis to determine an optimal strategy.

2. Methodology: SHARP

The authors propose SHARP (Scalable Hierarchical Adaptive Refinement for Policy synthesis), a method that accelerates policy synthesis by dynamically refining the MDP only where necessary.

Core Workflow

SHARP operates on a "refine-where-needed" principle through five iterative stages:

Partitioning (S1): The state space is initially partitioned into coarse blocks (e.g., a grid).
Hierarchy Construction (S2): These blocks form a hierarchy tree where the root is the entire state space, and children represent sub-blocks.
Local Sub-MDP Solving (S3): Each leaf node (block) is treated as a sub-MDP.
- Transitions leaving the block are connected to "boundary states."
- Boundary states are made absorbing with fixed values derived from the global value vector.
- A local solver (Value Iteration) computes optimal values and a partial policy for the block.
Value Propagation (S4): Local solutions are propagated up the tree to update the global value estimates.
Adaptive Refinement (S5): The system checks if refinement is needed.
- Criterion: A block is refined if its value spread (difference between max and min values within the block) exceeds a depth-adapted threshold ( $\theta$ ).
- Trigger: If a block's boundary values change significantly (exceeding $\eta_{thr}$ ) since the last solve, the block is re-solved.
- Action: Selected blocks are subdivided into smaller child blocks, and the process repeats.

Key Technical Mechanisms

Induced Sub-MDPs: To solve a block locally, SHARP constructs an induced sub-MDP including the block's states and one-step successors (boundary states). Boundary values are fixed to the current global estimate, allowing local Bellman updates without merging states.
Asynchronous Fixed-Point: The algorithm uses an asynchronous schedule where blocks are only re-solved when boundary changes are significant, reducing unnecessary computation.
Policy Composition: The final global policy is constructed by composing the local policies of the leaf nodes. Since the partition is disjoint, every state maps to exactly one local policy.

3. Key Contributions

SHARP Algorithm: A novel hierarchical, adaptive refinement framework specifically designed for policy synthesis (not just verification) that avoids state aggregation to preserve policy optimality.
Formal Guarantees: The authors provide theoretical proofs showing that the composed global policy is near-optimal.
- The global Bellman residual is bounded by the local solver tolerance ( $\epsilon$ ) plus the maximum boundary mismatch ( $\eta$ ).
- For Stochastic Shortest Path (SSP) and Maximum Reachability Probability ( $P_{max}$ ) objectives, the error bound is explicitly derived (e.g., $\|V_{fin} - V^*\|_\infty \le (\epsilon + \eta)/\alpha$ ).
Implementation: SHARP is implemented as an open-source extension to the PRISM model checker (Java), integrating with its explicit-state engine.
Extensive Evaluation: Evaluation across diverse benchmarks, including warehouse robotics (up to 1 million states), sequential arenas, and network protocols.

4. Results

The evaluation compares SHARP against PRISM's explicit engines (Value Iteration and Gauss-Seidel).

Performance (Speedup):
- On large warehouse models ( $1024 \times 1024$ grids, $\approx 1$ M states), SHARP achieves a 1.2× to 2× speedup over PRISM.
- For cost minimization ( $R_{min}$ ) on $1024 \times 1024$ models, SHARP reduced time from ~113s (PRISM-GS) to ~65s.
- On random wall configurations, SHARP demonstrated not only faster execution but also higher stability (lower variance in runtime) compared to PRISM.
Scalability: SHARP's runtime scales more favorably with model size than PRISM. While PRISM's time increased by ~8× when moving from $512^2$ to $1024^2$ states, SHARP's time increased by only ~5×.
Generalization:
- Spatial/Staged Models: SHARP excels on models with spatial structure (warehouses) or staged progression (sequential arenas), achieving up to 2× speedup on the $788$k-state arena model.
- Tightly Coupled Models: SHARP performed poorly (slower by 5×–100×) on tightly coupled protocol models (e.g., FireWire, WLAN) where inter-block dependencies are high, confirming that the overhead of hierarchy management outweighs benefits in these cases.
Accuracy: The quality of the synthesized policies is negligible compared to PRISM. The maximum deviation in value was $1.3 \times 10^{-4}$ , confirming that the hierarchical approach does not sacrifice solution quality.
Memory Overhead: SHARP requires more memory (e.g., ~18–20 GB for 1M states vs. ~6 GB for PRISM) due to the storage of the hierarchy tree and per-leaf data, but this remains within modern hardware limits.

5. Significance

Practical Impact: SHARP enables the verification and synthesis of policies for real-world, large-scale systems (like autonomous warehouse robots) that were previously computationally intractable or required excessive time to verify.
Efficiency vs. Accuracy Trade-off: It successfully balances efficiency and accuracy by focusing computational resources only on "fragile" or high-uncertainty regions of the state space, rather than treating the entire model uniformly.
Guidance for Practitioners: The paper provides actionable guidelines, noting that SHARP is most effective for models with limited cross-boundary dependencies (spatial or staged structures). It advises on hyperparameter tuning (e.g., using smaller initial partitions like $8\times8$ and conservative boundary thresholds) to maximize performance.
Theoretical Foundation: By formally bounding the error introduced by boundary mismatches, the work bridges the gap between heuristic hierarchical methods and rigorous probabilistic model checking, ensuring that the "divide and conquer" approach remains mathematically sound.

In conclusion, SHARP represents a significant advancement in scalable probabilistic model checking, offering a robust solution for policy synthesis in large MDPs where traditional flat solvers fail to scale.