# Adaptive Reward-Free Exploration

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

## Key facts

- Cited by 77 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2020.

## Built on by (most cited first, 30 of 77)

- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [BYOL-Explore: Exploration by Bootstrapped Prediction](https://mlsanity.com/paper/2206.08332/) (2022)
- [DrM: Mastering Visual Reinforcement Learning through Dormant Ratio Minimization](https://mlsanity.com/paper/2310.19668/) (2023)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [MADE: Exploration via Maximizing Deviation from Explored Regions](https://mlsanity.com/paper/2106.10268/) (2021)
- [Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost](https://mlsanity.com/paper/2202.06385/) (2022)
- [Optimistic Active Exploration of Dynamical Systems](https://mlsanity.com/paper/2306.12371/) (2023)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2110.06394/) (2021)
- [On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL](https://mlsanity.com/paper/2206.10770/) (2022)
- [Active Exploration for Inverse Reinforcement Learning](https://mlsanity.com/paper/2207.08645/) (2022)
- [The Challenges of Exploration for Offline Reinforcement Learning](https://mlsanity.com/paper/2201.11861/) (2022)
- [Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information](https://mlsanity.com/paper/2206.04282/) (2022)
- [Revisiting Simple Regret: Fast Rates for Returning a Good Arm](https://mlsanity.com/paper/2210.16913/) (2022)
- [Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Path](https://mlsanity.com/paper/2206.02678/) (2022)
- [Towards Theoretical Understanding of Inverse Reinforcement Learning](https://mlsanity.com/paper/2304.12966/) (2023)
- [Replicable Reinforcement Learning](https://mlsanity.com/paper/2305.15284/) (2023)
- [Improved Corruption Robust Algorithms for Episodic Reinforcement Learning](https://mlsanity.com/paper/2102.06875/) (2021)
- [On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2110.09771/) (2021)
- [Near-Optimal Collaborative Learning in Bandits](https://mlsanity.com/paper/2206.00121/) (2022)
- [Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs](https://mlsanity.com/paper/2203.09251/) (2022)
- [Optimistic PAC Reinforcement Learning: the Instance-Dependent View](https://mlsanity.com/paper/2207.05852/) (2022)
- [Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning](https://mlsanity.com/paper/2305.10282/) (2023)
- [Provably Efficient Adversarial Imitation Learning with Unknown Transitions](https://mlsanity.com/paper/2306.06563/) (2023)
- [ACE : Off-Policy Actor-Critic with Causality-Aware Entropy Regularization](https://mlsanity.com/paper/2402.14528/) (2024)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)
- [Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning](https://mlsanity.com/paper/2304.08944/) (2023)
- [Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settings](https://mlsanity.com/paper/2105.06029/) (2021)
- [Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solver](https://mlsanity.com/paper/2110.03244/) (2021)

## Abstract (arXiv)

Reward-free exploration is a reinforcement learning setting studied by Jin et al. (2020), who address it by running several algorithms with regret guarantees in parallel. In our work, we instead give a more natural adaptive approach for reward-free exploration which directly reduces upper bounds on the maximum MDP estimation error. We show that, interestingly, our reward-free UCRL algorithm can be seen as a variant of an algorithm of Fiechter from 1994, originally proposed for a different objective that we call best-policy identification. We prove that RF-UCRL needs of order (SAH4/varepsilon2)(log(1/δ) + S) episodes to output, with probability 1-δ, an varepsilon-approximation of the optimal policy for any reward function. This bound improves over existing sample-complexity bounds in both the small varepsilon and the small δ regimes. We further investigate the relative complexities of reward-free exploration and best-policy identification.