LTLf/LDLf Non-Markovian Rewards

Ronen I. Brafman, Giuseppe De Giacomo, Fabio PatriziAAAI 2018 · DOI

Abstract

In standard Markov Decision Processes (MDPs), rewards are restricted to the current state and action, a limitation known as the Markov assumption. This paper introduces a robust framework for handling non-Markovian rewards—those dependent on the history of an agent's actions—by utilizing Linear Dynamic Logic over finite traces ($LDL_f$). By compiling these complex reward specifications into minimal Deterministic Finite Automata (DFAs), the authors provide a method to transform non-Markovian problems into standard Markovian MDPs. This approach ensures state-space minimality, supports modular reward design, and offers a unifying logic for complex behavior specification.

Introduction

In the study of autonomous agents, the Markov Decision Process (MDP) serves as the foundational mathematical framework. Central to the MDP is the Markov assumption: the probability of moving to a new state and the reward received depend solely on the current state and the immediate action. While this assumption simplifies the underlying mathematics, it poses significant challenges for designing agents that must adhere to complex, history-dependent rules.

Consider a service robot tasked with delivering coffee. In a standard MDP, the robot might be rewarded for reaching a "delivered" state. However, real-world requirements are often more nuanced: the robot should only be rewarded if it delivers coffee after a specific request was logged, and perhaps penalized if it entered a restricted zone without first passing through a security checkpoint. These requirements are inherently non-Markovian; they depend on the sequence of events leading up to the present. Previous attempts to address this often led to bloated state spaces or lacked the expressive power to handle sophisticated procedural constraints.

Methodology: The $LDL_f$ Compilation Pipeline

The authors propose using Linear Dynamic Logic over finite traces ($LDL_f$) as the primary language for reward specification. $LDL_f$ is a highly expressive logic that bridges the gap between Linear Temporal Logic ($LTL_f$) and Regular Expressions. It allows for the description of complex temporal patterns, such as "if event X occurs, perform task Y until condition Z is met."

The core contribution of this work is a formal pipeline to convert these logical specifications into a format compatible with standard MDP solvers:

  1. Specification: Users define rewards as pairs $(\phi_i, r_i)$, where $\phi_i$ is an $LDL_f$ formula representing a specific behavior and $r_i$ is the scalar reward associated with satisfying that formula.
  2. Automata Construction: Each $LDL_f$ formula is converted into a Minimal Deterministic Finite Automaton (DFA). These automata function as "monitors" that track the agent's progress toward satisfying the reward conditions.
  3. Product MDP Construction: The original MDP is augmented with the state space of these automata. The new "extended" state consists of the original environment state plus the current state of each reward-tracking DFA.
  4. Markovian Transformation: Within this extended state space, the rewards become Markovian. The agent receives reward $r_i$ when the corresponding DFA transitions into an accepting state.

Key Insights and Theoretical Contributions

Expressive Power

$LDL_f$ is strictly more expressive than standard $LTL_f$. It can capture any property expressible in Monadic Second-Order Logic (MSO) on finite traces. This allows for "procedural" rewards that $LTL_f$ struggles to define, such as tasks that require repeating an action a specific number of times or following a complex sequence of sub-goals.

Guaranteed Minimality

A significant theoretical breakthrough in this paper is the proof of minimality. The authors demonstrate that if minimal DFAs are used for the reward formulas, the resulting extended MDP is also minimal in its state space. This is critical for practical applications, as the "curse of dimensionality"—the exponential growth of the state space—is the primary bottleneck in solving MDPs.

Modularity and Compositionality

The framework is inherently modular. New reward conditions can be added by constructing a single new DFA and integrating it into the product MDP, rather than redesigning the entire reward structure. Furthermore, the paper demonstrates that these automata can be constructed "on-the-fly" during the search process (using progression), avoiding the generation of unreachable state-space regions.

Results and Impact

The authors provide a formal Equivalence Theorem, proving that an optimal policy in the extended Markovian MDP is also an optimal policy for the original non-Markovian problem. This ensures that the transformation does not lose any information or change the agent's fundamental objectives.

While the conversion from logic to DFA can theoretically result in a double-exponential blow-up in states, the authors argue that for the types of specifications typically used in reward design, the resulting DFAs remain small and computationally manageable. Finally, the paper shows that $LDL_f$ can naturally encode all reward types proposed in previous major works, positioning it as a unifying framework for the field of temporal logic rewards.

Limitations and Future Directions

Despite its strengths, the framework has limitations:

  • Finite Traces: $LDL_f$ is designed for finite sequences. Extending this to infinite-horizon problems would require moving to $\omega$-automata (such as Büchi automata), which are significantly more difficult to minimize.
  • Worst-Case Complexity: The theoretical potential for state-space explosion remains a concern for extremely complex specifications.
  • Early Rewards: Future research could explore "monitoring" techniques to provide partial rewards when an agent is clearly on the path to satisfying a long-term formula, rather than providing a sparse reward only upon completion.

By providing a mathematically rigorous and computationally efficient way to handle non-Markovian rewards, this work significantly expands the complexity of behaviors that can be reliably trained and verified in autonomous agents.

Summary updated

BibTeX
@inproceedings{brafman2018ltlf,
  author = {Ronen I. Brafman and Giuseppe De Giacomo and Fabio Patrizi},
  title = {{LTLf/LDLf Non-Markovian Rewards}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11572},
}
Figure