Solving MDPs with LTLf+ and PPLTL+ Temporal Objectives
Giuseppe De Giacomo, Yong Li, Sven Schewe, Christoph Weinhuber, Pian Yu · 2025
Read Solving MDPs with LTLf+ and PPLTL+ Temporal Objectives by Giuseppe De Giacomo, Yong Li, Sven Schewe, Christoph Weinhuber, Pian Yu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-17264.txt.
Introduction
Giuseppe De Giacomo and co-authors show, in twenty twenty-five, how to solve Markov decision processes whose goals are stated in two new temporal logics. Temporal logics specify what should happen over time. The logics, LTLf+ and PPLTL+, match the expressive power of classic LTL on infinite traces. Yet they allow efficient automata-based methods, the trick that made finite-trace versions scale. Markov decision processes add probabilities: actions have uncertain outcomes. Their tailored technique exploits that structure.
The approach is simpler than its counterparts in reactive synthesis and planning, they argue. It tolerates a controlled form of nondeterminism in the automata, one that is good for probabilistic systems. Compositionality, solving pieces and combining them, makes the method implementation-friendly and suited to symbolic code.
Catalog record
| CREATOR | Giuseppe De Giacomo, Yong Li, Sven Schewe, Christoph Weinhuber, Pian Yu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 82 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-17264
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Solving MDPs with LTLf+ and PPLTL+ Temporal Objectives Giuseppe De Giacomo, Yong Li, Sven Schewe, Christoph Weinhuber, Pian Yu Abstract The temporal logics LTLf+ and PPLTL+ have recently been proposed to express objectives over infinite traces. These logics are appealing because they match the expressive power of LTL on infinite traces while enabling efficient DFA-based techniques, which have been crucial to the scalability of reactive synthesis and adversarial planning in LTLf and PPLTL over finite traces. In this paper, we demonstrate that these logics are also highly effective in the context of MDPs. Introducing a technique tailored for probabilistic systems, we leverage the benefits of efficient DFA-based methods and compositionality. This approach is simpler than its non-probabilistic counterparts in reactive synthesis and adversarial planning, as it accommodates a controlled form of nondeterminism (“good for MDPs”) in the automata when transitioning from finite to infinite traces. Notably, by exploiting compositionality, our solution is both implementation-friendly and well-suited for straightforward symbolic implementations. 1 Introduction Temporal logics are widely used as specification languages in reactive synthesis and adversarial planning Baier and Katoen (2008) ; Camacho et al. (2019) . Among these, linear temporal logic ( LTL ) Pnueli (1977) is perhaps the most commonly used. LTL is a formalism used to specify and reason about the temporal behaviour of systems over infinite traces. It has been extensively employed as a specification mechanism for temporally extended goals, as well as for expressing preferences and soft constraints in various fields, including business processes, robotics, and AI Bienvenu et al. (2011) ; Maggi et al. (2011) ; Fainekos et al. (2009) . Linear temporal logic over finite traces ( LTLf ) Baier and McIlraith (2006) ; De Giacomo and Vardi (2013) ; De Giacomo and Vardi (2015) is a variant of LTL with the same syntax but it is interpreted over finite instead of infinite traces. PPLTL is the pure-past version of LTLf and scans the trace backwards from the end towards the beginning De Giacomo et al. (2020) . It is well-established that strategy synthesis for LTLf and PPLTL can be derived from deterministic finite automata (DFA), thereby avoiding the challenges associated with determinising automata for infinite traces, typical of LTL reactive synthesis. The temporal logics LTLf+ and PPLTL+ have recently been proposed to express objectives over infinite traces Aminof et al. (2024) . These logics are directly based on Manna and Pnueli’s hierarchy of temporal properties Manna and Pnueli (1990) . This hierarchy categorizes temporal properties on infinite traces in four classes , which are obtained by requiring that a finite trace property holds for some prefixes of infinite traces (“guarantee”), all prefixes (“safety”), infinitely many prefixes (“recurrence”) and for all but finitely many prefixes (“persistence”). Notably every LTL property can be expressed as a Boolean combination of these four kinds of properties Manna and Pnueli (1990) . LTLf+ and PPLTL+ use respectively LTLf and PPLTL to express properties over finite traces and obtain the four basic kinds of infinite trace properties of the Manna and Pnueli’s hierarchy. This makes them particularly interesting from the computational point of view. While they retain the expressive power of LTL on infinite traces, they enable the lifting of DFA-based techniques developed for LTLf and PPLTL to obtain deterministic automata on infinite traces corresponding to formulas, thus avoiding determinisation of Büchi automata, which is known to be a notorious computational bottleneck. As a result, LTLf+ and PPLTL+ are particularly promising for a number of tasks, such as reactive synthesis Pnueli and Rosner (1989) ; Finkbeiner (2016) , supervisory control for temporal properties Ehlers et al. (2017) , and planning for temporally extended goals in nondeterministic domains Bacchus and Kabanza (1998) ; De Giacomo and Rubin (2018) . All these tasks require to obtain from the temporal formula a deterministic automaton on infinite traces , to be used as a game arena over which a strategy can be computed to achieve the required property. LTLf+ and PPLTL+ excel at these tasks by enabling simple arena construction through the Cartesian product of DFAs, corresponding to the finite trace ( LTLf / PPLTL ) components in the LTLf+ / PPLTL+ formula. On the other hand, the game to be solved over this arena is an Emerson-Lei game Emerson and Lei (1987) , which requires quite sophisticated techniques Hausmann et al. (2024) . In this paper, we demonstrate that these logics are even more effective in the context of MDPs. Traditionally, deterministic Rabin automata have been the standard choice for representing LTL specifications in MDPs Baier and Katoen (2008) . Due to the probabilistic nature of MDPs, the automaton for temporal specifications does not need to be entirely deterministic. State-of-the-art MDP synthesis methods use a restricted form of Büchi automata called Limit-Deterministic Büchi Automata (LDBAs) for LTL Hahn et al. (2015) ; Sickert et al. (2016) ; Shao and Kwiatkowska (2023) . Recent work has shown that an even more relaxed form of nondeterminism, termed “ good for MDPs ” (GFM), can be effectively used for MDP synthesis Hahn et al. (2020) ; Schewe et al. (2023) . Since this relaxed nondeterminism enables more succinct representations of temporal specifications, we adopt GFM automata in this work. By leveraging GFM’s controlled nondeterminism, we present techniques for solving MDPs with LTLf+ / PPLTL+ objectives that maintain the compositional DFA-based approach of Aminof et al. (2024) . Instead of using Emerson-Lei automata, our construction obtains simple LDBAs from the DFAs of LTLf / PPLTL components corresponding to Manna and Pnueli’s four classes, then composes them while preserving the “good for MDPs” property. The result is a GFM Büchi automaton that can be used to solve MDPs in a standard way Baier and Katoen (2008) . This gives us a simple technique that not only is sound, complete, and computationally optimal, but is both implementation-friendly and well-suited for straightforward symbolic implementation. 2 Preliminaries In the whole paper, we will fix a set of atomic propositions AP . We denote by \Sigma=2^{\textsf{AP}} the set of interpretations over AP ; \Sigma is also called the alphabet set. Let \Sigma^{*} and \Sigma^{\omega} denote the set of all finite and infinite sequences, respectively. The empty sequence is denoted as \epsilon and we index a sequence u=a_{0}a_{1}\cdots a_{n}\cdots from 0 . Moreover, we let \Sigma^{+}=\Sigma^{*}\setminus\{\epsilon\} . We denote by w{[i\cdots j]} the fragment that starts at position i and ends (inclusively) at position j . Particularly, \epsilon=w{[i\cdots j]} for all w if j<i . We denote by |w| the number of letters in w if w is a finite sequence and \infty otherwise. For a finite or infinite sequence w , w{[0\cdots i]} is said to be a prefix of w if 0\leq i<|w| . A trace is a non-empty finite or infinite sequence of letters in \Sigma ; Specially, \epsilon is not a trace. 2.1 LTLf+ and PPLTL+ over Infinite Traces LTLf+ and PPLTL+ have been derived from LTLf and PPLTL , respectively Aminof et al. (2024) . The syntax of an LTLf formula Baier and McIlraith (2006) ; De Giacomo and Vardi (2013) over a finite set of propositions AP is defined as \phi::=a\in\textsf{AP}\mid\neg\phi\mid\phi\land\phi\mid\phi\lor\phi\mid\textsf{X}\phi\mid\phi\textsf{U}\phi\mid\textsf{F}\phi\mid\textsf{G}\phi . Here X (strong Next), U (Until), F (or \diamond ) (Finally/Eventually), and G (or