{"id":"8c274698-9d2b-419d-937b-a6a2b31c24c8","arxiv_id":"2605.23182","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Introduces Good Policy Identification (GPI) and BEE-GPI algorithm whose sample complexity for positive instances has log(1/δ) coefficient O(H²/(V*−μ0)²) independent of state and action space sizes.","lead":"The paper formalizes Good Policy Identification (GPI) in episodic RL with bandit feedback as an alternative to finding the absolute best policy, proposing the BEE-GPI algorithm with sample complexity bounds. Practitioners may read it for more efficient exploration when only a sufficiently good policy is needed rather than the optimal one.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Claimed independence of log(1/δ) coefficient from |S| and |A| requires explicit confirmation that no policy-space factors enter the leading term in BEE-GPI analysis","rationale":"Reader correctly flags the standard episodic/bandit-feedback setting as the weakest assumption but does not isolate the size-independence claim as the load-bearing technical point. Because the full proof is referenced yet not reproduced here, the size-independence assertion remains the single most load-bearing unverified step; confirming or refuting it does not alter the current UNVERDICTED status.","tokens_in":1822,"tokens_out":392,"duration_ms":44875,"concrete_test":"Locate the theorem giving the positive-instance upper bound for BEE-GPI; extract the precise multiplier of log(1/δ) and verify whether it contains any explicit dependence on |S|, |A|, or quantities derived from them (e.g., covering numbers, number of candidate policies, or visitation terms).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that the high-probability term in the sample-complexity upper bound for positive instances scales as O(H²/(V*−μ₀)² log(1/δ)) with no additional |S| or |A| factors multiplying that coefficient. Under bandit feedback each episode returns only a scalar reward, so locating a policy whose value exceeds μ₀ still requires selecting among a policy class whose size grows with |S| and |A|. The provided lower bound only establishes necessity of the 1/(V*−μ₀)² factor; it does not rule out hidden |S|·|A| or |A|^H multipliers inside the log term or in the algorithm’s policy-selection subroutine. If any such factor appears in the proof of the upper bound, the “sharp contrast to BPI” statement fails.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.3","summary":"The paper introduces Good Policy Identification (GPI) as an alternative objective to Best Policy Identification (BPI) in episodic MDPs with bandit feedback. GPI requires identifying a policy whose expected episodic reward is at least a given threshold μ₀ (positive instance) or correctly declaring that no such policy exists (negative instance), under the fixed-confidence criterion that the output is correct with probability ≥1−δ. The authors propose the BEE-GPI algorithm, derive upper bounds on its expected sample complexity, and claim that for positive instances the leading coefficient of log(1/δ) is O(H²/(V*−μ₀)²) with no additional dependence on |S| or |A|. They also supply matching lower bounds establishing near-optimality of BEE-GPI and the necessity of the 1/(V*−μ₀)² factor, together with numerical experiments.","tokens_in":1996,"tokens_out":707,"duration_ms":19973,"significance":"If the stated upper-bound independence from state-action space sizes holds, the result supplies a practically useful relaxation of pure exploration whose sample complexity scales with the gap to a user-specified threshold rather than the full optimality gap. The lower-bound results add value by confirming that the gap dependence cannot be improved. The work therefore addresses a realistic regime in which identifying any sufficiently good policy is acceptable, potentially broadening the applicability of high-confidence exploration beyond the computationally prohibitive requirements of BPI.","major_comments":[{"comment":"Abstract (and the upper-bound analysis for positive instances): the claim that the coefficient of log(1/δ) is O(H²/(V*−μ₀)²) with no |S| or |A| factors is load-bearing for the asserted 'sharp contrast to BPI'. The lower bound only establishes necessity of the 1/(V*−μ₀)² term; the upper-bound proof for BEE-GPI must be checked to confirm that no policy-class covering factor (e.g., |A|^H or a covering number linear in |S|·|A|) multiplies the leading coefficient, given that each episode returns only a scalar reward.","section":"Abstract and upper-bound analysis"},{"comment":"The experimental section: without reported scaling plots or tables that vary |S| and |A| while holding H and (V*−μ₀) fixed, it is impossible to verify that the claimed space-size independence is observed in practice rather than masked by implementation details of the policy-selection subroutine.","section":"Numerical experiments"}],"minor_comments":[{"comment":"Clarify in the problem formulation whether μ₀ is treated as a known constant or must be estimated, and ensure the notation V* (optimal value) versus μ₀ (threshold) is used consistently in all theorems.","section":"Problem formulation"},{"comment":"The related-work discussion of BPI sample complexity should cite the specific bound (including its |S|·|A| dependence) that is being contrasted.","section":"Related work"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's central novelty rests on the proof that the leading coefficient truly lacks |S| and |A| factors; if that step is correct the contribution is substantial, but the current presentation leaves the key technical step uninspectable from the abstract alone."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their constructive comments, which help clarify the presentation of our results on Good Policy Identification. We address each major comment below.","responses":[{"response":"The upper-bound analysis for positive instances (detailed in the proof of the sample-complexity bound for BEE-GPI) proceeds by maintaining a candidate policy whose value is estimated directly from scalar episode returns. The selection rule and concentration arguments are constructed so that the leading log(1/δ) term depends only on H and the gap V*−μ₀; no explicit covering number over policies or states/actions enters the coefficient. The bandit-feedback setting is accounted for by using the total episodic reward as the sole observation, and the algorithm never enumerates or covers the full policy class. We are happy to expand the proof sketch with an explicit step-by-step accounting of all terms in a revision if the referee finds the current presentation insufficiently transparent.","revision_made":"partial","referee_comment":"[Abstract and upper-bound analysis] Abstract (and the upper-bound analysis for positive instances): the claim that the coefficient of log(1/δ) is O(H²/(V*−μ₀)²) with no |S| or |A| factors is load-bearing for the asserted 'sharp contrast to BPI'. The lower bound only establishes necessity of the 1/(V*−μ₀)² term; the upper-bound proof for BEE-GPI must be checked to confirm that no policy-class covering factor (e.g., |A|^H or a covering number linear in |S|·|A|) multiplies the leading coefficient, given that each episode returns only a scalar reward."},{"response":"We agree that explicit scaling experiments would provide stronger empirical support for the claimed independence. In the revised manuscript we will add tables and plots that systematically vary |S| and |A| while keeping H and the gap V*−μ₀ fixed, reporting wall-clock episodes required by BEE-GPI.","revision_made":"yes","referee_comment":"[Numerical experiments] The experimental section: without reported scaling plots or tables that vary |S| and |A| while holding H and (V*−μ₀) fixed, it is impossible to verify that the claimed space-size independence is observed in practice rather than masked by implementation details of the policy-selection subroutine."}],"tokens_in":1625,"tokens_out":512,"duration_ms":11685,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"This paper defines Good Policy Identification (GPI) as an alternative to Best Policy Identification. GPI requires returning a policy whose episode value meets or exceeds a given threshold μ₀ if one exists, or declaring none exists. The BEE-GPI algorithm is given with upper bounds on expected sample complexity under fixed confidence. For positive instances the coefficient on log(1/δ) is stated as O(H²/(V*−μ₀)²) with no further dependence on state or action space size. Lower bounds are also derived, and experiments are reported to support the approach. This formalization of GPI and the specific scaling claim are the new elements relative to prior BPI work. The lower-bound argument correctly isolates the necessity of the gap term. The motivation for a weaker objective that might scale better in large spaces is reasonable. The main soft spot is the independence claim itself. Bandit feedback returns only a scalar per episode, so any algorithm must still distinguish among policies whose number grows with |S| and |A|. The stress-test note correctly flags that the upper-bound proof must be checked to ensure no |S|·|A| or |A|^H factors enter the leading coefficient through the policy-selection step. Without the full derivations it is not possible to confirm the claim holds exactly as stated. The standard episodic MDP and independent-episode assumptions are used without issue. The work is aimed at researchers in RL pure exploration who want alternatives to BPI. A reader looking for new objectives with potentially better scaling will get value from the formalization and the gap dependence. It deserves a serious referee because the objective is cleanly motivated and the claimed improvement is concrete enough to be checked. I recommend sending it to peer review with a request that the authors clarify the bound derivation on the |S| and |A| independence.","headline":"The paper defines GPI as a relaxed pure-exploration goal and claims BEE-GPI achieves sample complexity whose log(1/δ) term scales only with H and the gap, independent of |S| and |A|.","tokens_in":2478,"tokens_out":456,"would_cite":false,"duration_ms":19241,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":{"model":"grok-4.3","evidence":[],"headline":"GPI sample-complexity analysis in episodic MDPs uses gap-dependent concentration bounds with no structural overlap to RS forcing chain","alignment":"orthogonal","rationale":"The paper's core contribution is an early-stopping optimistic BPI oracle (ES-BPI-UCRL) plus exploitation verification whose leading log(1/δ) term for positive instances scales as O(H²/(V*−μ₀)²) independent of |S|,|A|. This machinery relies on standard sub-Gaussian tail bounds, KL-ball confidence sets, and a fixed-confidence PAC guarantee; none of these invoke the reciprocal cost J, the golden-ratio fixed point, 8-tick periodicity, or any theorem in the RS forcing chain (reality_from_one_distinction, washburn_uniqueness_aczel, alexander_duality_circle_linking, etc.). The domain (tabular episodic RL pure exploration) lies outside the scope of the RS framework, which derives spacetime and constants from a single logical distinction with zero adjustable parameters.","tokens_in":73321,"confidence":"high","tokens_out":225,"duration_ms":6821,"cache_read_input_tokens":38528,"cache_creation_input_tokens":0},"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Identifying any policy above a reward threshold requires sample complexity independent of state and action space sizes in episodic RL.","keywords":["reinforcement learning","pure exploration","good policy identification","bandit feedback","episodic MDP","sample complexity","fixed confidence"],"falsifier":"An episodic MDP with a fixed positive gap V* - μ0 where every algorithm requires a number of episodes that grows with the number of states or actions.","tokens_in":2709,"feed_emoji":"🎯","tokens_out":452,"duration_ms":27419,"temperature":0.7,"pith_summary":"The paper introduces Good Policy Identification as a relaxed goal compared to Best Policy Identification in episodic reinforcement learning with bandit feedback. GPI requires finding a policy whose expected episode reward meets or exceeds a threshold μ0 if one exists, or correctly declaring that none does. The authors develop the BEE-GPI algorithm and show upper bounds where, for positive instances, the leading coefficient of log(1/δ) scales as O(H²/(V* - μ0)²) without additional dependence on the number of states or actions. Lower bounds establish that the gap dependence is necessary and that the algorithm is near-optimal for both positive and negative instances.","feed_headline":"GPI finds good policies with cost independent of state space size","feed_subtitle":"The log(1/δ) term scales only with horizon and reward gap, unlike best-policy identification.","key_machinery":"The BEE-GPI algorithm, which performs targeted exploration to certify existence or non-existence of a policy whose value meets the given threshold μ0.","core_discovery":"BEE-GPI solves the fixed-confidence Good Policy Identification problem and achieves expected sample complexity upper bounds in which the coefficient of log(1/δ) for positive instances is O(H²/(V* - μ0)²), independent of state and action space sizes, with matching lower bounds confirming the necessity of the gap term and the near-optimality of the algorithm.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["BEE-GPI finds good policies with sample cost independent of state space","GPI log term scales only with horizon and reward gap unlike BPI","Good policy identification complexity free of action state space sizes","BEE-GPI bounds GPI by H squared over gap squared without space sizes"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"Episodes are independent and the learner observes only the total reward at the end of each episode.","fun_headline_variants_meta":{"raw":{"variants":["BEE-GPI finds good policies with sample cost independent of state space","GPI log term scales only with horizon and reward gap unlike BPI","Good policy identification complexity free of action state space sizes","BEE-GPI bounds GPI by H squared over gap squared without space sizes"]},"model":"grok-4.3","cost_usd":0.007015,"raw_usage":{"total_tokens":3280,"prompt_tokens":733,"num_sources_used":0,"completion_tokens":67,"cost_in_usd_ticks":70149500,"prompt_tokens_details":{"text_tokens":733,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2480,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":733,"tokens_out":67,"duration_ms":14257,"temperature":1.0,"reasoning_tokens":2480,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-05-25T04:46:09.428439+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An episodic MDP with a fixed positive gap V* - μ0 where every algorithm requires a number of episodes that grows with the number of states or actions.","supporting_citations":[],"review_version":1}