mlsanityData to 7 Oct 2026

Fast active learning for pure exploration in reinforcement learning

arXiv 2007.13442 ↗First posted 27 Jul 2020cs.LG stat.MLcited by 92

Not on the map. Why?

Abstract (arXiv)

Realistic environments often provide agents with very limited feedback. When the environment is initially unknown, the feedback, in the beginning, can be completely absent, and the agents may first choose to devote all their effort on exploring efficiently. The exploration remains a challenge while it has been addressed with many hand-tuned heuristics with different levels of generality on one side, and a few theoretically-backed exploration strategies on the other. Many of them are incarnated by intrinsic motivation and in particular explorations bonuses. A common rule of thumb for exploration bonuses is to use 1/√n bonus that is added to the empirical estimates of the reward, where n is a number of times this particular state (or a state-action pair) was visited. We show that, surprisingly, for a pure-exploration objective of reward-free exploration, bonuses that scale with 1/n bring faster learning rates, improving the known upper bounds with respect to the dependence on the horizon H. Furthermore, we show that with an improved analysis of the stopping time, we can improve by a factor H the sample complexity in the best-policy identification setting, which is another pure-exploration objective, where the environment provides rewards but the agent is not penalized for its behavior during the exploration phase.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 17; 2023: 26; 2024: 15; 2025: 9; 2026: 12.

92 papers.

Sort:

By area:

  1. 2022Exploration in Deep Reinforcement Learning: A Surveycited by 158
  2. 2022BYOL-Explore: Exploration by Bootstrapped Predictioncited by 71
  3. 2024A Survey on Deep Active Learning: Recent Advances and New Frontierscited by 53
  4. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  5. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  6. 2023DrM: Mastering Visual Reinforcement Learning through Dormant Ratio Minimizationcited by 45
  7. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  8. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  9. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  10. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  11. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  12. 2023Active learning for data streams: a surveycited by 29
38 more
  1. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  2. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  3. 2022Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and Worst Pathcited by 21
  4. 2023Towards Theoretical Understanding of Inverse Reinforcement Learningcited by 21
  5. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  6. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  7. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  8. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  9. 2023Provably Efficient Adversarial Imitation Learning with Unknown Transitionscited by 16
  10. 2021Task-Optimal Exploration in Linear Dynamical Systemscited by 15
  11. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  12. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  13. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  14. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  15. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  16. 2024Offline Multitask Representation Learning for Reinforcement Learningcited by 14
  17. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
  18. 2022Understanding Adversarial Imitation Learning in Small Sample Regime: A Stage-coupled Analysiscited by 13
  19. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  20. 2023Learning to Make Adherence-Aware Advicecited by 13
  21. 2024How Can LLM Guide RL? A Value-Based Approachcited by 13
  22. 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalizationcited by 12
  23. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  24. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
  25. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 10
  26. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  27. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
  28. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  29. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  30. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  31. 2025SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfercited by 8
  32. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  33. 2023Towards Instance-Optimality in Online PAC Reinforcement Learningcited by 7
  34. 2023Concentration Bounds for Discrete Distribution Estimation in KL Divergencecited by 6
  35. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  36. 2022Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approachcited by 5
  37. 2022Cell-Free Latent Go-Explorecited by 5
  38. 2023Active Sensing with Predictive Coding and Uncertainty Minimizationcited by 5

50 most cited of 92 All 92 (JSON)