Learning Probabilistic Temporal Logic Specifications for Stochastic Systems
This addresses a bottleneck in formal verification and reinforcement learning by enabling specification learning for stochastic systems, though it is incremental as it extends existing logic-based methods to probabilistic settings.
The paper tackles the problem of inferring formal behavioral specifications for stochastic systems, which existing techniques cannot handle, by proposing a novel algorithm that learns concise probabilistic Linear Temporal Logic (PLTL) formulas from classified Markov chains, demonstrating effectiveness in automatically extracting specifications for reinforcement learning policies and probabilistic model variants.
There has been substantial progress in the inference of formal behavioural specifications from sample trajectories, for example, using Linear Temporal Logic (LTL). However, these techniques cannot handle specifications that correctly characterise systems with stochastic behaviour, which occur commonly in reinforcement learning and formal verification. We consider the passive learning problem of inferring a Boolean combination of probabilistic LTL (PLTL) formulas from a set of Markov chains, classified as either positive or negative. We propose a novel learning algorithm that infers concise PLTL specifications, leveraging grammar-based enumeration, search heuristics, probabilistic model checking and Boolean set-cover procedures. We demonstrate the effectiveness of our algorithm in two use cases: learning from policies induced by RL algorithms and learning from variants of a probabilistic model. In both cases, our method automatically and efficiently extracts PLTL specifications that succinctly characterise the temporal differences between the policies or model variants.