acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 , GPI only requires identifying a policy with expected reward in an episode at least 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 , 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 in our upper bound is , where is the episode length and 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 term. Numerical experiments further validate the efficiency of our approach.

Primary area:
learning theory
Keywords:
Pure Exploration, Good Policy Identification

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_gGn2OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the Good Policy Identification (GPI) problem, different from the mostly studied Best Policy Identification problem in the pure-exploration setting, which tries to identify a near-optimal policy with high probability; it tries to find policies that have an expected return larger than a predefined threshold with high probability. This problem can be considered an extension of 1-identification in the multi-armed bandit problem to a multi-step RL environment. There are 2 cases depending on the realizability of the policy under the predefined threshold and RL task. The authors introduce the algorithm BEE-GPI, which uses a distribution-robust Bellman operator to build upper and lower value confidence bounds. The authors provide sample complexity upper bounds for both of these cases and also provide corresponding sample complexity lower bounds for both cases to show the near-optimality of the sample complexity. In the experimental section, they provide a sample-size analysis in the tabular RL setting compared with BPI algorithms with modified targets.

Critical strengths
  1. The paper establishes finite sample-complexity upper bounds for both positive and negative instances and constructs hard instances yielding corresponding lower bounds. The proofs appear sound and solid.

  2. The experiments demonstrate empirical advantages over BPI algorithms adapted to the GPI task on the evaluated tabular environments.

Critical weaknesses
  1. The author claims that for traditional BPI, the hardness comes from the optimal value function $ V^* (s_0)$ being unknown. But for other BPI algorithms, V∗(s0)V^*(s_0) is not required; it is commonly approximated with a confidence upper bound. From my perspective, the relative tolerance ϵ\epsilon requires less prior knowledge than the reward threshold μ0\mu_0. The comparison needs more justification.

  2. Compared with "1-identification" in bandit problems, the algorithm design and analysis methods seem to largely follow from Z. Li and W. C. Cheung, ``Near Optimal Non-asymptotic Sample Complexity of 1-Identification,'' ICML, 2025. Even though the extension from bandit to a multistep environment is not trivial, the methodological novelty requires further clarification and justification.

Questions for authors

The BPI and GPI problems are equivalent when we choose μ0=V0∗(s0)−ϵ\mu_0 = V^*_0(s_0) - \epsilon on a positive instance; the sample complexity results need further comparison with existing BPI results.

2 comments
AuthorsOpenReview ↗

Follow-up on Our Rebuttal

Thank you for your feedback. As the discussion period nears its end, we would like to check whether our rebuttal has addressed your concerns. We are happy to answer any further questions.

I thank the authors for their response and maintain my positive score.

Reviewer_78e9OpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper investigates the problem of GPI in episodic fixed horizon RL. They propose BEE-GPI, a δ\delta-PAC algorithm in this setting and provides guarantees on the expected sample complexity. Experimental results compare the proposed approach to relevant exploration baselines adapted to the GPI task.

Critical strengths
  1. The paper investigates an interesting and practically relevant problem which is currently under-explored in the RL identification literature
  2. The mathematical analysis is sound and complete and the theoretical guarantees are interesting.
Critical weaknesses
  1. Lack of a general sample complexity lower bound for the proposed problem.
  2. Limited experimental evaluation.
Questions for authors
  1. The lower bounds presented in Thms. 4 and 5 are restricted to specific MDP constructions. To the best of my knowledge, the literature currently lacks a general instance dependent sample complexity lower bound for this setting. Could you include a derivation of such lower bound?

  2. One of the main theoretical contribution is the independence of the leading term in the expected sample complexity bound of the state and action space. However the experiments do not currently support this claim. Could you provide an empirical validation of this claim by e.g., increasing the MDP dimension and varying the confidece parameter?

2 comments
AuthorsOpenReview ↗

Follow-up on Our Rebuttal

Thank you again for your time and thoughtful feedback. As the discussion period approaching to its end, we would like to check whether our rebuttal has addressed your concerns. We are happy to answer any further questions.

