SEA-PARAM: Exploring Schedulers in Parametric MDPs

Sebastian Arming, Ezio Bartocci, Ana Sokolova

Introduction

Parametric Markov Decision Processes (PMDPs) provide a powerful framework for modeling systems that exhibit both probabilistic behavior and nondeterministic choices under uncertainty. In real-world applications such as robotics or power grid management, transition probabilities are rarely known with absolute precision. Instead, they are often functions of parameters representing noise, failure rates, or environmental conditions. This paper introduces SEA-PARAM, a tool designed to explore the "sea of waves"—the vast collection of performance functions generated by different schedulers across a parameter space—to identify optimal strategies under various criteria.

The Challenge of Parameter Uncertainty

Traditional approaches to PMDPs often focus on parameter synthesis, which seeks specific parameter values that satisfy a given property (e.g., "Is there a value of $p$ such that the failure rate is below 1%?"). However, in many scenarios, parameters are beyond the controller's influence. An autonomous robot must operate effectively whether a surface is slightly or significantly slippery. The goal shifts from finding parameters to finding a scheduler (a policy) that is robust across the entire parameter range.

Methodology: The SEA-PARAM Pipeline

The SEA-PARAM tool implements a two-stage pipeline to analyze PMDPs:

  1. Function Generation: Utilizing the PRISM model checker and Java Algebra Systems (JAS), the tool enumerates all simple (deterministic, memoryless) schedulers. For each scheduler, it computes a multivariate rational function that represents the reachability probability of a target state as a function of the parameters.
  2. Optimality Analysis: These functions are processed in Wolfram Mathematica to categorize schedulers based on ten distinct optimality classes. These include Dominant schedulers (best everywhere), Expectation schedulers (highest average performance given a distribution), and Stable schedulers (lowest variance/highest predictability).

Benchmark: Parametric Labyrinths

To evaluate the tool, the authors introduced "Parametric Labyrinths," where a robot navigates an $n \times n$ grid toward a target while avoiding "sinks." The transitions are governed by parameters representing the probability of veering off-course.

Figure 2: The behavior of state (1,1) under (a) Fixed failure and (b) Fixed success models, illustrating how parameters $l$ and $r$ define transition probabilities.

Visualizing the "Sea of Waves"

A central concept of the paper is the visualization of scheduler performance as overlapping surfaces, or "waves," in the parameter space. This visualization clarifies why a single "best" scheduler often does not exist; a strategy that is optimal in one region of the parameter space may perform poorly in another.

Figure 3: Reachability probability surfaces for various schedulers. The overlapping 'waves' demonstrate the complexity of selecting an optimal scheduler across the entire parameter range.

Key Insights and Results

The authors' evaluation revealed several critical insights:

  • Dominance is Rare: In complex models, it is uncommon for a single scheduler to outperform all others across the entire parameter range, necessitating the multi-faceted optimality definitions provided by SEA-PARAM.
  • Scalability: The tool successfully processed a $4 \times 4$ labyrinth involving over 4.4 million schedulers. While function generation is highly parallelizable, the symbolic integration and optimization required for certain optimality classes (like Expectation) remain computationally demanding.
  • History Dependency: While the tool focuses on simple schedulers, the authors note that history-dependent schedulers can achieve superior results by effectively "learning" parameter values through observed transitions.

Conclusion

SEA-PARAM offers a comprehensive framework for navigating the complexities of PMDPs. By moving beyond simple parameter synthesis and providing a structured way to evaluate scheduler performance under uncertainty, it enables engineers to select strategies that align with specific operational goals, whether they prioritize safety, efficiency, or predictability. Future work aims to address the computational complexity of high-order rational functions and the integration of history-dependent policies.

Summary updated

Abstract

:We study parametric Markov decision processes (PMDPs) and their reachability probabilities "independent" of the parameters. Different to existing work on parameter synthesis (implemented in the tools PARAM and PRISM), our main focus is on describing different types of optimal deterministic memoryless schedulers for the whole parameter range. We implement a simple prototype tool SEA-PARAM that computes these optimal schedulers and show experimental results.
BibTeX
@inproceedings{arming2017sea,
  author = {Sebastian Arming and Ezio Bartocci and Ana Sokolova},
  title = {{SEA-PARAM: Exploring Schedulers in Parametric MDPs}},
  booktitle = {QAPL@ETAPS},
  year = {2017},
  url = {https://openreview.net/forum?id=POGKiJCJct},
}
Figure