mlsanityData to 14 Oct 2026

Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality

arXiv 2605.24740 ↗First posted 23 May 2026cs.LG cs.GTcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Reinforcement learning (RL) for reachability specifications is fundamental in sequential decision-making, yet theoretical guarantees remain less explored. A recent work achieves asymptotic convergence to optimal policies. However, this approach provides limited insight into convergence dynamics. In this work, we present an alternative approach that provides deeper theoretical insights into convergence. Our approach builds on PAC learning with assumptions. PAC learning guarantees near-optimal policies with high confidence in finite time but requires knowing internal MDP parameters like minimum transition probability. We argue that while these parameters are unknown in RL, they can be iteratively refined and estimated with increasing accuracy. By iteratively satisfying PAC conditions, we show that exact optimality can be achieved in the limit. Empirical evaluations on standard benchmarks validate our theoretical insights into convergence dynamics.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 15 of its 45 references that are in the map. First posted on arXiv 23 May 2026.

Builds on

15 of 45 references.

References · 15

  1. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,809
  2. 2015End-to-End Training of Deep Visuomotor Policiescited by 875
  3. 2016Reinforcement Learning With Temporal Logic Rewardscited by 117
  4. 2019Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guaranteescited by 77
  5. 2018Omega-Regular Objectives in Model-Free Reinforcement Learningcited by 75
  6. 2018Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specificationscited by 72
  7. 2016Q-Learning for Robust Satisfaction of Signal Temporal Logic Specificationscited by 67
  8. 2017Environment-Independent Task Specifications via GLTLcited by 67
  9. 2021Compositional Reinforcement Learning from Logical Specificationscited by 67
  10. 2018Logically-Constrained Reinforcement Learningcited by 51
  11. 2019PAC Statistical Model Checking for Markov Decision Processes and Stochastic Gamescited by 32
  12. 2019Transfer of Temporal Logic Formulas in Reinforcement Learningcited by 31
3 more
  1. 2019Modular Deep Reinforcement Learning with Temporal Logic Specificationscited by 25
  2. 2024Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewardscited by 14
  3. 2023A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPscited by 13

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Q-Learning for Reachability in MEC-Free MDPs
  2. 2025PAC-Bayesian Reinforcement Learning Trains Generalizable Policies
  3. 2026PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure
  4. 2026Reachability-Aware Diffusion Policy Optimization
  5. 2024Statistical Guarantees for Lifelong Reinforcement Learning using PAC-Bayes Theory
  6. 2025Polynomial-Time Approximability of Constrained Reinforcement Learning
  7. 2026Certifying Almost-Sure Reachability in Unknown MDPs
  8. 2026Beyond Hard Constraints: Budget-Conditioned Reachability For Safe Offline Reinforcement Learning