- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
This paper studies the statistical benefits of on-policy RL for LLM reasoning under a hierarchical reward model, where deeper reward components become accessible only after reaching promising regions at earlier levels. The authors propose a Transformer-based actor–critic algorithm that adaptively collects prefix-level reward feedback and updates a KL-regularized policy. They establish regret upper bounds that match minimax lower bounds up to logarithmic factors for a fixed number of prompts. They further show that fixed-distribution sampling can suffer substantially slower convergence, including logarithmic regret decay under weak KL regularization. The paper is entirely theoretical and provides no empirical validation.
Critical strengths
The paper addresses an interesting theoretical question: why adaptive on-policy exploration can be more sample-efficient than fixed-distribution sampling. The authors provide a technically substantial analysis, including regret upper bounds, matching minimax lower bounds for a fixed number of prompts, and a theoretical separation from fixed-distribution sampling under their hierarchical reward model.
The mathematical analysis appears carefully developed, and preliminary AI-assisted checks did not identify obvious errors in the main proofs.
Critical weaknesses
I used GPT-6-Astra and Claude Opus 5.5 to help check the mathematical proofs and found no obvious errors. However, I have three major concerns.
1. Extremely poor organization and readability. The paper is filled with excessive definitions, lemmas, and technical details. It reads more like something written by AI for AI, rather than for human researchers. I had to rely on AI just to understand what the proofs were actually trying to establish. This is a serious presentation issue.
2. Highly artificial theoretical assumptions. It feels as if the authors started with a predetermined conclusion—that On-policy RL converges faster than Offline Sampling—and then constructed a theoretical framework specifically to prove it.
The infinite hierarchical reward structure, Hölder smoothness, positive maxima at every level, deep-enough zoom, exact zero-mean condition, and polynomial reward decay have no demonstrated grounding in realistic LLM reasoning. In particular, A3 and A4 seem almost designed to create an environment that favors on-policy exploration while making information acquisition unnecessarily difficult for fixed-distribution sampling.
Even more problematic is the assumption that the reference policy generates uniformly random bits. Real LLM post-training starts from a pretrained model with substantial prior knowledge, not a random generator.
Previous work, such as Yue et al. (2025), Does Reinforcement Learning Really Incentivize Reasoning Capacity in LLMs Beyond the Base Model? (NeurIPS 2025), uses large-k pass@k analysis to highlight the importance of reasoning capabilities already covered by the base model's distribution. What does comparing On-policy RL against sampling from a uniformly random reference policy actually tell us about real-world LLM post-training?
3. Most importantly, so what? The paper contains no experiments whatsoever, not even to validate whether its assumptions approximately hold in realistic LLM reasoning.
Even if every theorem is mathematically correct, the paper essentially shows that On-policy Sampling can converge faster than Fixed Sampling in a specially constructed environment that strongly favors adaptive exploration. One could construct countless mathematical problems where adaptive exploration outperforms fixed sampling. The real question is: What does this theory actually explain about RL in real LLMs? What have we learned that we did not already know?
I do not see a convincing answer to either question.
Questions for authors
-
Validity of assumptions: What evidence supports the relevance of the hierarchical reward structure, Hölder smoothness, polynomial decay, and especially A3 and A4 to real LLM reasoning tasks?
-
Robustness of theoretical results: Does the separation between on-policy and fixed-distribution sampling still hold when A3 and A4 are relaxed? How sensitive are the results to these assumptions?
-
Uniform reference policy: Why is a uniformly random reference policy a reasonable abstraction of a pretrained LLM? Would the theoretical separation still hold for a realistic, highly nonuniform pretrained policy?
-
Necessity of Transformers: Is the Transformer architecture essential to achieving the minimax-optimal rates? Could an appropriately designed MLP or another function approximator achieve the same results?
-
Practical significance: Even if all the theoretical results are correct, what new insights do they provide about real LLM post-training beyond the already-known benefits of adaptive exploration? What practical predictions or implications follow from this theory?
3 comments
Response to Reviewer y9Gr (2/2)
W2 & Q3: Uniform reference policy
Even more problematic is the assumption that the reference policy generates uniformly random bits. ... What does comparing On-policy RL against sampling from a uniformly random reference policy actually tell us about real-world LLM post-training?
Uniform reference policy: Why is a uniformly random reference policy a reasonable abstraction of a pretrained LLM? Would the theoretical separation still hold for a realistic, highly nonuniform pretrained policy?
The reference is not a random generator of tokens: represents the responses that the pretrained model can generate, i.e., the plausible texts it has learned. Each branching of the prefix tree is a choice among plausible continuations, such as plausible next words or alternative next steps of reasoning. The binary encoding is only for convenience and is not essential.
Our question is therefore how efficiently reward feedback moves probability mass to high-reward responses that the pretrained model can already generate. This is consistent with Yue et al. (2025), who observe that RL improves sampling efficiency within the reach of the base model rather than creating new reasoning patterns. Thus, their findings support rather than contradict our setting. We added this interpretation to Section 2.
Moreover, uniformity is not essential: for a reference whose density is bounded above and below, all our rates hold with constants depending on these bounds.
W3 & Q5: What we learn
Most importantly, so what? The paper contains no experiments whatsoever ... One could construct countless mathematical problems where adaptive exploration outperforms fixed sampling. The real question is: What does this theory actually explain about RL in real LLMs? What have we learned that we did not already know?
Practical significance: ... what new insights do they provide about real LLM post-training beyond the already-known benefits of adaptive exploration? What practical predictions or implications follow from this theory?
Our theory explains, in a model of hierarchical reasoning, why and by how much on-policy RL outperforms offline reward modeling. Beyond the known benefit of adaptive data collection (e.g., Wang et al., 2018; Xie et al., 2025; Foster et al., 2025), our results give the first minimax characterization of this gain, showing its size, what it depends on, and what cannot replace it:
- The gain is exponential. For a fixed number of prompts and without regularization, reaching regret takes queries with adaptive sampling, but queries for the best method that samples from a distribution fixed in advance (Theorems 3–5 and Proposition 39). The gap widens as decreases or as approaches , that is, for tasks that require high accuracy or whose reward decays slowly over the levels. In smooth optimization, by contrast, adaptive sampling improves only the exponent of a polynomial rate (Wang et al., 2018).
- A better reward model cannot close the gap. The lower bound of Theorem 5 holds for every estimator, query depth and output policy that use data from a distribution fixed in advance. The bottleneck is how the data are collected, not how the reward model is trained.
- The optimum is attained with the components of RL post-training. Our actor–critic uses a Transformer critic and a KL-regularized Gibbs policy update without optimism bonuses, and attains the minimax rate, which no adaptive algorithm can improve beyond logarithmic factors (Theorems 3 and 4).
In our synthetic experiment (Section 6), with a Transformer critic trained by finitely many gradient steps, on-policy sampling attains 89% lower final regret than fixed sampling at the same query budget, and makes 1928 queries that can resolve the deepest level, against 4.8.
Q4: Role of the Transformer
Necessity of Transformers: Is the Transformer architecture essential to achieving the minimax-optimal rates? Could an appropriately designed MLP or another function approximator achieve the same results?
The Transformer is not essential for the rates, which hold for any class with the same approximation and covering bounds. What matters is that the critic is a sequence model: the algorithm estimates the reward from coarse to fine resolution, and the resolution of a query is simply the length of its input. An MLP would need an explicit coarsening of its input to do the same. Among sequence models, we use the Transformer, the architecture of critics and reward models in practice. We added this explanation to Section 3.1.
We would be happy to clarify any remaining concerns during the discussion period. We would greatly appreciate it if you could consider increasing the score once all concerns have been resolved.
Follow-up on our response and summary of the revision
As the discussion period is ending soon, we would like to follow up on our response.
Our results give the first minimax characterization of the advantage of on-policy RL over fixed sampling in this setting. For a fixed number of prompts and without regularization, on-policy RL reaches regret with a number of queries polynomial in , whereas every method that samples from a distribution fixed in advance needs exponentially many, and our Transformer actor–critic attains the minimax rate. Our revision addresses your three main concerns as follows.
- Readability (W1). Section 2 now begins with a description of the setting as a deterministic tree-structured MDP, before the formal definitions. A prefix is a state, and the oracle returns its value under the reference policy.
- Assumptions (W2, Q1–Q3). Solving one step of reasoning reveals the next unknown step, and this hierarchy is widely recognized. The empirical studies now cited in the introduction and Appendix A report related phenomena, such as dependencies between conceptual, procedural and strategic subproblems. The zero-mean assumption (A4) turned out to be unnecessary. The lower bounds of Theorem 5 now hold for any sampling distribution chosen before the reward is revealed, so fixed sampling is not disadvantaged by a particular choice of distribution. Our synthetic experiment uses zoom depths shallower than the numerical condition of (A3) and still shows the benefit of on-policy sampling. Section 2 now explains the reference policy as a choice among the plausible continuations that the pretrained model can generate.
- Experiments and significance (W3, Q5). Section 6 now reports a synthetic experiment with six hierarchical levels and noisy observations, in which a Transformer critic is trained by a finite number of gradient steps. With the same query budget, the final regret of on-policy sampling is 89% lower than that of fixed sampling on average. Since Theorem 5 holds for every estimator that uses data from a distribution fixed in advance, a better reward model cannot close this exponential gap.
If any of your concerns remain, we would be happy to clarify them before the discussion period ends. Otherwise, we would greatly appreciate it if you could consider updating your score.
Thank you for your time and consideration.
Response to Reviewer y9Gr (1/2)
We thank the reviewer for checking our proofs and for the frank feedback. We address the concerns and questions below. All revisions mentioned here are included in the revised PDF.
W1: Readability
Most definitions and lemmas are needed for the matching upper and lower bounds and are deferred to the appendix. What we improve instead is the guidance in the main text. In this response, we explain our motivation and the meaning of each assumption as plainly as possible. In the revised PDF, Section 2 begins with a description of the setting in standard RL terms: a prefix is a state, and the oracle returns its value under the reference policy. The formal definitions follow. If any part of the problem setting or the claims remains unclear, we would be glad to revise it and would appreciate it if you could point it out during the discussion period.
W2 & Q1 & Q2: Assumptions
Our starting point was not the conclusion but the hierarchical structure of LLM reasoning, in which solving one step reveals the next unknown step. It is hardly in doubt that reasoning has this structure. Empirical studies report related phenomena, such as dependencies between conceptual, procedural and strategic subproblems (DEPTHQA; Ko et al., 2024), a shift of the learning bottleneck from procedural to strategic steps during RL (HICRA; Wang et al., 2026), and changes of the success probability concentrated at particular steps (VinePPO; Kazemnejad et al., 2025). Formal theorem proving also uses recursive subgoal decomposition (DeepSeek-Prover-V2; Ren et al., 2025). We now cite these studies in the introduction and Appendix A. We formalized this structure as reward maximization with a nonparametric reward and then asked what RL gains. The other assumptions are regularity conditions that quantify this structure:
Relaxing (A3) and (A4) (Q2). As above, (A4) can be dropped without changing the rates. (A3), in contrast, is needed for our upper bound. Without sufficiently deep zoom, the active cells need not contain a best response, and the original on-policy rate need not hold. Both lower bounds remain valid because the enlarged class contains the original one. However, our theory does not establish the same separation over this enlarged class. Our synthetic experiment (see W3) violates the numerical condition of (A3) and still shows a benefit from on-policy sampling, i.e., an empirical benefit beyond this sufficient condition.
Fixed sampling is not disadvantaged by design. What makes fixed sampling slow is not a particular distribution but that the distribution is fixed before the reward is revealed: we found that the lower bounds of Theorem 5 extend to any such distribution, and we added this result to Section 5.
Whether real reward models satisfy our assumptions quantitatively is beyond the scope of this theoretical work. For the hierarchy itself, we refer to the empirical studies above.