mlsanityData to 7 Oct 2026

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

arXiv 1409.5486 ↗First posted 18 Sep 2014eess.SY cs.SYcited by 49

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 9; 2023: 10; 2024: 7; 2025: 7; 2026: 6.

49 papers.

Sort:

  1. 2021Modular Deep Reinforcement Learning for Continuous Motion Planning with Temporal Logiccited by 38
  2. 2021Multi-Agent Reinforcement Learning with Temporal Logic Specificationscited by 27
  3. 2024DeepLTL: Learning to Efficiently Satisfy Complex LTL Specifications for Multi-Task RLcited by 20
  4. 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
  5. 2021On the (In)Tractability of Reinforcement Learning for LTL Objectivescited by 18
  6. 2023Eventual Discounting Temporal Logic Counterfactual Experience Replaycited by 18
  7. 2024Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learningcited by 18
  8. 2023Sample Efficient Model-free Reinforcement Learning from LTL Specifications with Optimality Guaranteescited by 17
  9. 2023Policy Synthesis and Reinforcement Learning for Discounted LTLcited by 14
  10. 2023Computably Continuous Reinforcement-Learning Objectives are PAC-learnablecited by 13
  11. 2023LASER: A Neuro-Symbolic Framework for Learning Spatial-Temporal Scene Graphs with Weak Supervisioncited by 13
  12. 2024Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewardscited by 13
37 more
  1. 2021Risk-averse autonomous systems: A brief history and recent developments from the perspective of optimal controlcited by 12
  2. 2022Joint Learning of Reward Machines and Policies in Environments with Partially Known Semanticscited by 12
  3. 2021Generalizing to New Domains by Mapping Natural Language to Lifted LTLcited by 11
  4. 2022LCRL: Certified Policy Synthesis via Logically-Constrained Reinforcement Learningcited by 11
  5. 2024LTL-Constrained Policy Optimization with Cycle Experience Replaycited by 10
  6. 2022Accelerated Reinforcement Learning for Temporal Logic Control Objectivescited by 9
  7. 2021Mungojerrie: Reinforcement Learning of Linear-Time Objectivescited by 6
  8. 2022Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectivescited by 6
  9. 2021Model-Free Learning of Safe yet Effective Controllerscited by 5
  10. 2022Learning Minimally-Violating Continuous Control for Infeasible Linear Temporal Logic Specificationscited by 5
  11. 2022Targeted Adversarial Attacks on Deep Reinforcement Learning Policies via Model Checkingcited by 5
  12. 2023Designing Behavior Trees from Goal-Oriented LTLf Formulascited by 5
  13. 2025TGPO: Temporal Grounded Policy Optimization for Signal Temporal Logic Taskscited by 5
  14. 2024Efficient Reinforcement Learning in Probabilistic Reward Machinescited by 4
  15. 2021Learning Optimal Strategies for Temporal Tasks in Stochastic Gamescited by 3
  16. 2021Assured Learning-enabled Autonomy: A Metacognitive Reinforcement Learning Frameworkcited by 3
  17. 2021Reinforcement Learning Based Temporal Logic Control with Soft Constraints Using Limit-deterministic Generalized Buchi Automatacited by 2
  18. 2023Omega-Regular Reward Machinescited by 2
  19. 2025Dual-Objective Reinforcement Learning with Novel Hamilton-Jacobi-Bellman Formulationscited by 2
  20. 2026Semantically Labelled Automata for Multi-Task Reinforcement Learning with LTL Instructionscited by 2
  21. 2023Reinforcement Learning for Omega-Regular Specifications on Continuous-Time MDPcited by 1
  22. 2024Integrating Explanations in Learning LTL Specifications from Demonstrationscited by 1
  23. 2026Zero-Shot Instruction Following in RL via Structured LTL Representationscited by 1
  24. 2022Alternating Good-for-MDP Automatacited by 0
  25. 2022Reinforcement Causal Structure Learning on Order Graphcited by 0
  26. 2023Searching for Optimal Runtime Assurance via Reachability and Reinforcement Learningcited by 0
  27. 2023Omega-Regular Decision Processescited by 0
  28. 2024Scaling Learning based Policy Optimization for Temporal Logic Tasks by Controller Network Dropoutcited by 0
  29. 2025Average Reward Reinforcement Learning for Omega-Regular and Mean-Payoff Objectivescited by 0
  30. 2025Physics-Informed Reward Machinescited by 0
  31. 2025Expressive Reward Synthesis with the Runtime Monitoring Languagecited by 0
  32. 2025Expressive Temporal Specifications for Reward Monitoringcited by 0
  33. 2025Zero-Shot Instruction Following in RL via Structured LTL Representationscited by 0
  34. 2026COOL-MC: Verifying and Explaining RL Policies for Platelet Inventory Managementcited by 0
  35. 2026COOL-MC: Verifying and Explaining RL Policies for Multi-bridge Network Maintenancecited by 0
  36. 2026Temporal-Causal Inference for Reinforcement Learning via Automata Learningcited by 0
  37. 2026Jaxolotl: A Unified High-Performance Benchmark Suite for LTL-Based Multi-Task RLcited by 0