acceptodds
Under review as a conference paper at ICLR 2027

Theoretical Foundations of max@ Reinforcement Learning

Abstract

Reinforcement Learning is a cornerstone technique for modern large reasoning models. Usually, for difficult tasks such as code generation and theorem proving, the agent is evaluated by generating responses rather than sampling a single response, and performance is then measured using a retry-aware metric such as @. Despite their practical importance, the theoretical foundations of learning under such criteria remain limited. In this work, we provide a theoretical study of the @ learning problem in finite-horizon reinforcement learning. We show that optimizing the @ objectives is fundamentally different from standard expected-return maximization. In particular, we prove that Markovian policies are in general insufficient, identify a compact state augmentation that restores optimality, and explicitly characterize the performance gap that can arise between history-dependent and non-history-dependent policies. Moreover, we show that learning @-optimal policies is statistically harder than standard reinforcement learning and provide an efficient algorithm that achieves the optimal sample complexity rate.

Primary area:
reinforcement learning
Keywords:
max@k, reinforcement learning, sample complexity, history-dependent policies

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_UeAtOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies finite-horizon reinforcement learning under an adaptive max@k objective, where later rollouts can use feedback from earlier attempts. It characterizes the history information needed for optimal control, develops a discretization-based planning algorithm, establishes planning hardness, and derives sample-complexity bounds under generative-model access.

Critical strengths

The paper addresses a relevant distinction between expected-return optimization and retry-aware objectives. Besides, the analysis covers both computational planning and statistical learning complexity.

Critical weaknesses
  1. Prior risk-sensitive RL work already augments states with cumulative rewards and uses discretization to recover dynamic programming. The paper should distinguish results that follow from these frameworks.
  2. The assumptions in this paper differ from independent best-of-k generation and many binary-verifier tasks.
  3. Retaining two reward statistics is compact online, but enumerating their possible values can substantially enlarge the planning state space. The space-complexity analysis is missing. Consequently, the claim that history dependence is not much more demanding than standard RL needs qualification.
  4. The homogeneous upper bound contains an additional AS2K2H2AS^2K^2H^2 term and matches the stated lower bound only in the sufficiently small-ϵ\epsilon regime, up to logarithmic factors. The inhomogeneous upper bound also has an additional horizon factor not matched by the presented lower bound. Comparisons should explicitly align objectives, access assumptions, reward normalization, and accuracy regimes.
  5. A reduction from SUBSET-SUM establishes hardness but does not by itself establish non-membership in NP. This stronger complexity claim requires a separate argument.
  6. The history Hh,i\mathcal H_{h,i} is available before selecting the action at step hh, whereas Gh,iG_{h,i} is defined to include the reward at that step.
  7. The example at line 205 has an incorrect quadratic coefficient, and lines 300-302 contain an inconsistent approximation constant and omit the KK dependence in runtime.
Questions for authors
  1. Which structural and planning results can be derived directly from existing general-utility state-augmentation frameworks? What technical obstacles are specific to cross-rollout max@k adaptation?
  2. Can you provide a concrete application mapping the states, actions, reward feedback, resets, and generative sampling interface?
  3. What is the space complexity of the discretized planning algorithm?
  4. Please state the precise regimes in which the sample-complexity bounds match. Can the additional K2K^2 term be reduced, and is the extra horizon factor in the inhomogeneous case necessary?
  5. What supports the assertion that exact planning is outside NP?
  6. Can you reconcile the definition of Gh,iG_{h,i} with the pre-action history and verify the resulting Bellman recursions?
3 comments

On the Critical Weaknesses

Below we answer a few points related to the raised concerns, as we answer to the remaining ones in the question section below.

The assumptions in this paper differ from independent best-of-k generation and many binary-verifier tasks.

We are not sure if we understood this point correctly, but an important point of this paper is showing that indepedent generation for max-at-k is sub-optimal. Proposition 1 also quantifies the sub-optimality of independent generation. We remain available for further clarifications.

A reduction from SUBSET-SUM establishes hardness but does not by itself establish non-membership in NP. This stronger complexity claim requires a separate argument.

