# Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guarantees

arXiv: https://arxiv.org/abs/1909.05304 · HTML: https://mlsanity.com/paper/1909.05304/

## Key facts

- Cited by 77 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2019.

## Built on by (most cited first, 30 of 77)

- [Evaluating Cognitive Maps and Planning in Large Language Models with CogEval](https://mlsanity.com/paper/2309.15129/) (2023)
- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [Safe Reinforcement Learning via Probabilistic Logic Shields](https://mlsanity.com/paper/2303.03226/) (2023)
- [Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic](https://mlsanity.com/paper/2102.12855/) (2021)
- [Provably Safe Reinforcement Learning: Conceptual Analysis, Survey, and Benchmarking](https://mlsanity.com/paper/2205.06750/) (2022)
- [On the (In)Tractability of Reinforcement Learning for LTL Objectives](https://mlsanity.com/paper/2111.12679/) (2021)
- [Sample Efficient Model-free Reinforcement Learning from LTL Specifications with Optimality Guarantees](https://mlsanity.com/paper/2305.01381/) (2023)
- [Active Task-Inference-Guided Deep Inverse Reinforcement Learning](https://mlsanity.com/paper/2001.09227/) (2020)
- [General agents contain world models](https://mlsanity.com/paper/2506.01622/) (2025)
- [ALLURE: Auditing and Improving LLM-based Evaluation of Text using Iterative In-Context-Learning](https://mlsanity.com/paper/2309.13701/) (2023)
- [Shielding Atari Games with Bounded Prescience](https://mlsanity.com/paper/2101.08153/) (2021)
- [Policy Synthesis and Reinforcement Learning for Discounted LTL](https://mlsanity.com/paper/2305.17115/) (2023)
- [Compositional Policy Learning in Stochastic Control Systems with Formal Guarantees](https://mlsanity.com/paper/2312.01456/) (2023)
- [Computably Continuous Reinforcement-Learning Objectives are PAC-learnable](https://mlsanity.com/paper/2303.05518/) (2023)
- [LCRL: Certified Policy Synthesis via Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/2209.10341/) (2022)
- [ConformalNL2LTL: Translating Natural Language Instructions into Temporal Logic Formulas with Conformal Correctness Guarantees](https://mlsanity.com/paper/2504.21022/) (2025)
- [We'll Fix it in Post: Improving Text-to-Video Generation with Neuro-Symbolic Feedback](https://mlsanity.com/paper/2504.17180/) (2025)
- [Accelerated Reinforcement Learning for Temporal Logic Control Objectives](https://mlsanity.com/paper/2205.04424/) (2022)
- [Contingency-constrained economic dispatch with safe reinforcement learning](https://mlsanity.com/paper/2205.06212/) (2022)
- [Specification-Guided Learning of Nash Equilibria with High Social Welfare](https://mlsanity.com/paper/2206.03348/) (2022)
- [Towards Safe Autonomous Driving Policies using a Neuro-Symbolic Deep Reinforcement Learning Approach](https://mlsanity.com/paper/2307.01316/) (2023)
- [Learning Minimally-Violating Continuous Control for Infeasible Linear Temporal Logic Specifications](https://mlsanity.com/paper/2210.01162/) (2022)
- [Adaptive Reward Design for Reinforcement Learning](https://mlsanity.com/paper/2412.10917/) (2024)
- [Model-Free Learning of Safe yet Effective Controllers](https://mlsanity.com/paper/2103.14600/) (2021)
- [Reinforcement Learning with Knowledge Representation and Reasoning: A Brief Survey](https://mlsanity.com/paper/2304.12090/) (2023)
- [Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration](https://mlsanity.com/paper/2410.12136/) (2024)
- [A Challenge to Build Neuro-Symbolic Video Agents](https://mlsanity.com/paper/2505.13851/) (2025)
- [Probabilistic Planning with Preferences over Temporal Goals](https://mlsanity.com/paper/2103.14489/) (2021)
- [Learning Symbolic Representations for Reinforcement Learning of Non-Markovian Behavior](https://mlsanity.com/paper/2301.02952/) (2023)
- [Learning Optimal Strategies for Temporal Tasks in Stochastic Games](https://mlsanity.com/paper/2102.04307/) (2021)

## Abstract (arXiv)

Reinforcement Learning (RL) has emerged as an efficient method of choice for solving complex sequential decision making problems in automatic control, computer science, economics, and biology. In this paper we present a model-free RL algorithm to synthesize control policies that maximize the probability of satisfying high-level control objectives given as Linear Temporal Logic (LTL) formulas. Uncertainty is considered in the workspace properties, the structure of the workspace, and the agent actions, giving rise to a Probabilistically-Labeled Markov Decision Process (PL-MDP) with unknown graph structure and stochastic behaviour, which is even more general case than a fully unknown MDP. We first translate the LTL specification into a Limit Deterministic Buchi Automaton (LDBA), which is then used in an on-the-fly product with the PL-MDP. Thereafter, we define a synchronous reward function based on the acceptance condition of the LDBA. Finally, we show that the RL algorithm delivers a policy that maximizes the satisfaction probability asymptotically. We provide experimental results that showcase the efficiency of the proposed method.