# Reinforcement Learning with Probabilistically Complete Exploration

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jan 2020.

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

- [R×R: Rapid eXploration for Reinforcement Learning via Sampling-based Reset Distributions and Imitation Pre-training](https://mlsanity.com/paper/2401.15484/) (2024)

## Abstract (arXiv)

Balancing exploration and exploitation remains a key challenge in reinforcement learning (RL). State-of-the-art RL algorithms suffer from high sample complexity, particularly in the sparse reward case, where they can do no better than to explore in all directions until the first positive rewards are found. To mitigate this, we propose Rapidly Randomly-exploring Reinforcement Learning (R3L). We formulate exploration as a search problem and leverage widely-used planning algorithms such as Rapidly-exploring Random Tree (RRT) to find initial solutions. These solutions are used as demonstrations to initialize a policy, then refined by a generic RL algorithm, leading to faster and more stable convergence. We provide theoretical guarantees of R3L exploration finding successful solutions, as well as bounds for its sampling complexity. We experimentally demonstrate the method outperforms classic and intrinsic exploration techniques, requiring only a fraction of exploration samples and achieving better asymptotic performance.