EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

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

Zetong Xuan, Alper Kamil Bozkurt, Miroslav Pajic, Yu Wang

Research Directions: Cyber-Physical Systems · 2025

DOI: 10.1017/cbp.2025.10004 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Research Directions: Cyber-Physical Systems, 2025. Verfasst von Zetong Xuan und 3 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Xuan, Z., Bozkurt, A. K., Pajic, M., & Wang, Y. (2025). A Necessary and Sufficient Condition for the Unique Solution of the Bellman Equation for LTL Surrogate Rewards. Research Directions: Cyber-Physical Systems. https://doi.org/10.1017/cbp.2025.10004

Vancouver

Xuan Z, Bozkurt AK, Pajic M, Wang Y. A Necessary and Sufficient Condition for the Unique Solution of the Bellman Equation for LTL Surrogate Rewards. Research Directions: Cyber-Physical Systems. 2025. doi:10.1017/cbp.2025.10004

BibTeX
@article{Xuan2025,
  author = {Xuan, Zetong and Bozkurt, Alper Kamil and Pajic, Miroslav and Wang, Yu},
  title = {A Necessary and Sufficient Condition for the Unique Solution of the Bellman Equation for LTL Surrogate Rewards},
  journal = {Research Directions: Cyber-Physical Systems},
  year = {2025},
  doi = {10.1017/cbp.2025.10004}
}
Kostenlos starten →