mlsanityData to 7 Oct 2026

Adaptive Reward-Free Exploration

arXiv 2006.06294 ↗First posted 11 Jun 2020cs.LG stat.MLcited by 77

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 17; 2023: 18; 2024: 11; 2025: 6; 2026: 11.

77 papers.

Sort:

By area:

  1. 2021Reward is enough for convex MDPscited by 82
  2. 2022BYOL-Explore: Exploration by Bootstrapped Predictioncited by 71
  3. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  4. 2023DrM: Mastering Visual Reinforcement Learning through Dormant Ratio Minimizationcited by 45
  5. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  6. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  7. 2023Optimistic Active Exploration of Dynamical Systemscited by 32
  8. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  9. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  10. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  11. 2022Active Exploration for Inverse Reinforcement Learningcited by 27
  12. 2022The Challenges of Exploration for Offline Reinforcement Learningcited by 26
38 more
  1. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  2. 2022Revisiting Simple Regret: Fast Rates for Returning a Good Armcited by 25
  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. 2023Replicable Reinforcement Learningcited by 21
  6. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
  7. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  8. 2022Near-Optimal Collaborative Learning in Banditscited by 18
  9. 2022Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPscited by 17
  10. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  11. 2023Provably Efficient Adversarial Imitation Learning with Unknown Transitionscited by 16
  12. 2024ACE : Off-Policy Actor-Critic with Causality-Aware Entropy Regularizationcited by 16
  13. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  14. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  15. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 15
  16. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14
  17. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  18. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 14
  19. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
  20. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  21. 2023Learning to Make Adherence-Aware Advicecited by 13
  22. 2022Provably Efficient Causal Model-Based Reinforcement Learning for Systematic Generalizationcited by 12
  23. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  24. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  25. 2021Gap-Dependent Unsupervised Exploration for Reinforcement Learningcited by 10
  26. 2023Provably Safe Reinforcement Learning with Step-wise Violation Constraintscited by 10
  27. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 10
  28. 2022Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RLcited by 9
  29. 2023Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learningcited by 9
  30. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  31. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited 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. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  35. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  36. 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
  37. 2024How does Inverse RL Scale to Large State Spaces? A Provably Efficient Approachcited by 5
  38. 2024Uncertainty-Aware Reward-Free Exploration with General Function Approximationcited by 5

50 most cited of 77 All 77 (JSON)