mlsanityData to 14 Oct 2026

Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback

arXiv 2605.23182 ↗First posted 22 May 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

Pure exploration in episodic Reinforcement Learning has primarily focused on Best Policy Identification (BPI), which seeks to identify a (near)-optimal policy with high confidence. Motivated by practical settings where a ``good enough'' policy suffices, we study an alternate objective of Good Policy Identification (GPI). For a given reward threshold μ0, GPI only requires identifying a policy with expected reward in an episode at least μ0 if such a policy exists (positive instance), or declaring None if no such policy exists (negative instance). We formalize GPI under the fixed-confidence setting. We require the output to be correct with probability ≥ 1-δ, and seek to minimize the expected sample complexity, which is the expected number of episodes explored for the output. We propose a novel algorithm BEE-GPI, and derive theoretically-grounded upper bounds on its sample complexity for positive and negative instances. Notably, for positive instances, the coefficient of log 1/δ in our upper bound is O(H2/(V^* - μ0)2), where H is the episode length and V^* is the optimal expected reward in an episode. The coefficient does not depend on the action and state space sizes otherwise, in sharp contrast to the sample complexity in BPI. We further establish lower bound results to show the near-optimality of BEE-GPI and the necessity of the 1/(V^* -μ)2 term. Numerical experiments further validate the efficiency of our approach.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 18 of its 22 references that are in the map. First posted on arXiv 22 May 2026.

Builds on

18 of 22 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning11 Jun

Other references · 17

  1. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  2. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  3. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  4. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  5. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  6. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  7. 2020Adaptive Reward-Free Explorationcited by 77
  8. 2019Pure Exploration with Multiple Correct Answerscited by 64
  9. 2017Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processescited by 57
  10. 2019The True Sample Complexity of Identifying Good Armscited by 37
  11. 2017Good Arm Identification via Bandit Feedbackcited by 30
  12. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
5 more
  1. 2020Adaptive Sampling for Best Policy Identification in Markov Decision Processescited by 20
  2. 2022Optimistic PAC Reinforcement Learning: the Instance-Dependent Viewcited by 17
  3. 2023An Anytime Algorithm for Good Arm Identificationcited by 6
  4. 2025Near Optimal Non-asymptotic Sample Complexity of 1-Identificationcited by 1
  5. 2026Closing the Gap on the Sample Complexity of 1-Identificationcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
  2. 2026Tight Sample Complexity Bounds for Entropic Best Policy Identification
  3. 2024Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysis
  4. 2026Average-Reward Policy Identification from a Single Continuing Trajectory
  5. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
  6. 2024Beyond Optimism: Exploration With Partially Observable Rewards
  7. 2023More for Less: Safe Policy Improvement With Stronger Performance Guarantees
  8. 2024Model-Free Active Exploration in Reinforcement Learning