mlsanityData to 14 Oct 2026

A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs

arXiv 2310.12248 ↗First posted 18 Oct 2023cs.LG cs.LOcited by 13

Not on the map. Why?

Abstract (arXiv)

Linear temporal logic (LTL) and omega-regular objectives -- a superset of LTL -- have seen recent use as a way to express non-Markovian objectives in reinforcement learning. We introduce a model-based probably approximately correct (PAC) learning algorithm for omega-regular objectives in Markov decision processes (MDPs). As part of the development of our algorithm, we introduce the epsilon-recurrence time: a measure of the speed at which a policy converges to the satisfaction of the omega-regular objective in the limit. We prove that our algorithm only requires a polynomial number of samples in the relevant parameters, and perform experiments which confirm our theory.

Key facts. Cited by 13 papers in the map (data through 14 Oct 2026). Builds on 10 of its 22 references that are in the map. First posted on arXiv 18 Oct 2023.

Builds on

10 of 22 references.

References · 10

  1. 2016Concrete Problems in AI Safetycited by 1,642
  2. 2019Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learningcited by 75
  3. 2017Environment-Independent Task Specifications via GLTLcited by 67
  4. 2014Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraintscited by 54
  5. 2014Verification of Markov Decision Processes using Learning Algorithmscited by 39
  6. 2019PAC Statistical Model Checking for Markov Decision Processes and Stochastic Gamescited by 32
  7. 2022Policy Optimization with Linear Temporal Logic Constraintscited by 19
  8. 2021On the (In)Tractability of Reinforcement Learning for LTL Objectivescited by 18
  9. 2023Policy Synthesis and Reinforcement Learning for Discounted LTLcited by 14
  10. 2015Faster Statistical Model Checking for Unbounded Temporal Propertiescited by 9

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 2; 2026: 5.

13 papers.

Sort:

By area:

  1. 2024Compositional Automata Embeddings for Goal-Conditioned Reinforcement Learningcited by 19
  2. 2024Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewardscited by 14
  3. 2024LTL-Constrained Policy Optimization with Cycle Experience Replaycited by 11
  4. 2024What Are the Odds? Improving the foundations of Statistical Model Checkingcited by 5
  5. 2023Mission-driven Exploration for Accelerated Deep Reinforcement Learning with Temporal Logic Task Specificationscited by 3
  6. 2024Regret-Free Reinforcement Learning for LTL Specificationscited by 1
  7. 2025Accelerated Learning with Linear Temporal Logic using Differentiable Simulationcited by 1
  8. 2025Near-Optimal Reinforcement Learning for Constrained Recurrence Objectivescited by 0
  9. 2026Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimalitycited by 0
  10. 2026Sample-Efficient Learning of Probabilistic Causes for Reachability in Markov Decision Processes with Probabilistic Guaranteescited by 0
  11. 2026PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distancecited by 0
  12. 2026Q-Learning for Reachability in MEC-Free MDPscited by 0
1 more
  1. 2026Certifying Almost-Sure Reachability in Unknown MDPscited by 0