Thank you for the additional details and discussion. I increased my score.

Reviewer_kWSJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies Good Policy Identification in episodic reinforcement learning under the fixed-confidence setting. The main different of the studied setting is that it aims to identify a policy whose expected return meets a given threshold μ0\mu_0, or return None if no qualified policy exists with probability at least 1−δ1-\delta. This paper focus on minimizing the expected number of sampled episodes. In this work, authors propose BEE-GPI, which searches for candidate policies using a BPI-UCRL subroutine with an early-stopping mechanism and then verifies them with high confidence using independent samples. The paper provides upper bounds on the expected sample complexity for both positive and negative instances. The authors further construct hard instances to derive sample complexity lower bounds and compare the proposed method with BPI-UCRL and BPI-UCBVI through numerical experiments in chain and grid-world environments.

Critical strengths
  • The Problem is well motivated and important for real scenarios.
  • The complexity analysis highlights a meaningful structural advantage: the upper bound of the regular case will separate the high confidence verification cost of non-explicit dependence S,AS,A from the search cost of the scale of the dependent problem, which provides a clear explanation for understanding the potential sample efficiency advantages of Good Policy Identification over the standard Best Policy Identification reductive.
Critical weaknesses

The technical distinction from the most related work has not been fully elaborated. Although the authors have cited Li & Cheung (2025) (with algorithm SEE), the related work section mainly emphasizes that their research focuses on the bandit scenario and does not specifically discuss the algorithmic relationship between SEE and BEE-GPI. SEE has adopted low-confidence candidate search, independent high-confidence verification, and a design that ensures a margin of the candidate threshold. Therefore, I hope the author to further explain: what new technical difficulties are brought by extending this framework to episodic MDP, and what are the key new contributions of the early stopping mechanism and sample complexity analysis in this paper compared to SEE. The current statement makes it difficult to fully assess the technical novelty of BEE-GPI.

Questions for authors

See Weakness

1 comment
AuthorsOpenReview ↗

Follow-up on Our Rebuttal

Thank you again for your time and thoughtful feedback. As the discussion period approaching to its end, we would like to check whether our rebuttal has addressed your concerns. We are happy to answer any further questions.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal

As the rebuttal phase comes to a close, we sincerely thank all reviewers for their time and constructive feedback. We are grateful that Reviewers gGn2 and 78e9 have acknowledged our responses. Below are the main points.

  1. Novelty relative to SEE (Reviewers kWSJ and gGn2). This was Reviewer kWSJ's single question, and Reviewer gGn2 raised it as well. We illustrated the difference from four perspectives:

    • SEE's per-arm oracles become exponentially costly on MDPs, if taking every policy as an arm.
    • BEE-GPI instead builds one confidence region around a shared transition estimate, with new stopping rules that make it δ\delta-PAC. Although this region differs from SEE's per-arm intervals, our design and analysis let it carry over across phases, which preserves the history recycling property.
    • Our new analysis gives polynomial best-of-both-worlds guarantees on both positive and negative instances (Theorems 2–3). Before this work, it was unclear whether this was achievable.
    • The new stopping rule removes the need for SEE's temporary container.
  2. Literature on BPI (Reviewer 78e9, Q1). We expanded our review of the Best Policy Identification literature. We see instance-dependent upper and lower bounds as a promising direction for future work.

  3. Additional experiments (Reviewer 78e9, Q2). We ran new experiments that confirm the coefficient of log⁡(1/δ)\log(1/\delta) does not depend on SS and AA.

  4. BPI vs. GPI (Reviewer gGn2). We explained how BPI and Good Policy Identification (GPI) differ as problems, and showed that reducing GPI to BPI is strictly suboptimal.

We will add all of these points to the revised paper. We are happy to answer any further questions while time permits.

Reference

Li & Cheung (2025). Near Optimal Non-asymptotic Sample Complexity of 1-Identification. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:34144-34184 Available from https://proceedings.mlr.press/v267/li25f.html.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.