mlsanityData to 7 Oct 2026

Gap-Dependent Unsupervised Exploration for Reinforcement Learning

arXiv 2108.05439 ↗First posted 11 Aug 2021cs.LGcited by 10

Not on the map. Why?

Abstract (arXiv)

For the problem of task-agnostic reinforcement learning (RL), an agent first collects samples from an unknown environment without the supervision of reward signals, then is revealed with a reward and is asked to compute a corresponding near-optimal policy. Existing approaches mainly concern the worst-case scenarios, in which no structural information of the reward/transition-dynamics is utilized. Therefore the best sample upper bound is proptowidetildeO(1/ε2), where ε>0 is the target accuracy of the obtained policy, and can be overly pessimistic. To tackle this issue, we provide an efficient algorithm that utilizes a gap parameter, ρ>0, to reduce the amount of exploration. In particular, for an unknown finite-horizon Markov decision process, the algorithm takes only widetildeO (1/ε · (H3SA / ρ + H4 S2 A) ) episodes of exploration, and is able to obtain an ε-optimal policy for a post-revealed reward with sub-optimality gap at least ρ, where S is the number of states, A is the number of actions, and H is the length of the horizon, obtaining a nearly quadratic saving in terms of ε. We show that, information-theoretically, this bound is nearly tight for ρ < Theta(1/(HS)) and H>1. We further show that proptowidetildeO(1) sample bound is possible for H=1 (i.e., multi-armed bandit) or with a sampling simulator, establishing a stark separation between those settings and the RL setting.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 32 of its 45 references that are in the map. First posted on arXiv 11 Aug 2021.

Builds on

32 of 45 references.

References · 32

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2018Is Q-learning Provably Efficient?cited by 485
  3. 2016Deep Visual Foresight for Planning Robot Motioncited by 276
  4. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  5. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  6. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  7. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  8. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  9. 2018Learning by Playing - Solving Sparse Reward Tasks from Scratchcited by 164
  10. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 105
  11. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 104
  12. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
20 more
  1. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  2. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  3. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  4. 2020Adaptive Reward-Free Explorationcited by 77
  5. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  6. 2020Q-learning with Logarithmic Regretcited by 59
  7. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 56
  8. 2021Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrapcited by 48
  9. 2021Beyond No Regret: Instance-Dependent PAC Reinforcement Learningcited by 41
  10. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  11. 2018Exploration in Structured Reinforcement Learningcited by 34
  12. 2019Improvisation through Physical Understanding: Using Novel Objects as Tools with Visual Foresightcited by 34
  13. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  14. 2020Planning in Markov Decision Processes with Gap-Dependent Sample Complexitycited by 34
  15. 2018Few-Shot Goal Inference for Visuomotor Learning and Planningcited by 30
  16. 2021Navigating to the Best Policy in Markov Decision Processescited by 28
  17. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  18. 2017Randomized Linear Programming Solves the Discounted Markov Decision Problem In Nearly-Linear (Sometimes Sublinear) Running Timecited by 11
  19. 2020Accommodating Picky Customers: Regret Bound and Exploration Complexity for Multi-Objective Reinforcement Learningcited by 11
  20. 2020Lenient Regret for Multi-Armed Banditscited by 8

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 4; 2023: 3; 2024: 0; 2025: 0; 2026: 1.

10 papers.

  1. 2023Provable Offline Preference-Based Reinforcement Learningcited by 55
  2. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  3. 2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
  4. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  5. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  6. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 13
  7. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  8. 2023Offline Minimax Soft-Q-learning Under Realizability and Partial Coveragecited by 9
  9. 2021Adaptive Multi-Goal Explorationcited by 4
  10. 2026A Reward-Free Viewpoint on Multi-Objective Reinforcement Learningcited by 2