{"id":"bd647515-27c3-41ca-8130-2044fced5ece","arxiv_id":"2607.17823","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For max@k (best-of-K) finite-horizon MDPs, Markovian policies are suboptimal, a compact (previous-best, current-cumulative) state augmentation restores optimality, exact planning is NP-hard but an FPTAS exists, and the minimax generative-model sample complexity is Θ(KH³SA/ε²).","lead":"This paper builds the first theory of RL with the 'max@k' objective, where an agent is scored by its best of K attempts. It proves that learning such policies is K times more sample-hungry than ordinary reinforcement learning, and that a good policy only needs to remember the best score so far and the current run's partial score.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lower-bound instance in B.1 assigns reward 1 to every step, so every policy obtains total H in every rollout; the claimed Ω(KH³SA/ε²) lower bound is unsupported as written.","rationale":"The reader identified the Π_C compression as the weakest assumption. I find a more fundamental issue in the lower-bound proof. The construction's reward function degenerates the objective: because every state-action pair gives reward 1, all trajectories have identical total return H, so no sample-complexity lower bound can be derived. The proof's own inequalities are incompatible with the stated rewards, indicating an unstated reward definition. This is directly load-bearing for the headline Θ result. It does not necessarily imply the theorem is false—likely the intended rewards are 0 at non-goal states—but it means the manuscript's central lower bound is not currently proven. The compression proof (Proposition 2) is terse but its main induction is plausible; the NP/PSPACE overclaim noted by the reader is a presentation issue. Given the lower-bound flaw is concrete and fixable, I retain CONDITIONAL rather than REJECT. A one-line correction plus a re-verified Step 2 would resolve it.","tokens_in":37382,"tokens_out":7271,"duration_ms":69830,"concrete_test":"Recompute V^π_{1,1}(s) for the M_0 of B.1 Step 1 under the stated rewards: for any deterministic or stochastic policy, each of the H steps contributes reward 1, so every rollout return is H and max@K is H almost surely; confirm that this makes both M_0 and M_{s,a} have value H for every policy. Then re-derive Step 2 after replacing r(s_i,a)=1 with r(s_i,a)=0 (reward 1 only at g) and check whether the inequalities V⋆(g) ≥ 3H/4, V⋆(s) ≤ H/64, and the subsequent KL/2 mass argument go through; if they do, Theorem 3 is repair-ready, but not as printed.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In B.1 Step 1, the lower-bound MDP is defined with r(g,a)=1 and r(s_i,a)=1 for every non-goal state and every action. Therefore every length-H trajectory has total reward exactly H, irrespective of transitions, and V^π_{1,1}(s)=H for every policy in both M_0 and every M_{s,a}. The max@K objective is constant, so no algorithm can be forced to distinguish the instances and the claimed Ω(KH^3SA/ε^2) cannot follow from this construction. The internal inequalities confirm the inconsistency: Step 2 asserts V⋆_{h+,i+}(g) ≥ 3H/4 while V⋆_{h+,i+}(s) ≤ H/64, but with the stated rewards V⋆(s)=H; and the footnote claiming cumulative reward 0 on F_{h,i} contradicts r(s_i,a)=1 (cumulative reward would be h−1). The proof implicitly uses zero rewards on non-goal steps, with reward only upon reaching g. As written, Theorem 3 — the lower-bound half of the central Θ(KH^3SA/ε²) claim — is unsupported; a one-line reward correction may repair it, but that correction is absent.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the max@k objective in finite-horizon reinforcement learning, where the agent is evaluated by the expected best reward over K rollouts from the same initial state. It claims three main results: (i) Markovian policies are generally suboptimal for max@k, and optimal policies can be restricted to a compressed class Π_C that conditions only on the current state, the previous best return M, and the cumulative reward G in the current rollout (Propositions 1–3); (ii) an epsilon-optimal history-dependent policy can be computed in time polynomial in the problem parameters and 1/epsilon (Theorem 1), while exact planning is NP-hard (Theorem 2); and (iii) the minimax sample complexity for PAC learning under a generative model is Θ(K H^3 S A / ε^2) up to log factors, established by a lower bound Ω(KH^3SAε^{-2}log(1/δ)) (Theorem 3) and a matching upper bound Õ(KSAH^3ε^{-2}log(1/δ)) (Theorem 4). The upper-bound algorithm samples each state-action pair uniformly, builds an empirical model, discretizes rewards, and plans in the compressed state space.","tokens_in":37533,"tokens_out":7228,"duration_ms":63501,"significance":"If the claims hold, the paper would be the first to give a tight minimax sample-complexity characterization for a retry-aware objective in finite-horizon MDPs, and it would rigorously quantify how max@k evaluation changes the learning problem relative to standard expected-return RL. The structural compression result (Proposition 2) is attractive and potentially useful beyond the exact setting, since it isolates the memory that an optimal reasoning-agent policy must keep across attempts. The planning FPTAS and the NP-hardness result are also meaningful, and the refined simulation analysis in the upper-bound proof (Lemmas 5–7) contains a variance bound that is specific to the max@k structure and is not obtained by a naive reduction to a KH-horizon MDP. These contributions justify serious interest in the paper, conditional on the correctness of the lower-bound construction and the rigor of the compressed-state optimality proof.","major_comments":[{"comment":"The lower-bound instance is internally inconsistent. Step 1 defines r(s_i,a)=1 for every non-goal state and r(g,a)=1 for the goal, so every length-H trajectory has total reward exactly H in the base instance M0 and in every alternative instance M_{s,a}. Consequently the max@K objective is identically H for every policy, and no (ε,δ)-correct algorithm can be forced to pay samples to distinguish the instances. The proof's Step 2 claims V⋆_{h+,i+}(g) ≥ 3H/4 while V⋆_{h+,i+}(s) ≤ H/64, but with the stated rewards both quantities are H. The footnote asserting that cumulative reward on the event F_{h,i} is 0 also contradicts r(s_i,a)=1, since the cumulative reward would be h−1. The algebra in Step 2 implicitly uses zero rewards on all non-goal steps, with reward obtained only upon reaching g. As written, Theorem 3, which is the lower-bound half of the central claimed rate Θ(KH^3SA/ε^2), is unsupported. The construction may be repairable by a one-line reward correction, but that correction is absent and the proof as submitted does not establish the theorem.","section":"Appendix B.1, Theorem 3"},{"comment":"Proposition 2 is load-bearing: both the planning FPTAS (Theorem 1) and the learning upper bound (Theorem 4) restrict attention to the class Π_C, so the claim that Π_C is sufficient for optimality needs a fully rigorous proof. The present proof is too terse and notationally confused: it defines an object with two repeated arguments, V̄⋆_{h,i}(H_{h,i})(H_{h,i}), and later evaluates V̄⋆ on the compressed history Φ while V⋆ is evaluated on the full history, without an explicit definition of V̄⋆ on the compressed state space. The critical step, showing that the greedy policy defined by the Bellman optimality equations for the Π_C-restricted optimum attains the original history-dependent optimum, is asserted by a 'recursion argument' that does not spell out the induction over rollout boundaries, nor justify that the maxima are attained at every compressed history. I recommend rewriting this proof with explicit dynamic-programming value functions on the triple (s,M,G), including a careful treatment of the boundary conditions V̄⋆_{H+1,i} = V̄⋆_{1,i+1}.","section":"Appendix A.2, Proposition 2"}],"minor_comments":[{"comment":"The description of the example in the text is inconsistent: the text refers to 'the risky action' twice, first with reward 1/2 and probability 1−γ and then with reward 1 and probability 1/4, while the caption assigns the reward 1/2 to the safe action. Please correct the typo and align the caption with the intended safe/risky assignment.","section":"Section 3.1, Figure 1 and accompanying text"},{"comment":"In the derivation of Q_-, the second displayed equation is labeled 'Q+ = ...' and should be 'Q_- = ...'; also the expression 'P[X≥T]' should be 'P[X≥L]' throughout.","section":"Appendix A.5, proof of Theorem 2"},{"comment":"The repeated argument notation V̄⋆_{h,i}(H_{h,i})(H_{h,i}) appears to be a typographical duplication; the value function on the compressed history should be defined as a function of Φ(H_{h,i}) once, and the proof should distinguish V̄⋆ on compressed states from V⋆ on raw histories consistently.","section":"Appendix A.2, notation"},{"comment":"The choice κ=O(εH^{-1}) is vague; the proof uses κ=ε/(9H). Please state the concrete constant or specify that it is a sufficiently small absolute constant.","section":"Section 4.3, Theorem 4 statement"}],"recommendation":"major_revision","confidential_remarks":"The lower-bound proof in Appendix B.1 is not merely incomplete; the constructed family of MDPs is degenerate because all rewards are 1, so every trajectory has the same total reward and Theorem 3 is unproven as stated. I believe the intended construction with zero non-goal rewards is likely repairable, and the paper contains a substantial body of plausible results, so I am recommending major revision rather than rejection. I would also suggest that the handling editor obtain a careful second reading of Proposition 2, since the compressed-state optimality proof is currently too terse to certify the foundation of the planning and learning results."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Max@k RL is a real gap in the theory, and this paper is the first to attack it head-on. The compression result, that optimal policies only need the previous best return and the current cumulative reward, is the key idea and is done well. Proposition 2's induction is terse, but the claim is credible and it gives you a finite augmented state to do dynamic programming on. The FPTAS in Theorem 1 and the Subset-Sum hardness in Theorem 2 also check out as far as I can verify; the 2κH error decomposition via Lemma 1 is clean. The upper bound in Theorem 4 looks like serious work: the extended-MDP reduction, the two simulation lemmas, and the variance lemma (≤3H²) are plausible, and matching a lower bound up to log factors would be a strong result. Now the soft spot, and it is a big one. The lower-bound instance in Appendix B.1 defines r(g,a)=1 and r(s_i,a)=1 for every non-goal state and every action. That means every H-step rollout has total reward exactly H, in the base instance and in every alternative instance. Every policy gets max@K value H, so no algorithm can be forced to distinguish the instances. The proof then asserts V⋆_{h+,i+}(s) ≤ H/64, which directly contradicts the stated rewards (V⋆_{1,1}(s)=H). This is not a minor typo in a constant; it removes the support for Theorem 3, the lower-bound half of the Θ(KH³SA/ε²) claim. The intended construction almost certainly gives zero reward on non-goal steps and reward only upon reaching the goal; with that one-line fix, the change-of-measure argument might go through. But that fix is not in the manuscript. Two smaller issues. Section 3.3 says the exact problem is 'not even in NP', but the theorem only proves NP-hardness of a gap decision problem; the PSPACE remark is honest, but that sentence overreaches. The reader also flagged a good-event threshold issue in B.1, that is secondary to the reward problem, and likely fixable. Bottom line: the planning half is a real contribution worth citing, and the learning upper bound is promising, but the lower bound as written does not stand. Send it to referees, but tell the authors to fix B.1 first. If the reward correction is as obvious as it looks, this becomes a good paper; right now, Theorem 3 is not usable.","headline":"Genuinely useful theory for max@k RL, and the planning half holds up; but the lower-bound construction in Theorem 3 is broken as written, so the headline sample-complexity claim needs a repair before it can be relied on.","tokens_in":745,"tokens_out":1310,"would_cite":true,"duration_ms":46294,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Learning to maximize the best of K rollouts costs a factor K more samples than standard reinforcement learning.","keywords":["max@k","reinforcement learning","finite-horizon MDP","history-dependent policies","state augmentation","sample complexity","generative model","planning hardness"],"falsifier":"Enumerate all deterministic $\\Pi_C$ policies on the two-rollout MDP of Proposition 3: the paper predicts the optimal max@k value is $42/32$. Any value below $42/32$ disproves the compression claim. Alternatively, on the hard instance family of Theorem 3, any $(\\epsilon,\\delta)$-correct algorithm that always stops with $o(K H^3 S A \\epsilon^{-2} \\log(\\delta^{-1}))$ samples would disprove the claimed minimax rate.","tokens_in":37077,"feed_emoji":"🎲","tokens_out":12968,"duration_ms":103120,"temperature":0.7,"pith_summary":"max@k reinforcement learning evaluates an agent by the best return among $K$ rollouts rather than by the return of a single trajectory. The paper establishes that this retry-aware objective changes the problem in a fundamental way: Markovian policies can be strictly suboptimal, and learning an $\\epsilon$-optimal policy from a generative model requires $\\Theta(K H^3 S A / \\epsilon^2)$ samples up to logarithmic factors, a factor $K$ more than classical RL. The mechanism that keeps the problem tractable is a compact memory: optimal policies need only remember the best return from previous rollouts and the cumulative reward inside the current rollout. With that compression, near-optimal planning can be done in polynomial time by discretizing rewards, even though exact planning is NP-hard. A reader should care because best-of-$K$ evaluation is how many reasoning and code-generation systems are scored, and this paper says optimizing the criterion directly is both necessary and achievable at a precisely quantified statistical cost.","feed_headline":"Max@k learning is K times harder than standard RL","feed_subtitle":"The best of K rollouts is provably harder to optimize, but remembering two numbers makes it tractable.","key_machinery":"The load-bearing object is the compressed history $\\Phi(H_{h,i})=(s_{h,i}, M_i, G_{h,i})$, where $M_i$ is the maximum reward collected in rollouts $1,\\dots,i-1$ and $G_{h,i}$ is the cumulative reward gathered in rollout $i$ up to step $h$. The paper proves that value functions and optimality equations factor through this triple, so the search can be restricted to $\\Pi_C$ policies. The planning FPTAS then discretizes the reward interval $[0,1]$ onto a grid of $O(H/\\kappa)$ points, making both $M$ and $G$ finite sets of size $O(H/\\kappa)$ and reducing backward induction to polynomial time. The learning upper bound combines this discretized Bellman solve with a uniform-sampling estimate of the transition kernel, while the lower bound is driven by a family of MDPs in which a good action succeeds with small probability $p$; because a single success among $K$ rollouts can decide the max@k value, an $(\\epsilon,\\delta)$-correct learner must place large total probability mass on the good action across all rollouts, forcing the extra factor $K$.","core_discovery":"The paper's central claim is that the max@k objective, the expected value of the best of $K$ independent horizon-$H$ rollouts, is not an expected-reward problem in disguise. It proves that Markovian policies are insufficient: there are MDPs in which the best history-dependent policy beats every Markovian policy by a factor of at least $1.24 - O(1/K)$. It then shows that full history dependence is unnecessary, because the optimal value is attained by policies in $\\Pi_C$, i.e., policies that condition only on the current state $s_{h,i}$, the previous best return $M_i$, and the cumulative return $G_{h,i}$ in the current rollout. Planning from this compressed representation admits a polynomial-time approximation scheme via uniform reward discretization, while exact planning is NP-hard through a reduction from Subset-Sum. For learning, the paper proves matching lower and upper bounds of order $K H^3 S A / \\epsilon^2$ (up to logs) in the small-$\\epsilon$ regime for the time-homogeneous generative-model setting, with an additional $H$ for time-inhomogeneous MDPs; this is exactly $K$ times the classical finite-horizon RL rate, and it is achieved by uniform sampling followed by backward induction on the empirical discretized model.","pith_inferences":["The paper's compression suggests a concrete recipe for value-based RL in reasoning tasks: augment the state with (previous best return, current cumulative reward) and run standard DP or Q-learning on that augmented state; the theory predicts this should dominate policies that ignore either coordinate.","The $K$ factor in the lower bound indicates that retry-aware learning should oversample rare, high-payoff branches, because one success out of $K$ attempts can determine the objective; this is a testable design principle for exploration in best-of-$K$ training.","The 1.24 multiplicative Markovian gap implies that independent best-of-$K$ sampling, even with a well-trained policy, is suboptimal relative to adaptive generation; a natural extension is to quantify how much adaptivity can help in realistic reasoning environments beyond the constructed worst-case MDP.","The planning hardness result suggests that practical max@k algorithms should target approximate solutions; it also leaves open whether a PSPACE-completeness characterization holds, which the paper explicitly flags as future work."],"forward_implications":["Any pipeline that trains on expected single-trajectory reward and then evaluates by best-of-$K$ is provably leaving performance on the table; the max@k objective itself is the right training target.","History-dependent max@k planning is not computationally hopeless: an $\\epsilon$-optimal policy can be computed in time polynomial in $K$, $S$, $A$, $H$, and $1/\\epsilon$, so the extra memory carries only a mild computational cost.","Exact max@k planning is NP-hard even when the required decision gap is exponentially small, so approximation is unavoidable in the worst case.","With a generative model, the minimax sample complexity is $\\Theta(K H^3 S A / \\epsilon^2)$ up to logarithms: retry-aware goals are $K$ times harder to learn, and time-inhomogeneous dynamics add another factor $H$.","The $K=1$ case recovers the classical finite-horizon RL rate, so the framework is a consistent generalization rather than a separate theory."],"supporting_citations":[{"why":"Provides the classical minimax rate $H^3SA/\\epsilon^2$ for generative-model RL that the $K$-factor lower and upper bounds must beat.","marker":"[Gheshlaghi Azar et al., 2013, Sidford et al., 2019]"},{"why":"Grounds the MDP Bellman optimality equations and backward induction used for the compressed representation.","marker":"[Puterman, 1990]"},{"why":"Shows that general utility functions of cumulative reward admit dynamic programming by augmenting the state with accumulated reward, the template extended to multi-rollout max@k.","marker":"Wu and Xu [2023]"},{"why":"Supplies the change-of-measure lemma used to convert the optimal-action margin into a lower bound on samples.","marker":"Garivier et al. [2019]"},{"why":"Supplies the KL lower-bound lemma used to finish the $K$-linear sample-complexity proof.","marker":"Domingues et al. [2021]"},{"why":"Supplies the $\\ell_1$ concentration inequality that controls the empirical transition kernel in the upper bound.","marker":"Jonsson et al. [2020]"},{"why":"Provides the Bernstein concentration inequalities behind the variance-aware simulation lemma.","marker":"[Boucheron et al., 2003]"},{"why":"Provides the technical stopping-time lemma that bounds the uniform-sampling phase.","marker":"Barbara et al. [2026]"}],"fun_headline_variants":["Best-of-K RL: Markovian policies fail, but 2 stats fix it","Max@k RL provably needs Kx more samples than standard","Compressed state makes max@k RL tractable, but NP-hard to plan","For best-of-K RL, remember best and sum: policy suffices","Max@k learning: K times sample cost, but exact via discretization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole argument rests on Proposition 2's compression claim: that no optimality is lost by restricting to policies that depend only on the current state, the best return from previous rollouts, and the cumulative reward of the current rollout; if that is false, both the efficient planning algorithm and the sample-complexity upper bound solve the wrong problem.","fun_headline_variants_meta":{"raw":{"variants":["Best-of-K RL: Markovian policies fail, but 2 stats fix it","Max@k RL provably needs Kx more samples than standard","Compressed state makes max@k RL tractable, but NP-hard to plan","For best-of-K RL, remember best and sum: policy suffices","Max@k learning: K times sample cost, but exact via discretization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000494,"raw_usage":{"total_tokens":2450,"prompt_tokens":996,"completion_tokens":1454,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":612,"completion_tokens_details":{"reasoning_tokens":1368}},"tokens_in":612,"tokens_out":1454,"duration_ms":9561,"temperature":1.0,"reasoning_tokens":1368,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:37:00.170438+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all deterministic $\\Pi_C$ policies on the two-rollout MDP of Proposition 3: the paper predicts the optimal max@k value is $42/32$. Any value below $42/32$ disproves the compression claim. Alternatively, on the hard instance family of Theorem 3, any $(\\epsilon,\\delta)$-correct algorithm that always stops with $o(K H^3 S A \\epsilon^{-2} \\log(\\delta^{-1}))$ samples would disprove the claimed minimax rate.","supporting_citations":[{"cited_title":"Explore first, exploit next: The true shape of regret in bandit problems","cited_arxiv_id":null,"evidence_quote":"Supplies the change-of-measure lemma used to convert the optimal-action margin into a lower bound on samples."},{"cited_title":"Concentration inequalities","cited_arxiv_id":null,"evidence_quote":"Provides the Bernstein concentration inequalities behind the variance-aware simulation lemma."},{"cited_title":"Optimal rates for feasible payoff set estimation in games","cited_arxiv_id":null,"evidence_quote":"Provides the technical stopping-time lemma that bounds the uniform-sampling phase."}],"review_version":2}