mlsanityData to 14 Oct 2026

Exact Model-Free Policy Iteration for Co-safe LTL Planning

arXiv 2608.05047 ↗First posted 5 Aug 2026eess.SY cs.FL cs.ROcited by 0

On the map: Deep reinforcement learning methods → Interpretable and logic-guided RL

Abstract (arXiv)

This work studies model-free reinforcement learning for co-safe linear temporal logic (sc-LTL) objectives in finite Markov decision processes, which can be reduced to maximal reachability objectives via the standard product construction. For this problem, direct sample-based bootstrap methods (e.g., TD or Q-learning) may fail to converge to optimal policies due to the noncontractive nature and nonuniqueness of solutions to the Bellman equation. We develop a new two-step model-free reinforcement learning method that first uses a discounted surrogate to identify a clamp set that resolves this nonuniqueness, and then applies undiscounted policy evaluation and greedy policy improvement with guarantees of finding an optimal solution. We prove almost-sure convergence of the policy evaluation step and finite termination of the policy iteration algorithm at an optimal policy. These theoretical results are validated through numerical experiments on a stochastic grid world.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in Interpretable and logic-guided RL, one of 15 directions in Deep reinforcement learning methods. Builds on 13 of its 28 references that are in the map. First posted on arXiv 5 Aug 2026.

Builds on

13 of 28 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards16 Oct
  2. 2024Sample-Efficient Reinforcement Learning with Temporal Logic Objectives: Leveraging the Task Specification to Guide Exploration16 Oct

Other references · 11

  1. 2019Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learningcited by 75
  2. 2018Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specificationscited by 72
  3. 2014Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraintscited by 54
  4. 2014Verification of Markov Decision Processes using Learning Algorithmscited by 39
  5. 2019Certified Reinforcement Learning with Logic Guidancecited by 36
  6. 2019PAC Statistical Model Checking for Markov Decision Processes and Stochastic Gamescited by 32
  7. 2023Eventual Discounting Temporal Logic Counterfactual Experience Replaycited by 19
  8. 2023Sample Efficient Model-free Reinforcement Learning from LTL Specifications with Optimality Guaranteescited by 18
  9. 2020Model-Free Reinforcement Learning for Stochastic Games with Linear Temporal Logic Objectivescited by 7
  10. 2018Monte Carlo Tree Search for Verifying Reachability in Markov Decision Processescited by 2
  11. 2019Topological Approximate Dynamic Programming under Temporal Logic Constraintscited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Regret-Free Reinforcement Learning for LTL Specifications
  2. 2024Analysis of Off-Policy Multi-Step TD-Learning with Linear Function Approximation
  3. 2025Analysis of Off-Policy n-Step TD-Learning with Linear Function Approximation
  4. 2025TGPO: Temporal Grounded Policy Optimization for Signal Temporal Logic Tasks
  5. 2025A Survey of Safe Reinforcement Learning and Constrained MDPs: A Technical Survey on Single-Agent and Multi-Agent Safety
  6. 2025Accelerated Learning with Linear Temporal Logic using Differentiable Simulation
  7. 2026Efficient Bayes-Adaptive Reinforcement Learning with Temporal Logic Specifications
  8. 2024Probabilistic Model Checking of Stochastic Reinforcement Learning Policies