- 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
- 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.
- The assumptions in this paper differ from independent best-of-k generation and many binary-verifier tasks.
- 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.
- The homogeneous upper bound contains an additional term and matches the stated lower bound only in the sufficiently small- 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.
- 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.
- The history is available before selecting the action at step , whereas is defined to include the reward at that step.
- The example at line 205 has an incorrect quadratic coefficient, and lines 300-302 contain an inconsistent approximation constant and omit the dependence in runtime.
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?
- Can you provide a concrete application mapping the states, actions, reward feedback, resets, and generative sampling interface?
- What is the space complexity of the discretized planning algorithm?
- Please state the precise regimes in which the sample-complexity bounds match. Can the additional term be reduced, and is the extra horizon factor in the inhomogeneous case necessary?
- What supports the assertion that exact planning is outside NP?
- Can you reconcile the definition of with the pre-action history and verify the resulting Bellman recursions?
3 comments
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
Rebuttal
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.
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.
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.
We fixed both typos.
Questions For Authors
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 K.
We have clarified this point in our revision.
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.
The space complexity is polynomial in the size of the instance and 1/ϵ. We need to store the policy and the values for backward induction. This requires O(ϵ2KS2H5). An additional O(HS2A) memory is needed to operate on the MDP in input. We included this detail in our revision.
The regime for which the bound match is ϵ≲KSH and we inserted it in the revision (the exact expression can be found in the updated manuscript). It is unclear whether the K2-term independent of ϵ 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.
We refear to the answer given to reviewer NEAF for the same question.
We thank the reviewer for spotting the typo. We corrected the definition of Gh,i. Our arguments in the proofs are not impacted.