# A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2014.

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

- [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)
- [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)
- [LASER: A Neuro-Symbolic Framework for Learning Spatial-Temporal Scene Graphs with Weak Supervision](https://mlsanity.com/paper/2304.07647/) (2023)
- [Risk-averse autonomous systems: A brief history and recent developments from the perspective of optimal control](https://mlsanity.com/paper/2109.08947/) (2021)
- [Joint Learning of Reward Machines and Policies in Environments with Partially Known Semantics](https://mlsanity.com/paper/2204.11833/) (2022)
- [Generalizing to New Domains by Mapping Natural Language to Lifted LTL](https://mlsanity.com/paper/2110.05603/) (2021)
- [LCRL: Certified Policy Synthesis via Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/2209.10341/) (2022)
- [LTL-Constrained Policy Optimization with Cycle Experience Replay](https://mlsanity.com/paper/2404.11578/) (2024)
- [Accelerated Reinforcement Learning for Temporal Logic Control Objectives](https://mlsanity.com/paper/2205.04424/) (2022)
- [Mungojerrie: Reinforcement Learning of Linear-Time Objectives](https://mlsanity.com/paper/2106.09161/) (2021)
- [Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectives](https://mlsanity.com/paper/2202.02404/) (2022)
- [Learning Minimally-Violating Continuous Control for Infeasible Linear Temporal Logic Specifications](https://mlsanity.com/paper/2210.01162/) (2022)
- [TGPO: Temporal Grounded Policy Optimization for Signal Temporal Logic Tasks](https://mlsanity.com/paper/2510.00225/) (2025)
- [Model-Free Learning of Safe yet Effective Controllers](https://mlsanity.com/paper/2103.14600/) (2021)
- [Targeted Adversarial Attacks on Deep Reinforcement Learning Policies via Model Checking](https://mlsanity.com/paper/2212.05337/) (2022)
- [Designing Behavior Trees from Goal-Oriented LTLf Formulas](https://mlsanity.com/paper/2307.06399/) (2023)
- [Efficient Reinforcement Learning in Probabilistic Reward Machines](https://mlsanity.com/paper/2408.10381/) (2024)
- [Learning Optimal Strategies for Temporal Tasks in Stochastic Games](https://mlsanity.com/paper/2102.04307/) (2021)
- [Assured Learning-enabled Autonomy: A Metacognitive Reinforcement Learning Framework](https://mlsanity.com/paper/2103.12558/) (2021)
- [Dual-Objective Reinforcement Learning with Novel Hamilton-Jacobi-Bellman Formulations](https://mlsanity.com/paper/2506.16016/) (2025)
- [Reinforcement Learning Based Temporal Logic Control with Soft Constraints Using Limit-deterministic Generalized Buchi Automata](https://mlsanity.com/paper/2101.10284/) (2021)

## Abstract (arXiv)

We propose to synthesize a control policy for a Markov decision process (MDP) such that the resulting traces of the MDP satisfy a linear temporal logic (LTL) property. We construct a product MDP that incorporates a deterministic Rabin automaton generated from the desired LTL property. The reward function of the product MDP is defined from the acceptance condition of the Rabin automaton. This construction allows us to apply techniques from learning theory to the problem of synthesis for LTL specifications even when the transition probabilities are not known a priori. We prove that our method is guaranteed to find a controller that satisfies the LTL property with probability one if such a policy exists, and we suggest empirically with a case study in traffic control that our method produces reasonable control strategies even when the LTL property cannot be satisfied with probability one.