Introduction
Linear Temporal Logic (LTL) provides a formal and expressive framework for specifying complex objectives in Cyber-Physical Systems (CPS), such as "visit region A, then B, and never enter C." When the underlying system dynamics are uncertain, model-free Reinforcement Learning (RL) is a powerful tool for finding policies that satisfy these specifications. To integrate LTL with RL, researchers often use "surrogate rewards" and two distinct discount factors ($\gamma$ and $\gamma_B$) to ensure the agent's expected return approximates the probability of satisfying the LTL objective.
The Challenge of Non-Uniqueness
A common practice in recent literature is to set the primary discount factor ($\gamma$) to 1 to achieve a more accurate approximation of satisfaction probabilities. However, this paper identifies a critical mathematical oversight: when $\gamma = 1$, the standard Bellman equation—the fundamental recursive formula used in RL to update value functions—may lose its uniqueness. This means an RL agent could converge to any number of valid mathematical solutions, most of which do not represent the true expected return. This leads to inaccurate value estimations and suboptimal system behavior.
Methodology and the Uniqueness Condition
The authors analyze this problem by combining the system's physical states with the states of a Limit-Deterministic Büchi Automaton (LDBA) to create a Product MDP. By partitioning this state space, they pinpoint exactly where the uniqueness property breaks down.
They discovered that uniqueness is lost within rejecting Bottom Strongly Connected Components (BSCCs). These are "dead-end" regions in the state space where the LTL goal can never be satisfied. Mathematically, any constant value added to the states in these components still satisfies the Bellman equation when $\gamma = 1$.
To resolve this, the authors propose and prove a necessary and sufficient condition: the Bellman equation has the true expected return as its unique solution if and only if the values for all states within rejecting BSCCs are explicitly set to zero.
Experimental Validation
The theory was tested using a benchmark LTL planning problem involving a 1,040-state Product MDP and a complex formula with nested temporal operators.
- Tabular RL: Without the uniqueness condition, random initialization led to a massive approximation error of 16.75. By enforcing the zero-condition ($U_0 = 0$), the error dropped to a negligible 0.0079.
- Deep RL: The study highlights a specific vulnerability in Deep RL. Because neural networks share parameters across states (generalization), training on "good" states can "leak" non-zero values into the "dead-end" rejecting states. The authors demonstrated that a "Subset" training approach, which maintains the zero-condition, is essential for preventing error spikes during training.
Conclusion
This research provides a vital theoretical foundation for LTL-based Reinforcement Learning. By identifying the necessity of grounding rejecting states to zero, it ensures that RL agents can reliably evaluate complex tasks. Future work will focus on extending these conditions from policy evaluation to optimal control and developing model-free methods to identify BSCCs in high-dimensional environments.
Summary updated