💻 computer science

Multi-Objective Statistical Model Checking using Lightweight Strategy Sampling (extended version)

This paper presents the first statistical model checking approach for multi-objective Pareto queries using lightweight strategy sampling, featuring an incremental scheme for asymptotic convergence and heuristic methods for finite-time approximations, which are implemented and validated within the Modest Toolset.

Original authors: Pedro R. D'Argenio, Arnd Hartmanns, Patrick Wienhöft, Mark van Wijk

Published 2026-07-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pedro R. D'Argenio, Arnd Hartmanns, Patrick Wienhöft, Mark van Wijk

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 the captain of a spaceship. You have two main goals: you want to collect as much treasure as possible (maximize reward), but you also want to use as little fuel as possible (minimize cost).

The problem is, these two goals fight each other. If you go fast to get more treasure, you burn more fuel. If you go slow to save fuel, you get less treasure. There isn't one single "best" path; instead, there is a whole curve of "best possible trade-offs." In math, this curve is called the Pareto Front.

For a long time, computer scientists had a way to find this curve perfectly, but it was like trying to count every single grain of sand on a beach to find the perfect spot to build a castle. If the beach (the computer model) was too big, the method would crash or take forever. This is called the "state space explosion."

Then, they invented a faster way called Statistical Model Checking (SMC). Instead of counting every grain of sand, you just pick a few handfuls at random, measure them, and use statistics to guess what the whole beach looks like. It's fast and works for huge beaches, but until now, it could only check one goal at a time (e.g., "How much treasure can I get?"). It couldn't handle the tricky trade-off between treasure and fuel.

This paper introduces a new method to find that "treasure vs. fuel" curve using the fast, random-sampling approach. Here is how they did it, using some everyday analogies:

1. The "Magic Dice" Strategy (Lightweight Strategy Sampling)

Imagine you have a giant library of every possible way your spaceship could fly. You can't read every book in the library. Instead, you have a "Magic Dice" (called a hash function).

You roll the dice to pick a random flight plan (a "strategy").
You simulate that flight plan on your computer to see how much treasure and fuel it used.
Because the dice is "lightweight," you can pick millions of different flight plans without needing a super-computer to remember them all. You just need a tiny note (a 32-bit number) to remember which plan you picked.

2. The "Confidence Box"

When you simulate a flight plan, you don't get a perfect number; you get an estimate with a little bit of uncertainty.

Think of this as a box drawn around your result.
The center of the box is your best guess.
The size of the box represents how sure you are. If you run the simulation 10 times, the box is small. If you run it once, the box is huge.
The paper's math guarantees that if you draw enough boxes, the true best results are almost certainly hiding inside them.

3. Finding the Curve (The Pareto Front)

The researchers tried two main ways to find the best trade-off curve using these boxes:

Method A: The "Endless Explorer" (Incremental Sampling)
Imagine you are a hiker trying to map a mountain range. You don't stop; you just keep walking and drawing the map as you go.

You keep picking random flight plans and drawing their boxes.
Over time, you draw a "floor" (under-approximation) and a "ceiling" (over-approximation) around the true mountain range.
As you keep walking, the floor and ceiling get closer and closer together until they perfectly outline the mountain.
The Catch: You have to keep walking forever to get the perfect outline.

Method B: The "Smart Hunter" (Fixed-Budget Algorithms)
Imagine you have a limited amount of time (say, 1 hour) to find the best spots. You can't walk forever, so you need to be smart about where you look. The paper proposes three "hunting strategies":

Weight Vector Refinement: You pick a direction (e.g., "I care more about treasure than fuel"), find the best spot for that, then change the direction slightly and look again. You keep refining your search.
Fixed Iteration Budget: You pick a group of flight plans, test them, throw away the ones that look terrible, and give your remaining time to the "winners" to test them more carefully.
Fixed Strategy Budget: Similar to the above, but instead of just testing the winners more, you keep adding new random flight plans to the mix while testing the winners, ensuring you don't miss a hidden gem.

