# Computationally efficient safe exploration in reinforcement learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Safe and constrained RL, one of 15 directions in Deep reinforcement learning methods.
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 19 Sep 2026.

## Placed in

- Deep reinforcement learning methods / [Safe and constrained RL](https://mlsanity.com/deeprl/safe-and-constrained-rl/)

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

- [Constrained Policy Optimization](https://mlsanity.com/paper/1705.10528/) (2017)
- [Safe Learning in Robotics: From Learning-Based Control to Safe Reinforcement Learning](https://mlsanity.com/paper/2108.06266/) (2021)
- [Safe Model-based Reinforcement Learning with Stability Guarantees](https://mlsanity.com/paper/1705.08551/) (2017)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [A Lyapunov-based Approach to Safe Reinforcement Learning](https://mlsanity.com/paper/1805.07708/) (2018)
- [Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator](https://mlsanity.com/paper/1801.05039/) (2018)
- [Safe Reinforcement Learning in Constrained Markov Decision Processes](https://mlsanity.com/paper/2008.06626/) (2020)
- [Safe Exploration in Finite Markov Decision Processes with Gaussian Processes](https://mlsanity.com/paper/1606.04753/) (2016)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Safe Exploration for Interactive Machine Learning](https://mlsanity.com/paper/1910.13726/) (2019)
- [Probabilistically Safe Robot Planning with Confidence-Based Human Predictions](https://mlsanity.com/paper/1806.00109/) (2018)
- [Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs](https://mlsanity.com/paper/2306.11700/) (2023)
- [On Safety in Safe Bayesian Optimization](https://mlsanity.com/paper/2403.12948/) (2024)
- [A safe exploration approach to constrained Markov decision processes](https://mlsanity.com/paper/2312.00561/) (2023)
- [Safe exploration in reproducing kernel Hilbert spaces](https://mlsanity.com/paper/2503.10352/) (2025)
- [A computationally lightweight safe learning algorithm](https://mlsanity.com/paper/2309.03672/) (2023)
- [Safety and optimality in learning-based control at low computational cost](https://mlsanity.com/paper/2505.08026/) (2025)
- [Computationally lightweight classifiers with frequentist bounds on predictions](https://mlsanity.com/paper/2603.22128/) (2026)
- [Safe learning-based control via function-based uncertainty quantification](https://mlsanity.com/paper/2604.01173/) (2026)

## Abstract (arXiv)

Reinforcement learning in real-life applications requires safety guarantees during exploration. Typical reinforcement learning algorithms do not provide such guarantees, and many modifications that do rely on Gaussian processes (GPs), which have a large computational cost. We propose a computationally lightweight algorithm based on the Nadaraya-Watson estimator that safely explores and optimizes constrained Markov decision processes (MDPs). Our algorithm, textscCoLSafe-MDP, uses an estimator that scales in constant-time with bounds on the estimates, a significant improvement from its GP-based counterparts that scale cubically with the number of data points. We then evaluate its performance in a grid-based environment and on observational Martian terrain data.