Introduction
In the field of Decision Theoretic Planning (DTP), the Markov Decision Process (MDP) serves as the standard mathematical framework for modeling sequential decision-making. The power of the MDP lies in the Markov property: the assumption that the future state of the environment depends only on the current state and the action taken, rather than the history of how the agent arrived there. While this property simplifies the underlying mathematics, it creates a significant bottleneck when defining complex goals.
This paper, originally presented at the 1996 AAAI proceedings, addresses a fundamental limitation of standard reward systems: their inherent "memoryless" nature. In many real-world scenarios, rewards are not tied to a static snapshot of the world but to a sequence of events over time. By introducing a method to specify rewards using temporal logic and automatically expanding the state space, the authors provide a bridge between complex, history-dependent behaviors and the efficient solvers available for standard MDPs.
The Problem: The Memoryless Constraint
In a standard MDP, a reward function $R(s)$ assigns a scalar value to a state $s$. This works well for simple goals like "reach the exit." However, it fails for tasks that require context.
Consider a service robot tasked with delivering coffee. A naive reward for the state has_delivered_coffee might encourage the robot to deliver coffee repeatedly, even if no one asked for it. Ideally, we only want to reward the robot if a request was made at some point in the past. To model this in a standard MDP, a designer must manually engineer a new state, such as coffee_requested_and_not_yet_delivered. This manual "state engineering" is tedious, prone to errors, and becomes mathematically intractable as the complexity of the desired behavior grows.
Methodology: Automating State Expansion
The authors propose a three-part solution to automate the transformation of non-Markovian rewards into a Markovian framework.
1. Past Linear Temporal Logic (PLTL)
While standard Linear Temporal Logic (LTL) is often used to describe future paths, the authors utilize Past Linear Temporal Logic (PLTL). This backward-looking logic allows designers to define rewards based on the agent's history. For example, a reward can be conditioned on a formula such as "Reward the agent if it is in state $A$, provided that event $B$ occurred at some point in the past."
2. Regression of Formulas
To bridge the gap between history and the current state, the authors define a regression operator. This mathematical tool takes a temporal formula and a specific state, then derives exactly what conditions must have been met in the previous state for the formula to remain true in the current state. This allows the system to track the "truth value" of complex behaviors step-by-step.
3. The Expansion Algorithm
The core contribution of the paper is an algorithm that automatically generates an "annotated" state space. This process occurs in three phases:
- Phase I (Identification): The algorithm determines which parts of the history are relevant to the reward formulas.
- Phase II (Construction): It builds a new transition graph where each state is a tuple consisting of the original physical state and a "label" representing the necessary historical context.
- Phase III (Minimization): To prevent unnecessary complexity, the algorithm minimizes the state space using techniques similar to those used in minimizing Finite State Automata, ensuring the resulting model is as compact as possible.
Key Insights and Results
The paper establishes several critical theoretical foundations for history-dependent planning:
- The Equivalence Theorem: The authors prove (Theorem 4.9) that the expanded MDP is mathematically equivalent to the original non-Markovian problem. This ensures that an optimal policy found in the expanded, Markovian space is guaranteed to be optimal for the original complex behavior.
- Compatibility with Standard Tools: Because the output of the algorithm is a standard MDP, researchers can apply "off-the-shelf" algorithms like Value Iteration or Policy Iteration to solve problems that were previously considered too complex for the MDP framework.
- Intent and Fulfillment: The authors argue that while physical dynamics (e.g., how a robot moves) are often Markovian, human-defined rewards almost never are. By automating the tracking of intent and fulfillment, they move the burden of state engineering from the human designer to the algorithm.
Limitations and Future Directions
Despite the elegance of the expansion algorithm, the authors acknowledge the challenge of state explosion. In the worst-case scenario, the state space can grow exponentially relative to the number of temporal constraints. If a behavior depends on a vast number of distinct past events, the resulting MDP may become too large to solve efficiently.
The paper suggests two primary avenues for future research:
- Factored Representations: Combining this approach with factored MDPs (such as Bayesian Networks) could allow the expanded state space to be represented more efficiently without enumerating every possible state.
- Non-Markovian Dynamics: While this paper focuses on complex rewards in a Markovian world, the authors note that extending these techniques to environments where the physics itself is history-dependent is a natural and necessary next step.
Conclusion
By formalizing the relationship between temporal logic and state space expansion, this work provides a rigorous method for teaching agents to understand not just where they are, but how they got there. It remains a foundational text for researchers looking to balance the mathematical simplicity of MDPs with the nuanced requirements of real-world task specification.
Summary updated