What Did They Find?

The authors built a tool (called modes) and tested it on many different problems, from scheduling energy in a smart home to navigating a submarine in the deep sea.

The Good News: Their method worked on problems that were too huge for the old, perfect methods. They found good trade-off curves in seconds or minutes, where the old methods would have taken hours or crashed.
The "Simple" Winner: Surprisingly, the most effective strategy was often the simplest one: just pick a lot of random flight plans, throw away the ones that are clearly bad immediately, and use your remaining time to test the rest. You don't need complex math to discard the bad ones; just looking at the raw numbers was enough.
The Limitation: Because they are using random sampling, they can never be 100% certain they found the absolute perfect curve in a fixed amount of time. They can only say, "We are 95% sure the true answer is inside this area." However, for massive, complex problems, being 95% sure is much better than not being able to solve the problem at all.

In Summary

This paper gives us a new way to solve "pick your poison" problems (like speed vs. safety, or cost vs. quality) for giant computer models. Instead of trying to calculate every single possibility (which is impossible for big systems), they use a smart, random sampling technique to draw a very accurate map of the best possible trade-offs, all while using very little computer memory.

Technical Summary: Multi-Objective Statistical Model Checking using Lightweight Strategy Sampling

Problem Statement

Statistical Model Checking (SMC) is a well-established technique for verifying probabilistic systems with large state spaces where exhaustive Probabilistic Model Checking (PMC) fails due to state space explosion. However, existing SMC approaches are limited to evaluating single properties at a time. In many practical scenarios, such as balancing satellite battery usage against utility or optimizing heat-pump cost versus comfort, decision-makers require the Pareto front: the set of optimal trade-offs between multiple, often conflicting, objectives.

While multi-objective PMC algorithms exist (e.g., using linear programming or value iteration), they require full state space exploration, making them inapplicable to models with billions of states or high-dimensional objective spaces. Furthermore, existing tools like Uppaal Stratego handle multi-objective problems only via lexicographic ordering or single-dimensional optimization, failing to capture trade-offs between equal-priority objectives. There is currently no SMC approach capable of computing Pareto fronts for multi-objective queries while maintaining the constant memory footprint characteristic of SMC.

Methodology

The paper proposes the first SMC approach for multi-objective Pareto queries, built upon Lightweight Strategy Sampling (LSS). The core methodology involves the following components:

1. Lightweight Strategy Sampling (LSS)

To handle the nondeterminism in Markov Decision Processes (MDPs) without storing per-state strategy information, the authors utilize LSS. Instead of explicitly storing a strategy, LSS uses a compact identifier (e.g., a 32-bit integer) and a hash function to deterministically resolve nondeterministic choices during simulation. This allows the simulation of a vast number of distinct strategies using constant memory, independent of the model's state space size.

2. Statistical Approximation of the Pareto Front

The approach samples deterministic strategies and evaluates them via SMC to obtain confidence intervals (CIs) for each objective.

Confidence Boxes: For a sampled strategy $\sigma$ , SMC produces a $d$ -dimensional confidence box $B_\sigma$ around the estimated mean vector $\hat{x}_\sigma$ .
Under- and Overapproximation: The convex hull of the "most pessimistic" corners of these boxes forms a candidate underapproximation ( $\underline{C}$ ) of the achievable set. Conversely, the "most optimistic" corners form a candidate overapproximation ( $\overline{C}$ ).
Multiple Comparisons: To ensure the simultaneous correctness of all confidence boxes with probability $\gamma$ , the authors apply the Bonferroni correction (union bound) to distribute the error budget across strategies and dimensions.

3. Algorithms

The paper introduces two categories of algorithms:

A. Incremental Sampling with Convergence
This scheme indefinitely samples batches of strategies. It dynamically adjusts the error budget per batch (using a factor $f$ ) to ensure that, in the limit, the under- and overapproximations converge to a simultaneous confidence band around the true Pareto front. This provides a theoretical guarantee of almost sure convergence given ideal LSS.

