Learning Markov Decision Processes for Model Checking

Hua Mao, Yingke Chen, Manfred Jaeger, Thomas D. Nielsen, Kim G. Larsen, Brian Nielsen

TL;DR

This paper introduces IOALERGIA, an algorithm that automatically learns deterministic labeled Markov decision processes (DLMDPs) from observed input-output sequences of reactive systems. This is crucial for model checking complex systems where manual model construction is time-consuming and error-prone, enabling more efficient verification and analysis.

What Problem Does This Paper Address?

Constructing accurate formal models of complex systems for verification is a significant bottleneck in software engineering. Traditional model checking relies on manually created models, which are often difficult, time-consuming, and prone to errors, especially for legacy systems or third-party components. While learning techniques exist for simpler models like Markov chains, many real-world systems exhibit both probabilistic and nondeterministic behavior, making them better represented by Markov Decision Processes (MDPs). The challenge is to automatically learn these more expressive MDP models from observed system behavior, which is typically a sequence of inputs and outputs.

Methods

The paper proposes the IOALERGIA algorithm, an extension of the ALERGIA algorithm, designed to learn deterministic labeled Markov decision processes (DLMDPs). The learning process involves two main phases:

  1. IOFPTA Construction: The observed input-output sequences are first represented as an Input/Output Frequency Prefix Tree Automaton (IOFPTA). This tree structure captures the frequency of transitions and outputs for different input sequences. The "err" symbol is handled to distinguish between enabled and disabled actions.
  2. IOALERGIA Learning: This phase iteratively merges nodes in the IOFPTA that are deemed "compatible." Compatibility is determined by comparing:
  3. The output labels of the nodes.
  4. The probabilistic distributions of transitions for each input action using the Hoeffding bound (Algorithm 3), which quantifies the statistical evidence for differences.
  5. Recursively, the compatibility of their successor nodes. The algorithm maintains two sets of states: RED (representative states for the final model) and BLUE (states to be tested for merging). Merging occurs when a BLUE state is compatible with a RED state, consolidating them into a single state in the learned DLMDP.

Datasets

The paper uses data generated from two slot machine models:

  • Deterministic Slot Machine: A baseline model with 3 reels, each having 5 symbols, and defined prize configurations.
  • Nondeterministic Slot Machine: An extension of the deterministic model, introducing indistinguishable symbols (b1, b2) on one reel, making the transitions probabilistic and the choice of which reel to spin nondeterministic.

The experiments involve generating datasets of varying sizes (number of symbols and sequences) from these models to evaluate the learning algorithm.

Key Insights and Ideas

  • Bridging the Gap: IOALERGIA effectively extends learning from simpler probabilistic models to more expressive DLMDPs, which are better suited for modeling complex reactive systems with both probabilistic and nondeterministic choices.
  • Statistical Compatibility: The use of the Hoeffding bound for comparing transition probabilities is a key mechanism for determining state compatibility, allowing the algorithm to handle noisy or limited observational data.
  • Handling Nondeterminism: The algorithm's ability to learn models from nondeterministic systems (like the modified slot machine) is a significant step towards modeling real-world systems.
  • Model Complexity vs. Accuracy: The paper explores the trade-off between model complexity (number of states) and accuracy, using the BIC score to find an optimal balance.
  • Practical Applicability: The case study with slot machines demonstrates the algorithm's ability to learn models that approximate the behavior of both deterministic and nondeterministic generating models, including capturing optimal actions.

Key Results

  • Convergence: The paper shows theoretical convergence results, indicating that with sufficient data, IOALERGIA can identify the true model's structure (up to bisimulation equivalence) and converge to the correct parameter values.
  • Slot Machine Experiments:
    • For deterministic slot machines, learned models closely approximated the maximal/minimal probabilities of winning and the maximal expected reward, with high accuracy for optimal actions.
  • For nondeterministic slot machines, learned models also provided good approximations of probabilities and rewards. While the accuracy of optimal actions was slightly lower than in the deterministic case, it still significantly outperformed random choices.
  • Model Size: The learned models generally had a comparable or smaller number of states than the original generating models, indicating efficient learning.

Limitations and Future Work

  • Routine Use: The authors acknowledge that further research is needed to make the learning algorithm suitable for routine use, similar to learning algorithms for deterministic automata.
  • Distance Measurement: Measuring the distance between the learned model and the generating model is suggested as a future work direction.
  • Active Learning: The paper suggests refining the approach with active learning techniques to improve data acquisition efficiency.
  • Compositional Systems: Extending the learning approach to learn models for individual components in compositional systems is another promising avenue.
  • PCTL Formulas: While LTL properties are well-approximated, similar results do not carry over to PCTL formulas, suggesting a limitation in learning probabilistic quantitative properties directly.

Summary updated

Abstract

Constructing an accurate system model for formal model verification can be both resource demanding and time-consuming. To alleviate this shortcoming, algorithms have been proposed for automatically learning system models based on observed system behaviors. In this paper we extend the algorithm on learning probabilistic automata to reactive systems, where the observed system behavior is in the form of alternating sequences of inputs and outputs. We propose an algorithm for automatically learning a deterministic labeled Markov decision process model from the observed behavior of a reactive system. The proposed learning algorithm is adapted from algorithms for learning deterministic probabilistic finite automata, and extended to include both probabilistic and nondeterministic transitions. The algorithm is empirically analyzed and evaluated by learning system models of slot machines. The evaluation is performed by analyzing the probabilistic linear temporal logic properties of the system as well as by analyzing the schedulers, in particular the optimal schedulers, induced by the learned models.
BibTeX
@misc{mao2012learning,
  author = {Hua Mao and Yingke Chen and Manfred Jaeger and Thomas D. Nielsen and Kim G. Larsen and Brian Nielsen},
  title = {{Learning Markov Decision Processes for Model Checking}},
  year = {2012},
  eprint = {1212.3873},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1212.3873},
}
Figure