mlsanityData to 14 Oct 2026

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

arXiv 2305.01381 ↗First posted 2 May 2023cs.LG cs.AI cs.FLcited by 18

Not on the map. Why?

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.

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

16 of 46 references.

References · 16

  1. 2016OpenAI Gymcited by 1,736
  2. 2016Modular Multitask Reinforcement Learning with Policy Sketchescited by 203
  3. 2020Reward Machines: Exploiting Reward Function Structure in Reinforcement Learningcited by 191
  4. 2016Reinforcement Learning With Temporal Logic Rewardscited by 117
  5. 2019Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guaranteescited by 77
  6. 2018Omega-Regular Objectives in Model-Free Reinforcement Learningcited by 75
  7. 2019Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learningcited by 75
  8. 2018Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specificationscited by 72
  9. 2020A Composable Specification Language for Reinforcement Learning Taskscited by 69
  10. 2016Q-Learning for Robust Satisfaction of Signal Temporal Logic Specificationscited by 67
  11. 2017Environment-Independent Task Specifications via GLTLcited by 67
  12. 2021Compositional Reinforcement Learning from Logical Specificationscited by 67
4 more
  1. 2014A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specificationscited by 49
  2. 2021Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logiccited by 39
  3. 2019Transfer of Temporal Logic Formulas in Reinforcement Learningcited by 31
  4. 2020Temporal-Logic-Based Reward Shaping for Continuing Reinforcement Learning Taskscited by 28

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 3; 2025: 7; 2026: 7.

18 papers.

Sort:

By area:

  1. 2024DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RLcited by 21
  2. 2024Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewardscited by 14
  3. 2025One Subgoal at a Time: Zero-Shot Generalization to Arbitrary Linear Temporal Logic Requirements in Multi-Task Reinforcement Learningcited by 8
  4. 2024Directed Exploration in Reinforcement Learning from Linear Temporal Logiccited by 7
  5. 2023Mission-driven Exploration for Accelerated Deep Reinforcement Learning with Temporal Logic Task Specificationscited by 3
  6. 2025Learning Probabilistic Temporal Logic Specifications for Stochastic Systemscited by 2
  7. 2025Accelerated Learning with Linear Temporal Logic using Differentiable Simulationcited by 1
  8. 2025Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processescited by 1
  9. 2026Zero-Shot Instruction Following in RL via Structured LTL Representationscited by 1
  10. 2026SpecRLBench: A Benchmark for Generalization in Specification-Guided Reinforcement Learningcited by 1
  11. 2025Hyperproperty-Constrained Secure Reinforcement Learningcited by 0
  12. 2025Zero-Shot Instruction Following in RL via Structured LTL Representationscited by 0
6 more
  1. 2025About Time: Model-free Reinforcement Learning with Timed Reward Machinescited by 0
  2. 2026COOL-MC: Verifying and Explaining RL Policies for Platelet Inventory Managementcited by 0
  3. 2026COOL-MC: Verifying and Explaining RL Policies for Multi-bridge Network Maintenancecited by 0
  4. 2026Value Functions as Supermartingale Certificatescited by 0
  5. 2026Exact Model-Free Policy Iteration for Co-safe LTL Planningcited by 0
  6. 2026Jaxolotl: A Unified High-Performance Benchmark Suite for LTL-Based Multi-Task RLcited by 0