# Sample Efficient Model-free Reinforcement Learning from LTL Specifications with Optimality Guarantees

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 46 references that are in the map.
- First posted on arXiv 2 May 2023.

## Builds on (most cited first, 16 of 16)

- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Modular Multitask Reinforcement Learning with Policy Sketches](https://mlsanity.com/paper/1611.01796/) (2016)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guarantees](https://mlsanity.com/paper/1909.05304/) (2019)
- [Omega-Regular Objectives in Model-Free Reinforcement Learning](https://mlsanity.com/paper/1810.00950/) (2018)
- [Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning](https://mlsanity.com/paper/1909.07299/) (2019)
- [Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specifications](https://mlsanity.com/paper/1807.06333/) (2018)
- [A Composable Specification Language for Reinforcement Learning Tasks](https://mlsanity.com/paper/2008.09293/) (2020)
- [Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications](https://mlsanity.com/paper/1609.07409/) (2016)
- [Environment-Independent Task Specifications via GLTL](https://mlsanity.com/paper/1704.04341/) (2017)
- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications](https://mlsanity.com/paper/1409.5486/) (2014)
- [Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logic](https://mlsanity.com/paper/2102.12855/) (2021)
- [Transfer of Temporal Logic Formulas in Reinforcement Learning](https://mlsanity.com/paper/1909.04256/) (2019)
- [Temporal-Logic-Based Reward Shaping for Continuing Reinforcement Learning Tasks](https://mlsanity.com/paper/2007.01498/) (2020)

## Built on by (most cited first, 18 of 18)

- [DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RL](https://mlsanity.com/paper/2410.04631/) (2024)
- [Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards](https://mlsanity.com/paper/2410.12175/) (2024)
- [One Subgoal at a Time: Zero-Shot Generalization to Arbitrary Linear Temporal Logic Requirements in Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2508.01561/) (2025)
- [Directed Exploration in Reinforcement Learning from Linear Temporal Logic](https://mlsanity.com/paper/2408.09495/) (2024)
- [Mission-driven Exploration for Accelerated Deep Reinforcement Learning with Temporal Logic Task Specifications](https://mlsanity.com/paper/2311.17059/) (2023)
- [Learning Probabilistic Temporal Logic Specifications for Stochastic Systems](https://mlsanity.com/paper/2505.12107/) (2025)
- [Accelerated Learning with Linear Temporal Logic using Differentiable Simulation](https://mlsanity.com/paper/2506.01167/) (2025)
- [Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes](https://mlsanity.com/paper/2512.14617/) (2025)
- [Zero-Shot Instruction Following in RL via Structured LTL Representations](https://mlsanity.com/paper/2602.14344/) (2026)
- [SpecRLBench: A Benchmark for Generalization in Specification-Guided Reinforcement Learning](https://mlsanity.com/paper/2604.24729/) (2026)
- [Hyperproperty-Constrained Secure Reinforcement Learning](https://mlsanity.com/paper/2508.00106/) (2025)
- [Zero-Shot Instruction Following in RL via Structured LTL Representations](https://mlsanity.com/paper/2512.02633/) (2025)
- [About Time: Model-free Reinforcement Learning with Timed Reward Machines](https://mlsanity.com/paper/2512.17637/) (2025)
- [COOL-MC: Verifying and Explaining RL Policies for Platelet Inventory Management](https://mlsanity.com/paper/2603.02396/) (2026)
- [COOL-MC: Verifying and Explaining RL Policies for Multi-bridge Network Maintenance](https://mlsanity.com/paper/2603.07546/) (2026)
- [Value Functions as Supermartingale Certificates](https://mlsanity.com/paper/2605.31524/) (2026)
- [Exact Model-Free Policy Iteration for Co-safe LTL Planning](https://mlsanity.com/paper/2608.05047/) (2026)
- [Jaxolotl: A Unified High-Performance Benchmark Suite for LTL-Based Multi-Task RL](https://mlsanity.com/paper/2609.38065/) (2026)

## Abstract (arXiv)

Linear Temporal Logic (LTL) is widely used to specify high-level objectives for system policies, and it is highly desirable for autonomous systems to learn the optimal policy with respect to such specifications. However, learning the optimal policy from LTL specifications is not trivial. We present a model-free Reinforcement Learning (RL) approach that efficiently learns an optimal policy for an unknown stochastic system, modelled using Markov Decision Processes (MDPs). We propose a novel and more general product MDP, reward structure and discounting mechanism that, when applied in conjunction with off-the-shelf model-free RL algorithms, efficiently learn the optimal policy that maximizes the probability of satisfying a given LTL specification with optimality guarantees. We also provide improved theoretical results on choosing the key parameters in RL to ensure optimality. To directly evaluate the learned policy, we adopt probabilistic model checker PRISM to compute the probability of the policy satisfying such specifications. Several experiments on various tabular MDP environments across different LTL tasks demonstrate the improved sample efficiency and optimal policy convergence.