# Reward-Free Exploration for Reinforcement Learning

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

## Key facts

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

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

- [DeepSeek-Prover-V1.5: Harnessing Proof Assistant Feedback for Reinforcement Learning and Monte-Carlo Tree Search](https://mlsanity.com/paper/2408.08152/) (2024)
- [Learning One Representation to Optimize All Rewards](https://mlsanity.com/paper/2103.07945/) (2021)
- [Don't Change the Algorithm, Change the Data: Exploratory Data for Offline Reinforcement Learning](https://mlsanity.com/paper/2201.13425/) (2022)
- [Is RLHF More Difficult than Standard RL?](https://mlsanity.com/paper/2306.14111/) (2023)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [BYOL-Explore: Exploration by Bootstrapped Prediction](https://mlsanity.com/paper/2206.08332/) (2022)
- [Learning Successor States and Goal-Dependent Values: A Mathematical Viewpoint](https://mlsanity.com/paper/2101.07123/) (2021)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [The Complexity of Markov Equilibrium in Stochastic Games](https://mlsanity.com/paper/2204.03991/) (2022)
- [DrM: Mastering Visual Reinforcement Learning through Dormant Ratio Minimization](https://mlsanity.com/paper/2310.19668/) (2023)
- [Settling the Sample Complexity of Online Reinforcement Learning](https://mlsanity.com/paper/2307.13586/) (2023)
- [Beyond No Regret: Instance-Dependent PAC Reinforcement Learning](https://mlsanity.com/paper/2108.02717/) (2021)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [MADE: Exploration via Maximizing Deviation from Explored Regions](https://mlsanity.com/paper/2106.10268/) (2021)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [Learning more skills through optimistic exploration](https://mlsanity.com/paper/2107.14226/) (2021)
- [First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach](https://mlsanity.com/paper/2112.03432/) (2021)
- [Provable Benefits of Representational Transfer in Reinforcement Learning](https://mlsanity.com/paper/2205.14571/) (2022)
- [The Importance of Non-Markovianity in Maximum State Entropy Exploration](https://mlsanity.com/paper/2202.03060/) (2022)
- [Fast Rates for Maximum Entropy Exploration](https://mlsanity.com/paper/2303.08059/) (2023)
- [Geometric Entropic Exploration](https://mlsanity.com/paper/2101.02055/) (2021)
- [On the Theory of Reinforcement Learning with Once-per-Episode Feedback](https://mlsanity.com/paper/2105.14363/) (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)
- [A Simple Reward-free Approach to Constrained Reinforcement Learning](https://mlsanity.com/paper/2107.05216/) (2021)
- [Learning in Observable POMDPs, without Computationally Intractable Oracles](https://mlsanity.com/paper/2206.03446/) (2022)
- [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)

## Abstract (arXiv)

Exploration is widely regarded as one of the most challenging aspects of reinforcement learning (RL), with many naive approaches succumbing to exponential sample complexity. To isolate the challenges of exploration, we propose a new "reward-free RL" framework. In the exploration phase, the agent first collects trajectories from an MDP M without a pre-specified reward function. After exploration, it is tasked with computing near-optimal policies under for M for a collection of given reward functions. This framework is particularly suitable when there are many reward functions of interest, or when the reward function is shaped by an external agent to elicit desired behavior. We give an efficient algorithm that conducts tildeO(S2Apoly(H)/ε2) episodes of exploration and returns ε-suboptimal policies for an arbitrary number of reward functions. We achieve this by finding exploratory policies that visit each "significant" state with probability proportional to its maximum visitation probability under any possible policy. Moreover, our planning procedure can be instantiated by any black-box approximate planner, such as value iteration or natural policy gradient. We also give a nearly-matching Omega(S2AH2/ε2) lower bound, demonstrating the near-optimality of our algorithm in this setting.