B. Fixed-Budget Sampling
Recognizing that practical applications have finite time, three heuristic algorithms are proposed to find the best approximation within a fixed simulation budget:

Weight Vector Refinement (WVR): Adapts multi-objective PMC techniques by linearly scalarizing objectives. It iteratively refines weight vectors based on the distance between current approximations and discards suboptimal strategies.
Fixed Iteration Budget (FIB): Samples an initial set of strategies and iteratively performs simulation runs, discarding the worst-performing strategies in each iteration to concentrate the budget on promising candidates.
Fixed Strategy Budget (FSB): Similar to FIB but ensures that the final set of surviving strategies receives a uniform number of simulation runs, sampling new strategies to replace discarded ones.

Strategy Selection Heuristics:
To filter strategies, the authors define several rules based on sample means and confidence intervals (e.g., "Simple," "Far Enough," "Conservatively Far"). These rules determine if a strategy is dominated by another with sufficient statistical confidence to be discarded.

Key Contributions

First Multi-Objective SMC: The paper presents the first SMC framework capable of approximating Pareto fronts for $d$ equal-priority objectives.
Constant Memory: The approach maintains the primary advantage of SMC: memory usage is constant relative to the model's state space size, enabling the analysis of models with billions of states.
Statistical Guarantees: The incremental scheme provides a theoretical guarantee of convergence to a confidence band around the true Pareto front. The fixed-budget algorithms provide statistically sound lower bounds (underapproximations) with a specified confidence level.
Implementation and Evaluation: The techniques are implemented in the modes simulator within the Modest Toolset. The authors evaluate the approach on 40 benchmark instances from quantitative verification and reinforcement learning literature, comparing results against the PMC tool Storm.

Experimental Results

The experiments demonstrate that the proposed SMC approach can handle instances where PMC tools (Storm) fail due to state space explosion or timeout.

Scalability: For large models (e.g., fruit_tree with $2.7 \times 10^9$ states, puddle_world variants with hundreds of millions of states), the SMC approach successfully computes Pareto front approximations in seconds to minutes, whereas PMC tools timed out or could not complete.
Accuracy: For smaller models where PMC results are available, the SMC approximations often closely match the true Pareto front (e.g., deep_sea and fruit_tree models with multiplicative $\epsilon$ close to 1). However, accuracy varies; for some models like breakable_bottles, the approximation can be further from the true front, highlighting the stochastic nature of the sampling.
Algorithm Performance: Among the fixed-budget algorithms, FSB (Fixed Strategy Budget) combined with the Simple heuristic and a configuration favoring a high number of initial strategies with fewer runs per strategy generally yielded the best hypervolume results.
Heuristic Impact: The "Simple" rule (discarding strategies based purely on sample means) often performed best, suggesting that early discarding of non-promising strategies is beneficial in the tested benchmark set.

Significance and Claims

The authors claim that this work bridges a critical gap between the scalability of SMC and the complexity of multi-objective optimization. By leveraging lightweight strategy sampling, the approach enables the verification of trade-offs in systems that are otherwise intractable for exhaustive methods.

The paper modestly acknowledges limitations:

Overapproximation: While the incremental scheme converges to a confidence band, fixed-budget algorithms cannot guarantee a valid overapproximation in finite time because they may miss the optimal strategy entirely.
Strategy Space: The method assumes a finite strategy space (via fixed-size identifiers). While practical, this is a limitation compared to the theoretical infinite space of strategies in general MDPs.
Model Class: While demonstrated on MDPs, the approach is directly applicable to any model class supported by LSS, such as Markov automata and probabilistic timed automata, provided runs almost surely terminate.

The work is presented as a foundational step, offering a practical tool for multi-objective verification in large-scale systems where traditional exhaustive methods are unavailable.