mlsanityData to 7 Oct 2026

Reward-Free Exploration for Reinforcement Learning

arXiv 2002.02794 ↗First posted 7 Feb 2020cs.LG stat.MLcited by 177

Not on the map. Why?

Cited by 21 in Offline RL and imitation learning from data, but placed by its own abstract, which didn’t fit.

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 29; 2022: 39; 2023: 41; 2024: 33; 2025: 12; 2026: 23.

177 papers.

Sort:

By area:

  1. 2024DeepSeek-Prover-V1.5: Harnessing Proof Assistant Feedback for Reinforcement Learning and Monte-Carlo Tree Searchcited by 189
  2. 2021Learning One Representation to Optimize All Rewardscited by 110
  3. 2023Is RLHF More Difficult than Standard RL?cited by 96
  4. 2022Don't Change the Algorithm, Change the Data: Exploratory Data for Offline Reinforcement Learningcited by 93
  5. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  6. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  7. 2022BYOL-Explore: Exploration by Bootstrapped Predictioncited by 71
  8. 2021Learning Successor States and Goal-Dependent Values: A Mathematical Viewpointcited by 67
  9. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  10. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  11. 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
  12. 2023DrM: Mastering Visual Reinforcement Learning through Dormant Ratio Minimizationcited by 45
38 more
  1. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 44
  2. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  3. 2021Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Gamescited by 40
  4. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  5. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  6. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  7. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  8. 2021Learning more skills through optimistic explorationcited by 37
  9. 2022The Importance of Non-Markovianity in Maximum State Entropy Explorationcited by 35
  10. 2021Geometric Entropic Explorationcited by 32
  11. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  12. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  13. 2023Fast Rates for Maximum Entropy Explorationcited by 32
  14. 2023Optimistic Active Exploration of Dynamical Systemscited by 32
  15. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  16. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  17. 2021A Simple Reward-free Approach to Constrained Reinforcement Learningcited by 28
  18. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  19. 2022Active Exploration for Inverse Reinforcement Learningcited by 27
  20. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  21. 2021Reward Poisoning in Reinforcement Learning: Attacks Against Unknown Learners in Unknown Environmentscited by 26
  22. 2022The Challenges of Exploration for Offline Reinforcement Learningcited by 26
  23. 2023Provable Reward-Agnostic Preference-Based Reinforcement Learningcited by 25
  24. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  25. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  26. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  27. 2023Towards Theoretical Understanding of Inverse Reinforcement Learningcited by 21
  28. 2023Replicable Reinforcement Learningcited by 21
  29. 2023Zero-Shot Reinforcement Learning from Low Quality Datacited by 21
  30. 2023Accelerating Exploration with Unlabeled Prior Datacited by 21
  31. 2021Provably Efficient Algorithms for Multi-Objective Competitive RLcited by 20
  32. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  33. 2024A Single Goal is All You Need: Skills and Exploration Emerge from Contrastive RL without Rewards, Demonstrations, or Subgoalscited by 20
  34. 2022Offline Reinforcement Learning with Differential Privacycited by 19
  35. 2021Design of Experiments for Stochastic Contextual Linear Banditscited by 18
  36. 2021Unsupervised Reinforcement Learning in Multiple Environmentscited by 17
  37. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  38. 2023Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both Worlds in Stochastic and Deterministic Environmentscited by 17

50 most cited of 177 All 177 (JSON)