We refer to the answer given to reviewer NEAF for the same question. We remark that this concern pertains to an informal comment in the discussion, not to the correctness of Theorem 2. The discussion was deliberately high-level, intended only to suggest possible directions for future research.

The example at line 205 has an incorrect quadratic coefficient, and lines 300-302 contain an inconsistent approximation constant and omit the KK dependence in runtime.

We fixed both typos.

Questions For Authors

Which structural and planning results can be derived directly from existing general-utility state-augmentation frameworks? What technical obstacles are specific to cross-rollout max@k adaptation?

Our results cannot be directly derived from existing general-utility frameworks.

  • For what concerns planning, we need to consider that the policy can adapt across several rollouts, which is a specific feature of max-at-k optimization. Wu & Xu (2023) consider general utilities but within a single-episode. We share with them the idea of discretizing rewards, but crucially we need to understand how to propagate information through rollouts, which sufficient statistics are necessary, and how the reward discretization impacts these choiches.

  • Concerning the other theoretical results, instead, we observe that they are directly tailored around the max-at-k metric and cannot follow from general tools: the hardness and the sub-optimality gap cannot consider general metric by definition, and all the theorems of the learning sections are tailored around the dependency in KK.

We have clarified this point in our revision.

Can you provide a concrete application mapping the states, actions, reward feedback, resets, and generative sampling interface?

An example could be iterative test-guided code generation, where an agent selects and refines programs using a frozen LLM. The current program and the task are encoded in the state, while the actions are a set of coding / repairing instructions. Here, the frozen LLM induces stochastic transitions. The reward at each step could be the improvement in the test-ratio pass. The reset means that we return to the original programming task. Finally, concerning the generative model, we note that it is a natural assumption when a virtual simulator is available, like in this example. Furthermore, it is also common in the RL theory community as discussed in Section 4.

What is the space complexity of the discretized planning algorithm?

The space complexity is polynomial in the size of the instance and 1/ϵ1/\epsilon. We need to store the policy and the values for backward induction. This requires O(KS2H5ϵ2)O(\frac{KS^2H^5}{\epsilon^2}). An additional O(HS2A)O(HS^2A) memory is needed to operate on the MDP in input. We included this detail in our revision.

Please state the precise regimes in which the sample-complexity bounds match. Can the additional K2K^2 term be reduced, and is the extra horizon factor in the inhomogeneous case necessary?

The regime for which the bound match is ϵ≲HKS\epsilon \lesssim \sqrt{\frac{H}{KS}} and we inserted it in the revision (the exact expression can be found in the updated manuscript). It is unclear whether the K2K^2-term independent of ϵ\epsilon is due to sub-optimality of the algorithm, its analysis, or the lower bound. We leave this to future work, and we highlighted this future line of research in our revision. Our focus was to derive tight bounds for the high-accuracy regime. The extra horizon factor commonly arises in RL with time inhomogeneous transitions, see, e.g., "Breaking the sample size barrier in model-based reinforcement learning with a generative model." Li et al., NeurIPS 2020 for a survey of results.

What supports the assertion that exact planning is outside NP?

We refear to the answer given to reviewer NEAF for the same question.

Can you reconcile the definition of Gh,iG_{h,i} with the pre-action history and verify the resulting Bellman recursions?

We thank the reviewer for spotting the typo. We corrected the definition of Gh,iG_{h,i}. Our arguments in the proofs are not impacted.

Thanks for the author's reply. I will keep my score.

Dear reviewer UeAt, could you briefly clarify which concerns you feel remain unresolved after the authors’ response and are driving your decision to keep your score? This would be helpful for me in calibrating my own assessment of the paper. Thank you

