# Provably Safe PAC-MDP Exploration Using Analogies

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jul 2020.

## Built on by (most cited first, 9 of 9)

- [Safe Reinforcement Learning by Imagining the Near Future](https://mlsanity.com/paper/2202.07789/) (2022)
- [Learning Barrier Certificates: Towards Safe Reinforcement Learning with Zero Training-time Violations](https://mlsanity.com/paper/2108.01846/) (2021)
- [Provable Safe Reinforcement Learning with Binary Feedback](https://mlsanity.com/paper/2210.14492/) (2022)
- [Anytime-Constrained Reinforcement Learning](https://mlsanity.com/paper/2311.05511/) (2023)
- [Deterministic Policies for Constrained Reinforcement Learning in Polynomial Time](https://mlsanity.com/paper/2405.14183/) (2024)
- [Long-term Safe Reinforcement Learning with Binary Feedback](https://mlsanity.com/paper/2401.03786/) (2024)
- [Anytime-Constrained Equilibria in Polynomial Time](https://mlsanity.com/paper/2410.23637/) (2024)
- [Polynomial-Time Approximability of Constrained Reinforcement Learning](https://mlsanity.com/paper/2502.07764/) (2025)
- [Safe Sequential Optimization for Switching Environments](https://mlsanity.com/paper/2311.02119/) (2023)

## Abstract (arXiv)

A key challenge in applying reinforcement learning to safety-critical domains is understanding how to balance exploration (needed to attain good performance on the task) with safety (needed to avoid catastrophic failure). Although a growing line of work in reinforcement learning has investigated this area of "safe exploration," most existing techniques either 1) do not guarantee safety during the actual exploration process; and/or 2) limit the problem to a priori known and/or deterministic transition dynamics with strong smoothness assumptions. Addressing this gap, we propose Analogous Safe-state Exploration (ASE), an algorithm for provably safe exploration in MDPs with unknown, stochastic dynamics. Our method exploits analogies between state-action pairs to safely learn a near-optimal policy in a PAC-MDP sense. Additionally, ASE also guides exploration towards the most task-relevant states, which empirically results in significant improvements in terms of sample efficiency, when compared to existing methods.