A Necessary and Sufficient Condition for the Unique Solution of the Bellman Equation for LTL Surrogate Rewards

Zetong Xuan, Alper Kamil Bozkurt, Miroslav Pajić, Yu WangResearch 2025 · DOI

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

Abstract

Abstract Linear Temporal Logic (LTL) offers a formal way of specifying complex objectives for Cyber-Physical Systems (CPS). In the presence of uncertain dynamics, the planning for an LTL objective can be solved by model-free reinforcement learning (RL). Surrogate rewards for LTL objectives are commonly utilized in model-free RL for LTL objectives. In a widely adopted surrogate reward approach, two discount factors are used to ensure that the expected return (i.e., the cumulative reward) approximates the satisfaction probability of the LTL objective. The expected return then can be estimated by methods using the Bellman updates such as RL. However, the uniqueness of the solution to the Bellman equation with two discount factors has not been explicitly discussed. We demonstrate, through an example, that when one of the discount factors is set to one, as allowed in many previous works, the Bellman equation may have multiple solutions, leading to an inaccurate evaluation of the expected return. To address this issue, we propose a condition that ensures the Bellman equation has the expected return as its unique solution. Specifically, we require that the solutions for states within rejecting bottom strongly connected components (BSCCs) be zero. We prove that this condition guarantees the uniqueness of the solution, first for recurrent states (i.e., states within a BSCC) and then for transient states. Finally, we numerically validate our results through case studies.
BibTeX
@inproceedings{xuan2025necessary,
  author = {Zetong Xuan and Alper Kamil Bozkurt and Miroslav Pajić and Yu Wang},
  title = {{A Necessary and Sufficient Condition for the Unique Solution of the Bellman Equation for LTL Surrogate Rewards}},
  booktitle = {Research},
  year = {2025},
  doi = {10.1017/cbp.2025.10004},
}
Figure