Solving MDPs with LTLf+ and PPLTL+ Temporal Objectives

Giuseppe De Giacomo, Yong Li, Sven Schewe, Christoph Weinhuber, Pian YuIJCAI 2025 · DOI

TL;DR

This paper introduces a novel approach to solving Markov Decision Processes (MDPs) with complex temporal objectives expressed in the LTLf+ and PPLTL+ logics. By leveraging efficient, compositionally built automata and a controlled form of nondeterminism, the authors provide a scalable and implementation-friendly method for synthesizing optimal strategies in probabilistic systems.

What Problem Does This Paper Address?

Reasoning about and synthesizing strategies for probabilistic systems, specifically Markov Decision Processes (MDPs), often involves specifying desired temporal behaviors. Traditional methods for temporal logic specifications in MDPs, like those using Rabin automata for LTL, can be computationally expensive. While recent advancements have introduced logics like LTLf+ and PPLTL+ that allow for more efficient synthesis by enabling the use of deterministic finite automata (DFAs) for finite trace properties, their application to probabilistic, infinite-trace objectives in MDPs still presented challenges. Specifically, adapting these DFA-based techniques to the probabilistic nature of MDPs while maintaining efficiency and scalability was an open problem. The authors aim to bridge this gap by developing a method that effectively combines the expressive power of LTLf+/PPLTL+ with the efficiency of DFA-based techniques for MDPs.

Methods

The core of this paper lies in constructing "Good-for-MDPs" (GFM) automata for LTLf+ and PPLTL+ formulas, which are then used to solve MDPs. The approach is compositional:

  • Automata Construction: They first construct DFAs for the finite-trace LTLf/PPLTL subformulas of the given LTLf+/PPLTL+ specification. These DFAs are then transformed into Büchi automata (specifically, Limit-Deterministic Büchi Automata or LDBAs) corresponding to the four temporal property classes (guarantee, safety, recurrence, persistence) defined by Manna and Pnueli.
  • Boolean Combinations: The automata for these basic temporal properties are then combined using Cartesian products for union and a specialized intersection construction to handle Boolean combinations (AND, OR, NOT) of formulas. This compositional approach allows for intermediate optimization of automata.
  • GFM Property: The key insight is that these constructed automata are "Good-for-MDPs" (GFM). This property means that their nondeterminism can be resolved by a strategy in an MDP to achieve the maximal satisfaction probability of the specification. They prove this GFM property using an "AEC-simulation game" between a "Spoiler" and a "Duplicator," demonstrating that their constructed automata can AEC-simulate existing GFM automata.
  • MDP Synthesis: Once a GFM Büchi automaton for the temporal objective is constructed, it's used to build a product MDP. Strategies are then synthesized on this product MDP by identifying accepting maximal end-components (AMECs) and computing optimal paths to them.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • LTLf+/PPLTL+ for MDPs: The paper demonstrates that LTLf+ and PPLTL+ are not only expressive for temporal objectives but also highly effective when adapted to the probabilistic setting of MDPs.
  • Controlled Nondeterminism (GFM): The core innovation is the use of GFM automata. This "controlled nondeterminism" is crucial for bridging the gap between deterministic automata used for finite traces and the probabilistic nature of infinite traces in MDPs, allowing for efficient synthesis.
  • Compositionality and DFA Efficiency: By breaking down complex temporal formulas into simpler DFA-based components and composing them, the method leverages the efficiency of DFA operations (like minimization) at intermediate steps, leading to more scalable solutions than approaches that determinize complex automata directly.
  • Implementation-Friendly Approach: The compositional and DFA-centric nature of the construction makes it well-suited for symbolic implementation, which is a significant practical advantage.

Key Results

  • The paper provides a provably correct technique to construct GFM Büchi automata for LTLf+ and PPLTL+ formulas.
  • The constructed automata are shown to be GFM, enabling optimal strategy synthesis for MDPs.
  • The number of states in the constructed automata is shown to be doubly exponential in the formula length for LTLf+ and single exponential for PPLTL+, which is noted as optimal in the worst case.
  • The method is presented as being implementation-friendly and well-suited for symbolic implementation.

Limitations and Future Work

  • Complexity: While the approach leverages DFA efficiency, the worst-case state space complexity for the automata can still be exponential, which is inherent to temporal logic synthesis.
  • Future Work: The authors explicitly mention their aim to implement this approach using symbolic techniques within state-of-the-art tools like PRISM. This would facilitate practical application in domains such as AI, robotics, and probabilistic verification. They also suggest that the GFM automata are more succinct than deterministic automata, which can lead to smaller product MDPs and thus smaller strategies.

Summary updated

BibTeX
@inproceedings{giacomo2025solving,
  author = {Giuseppe De Giacomo and Yong Li and Sven Schewe and Christoph Weinhuber and Pian Yu},
  title = {{Solving MDPs with LTLf+ and PPLTL+ Temporal Objectives}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/944},
}
Figure