mlsanityData to 7 Oct 2026

Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints

arXiv 1404.7073 ↗First posted 28 Apr 2014eess.SY cs.LG cs.LOcited by 53

Not on the map. Why?

Abstract (arXiv)

We consider synthesis of control policies that maximize the probability of satisfying given temporal logic specifications in unknown, stochastic environments. We model the interaction between the system and its environment as a Markov decision process (MDP) with initially unknown transition probabilities. The solution we develop builds on the so-called model-based probably approximately correct Markov decision process (PAC-MDP) methodology. The algorithm attains an varepsilon-approximately optimal policy with probability 1-δ using samples (i.e. observations), time and space that grow polynomially with the size of the MDP, the size of the automaton expressing the temporal logic specification, frac1varepsilon, frac1δ and a finite time horizon. In this approach, the system maintains a model of the initially unknown MDP, and constructs a product MDP based on its learned model and the specification automaton that expresses the temporal logic constraints. During execution, the policy is iteratively updated using observation of the transitions taken by the system. The iteration terminates in finitely many steps. With high probability, the resulting policy is such that, for any state, the difference between the probability of satisfying the specification under this policy and the optimal one is within a predefined bound.

Key facts. Cited by 53 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Apr 2014.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 9; 2022: 6; 2023: 11; 2024: 12; 2025: 8; 2026: 6.

53 papers.

Sort:

By area:

  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. 2020Active Task-Inference-Guided Deep Inverse Reinforcement Learningcited by 17
  9. 2023Robust Control for Dynamical Systems With Non-Gaussian Noise via Formal Abstractionscited by 16
  10. 2023Policy Synthesis and Reinforcement Learning for Discounted LTLcited by 14
  11. 2021Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noisecited by 13
  12. 2023Computably Continuous Reinforcement-Learning Objectives are PAC-learnablecited by 13
38 more
  1. 2024Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewardscited by 13
  2. 2023A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPscited by 12
  3. 2021Generalizing to New Domains by Mapping Natural Language to Lifted LTLcited by 11
  4. 2024LTL-Constrained Policy Optimization with Cycle Experience Replaycited by 10
  5. 2022Automata Learning meets Shieldingcited by 9
  6. 2025One Subgoal at a Time: Zero-Shot Generalization to Arbitrary Linear Temporal Logic Requirements in Multi-Task Reinforcement Learningcited by 8
  7. 2021Hierarchical Potential-based Reward Shaping from Task Specificationscited by 7
  8. 2024Learning Robust Reward Machines from Noisy Labelscited by 7
  9. 2022Model-Free Reinforcement Learning for Symbolic Automata-encoded Objectivescited by 6
  10. 2021Model-Free Learning of Safe yet Effective Controllerscited by 5
  11. 2024What Are the Odds? Improving the foundations of Statistical Model Checkingcited by 5
  12. 2022PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDPcited by 4
  13. 2021Learning Optimal Strategies for Temporal Tasks in Stochastic Gamescited by 3
  14. 2023Mission-driven Exploration for Accelerated Deep Reinforcement Learning with Temporal Logic Task Specificationscited by 3
  15. 2024On the Uniqueness of Solution for the Bellman Equation of LTL Objectivescited by 3
  16. 2024Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Explorationcited by 3
  17. 2021Reinforcement Learning Based Temporal Logic Control with Soft Constraints Using Limit-deterministic Generalized Buchi Automatacited by 2
  18. 2023Reinforcement Learning with Temporal-Logic-Based Causal Diagramscited by 2
  19. 2024Composing Reinforcement Learning Policies, with Formal Guaranteescited by 2
  20. 2024Tractable Offline Learning of Regular Decision Processescited by 2
  21. 2023Co-learning Planning and Control Policies Constrained by Differentiable Logic Specificationscited by 1
  22. 2024Regret-Free Reinforcement Learning for LTL Specificationscited by 1
  23. 2025Accelerated Learning with Linear Temporal Logic using Differentiable Simulationcited by 1
  24. 2026Zero-Shot Instruction Following in RL via Structured LTL Representationscited by 1
  25. 2022Safe Policy Improvement in Constrained Markov Decision Processescited by 0
  26. 2022Reinforcement Causal Structure Learning on Order Graphcited by 0
  27. 2023Topology-Guided Modular Actor-Critic Learning for Continuous Systems under Temporal Objectivescited by 0
  28. 2023Fulfilling Formal Specifications ASAP by Model-free Reinforcement Learningcited by 0
  29. 2023Omega-Regular Decision Processescited by 0
  30. 2024Scaling Learning based Policy Optimization for Temporal Logic Tasks by Controller Network Dropoutcited by 0
  31. 2025Average Reward Reinforcement Learning for Omega-Regular and Mean-Payoff Objectivescited by 0
  32. 2025Physics-Informed Reward Machinescited by 0
  33. 2025Constraints-Guided Diffusion Reasoner for Neuro-Symbolic Learningcited by 0
  34. 2025Expressive Reward Synthesis with the Runtime Monitoring Languagecited by 0
  35. 2025Near-Optimal Reinforcement Learning for Constrained Recurrence Objectivescited by 0
  36. 2025Zero-Shot Instruction Following in RL via Structured LTL Representationscited by 0
  37. 2026COOL-MC: Verifying and Explaining RL Policies for Platelet Inventory Managementcited by 0
  38. 2026COOL-MC: Verifying and Explaining RL Policies for Multi-bridge Network Maintenancecited by 0

50 most cited of 53 All 53 (JSON)