# Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality

arXiv: https://arxiv.org/abs/2605.24740 · HTML: https://mlsanity.com/paper/2605.24740/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 15 of 15)

- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [End-to-End Training of Deep Visuomotor Policies](https://mlsanity.com/paper/1504.00702/) (2015)
- [Reinforcement Learning With Temporal Logic Rewards](https://mlsanity.com/paper/1612.03471/) (2016)
- [Reinforcement Learning for Temporal Logic Control Synthesis with Probabilistic Satisfaction Guarantees](https://mlsanity.com/paper/1909.05304/) (2019)
- [Omega-Regular Objectives in Model-Free Reinforcement Learning](https://mlsanity.com/paper/1810.00950/) (2018)
- [Foundations for Restraining Bolts: Reinforcement Learning with LTLf/LDLf restraining specifications](https://mlsanity.com/paper/1807.06333/) (2018)
- [Q-Learning for Robust Satisfaction of Signal Temporal Logic Specifications](https://mlsanity.com/paper/1609.07409/) (2016)
- [Environment-Independent Task Specifications via GLTL](https://mlsanity.com/paper/1704.04341/) (2017)
- [Compositional Reinforcement Learning from Logical Specifications](https://mlsanity.com/paper/2106.13906/) (2021)
- [Logically-Constrained Reinforcement Learning](https://mlsanity.com/paper/1801.08099/) (2018)
- [PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games](https://mlsanity.com/paper/1905.04403/) (2019)
- [Transfer of Temporal Logic Formulas in Reinforcement Learning](https://mlsanity.com/paper/1909.04256/) (2019)
- [Modular Deep Reinforcement Learning with Temporal Logic Specifications](https://mlsanity.com/paper/1909.11591/) (2019)
- [Reinforcement Learning with LTL and ω-Regular Objectives via Optimality-Preserving Translation to Average Rewards](https://mlsanity.com/paper/2410.12175/) (2024)
- [A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs](https://mlsanity.com/paper/2310.12248/) (2023)

## 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.