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

arXiv: https://arxiv.org/abs/2605.23182 · HTML: https://mlsanity.com/paper/2605.23182/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 18 of 18)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Pure Exploration with Multiple Correct Answers](https://mlsanity.com/paper/1902.03475/) (2019)
- [Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes](https://mlsanity.com/paper/1710.09988/) (2017)
- [The True Sample Complexity of Identifying Good Arms](https://mlsanity.com/paper/1906.06594/) (2019)
- [Good Arm Identification via Bandit Feedback](https://mlsanity.com/paper/1710.06360/) (2017)
- [Navigating to the Best Policy in Markov Decision Processes](https://mlsanity.com/paper/2106.02847/) (2021)
- [Adaptive Sampling for Best Policy Identification in Markov Decision Processes](https://mlsanity.com/paper/2009.13405/) (2020)
- [Optimistic PAC Reinforcement Learning: the Instance-Dependent View](https://mlsanity.com/paper/2207.05852/) (2022)
- [An Anytime Algorithm for Good Arm Identification](https://mlsanity.com/paper/2310.10359/) (2023)
- [Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning](https://mlsanity.com/paper/2406.06856/) (2024)
- [Near Optimal Non-asymptotic Sample Complexity of 1-Identification](https://mlsanity.com/paper/2506.06978/) (2025)
- [Closing the Gap on the Sample Complexity of 1-Identification](https://mlsanity.com/paper/2601.15620/) (2026)

## 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.