Reviewer_uhWoOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies a finite-horizon Markov decision process in which an agent sample k rollouts, each starting from the same initial state. Its objective is to maximize the expected value of the largest cumulative reward obtained in one of these k rollouts. Actions in a rollout may depend on observations made both earlier in that rollout and in previous rollouts. The paper shows that decisions based only on the current state, step, and rollout number can be suboptimal. It then shows that an optimal agent needs to retain only the best reward from previous rollouts and the reward accumulated so far in the current rollout, alongside the current state. Building on this observation, the authors give an efficient method for finding an approximately optimal policy. They also give an hardness result for exact planning. For an unknown model with generative access, they give a sample-complexity lower bound and an upper bound with matching leading dependence in the time-homogeneous case.

Critical strengths

The setting is interesting and well motivated : it is relevant to LLMs used for code generation and theorem proving, where a model can generate several candidate solutions and then choose the "best one".

This paper gives comprehensive characterization of the problem through three connected questions: what the agent needs to remember, how it should plan, and how much data it needs to learn.

First, on memory, author shows that Markovian policies can be suboptimal. It identifies a sufficient representation of the history: the best return from previous rollout and the cumulative return in the current rollout, together with the current state and time indices. It also shows that dropping one of these two representations reduce performance. This result useful for algorithm design: the agent can retain the information needed for optimal decisions without storing its full history.

Second, the planning results show that near-optimal history-dependent policies can be computed without an exponential computational cost. The difficulty is that the two return summaries can still take exponentially many values. The authors address this by rounding rewards to a finite grid, which limits the number of possible return values and makes dynamic programming efficient. A particularly useful feature is that the approximation error does not grow with K: increasing the number of attempts does not require finer rounding to maintain the same accuracy. The hardness result for exact planning strengthens this contribution by showing that a computational barrier exists even with two rollouts, giving a clear justification for studying efficient approximation.

Third, the learning section identifies the leading statistical cost of allowing more attempts and shows that a simple algorithm can achieve it. Obtaining the right dependence on K requires an analysis that uses the structure of the max@k Bellman equation : the proof controls the accumulated variance using the bounded final score, avoiding the weaker bounds that would follow from treating the problem as a generic process of length KH. The agreement between the lower bound and the leading upper-bound term establishes that the extra factor of K is unavoidable, for time-homogeneous MDPs and sufficiently small error tolerance, up to logarithmic factors.

Critical weaknesses

W1 - Related work

Missing connection to transition-lookahead RL. The related work should discuss the setting of reinforcement learning with look-ahead information. In that setting, before choosing an action, the agent observes the states that would be visited upon playing any action sequence of length \ell. [1] shows that exact planning is polynomial-time solvable with one-step lookahead but becomes NP-hard as soon as the lookahead horizon is at least two. The setting and the reduction seem very close to your setting discussing the differences would help identify what is specific to the max-over-rollouts objective in the present planning results. See ([2], [3], [4]) for more references.

W2 Policy class

The stated policy class cannot support the learning guarantee. Proposition 2 fixes the reset state, whereas Eq. (4) requires one policy to be approximately optimal from every starting state. The compressed representation omits the reset state, so identical compressed histories can require different optimal actions because subsequent rollouts reset to different states. Consequently, Theorem 4 guarantee is false as written, even with known transitions.

W3 Hardness result

The hardness result needs a model-consistent construction and more precise complexity claims. The reduction uses stochastic immediate rewards, whereas the formal model specifies deterministic state–action rewards. The reduction supports hardness of exact planning and exponentially accurate approximation. Moreover, the assertion that the problem is “not even in NP” does not follow from hard policy evaluation and requires an appropriate complexity argument and assumptions.

[1] C. Pla, H. Richard, M. Abeille, N. Merlis, V. Perchet, On the Hardness of Reinforcement Learning with Transition Look-Ahead.

[2] Chenbei Lu, Zaiwei Chen, Tongxin Li, Chenye Wu, Adam Wierman, Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach.

[3] N. Merlis, Reinforcement Learning with Lookahead Information.

[4] C. Pla, H. Richard, M. Abeille, V. Perchet, Near-Optimal Reinforcement Learning with Multi-Step Transition Lookahead.

Questions for authors

Q1. Reset-state dependence. Is the learner intended to return one policy for all reset states or a family {πs0}\{\pi_{s_0}\}? Proposition 2 fixes the reset state, whereas Eq. (4) requires simultaneous guarantees. Should s0s_0be included explicitly in the policy input, and how would this affect the planning complexity?

