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

• URL: http://arxiv.org/abs/2608.05047v1
• Date: Wed, 05 Aug 2026 16:58:25 GMT
• Title: Exact Model-Free Policy Iteration for Co-safe LTL Planning
• Abstract summary: This work studies model-free reinforcement learning for co-safe linear temporal logic objectives in finite Markov decision processes.<n>We develop a new two-step model-free reinforcement learning method that first uses a discounted surrogate to identify a clamp set.<n>We prove almost-sure convergence of the policy evaluation step and finite termination of the policy iteration algorithm at an optimal policy.
• Score: 2.5735476569508995
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Duality [53.525547349715595]
  We propose a novel primal-only algorithm called Rectified Robust Policy Optimization (RRPO)<n>RRPO operates directly on the primal problem without relying on dual formulations.<n>We show convergence to an approximately optimal feasible policy with complexity matching the best-known lower bound.
  arXiv  Detail & Related papers  (2025-08-24T16:59:38Z)
• Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning [66.4260157478436]
  We study reinforcement learning in the policy learning setting.<n>The goal is to find a policy whose performance is competitive with the best policy in a given class of interest.
  arXiv  Detail & Related papers  (2025-07-06T14:40:05Z)
• Quantile-Optimal Policy Learning under Unmeasured Confounding [55.72891849926314]
  We study quantile-optimal policy learning where the goal is to find a policy whose reward distribution has the largest $alpha$-quantile for some $alpha in (0, 1)$.<n>Such a problem suffers from three main challenges: (i) nonlinearity of the quantile objective as a functional of the reward distribution, (ii) unobserved confounding issue, and (iii) insufficient coverage of the offline dataset.
  arXiv  Detail & Related papers  (2025-06-08T13:37:38Z)
• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [69.1820058966619]
  We tackle average-reward infinite-horizon POMDPs with an unknown transition model.<n>We present a novel and simple estimator that overcomes this barrier.
  arXiv  Detail & Related papers  (2025-01-30T22:29:41Z)
• Model-Free $\mu$-Synthesis: A Nonsmooth Optimization Perspective [4.477225073240389]
  In this paper, we revisit an important policy search benchmark, namely $mu$-synthesis. We show that subgradient-based search methods have led to impressive numerical results in practice.
  arXiv  Detail & Related papers  (2024-02-18T17:17:17Z)
• Probabilistic Reach-Avoid for Bayesian Neural Networks [71.67052234622781]
  We show that an optimal synthesis algorithm can provide more than a four-fold increase in the number of certifiable states. The algorithm is able to provide more than a three-fold increase in the average guaranteed reach-avoid probability.
  arXiv  Detail & Related papers  (2023-10-03T10:52:21Z)
• Randomized Policy Optimization for Optimal Stopping [0.0]
  We propose a new methodology for optimal stopping based on randomized linear policies. We show that our approach can substantially outperform state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-03-25T04:33:15Z)
• Bellman Residual Orthogonalization for Offline Reinforcement Learning [53.17258888552998]
  We introduce a new reinforcement learning principle that approximates the Bellman equations by enforcing their validity only along a test function space. We exploit this principle to derive confidence intervals for off-policy evaluation, as well as to optimize over policies within a prescribed policy class.
  arXiv  Detail & Related papers  (2022-03-24T01:04:17Z)
• A Reinforcement Learning Approach to the Stochastic Cutting Stock Problem [0.0]
  We propose a formulation of the cutting stock problem as a discounted infinite-horizon decision process. An optimal solution corresponds to a policy that associates each state with a decision and minimizes the expected total cost.
  arXiv  Detail & Related papers  (2021-09-20T14:47:54Z)
• An Offline Risk-aware Policy Selection Method for Bayesian Markov Decision Processes [0.0]
  Exploitation vs Caution (EvC) is a paradigm that elegantly incorporates model uncertainty abiding by the Bayesian formalism. We validate EvC with state-of-the-art approaches in different discrete, yet simple, environments offering a fair variety of MDP classes. In the tested scenarios EvC manages to select robust policies and hence stands out as a useful tool for practitioners.
  arXiv  Detail & Related papers  (2021-05-27T20:12:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.