# Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning

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

## Key facts

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

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

- [Safe Multi-Agent Reinforcement Learning via Shielding](https://mlsanity.com/paper/2101.11196/) (2021)
- [Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic](https://mlsanity.com/paper/2102.12855/) (2021)
- [Multi-Agent Reinforcement Learning with Temporal Logic Specifications](https://mlsanity.com/paper/2102.00582/) (2021)
- [DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RL](https://mlsanity.com/paper/2410.04631/) (2024)
- [Policy Optimization with Linear Temporal Logic Constraints](https://mlsanity.com/paper/2206.09546/) (2022)
- [Eventual Discounting Temporal Logic Counterfactual Experience Replay](https://mlsanity.com/paper/2303.02135/) (2023)
- [Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2411.00205/) (2024)
- [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)
- [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)
- [Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards](https://mlsanity.com/paper/2410.12175/) (2024)
- [Computably Continuous Reinforcement-Learning Objectives are PAC-learnable](https://mlsanity.com/paper/2303.05518/) (2023)
- [A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs](https://mlsanity.com/paper/2310.12248/) (2023)
- [Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics](https://mlsanity.com/paper/2204.11833/) (2022)
- [LCRL: Certified Policy Synthesis via Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/2209.10341/) (2022)
- [Model-based Dynamic Shielding for Safe and Efficient Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2304.06281/) (2023)
- [LgTS: Dynamic Task Sampling using LLM-generated sub-goals for Reinforcement Learning Agents](https://mlsanity.com/paper/2310.09454/) (2023)
- [LTL-Constrained Policy Optimization with Cycle Experience Replay](https://mlsanity.com/paper/2404.11578/) (2024)
- [Temporal Logic Specification-Conditioned Decision Transformer for Offline Safe Reinforcement Learning](https://mlsanity.com/paper/2402.17217/) (2024)
- [Accelerated Reinforcement Learning for Temporal Logic Control Objectives](https://mlsanity.com/paper/2205.04424/) (2022)
- [Directed Exploration in Reinforcement Learning from Linear Temporal Logic](https://mlsanity.com/paper/2408.09495/) (2024)
- [Mungojerrie: Reinforcement Learning of Linear-Time Objectives](https://mlsanity.com/paper/2106.09161/) (2021)
- [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)
- [Lifelong Reinforcement Learning with Temporal Logic Formulas and Reward Machines](https://mlsanity.com/paper/2111.09475/) (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)
- [Learning Optimal Strategies for Temporal Tasks in Stochastic Games](https://mlsanity.com/paper/2102.04307/) (2021)
- [Logic-based Reward Shaping for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2206.08881/) (2022)

## Abstract (arXiv)

We present a reinforcement learning (RL) framework to synthesize a control policy from a given linear temporal logic (LTL) specification in an unknown stochastic environment that can be modeled as a Markov Decision Process (MDP). Specifically, we learn a policy that maximizes the probability of satisfying the LTL formula without learning the transition probabilities. We introduce a novel rewarding and path-dependent discounting mechanism based on the LTL formula such that (i) an optimal policy maximizing the total discounted reward effectively maximizes the probabilities of satisfying LTL objectives, and (ii) a model-free RL algorithm using these rewards and discount factors is guaranteed to converge to such policy. Finally, we illustrate the applicability of our RL-based synthesis approach on two motion planning case studies.