Q2. Scope of the hardness result. Can you provide a deterministic-reward encoding of the reduction’s stochastic rewards? Beyond NP-hardness of exact planning, what additional arguments and complexity assumptions support the claims of nonmembership in NP as well as necessary inverse-polynomial dependence on accuracy?

Q3. Relation to transition-lookahead results. How do your setting and hardness results relate to [1]?

5 comments

(Question 1) Reset-state dependence. Is the learner intended to return one policy for all reset states or a family πs0\pi_{s_0} ? Proposition 2 fixes the reset state, whereas Eq. (4) requires simultaneous guarantees. Should s0s_0 be included explicitly in the policy input, and how would this affect the planning complexity?

We thank the reviewer for spotting this. The planning section was dealing with a fixed initial state, while in the learning section we were considering optimality accordingly to multiple states. Fixing this inconsistency for the most general result requires only a minor modification, that is including the initial state in the compressed representation so that our planning algorithm computes an optimal policy for each starting state. This only adds an additional SS term to the computational complexity and a extra log⁡(S)\log(S) term in the sample complexity. We have revised the paper accordingly.

(Question 2) Scope of the hardness result. Can you provide a deterministic-reward encoding of the reduction’s stochastic rewards? Beyond NP-hardness of exact planning, what additional arguments and complexity assumptions support the claims of nonmembership in NP as well as necessary inverse-polynomial dependence on accuracy?

The fact that in the reduction we use stochastic rewards, while our model only assumes deterministic reward is not an issue: a reward distribuited as a Beroulli of parameter pp can be simulated by a stocastic transition that leads to a state with reward 11 with probability pp. The blowup is only by a constant factor. We added a brief note to clarify this point, but a full formal discussion of this aspect would obscure the main result without materially improving it. For the "not even in NP" issue, we refer to the answer to this question to reviewer NEAF.

(Question 3) Relation to transition-lookahead results. How do your setting and hardness results relate to [1]?

We were familiar with the lookahead setting, but we didn't tought of a formal connections between the settings. However, upon further looking we do not really see a connection between the two problems or in the proof ideas (i.e., Theorem 2 in [1]). Our proof works by building long chains of bernoulli variables and we exploit the maximum with the deterministic reward RsafeR_{safe} collected at k=1k=1. Our understanding of the proof of Theorem 2 in [1] is that the agent need to decide at each state wether to wait for another set or commit to the current one, obtaining a payoff determined by the expected maximum of the random rewards. To show how different are the two reductions, our instances are hard even when we have to decide between two actions, while the hardness of [1] is for a (more standard) large combinatorial decision space.

Moreover, our hardness proof is mainly needed to exlude a more efficient planning algorithm than the one presented in Section 3.2, while in [1] it is a stronger impossibility result.

If the reviewer has a deeper understanding of the formal connections between the two frameworks, we would be happy to discuss about it. Nevertheless, we added a small discussion of the lookahead framework as another nonstandard RL framework with interesting NP-hardness result.

Thank you for your answers. Regarding the connection between max@k and RL with look-ahead : If we set (H=\ell) and allow infinitely many rollouts, would selecting the best rollout be equivalent to choosing the best action sequence with (\ell)-step lookahead?

We thank the reviewer for taking the time to engage with the discussion. Even in this limiting case proposed by the reviewer, we do not see a natural equivalence between the two settings. Indeed, when H=ℓH=\ell and K→∞K\to\infty, the optimal max@k policy achieves the largest return among all trajectories of positive probability. This quantity can be computed in polynomial time by backward induction (by leveraging the support of the transition kernel rather than the expectations). In contrast, transition-lookahead RL optimizes the expected return using advance knowledge of counterfactual transitions, and [1] establishes that exact planning in this setting is NP-hard for ℓ≥2\ell\geq 2 under discounted and average-reward objectives. This establishes that in this limiting case, the problems are fundamentally different.

