- 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
-
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.
-
The experiments demonstrate empirical advantages over BPI algorithms adapted to the GPI task on the evaluated tabular environments.
Critical weaknesses
-
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, is not required; it is commonly approximated with a confidence upper bound. From my perspective, the relative tolerance requires less prior knowledge than the reward threshold . The comparison needs more justification.
-
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 on a positive instance; the sample complexity results need further comparison with existing BPI results.
2 comments
I thank the authors for their response and maintain my positive score.
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.