More generally, we do not see a natural reduction or equivalence between the two settings. While the respective hardness results suggest a connection (in terms of polynomial-time reductions) at the level of computational complexity, this does not imply a natural correspondence between the planning problems. We interpret the reviewer’s suggestion as pointing to such a structural equivalence rather than a generic complexity-theoretic reduction, and we currently cannot see one.

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

The paper considers finite-horizon RL with the expected maximum return over KK rollouts as its objective. It shows that Markov policies can perform worse than history-dependent policies by a constant factor in some instances. The authors also prove that an optimal policy only needs the current state, the best return from previous rollouts, and the cumulative reward in the current rollout. This leads to a polynomial-time approximation algorithm for planning, along with an NP-hardness result for highly accurate planning. With access to a generative model, the authors prove a sample complexity lower bound of Ω(KSAH3ϵ−2log⁡(1/δ))\Omega(KSAH^3\epsilon^{-2}\log(1/\delta)). Their upper bound matches the leading rate for time-homogeneous MDPs when ϵ\epsilon is sufficiently small. The paper does not include experiments.

Critical strengths
  1. The paper provides a useful characterization of the information needed for optimal \max@k\max@k policies. It shows that Markov policies can be suboptimal, while the previous best return and the current cumulative reward are sufficient to summarize the relevant history. The authors also show that neither statistic can be omitted in general. These results provide a clear basis for the planning algorithm.
  2. The paper covers both planning and learning under the \max@k\max@k objective. It provides a polynomial-time approximation algorithm and an NP-hardness result for highly accurate planning. For the learning problem, the authors use a variance analysis specific to \max@k\max@k, avoiding the loose bounds that would result from treating the problem as a standard KHKH-step MDP. This gives a leading sample complexity term with linear dependence on KK when ϵ\epsilon is sufficiently small.
Critical weaknesses
  1. In Appendix C.1, Equation (11) is used to derive ∑s∈Sˉ∑a∈APM0(Es,a)≤Sˉ\sum_{s\in\bar{\mathcal{S}}}\sum_{a\in\mathcal{A}}\mathbb{P}_{\mathcal{M}_0}(\mathcal{E}_{s,a})\le\bar{S}. However, this inequality does not follow from the definition of Es,a\mathcal{E}_{s,a}. The event requires the total mass on action aa to be at least KL/2KL/2, while Equation (11) only states that the masses sum to KLKL across actions. In particular, two actions can each have mass KL/2KL/2, so both events may occur. The proof therefore needs correction at this step. In Step 4, the coefficient also changes from p/(8Δ2)p/(8\Delta^2) to p/(2Δ2)p/(2\Delta^2) without explanation. The first issue may be resolved by using the stronger inequality already proved in Step 2 to redefine Es,a\mathcal{E}_{s,a}.

  2. Theorem 4 uses a different history representation from the one defining ΠC\Pi_C. The PAC definition uses the true cumulative and previous best returns, while the algorithm uses discretized rewards to compute them. The discretized values cannot always be recovered from the true returns. Thus, the returned policy is not necessarily in ΠC\Pi_C. It is unclear whether the claimed matching upper and lower bounds apply to the same policy class.

Questions for authors
  1. Could the authors provide a corrected proof of Theorem 3? As noted above, Equation (11) does not justify ∑s∈Sˉ∑a∈APM0(Es,a)≤Sˉ\sum_{s\in\bar{\mathcal{S}}}\sum_{a\in\mathcal{A}}\mathbb{P}_{\mathcal{M}_0}(\mathcal{E}_{s,a})\le\bar{S} with the current definition of Es,a\mathcal{E}_{s,a}. The stronger inequality in Step 2 may allow a higher threshold. Please also clarify the change from p/(8Δ2)p/(8\Delta^2) to p/(2Δ2)p/(2\Delta^2) and the parameter conditions needed for Theorem 3.
  2. Does the policy returned by Theorem 4 belong to ΠC\Pi_C as originally defined? If not, what is the intended output policy class, and does the lower bound in Theorem 3 still apply to that class?
  3. The discussion following Theorem 2 claims that the exact problem is "not even in NP." What supports this conclusion? The reduction establishes NP-hardness, which alone does not rule out membership in NP.
3 comments

Could the authors provide a corrected proof of Theorem 3? As noted above, Equation (11) does not justify ∑s∈S~∑a∈APM0(Es,a)≤Sˉ\sum_{s\in\tilde{\mathcal S}}\sum_{a\in\mathcal A}\mathbb P_{\mathcal M_0}(\mathcal E_{s,a})\leq\bar S with the current definition of Es,a\mathcal E_{s,a}. The stronger inequality in Step 2 may allow a higher threshold. Please also clarify the change from p/(8Δ2)p/(8\Delta^2) to p/(2Δ2)p/(2\Delta^2) and the parameter conditions needed for Theorem 3.

We thank the reviewer for pointing out these typos. For the first point, we note that we actually obtained ∑i∑hαi,h>KL/2\sum_i \sum_h \alpha_{i,h} > KL/2. Replacing ≥\ge with >> in the definition of the event solves the issue. For the second one, it was typo. In the revision, we now use 88 instead of 22. We also added the the parameter needed for Theorem 3 in the appendix as we believe it does not add value in the main text.

Does the policy returned by Theorem 4 belong to ΠC\Pi_C as originally defined? If not, what is the intended output policy class, and does the lower bound in Theorem 3 still apply to that class?

We thank the reviewer for pointing out this imprecision. Fixing this point takes only a few changes. In general, the policy returned by Theorem 4 belongs to ΠCκ\Pi_C^\kappa, so it does not necessarily belong to ΠC\Pi_C. This is consistent with the standard learning objective in RL (i.e., return any policy which is ϵ\epsilon-optimal). We now fixed the definition of the PAC formulation (Equation 4) so that the output class is now explictly any history dependent policy. Theorem 3 applies also to this broader class via a minor modification of the definition of α\alpha that we used in the proof (this is to account for arbitrary history-dependent selection rules). Intuitively, the reason is that, since reaching the goal is hard, every history-dependent policy must place sufficient mass on the optimal action to be nearly-optimal. We revised the proof accordingly.

The discussion following Theorem 2 claims that the exact problem is "not even in NP." What supports this conclusion? The reduction establishes NP-hardness, which alone does not rule out membership in NP.

We agree that the current writing can be improved. We made the sentence more precise in the updated version of the paper. Intutively, the implicit missing logical link is as follows: the size of the decision space (i.e., number of alternative continuation policies) is constant. So if a policy could be evaluated efficiently, then we could find the optimal one by enumeration. Thus, the NP-hardness result shows that answering the question "what is the value of a policy" is NP-hard. However, intuitively, verifying optimality should be in P for the problem to be in NP. This intuition is not entirely precise, since membership in NP does not require computing the exact value of a policy, but only verifying that the given action is better than the other. This is not an issue because formally our proof also shows coNP-harndess since our reduction maps YES instances to Q−−Q+>βQ_--Q_+>\beta and NO instances to Q−−Q+<−βQ_--Q_+<-\beta. So membership in NP would collapse coNP$\subseteq$NP. We are happy to add a note on this, but we would avoid adding a formal proof since it is not central to the main discussion of the paper and would require too many unnecessary details. We remark that we included this high-level discussion primarily because the gap between the NP-hardness lower bound and a potential PSPACE upper bound suggests an interesting direction for future research.

Thank you for the response and revisions. The updated proof of Theorem 3 and the changes to the policy class in Theorem 4 address my main concerns. The clarification following Theorem 2 is also helpful. I will update my rating to 3.

We thank the reviewer for the acknowledgement and engaging in the discussion. We are glad that concerns are solved.

Comments on the paper

1 comment

We thank all reviewers for their feedback. We have addressed all concerns raised in the reviews. We emphasize that all of the issues required minor corrections. We uploaded a new pdf where the relevant changes have been highlighted in green. We respectfully ask the reviewers to reconsider their scores in light of these clarifications and corrections.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.