acceptodds
Under review as a conference paper at ICLR 2027

Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers

Abstract

Reinforcement learning (RL) has become a standard tool for post-training language models on reasoning tasks, where the policy is updated by reward feedback while exploring the space of responses. Despite its empirical success, theoretical understanding of RL post-training remains limited, in particular of why on-policy exploration combined with a neural reward model is effective. In this paper, we address this question by modeling the reward as a hierarchical function on the response space: the reward consists of infinitely many local components, each of which becomes relevant only after the preceding ones have been resolved. We show that a natural Transformer-based actor-critic algorithm, which alternates between sampling from the current KL-regularized policy, fitting a Transformer critic to the observed rewards, and updating the policy, achieves the minimax optimal rates in the query budget and in the regularization strength up to logarithmic factors, and is minimax optimal for a fixed number of prompts. In contrast, we prove that sampling from the fixed reference distribution, as in offline reward modeling, can limit regret decay to a logarithmic rate. These results show that on-policy exploration progressively zooms in on the region where the reward is concentrated, and quantify its benefit for RL post-training.

Primary area:
learning theory
Keywords:
reinforcement learning, reasoning, minimax optimality

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 4 reviews, above 27% of the others.
Reviewer_y9GrOpenReview ↗
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
  1. 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?

  2. 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?

  3. 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?

  4. 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?

  5. 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
AuthorsOpenReview ↗

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

Extremely poor organization and readability. ... I had to rely on AI just to understand what the proofs were actually trying to establish.

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

Highly artificial theoretical assumptions. It feels as if the authors started with a predetermined conclusion ... 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.

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?

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:

  • Hölder smoothness (A1). Responses with close prefixes have close rewards, the standard regularity condition in nonparametric analysis.
  • Polynomial decay of cic_i. Deeper levels are finer details, and γ\gamma controls how quickly they become minor, i.e., the effective length of reasoning. The decay also makes the infinite sum well defined.
  • Positive maxima and deep-enough zoom (A2, A3). Sufficient conditions that the gain of solving the next level exceeds the loss on the levels already solved, so that the hierarchy leads to the best response. (A3) only constrains the constants of the model: the zoom depths, the smoothness, and the gain.
  • Zero mean (A4). We imposed (A4) to express that deeper levels stay hidden until the shallower ones are solved, not to hinder fixed sampling. Re-examining the proofs, we found that (A4) can be dropped. The nested supports alone already make deeper levels nearly invisible to coarse queries, so the upper bounds of Theorem 3 still hold with the same rates. The lower bounds continue to hold since the class only becomes larger. We added these results with proofs to the appendix.

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.

AuthorsOpenReview ↗

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: Ω\Omega 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 ε\varepsilon takes Θ~(ε−(2γ+1)/(γ−1))\widetilde\Theta(\varepsilon^{-(2\gamma+1)/(\gamma-1)}) queries with adaptive sampling, but exp⁡(Θ(ε−1/(γ−1)))\exp(\Theta(\varepsilon^{-1/(\gamma-1)})) queries for the best method that samples from a distribution fixed in advance (Theorems 3–5 and Proposition 39). The gap widens as ε\varepsilon decreases or as γ\gamma approaches 11, 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.

AuthorsOpenReview ↗

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 ε\varepsilon with a number of queries polynomial in 1/ε1/\varepsilon, 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.

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

This paper studies RL post-training theory. They model LLM reasoning rewards as hierarchically nested: each deeper step becomes visible only after earlier ones are solved. Under this model, they show that a PPO/PRM-style Transformer actor–critic achieves minimax-optimal rates, up to log factors, through on-policy exploration. By contrast, sampling from a fixed reference distribution, as in offline reward modeling, can only reach a logarithmic rate. On-policy RL wins because it progressively zooms in on where the next step is revealed.

Critical strengths

This paper gives a new theoretical formulation of RL post-training for LLM reasoning. The authors propose a hierarchically nested reward model in which reasoning difficulties are revealed sequentially. Each deeper reward component is supported only on a region reached by resolving the previous ones, and it is invisible from outside that region. The formulation captures a feature of multi-step reasoning that standard bandit or generic MDP analyses do not isolate.

Critical weaknesses
  1. Presentation. The presentation of this work is really hard to follow. The setting is built from many bespoke objects (bit-interleaving embedding, dyadic cubes, nested cells, zoom depths, cube-average oracle) and is never stated as a standard decision problem. It is in fact a special case of a deterministic tree-structured MDP: states are prefixes, transitions are known, the reward is terminal, and the oracle is the reference-policy value of a prefix. The hierarchical reward is essentially a combination-lock structure. Stating this view explicitly would make the paper much easier to follow and clarify its relation to existing results, e.g., combination-lock lower bounds and coverage requirements in offline RL.
  2. Strong and inpractice assumptions. Several assumptions are hard to justify for real LLM reasoning: (a) The model assumes the locally best step always leads to the final answer, and that a wrong prefix can never be recovered. In practice, reasoning models often revise earlier steps (“wait, let me think again”), so an early mistake is not necessarily fatal. (b) Two responses are considered similar only if they share a long prefix, and early tokens dominate the reward while later tokens matter less and less. In reality, two responses that differ in their first few tokens can be semantically identical. Conversely, a single late token, such as the final answer, can completely change the reward. (c) Rewards for different prompts are assumed to be unrelated, so nothing learned on one prompt helps on another. In practice, generalization across prompts is the main reason to train a shared reward model. Overall, these assumptions limit the practical relevance of the theory.
Questions for authors

See weakness.

2 comments
AuthorsOpenReview ↗

Response to Reviewer LZAv

We thank the reviewer for the helpful feedback, in particular the suggestion on the presentation. We address the concerns below. All revisions mentioned here are included in the revised PDF.

W1: Presentation as a tree-structured MDP

The presentation of this work is really hard to follow. ... It is in fact a special case of a deterministic tree-structured MDP ... The hierarchical reward is essentially a combination-lock structure. Stating this view explicitly would make the paper much easier to follow and clarify its relation to existing results, e.g., combination-lock lower bounds and coverage requirements in offline RL.

Your reading is correct: our setting is a deterministic tree-structured MDP whose states are prefixes, whose transitions are known, whose reward is terminal, and whose oracle returns the value of a prefix under the reference policy. In this view, a dyadic cube is simply a prefix, regarded as the set of its completions, and the cube average is its value. The hierarchical reward has a combination-lock structure (Koenig and Simmons, 1993; Du et al., 2019), in which solving one level reveals the next. We added this view at the beginning of Section 2, before the formal definitions. It also clarifies the relation to the results you mention:

  • Combination locks. Combination-lock lower bounds show that passive data collection can require a number of trajectories exponential in the horizon (Xiao et al., 2022). In our setting, fixed sampling faces the same barrier: in the weak-regularization regime of Theorem 5, reaching worst-case regret ε\varepsilon requires at least Mexp⁡(c ε−1/(γ−1))M\exp(c\,\varepsilon^{-1/(\gamma-1)}) queries. Under the hierarchical reward, our on-policy actor-critic overcomes this barrier with a polynomial rate. Beyond this, our results give the minimax rate for a fixed number of prompts, up to logarithmic factors, which shows how the difficulty depends on the decay and smoothness of the levels. This rate is attained by on-policy RL with a Transformer critic, as in LLM post-training.
  • Coverage in offline RL. The reference mass of the correct cell at level kk is 2−dLk2^{-dL_k}, so the coverage coefficient of reference data with respect to the policy concentrated on this cell is 2dLk2^{dL_k}, exponential in the depth. This is the mechanism behind the fixed-sampling lower bound of Theorem 5, whereas on-policy sampling raises the probability of reaching this region as it learns.

We discuss these relations in Appendix A, to which Section 2 refers. There we also compare Theorem 5 with guarantees in offline RL, which are stated through coverage coefficients, and our setting with adaptive exploration in block MDPs (Du et al., 2019), whose guarantees are polynomial in the number of latent states. If the prefixes themselves are taken as the states, there are 2dh2^{dh} states at depth hh, which cannot be merged into fewer latent states, so these guarantees grow exponentially with the depth.

W2: Self-correction, similarity of responses, and relations between prompts

(a) The model assumes the locally best step always leads to the final answer, and that a wrong prefix can never be recovered. ... (b) Two responses are considered similar only if they share a long prefix, and early tokens dominate the reward while later tokens matter less and less. ... (c) Rewards for different prompts are assumed to be unrelated ...

We do not claim that our theory reflects every aspect of RL for LLMs. Our contribution is to show, in the form of minimax optimal rates, that RL is effective for hierarchical reasoning. For more complex structures, further algorithmic devices would certainly help. However, a model including all such features would obscure which of them determines the rates, and we therefore isolate the hierarchy to identify its effect. Accordingly, our model does not capture the following:

  • (a) Self-correction. Revisions within a response.
  • (b) Similarity of responses. Responses that differ in wording but not in meaning, and a single late token that decides the reward, since our model compares responses through their common prefix.
  • (c) Relations between prompts. Generalization across prompts, which requires additional assumptions on how prompts are related and is beyond our focus on the hierarchy within each prompt.

These are interesting directions, and we added them to the limitations and future work.


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.

AuthorsOpenReview ↗

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 ε\varepsilon with a number of queries polynomial in 1/ε1/\varepsilon, 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 two main concerns as follows.

  • Presentation (W1). Following your suggestion, Section 2 now begins with the view of our setting as a deterministic tree-structured MDP with a combination-lock reward, before the formal definitions. Appendix A relates our results to combination-lock lower bounds and to coverage in offline RL. In this view, fixed sampling faces the combination-lock barrier (Theorem 5), and our on-policy actor–critic overcomes it with a polynomial rate.
  • Assumptions (W2). We added self-correction, similarity of responses, and relations between prompts to the limitations and future work (Appendix B). Our model isolates the hierarchy so that its effect on the rates can be identified. Within this model, the zero-mean assumption (A4) turned out to be unnecessary, and the lower bounds of Theorem 5 now hold for any sampling distribution chosen before the reward is revealed.

The revision also adds a synthetic experiment (Section 6) with noisy observations and a Transformer critic 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.

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.

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

This paper studies the statistical role of on-policy exploration in RL post-training. It models each prompt’s reward as an infinitely deep hierarchy of smooth components supported on nested regions of a response embedding space. Under this model, the authors derive minimax regret rates for adaptive algorithms, prove a fixed-reference-sampling lower bound, and give an on-policy actor-critic procedure with a Transformer critic and Gibbs actor that matches the rates up to logarithmic and prompt-count factors. The paper interprets the result as a formal explanation of why progressively concentrating on promising response regions can help with multi-stage reasoning rewards.

Critical strengths
  1. The paper offers a novel theoretical abstraction of progressive exploration in multi-stage reasoning rewards. The nested-cell construction makes the difference between fixed sampling and adaptive sampling mathematically explicit.

  2. The minimax framing and fixed-sampling lower bound are valuable. The work does more than propose an algorithm: it identifies the statistical source of the claimed advantage and relates the result to continuum-armed bandits and KL-regularized policy optimization.

Critical weaknesses
  1. The model is highly stylized relative to real LLM reasoning. Responses are infinite binary sequences embedded into a dyadic cube, and the hierarchy, smoothness, zero-mean, and separation assumptions are imposed by construction. The paper does not show that real language-model response spaces or reward models approximately satisfy these assumptions.

  2. There are no experiments, even on the synthetic hierarchical reward class. The proposed actor-critic assumes exact ERM and exact Gibbs sampling, while the paper explicitly leaves optimization and practical approximation largely open. Without an empirical study, it is difficult to assess whether the mechanism survives finite optimization, approximate sampling, model misspecification, and noisy rewards.

Questions for authors
  1. Can the authors provide a synthetic experiment that verifies the predicted rates and compares on-policy sampling, fixed-reference sampling, approximate Gibbs sampling, and finite-step Transformer actor-critic training?

  2. Which assumptions are essential for the lower bound and which are technical conveniences? In particular, how does the result change if the nested structure is approximate or the deeper components do not have exact zero mean outside the active cell?

  3. Can the authors quantify the effect of approximate ERM, approximate Gibbs sampling, finite critic capacity, and optimization error on regret? These are central to interpreting the result as relevant to practical RL post-training.

  4. The prompt-wise upper bound contains an extra factor and there is a parameter band without a guarantee. How substantial are these gaps in realistic parameter regimes?

3 comments
AuthorsOpenReview ↗

Response to Reviewer wSf4 (1/2)

We thank the reviewer for the careful reading and the constructive feedback. We address the concerns and questions below. All revisions mentioned here are included in the revised PDF.

W1: Stylized model

The model is highly stylized relative to real LLM reasoning. ... The paper does not show that real language-model response spaces or reward models approximately satisfy these assumptions.

We understand that our model does not capture every aspect of LLM reasoning. Our focus is the hierarchical structure of reasoning, in which solving one step reveals the next unknown step. This structure is widely recognized, and 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. No prior work has characterized how this structure determines the optimal rates of RL. In this model, we show that on-policy RL is minimax optimal for a fixed number of prompts and provably better than fixed sampling. The other assumptions are regularity conditions that quantify this structure, each with a simple meaning, and (A4) turns out to be unnecessary:

  • Smoothness (A1). Responses with close prefixes have close rewards.
  • Decay of cic_i. Deeper levels are finer details, and γ\gamma controls how quickly they become minor, i.e., the effective length of reasoning. The decay also makes the reward well defined.
  • Separation (A2, A3). A sufficient condition that the gain of solving the next level exceeds the loss on the levels already solved, so that the hierarchy leads to the best response. (A3) only constrains the constants of the model: the zoom depths, the smoothness, and the gain.
  • Zero mean (A4). We imposed (A4) to express that deeper levels stay hidden until the shallower ones are solved. Re-examining the proofs, we found that (A4) can be dropped. The nested supports alone already make deeper levels nearly invisible to coarse queries, so the upper bounds of Theorem 3 still hold with the same rates. The lower bounds continue to hold since the class only becomes larger. We added these results with proofs to the appendix.

Our synthetic experiment below also violates the numerical condition of (A3), and still shows the benefit of on-policy sampling. Whether real reward models satisfy these conditions quantitatively is beyond the scope of this theoretical work. For the hierarchy itself, we refer to the empirical studies above.

W2 & Q1: Synthetic experiment

There are no experiments, even on the synthetic hierarchical reward class. ... it is difficult to assess whether the mechanism survives finite optimization, approximate sampling ...

Can the authors provide a synthetic experiment that verifies the predicted rates and compares on-policy sampling, fixed-reference sampling, approximate Gibbs sampling, and finite-step Transformer actor-critic training?

We added a synthetic experiment as Section 6, with details in Appendix H. The reward has six hierarchical levels on [0,1]2[0,1]^2 (4096 cells at the finest resolution), and each prefix query is observed with Gaussian noise. A causal Transformer critic is trained by a finite number of gradient steps, and the actor is the Gibbs policy of the learned critic. We compare fixed sampling from the uniform reference with on-policy sampling, using the same model, initialization, noise, query budget, and number of optimizer steps, over ten paired seeds. The actor is computed exactly on the grid. We discuss approximate Gibbs sampling in the next section.

  • Regret. The final regret was 0.055±0.0310.055\pm0.031 for fixed sampling and 0.006±0.0120.006\pm0.012 for on-policy sampling (mean ±\pm SD), 89% lower on average.
  • Mechanism. Under fixed sampling, the number of observations inside the correct parent cell of each level decreased geometrically with the level, matching the expected counts under uniform sampling. At the deepest level, it was 4.8 (expected: 6), whereas on-policy sampling made 1928 observations. The final actor put 0.7% and 13.1% of its mass, respectively, on the deepest correct cell (25.7% for the optimal policy).

Regarding the predicted rates, we do not fit the exponents. They are minimax rates, which describe the hardest reward in the class, whereas any experiment runs on particular rewards, whose regret can decay faster. The experiment instead tests the mechanism behind the separation.

AuthorsOpenReview ↗

Response to Reviewer wSf4 (2/2)

W2 & Q3: Approximate ERM, approximate Gibbs sampling, and finite capacity

The proposed actor-critic assumes exact ERM and exact Gibbs sampling ... model misspecification, and noisy rewards.

Can the authors quantify the effect of approximate ERM, approximate Gibbs sampling, finite critic capacity, and optimization error on regret? ...

Our results concern statistical efficiency, i.e., the number of reward queries, such as rollouts and reward-model calls, needed to reach a given regret. Minimax guarantees for deep networks and Transformers are proved for the global empirical risk minimizer (Suzuki, ICLR 2019; Suzuki and Nitanda, NeurIPS 2021; Takakura and Suzuki, ICML 2023), with the optimization error as a separate term in Imaizumi and Fukumizu (AISTATS 2019) and Schmidt-Hieber (2020). Our critic analysis follows this framework. For the actor, prior statistical analyses of KL-regularized RL likewise use exact Gibbs policy updates (Xiong et al., ICML 2024; Zhao et al., ICML 2025). RLHF methods such as PPO and DPO approximate this policy with a parametric one (Ouyang et al., 2022; Rafailov et al., 2023). We adopt both idealizations to separate this question from computation. Nevertheless, most of the listed effects are already covered or can be quantified:

  • Approximate ERM and optimization error. An optimization error ϵopt\epsilon_{\mathrm{opt}} in the empirical risk enters our risk bound additively, so the regret bound of Theorem 3 is unchanged as long as ϵopt≲(pS/M)εh2\epsilon_{\mathrm{opt}}\lesssim(p_S/M)\varepsilon_h^2 at phase hh.
  • Approximate Gibbs sampling. For the data-collection steps of our algorithm, we expect the same rates if the sampling distribution in every phase is within constant density ratios of the Gibbs policy.
  • Finite critic capacity and model misspecification. This is already part of our theory: as in nonparametric regression, the critic risk is bounded by the sum of the approximation error of order N−2α/dN^{-2\alpha/d} for a network of size NN and the estimation error (Lemma 23), and Theorem 3 follows by balancing the two.
  • Noisy rewards. Our observations already include sub-Gaussian noise (Section 2.3), and all rates hold with constants depending on the noise level.

Q2: Assumptions essential for the lower bound

Which assumptions are essential for the lower bound and which are technical conveniences? In particular, how does the result change if the nested structure is approximate or the deeper components do not have exact zero mean outside the active cell?

Relaxing an assumption on the reward only enlarges the class, so the lower bounds remain valid. What these assumptions affect is whether our upper bound for on-policy RL still holds.

  • Zero mean. (A4) turned out to be unnecessary. As above, it can be dropped without changing the rates of Theorem 3, so the minimax rates and the separation are unchanged.
  • Approximate nesting. The lower bounds still hold by the same argument. The nesting itself, however, is not a technical convenience: it is the hierarchy, in which a deeper level becomes visible only after the shallower ones are solved. If deeper components were substantially nonzero outside their active cells, a deeper level would be visible without solving the shallower ones, and the reward would no longer be hierarchical, which is outside the phenomenon our model is designed to capture.

Q4: Size of the gaps

The prompt-wise upper bound contains an extra factor and there is a parameter band without a guarantee. How substantial are these gaps in realistic parameter regimes?

Up to logarithmic factors, the ratio of the upper to the lower bound under weak regularization is M(1+d/(2α))(γ−1)/(2γ+1)M^{(1+d/(2\alpha))(\gamma-1)/(2\gamma+1)}, and the ratio of the endpoints of the band is M(1+d/(2α))γ/(2γ+1)M^{(1+d/(2\alpha))\gamma/(2\gamma+1)}. For a fixed number of prompts, both reduce to logarithmic factors. These factors affect only the dependence on MM, not on nn, so the separation from fixed sampling is unaffected. They arise because our risk bound for the shared critic holds on average over prompts, not for each prompt separately. With a separate critic per prompt, MζMM^{\zeta_M} can be reduced to MM up to logarithmic factors, which closes both gaps up to logarithmic factors. A shared critic could instead benefit from structure shared across prompts, but this requires additional assumptions on how prompts are related, which are beyond our focus on the hierarchy within each prompt.


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.

AuthorsOpenReview ↗

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 ε\varepsilon with a number of queries polynomial in 1/ε1/\varepsilon, 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 two main concerns as follows.

  • Experiments (W2, Q1). 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, and on-policy sampling makes 1928 queries that can resolve the deepest level, against 4.8.
  • Assumptions (W1, Q2). 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, and the lower bounds of Theorem 5 now hold for any sampling distribution chosen before the reward is revealed. Under this hierarchical structure, the limitation of fixed sampling therefore lies in how the data are collected, and a better reward model cannot remove it.

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.

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

Paper looks at KL-regularized RL post-training when the reward is hierarchical. For each prompt the reward is f=∑icihif = \sum_i c_i h_i with ci≍i−γc_i \asymp i^{-\gamma}, and each hih_i only lives inside a small cell around the maximizer of the level before it. The learner can query any prefix and gets back the average terminal reward over reference-policy completions, plus noise. Because of the zero-mean assumption (A4), a coarse prefix tells you nothing about levels it hasn't reached yet.

The algorithm is an on-policy actor-critic. Each round it samples from the Gibbs policy of the current score, picks how deep to query based on the actor's own prefix probabilities, refits a causal Transformer critic by least squares on the new batch, and updates the score only on cubes with enough actor mass.

There are three main results. With weak or no regularization the regret is O~((n/MζM)−(γ−1)/(2γ+1))\tilde O\big((n/M^{\zeta_M})^{-(\gamma-1)/(2\gamma+1)}\big), and the bottleneck is how deep the budget lets you go. With a large budget it is O~(ρ (nρ2+1/γ/M)−2α/(2α+d))\tilde O\big(\rho\,(n\rho^{2+1/\gamma}/M)^{-2\alpha/(2\alpha+d)}\big), which is basically local Hölder estimation near the optimum. Lower bounds over all adaptive algorithms match these in nn and ρ\rho, and match fully up to logs when MM is fixed. Finally, if responses are drawn from the fixed reference distribution, regret can only decay logarithmically in the weak-regularization regime, or picks up a factor ec0ρ−1/γe^{c_0\rho^{-1/\gamma}} when the budget is large.

There are no experiments.

Critical strengths
  1. The lower bounds hold for any adaptive algorithm, not just the one proposed. Since they match the upper bounds in nn and ρ\rho, the rates describe the problem itself rather than a loose analysis of Algorithm 1. I also liked the argument in Lemma 37, which tracks a Hellinger-affinity potential along adaptive histories. It handles adaptivity cleanly.

  2. The separation result is fair to the fixed-sampling side. Algorithms in Aunif\mathcal A_{\rm unif} can choose query depth adaptively, reuse all past data and output any policy they like. Only the response distribution is frozen. Deep levels still show up only through exponentially rare events, and Proposition 39 shows the logarithmic rate is actually achieved, so the bound is tight there. This gives a statistical reason, separate from optimization, for why changing the response distribution can matter.

Critical weaknesses
  1. A lot rides on the modeling assumptions. (A4) in particular: unresolved levels cancel exactly under averaging, and that is what makes deep levels invisible to coarse queries. On top of that the paper assumes a uniform reference distribution, a prefix oracle that returns reference-completion averages, known θ\theta, exact ERM and exact Gibbs sampling. I can't tell how much of the separation survives approximate cancellation, trajectory-level rewards, a skewed base model or approximate optimization. The authors are honest about the optimization part. Still, I read this as a theoretical separation result, and not yet as an account of what happens in real post-training.

  2. In the large-budget regime the separation is smaller than the abstract makes it sound. Proposition 40 says that for any fixed ρ>0\rho > 0, fixed sampling gets the same exponent of nn as the on-policy method. What changes is the prefactor, ec0ρ−1/γe^{c_0\rho^{-1/\gamma}} instead of something polynomial in ρ−1\rho^{-1}. That's a real difference, but it's about how the bound scales with ρ\rho, and the abstract and Section 5 lead with the logarithmic rate. I'd like this stated plainly in the main text.

  3. Optimality in MM is incomplete, and there's a band of ρ\rho with no guarantee. The weak-regularization upper bound depends on n/MζMn/M^{\zeta_M} and the lower bound on n/Mn/M. For fixed MM that's a log factor; for growing MM it's polynomial. Theorem 3 also leaves a range of ρ\rho between its two cases uncovered. The authors say all this themselves, so I'm not weighting it much, but "minimax optimal" really means "minimax optimal for fixed MM".

  4. I'm not sure the Transformer matters for the statistics. The comparators in Lemmas 17 and 27 store the correct-path bits as weights, and the proof only uses the covering number of the class. I think any nonparametric class with similar approximation and covering bounds would give the same rates. That's fine, but the title and abstract lead with Transformers, so a sentence on what (if anything) is specific to them would help.

Questions for authors

In the rebuttal, I’d most like to see responses to the weaknesses listed above and to the questions below.

Q1. By Lemma 19(iii), each step selects at most 1/κ01/\kappa_0 cubes and splits each into 2dS2^{dS} children with S=O(log⁡L)S = O(\log L). So the partition stays polynomial in size, and it looks like child prefix masses can be computed exactly from the stored critics. Is that correct? If so, the only real computational gap is the non-convex ERM. With an ϵopt\epsilon_{\rm opt}-approximate ERM, does ϵopt\epsilon_{\rm opt} just add to (56), or does it get amplified by the pointwise step in (57)?

Q2. Where does MζMM^{\zeta_M} come from? Here is how I read Lemma 23 and the proof of Proposition 18, and please correct me if I'm wrong. One factor of MM comes from turning joint L2L_2 risk into pointwise accuracy (the M/pSM/p_S in (57)). Another comes from the covering entropy, since one network has to fit MM unrelated rewards. The last, Md/(2α)M^{d/(2\alpha)}, comes from needing N≳Md/(2α)N \gtrsim M^{d/(2\alpha)} so that the approximation error also drops below rh∝1/Mr_h \propto 1/M. If that's right, a separate critic per prompt should remove the second and third factors, and a prompt-wise risk bound would remove the first. Is there something that blocks this, or is the shared critic mainly there to look like practice?

Q3. How much does the fixed-sampling lower bound depend on exact cancellation? Suppose ∣∫gi dμ∣≤ϵi\left|\int g_i\,d\mu\right| \le \epsilon_i instead. Coarse queries would then leak a little about deeper levels. Is there a threshold on ϵi\epsilon_i, relative to cic_i or to 2−dℓ⋆i2^{-d\ell_\star i} say, below which the logarithmic bound still holds? Separately, I'd guess the bound extends to any fixed sampling distribution chosen before the reward is revealed, by putting the nested cells where that distribution has little mass. If so, a remark would make clear that the separation is about adaptivity and not about uniformity.

3 comments
AuthorsOpenReview ↗

Response to Reviewer Xuvz (1/2)

We thank the reviewer for the careful reading and the detailed, constructive feedback. We address the concerns and questions below. All revisions mentioned here are included in the revised PDF.

W1 & Q3: Approximate cancellation (A4)

(A4) in particular: unresolved levels cancel exactly under averaging ... I can't tell how much of the separation survives approximate cancellation ...

How much does the fixed-sampling lower bound depend on exact cancellation? ... Is there a threshold on ϵi\epsilon_i ... below which the logarithmic bound still holds?

Thank you for this sharp question. Re-examining the proofs, we found that the separation survives approximate cancellation in full, and no threshold on ϵi\epsilon_i is needed. Keeping the nested supports and (A1)–(A3), we replace (A4) by ∣∫gidμ∣≤ϵi\left\lvert\int g_i d\mu\right\rvert\le\epsilon_i with arbitrary ϵi\epsilon_i, and the upper bounds of Theorem 3 still hold with the same rates. In other words, (A4) can be removed. Since this class contains the zero-mean class, the lower bounds of Theorems 4 and 5 continue to hold, so Theorem 3 remains minimax optimal. We added these results with proofs to the appendix.

Q3: Arbitrary fixed sampling distributions

Separately, I'd guess the bound extends to any fixed sampling distribution chosen before the reward is revealed, ... a remark would make clear that the separation is about adaptivity and not about uniformity.

Yes, your guess is correct. For any sampling distribution chosen before the reward is revealed, placing the nested cells where it has small mass gives both lower bounds of Theorem 5. We restated Theorem 5 for this class of algorithms in Section 5, with the proofs in Appendix G, and the abstract, the contributions and the conclusion now refer to a distribution fixed in advance. The separation is thus about adaptivity, not uniformity.

W1: Other modeling assumptions

The paper assumes a uniform reference distribution, a prefix oracle that returns reference-completion averages, known θ\theta ...

  • Skewed base model. If the uniform reference is replaced by a skewed reference policy whose density with respect to μ\mu is bounded above and below, all our rates hold up to constants.
  • Prefix oracle and trajectory-level rewards. The prefix oracle is natural for LLM reasoning: completing a prefix with one rollout of the reference policy and observing the trajectory-level reward gives an unbiased observation of Q(m,D)Q(m,D), as in Math-Shepherd (Wang et al., 2024). Our model already covers this observation, since the randomness of the completion is part of the sub-Gaussian noise in Section 2.3.
  • Known θ\theta. Knowing the structural parameters θ\theta is standard in nonparametric minimax analysis, and our lower bounds hold even for learners that know θ\theta. For a fixed number of prompts, unknown θ\theta in a known compact range can be handled by a standard data-splitting argument, which keeps both rates up to logarithmic factors. The budget is split among a polylogarithmic number of candidate schedules on a grid, and the output policy is selected with validation queries.

W1 & Q1: Exact ERM and exact Gibbs sampling

exact ERM and exact Gibbs sampling ... approximate optimization.

By Lemma 19(iii), ... child prefix masses can be computed exactly from the stored critics. Is that correct? ... With an ϵopt\epsilon_{\mathrm{opt}}-approximate ERM, does ϵopt\epsilon_{\mathrm{opt}} just add to (56), or does it get amplified by the pointwise step in (57)?

As you suggest, exact Gibbs sampling is computationally feasible in our algorithm. The score WhW_h of Algorithm 1 is piecewise constant on a partition of size polynomial in nn and MM, so prefix masses are finite sums and the Gibbs actor can be sampled autoregressively. The remaining computational assumption is a global empirical risk minimizer, as in the minimax analyses of deep networks and Transformers (Imaizumi and Fukumizu, AISTATS 2019; Suzuki, ICLR 2019; Suzuki and Nitanda, NeurIPS 2021; Takakura and Suzuki, ICML 2023).

If the ERM is ϵopt\epsilon_{\mathrm{opt}}-approximate in the average empirical squared loss, ϵopt\epsilon_{\mathrm{opt}} adds to (56) and is amplified by M/pSM/p_S in (57). Hence ϵopt≲(pS/M)εh2\epsilon_{\mathrm{opt}}\lesssim(p_S/M)\varepsilon_h^2 preserves the target accuracy εh\varepsilon_h of phase hh. Empirically, our new synthetic experiment (Section 6) trains a Transformer critic by a finite number of gradient steps instead of exact ERM. With the same query budget, the final regret of on-policy sampling is still 89% lower than that of fixed sampling on average.

AuthorsOpenReview ↗

Response to Reviewer Xuvz (2/2)

W1: Relevance to real post-training

Still, I read this as a theoretical separation result, and not yet as an account of what happens in real post-training.

We agree that our result is a theoretical separation. However, the structure behind it, in which solving one step reveals the next unknown step, is a widely recognized feature of LLM reasoning. 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. No prior work has characterized how this structure determines the optimal rates of RL and the advantage of on-policy over fixed sampling. We formalize this structure as regularized reward maximization with a nonparametric reward, and show that on-policy RL is minimax optimal for a fixed number of prompts and provably better than fixed sampling.

W2: Separation in the large-budget regime

In the large-budget regime the separation is smaller than the abstract makes it sound. ... I'd like this stated plainly in the main text.

As the reviewer notes, for fixed ρ>0\rho>0 fixed sampling attains the same exponent of nn (Proposition 40), and the difference appears in the prefactor. For larger budgets, fixed sampling reaches this rate only with the multiplicative price exp⁡(c0ρ−1/γ)\exp(c_0\rho^{-1/\gamma}). However, the logarithmic bound of Theorem 5 is not confined to a narrow regime: it holds for all ρ≲(log⁡(en/M))−γ\rho\lesssim(\log(en/M))^{-\gamma}, a threshold that decreases only polylogarithmically in nn. Over this range, on-policy sampling attains a polynomial rate, except in the narrow band of Theorem 3, while every fixed-sampling method is limited to a logarithmic one. The paragraph after Theorem 5 in Section 5 states both facts, and the third contribution states that the logarithmic rate holds when the regularization is weak. We added the same qualification, "when the regularization is weak", to the abstract.

W3 & Q2: Dependence on MM and the band of ρ\rho

Optimality in MM is incomplete, and there's a band of ρ\rho with no guarantee. ... "minimax optimal" really means "minimax optimal for fixed MM".

Where does MζMM^{\zeta_M} come from? ... Is there something that blocks this, or is the shared critic mainly there to look like practice?

Your reading of the three factors is correct, and the shared critic is indeed chosen to mirror practice, where one critic or reward model is trained across many prompts. With a separate critic per prompt and a prompt-wise risk bound, MζMM^{\zeta_M} can be reduced to MM up to logarithmic factors, which closes both the gap in MM and the band of ρ\rho up to logarithmic factors. We keep the shared critic in our main results. As stated in the abstract and Section 4, minimax optimality refers to a fixed number of prompts.

W4: Role of the Transformer

I'm not sure the Transformer matters for the statistics. ... a sentence on what (if anything) is specific to them would help.

As the reviewer notes, the rates themselves hold for any class with the same approximation and covering bounds. What is specific to our critic is that it is a sequence model: the algorithm estimates the reward from coarse to fine resolution, i.e., from shallow levels to deep ones, 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 because it is the architecture of critics and reward models in practice. We added this explanation to Section 3.1, where the Transformer critic is introduced.


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.

I appreciate the authors' thoughtful rebuttal and additional results, which address several of my technical concerns. However, I remain unconvinced about how well the findings translate to real LLM post-training, given the strong hierarchical reward assumptions and idealized learning setting. The synthetic experiment is helpful, but does little to bridge this gap. About presentation, i think it could be clearer and more focused on the main insights and the writing. While I recognize the theoretical value of the work, I still find it slightly below the acceptance bar for a venue like ICLR and will keep my rating unchanged.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions and new results

We thank all reviewers for their careful reading and constructive feedback. Our paper studies RL post-training for reasoning with a hierarchical structure, in which solving one step reveals the next unknown step. We show that on-policy RL with a Transformer critic attains the minimax rate, whereas every method that samples from a distribution fixed before the reward is revealed is limited to a logarithmic rate over a wide range of regularization strengths. Below, in light of the reviewers' comments, we restate the significance of our results and summarize our revisions. All revisions are included in the revised PDF.

Significance

The statistical theory of deep networks and Transformers has studied how well a fixed target function can be estimated from data drawn from a fixed distribution (e.g., Suzuki, 2019; Takakura and Suzuki, 2023). This theory has not handled a nested hierarchy over sequences, in which the resolution of the problem changes with depth. In our setting, in contrast, the learner has to estimate a finer reward component on a smaller region as learning proceeds, because a deeper level is nonzero only inside the region reached by solving the shallower ones, and on-policy data move into that region. Such a nested structure arises naturally in logical reasoning. Reviewer LZAv noted that our formulation "captures a feature of multi-step reasoning that standard bandit or generic MDP analyses do not isolate", and Reviewer wSf4 that it "offers a novel theoretical abstraction of progressive exploration in multi-stage reasoning rewards".

We are the first to show, with matching upper and lower bounds, that this structure produces a large separation between on-policy and fixed sampling, polynomial versus logarithmic when the regularization is weak, and that a Transformer actor–critic attains the minimax rate for a fixed number of prompts. As Reviewer Xuvz noted, the lower bounds "describe the problem itself rather than a loose analysis of Algorithm 1", so the separation "gives a statistical reason, separate from optimization, for why changing the response distribution can matter". We believe this is an important step toward understanding the training of Transformers for LLM reasoning.

New theoretical results (with proofs)

  • Removal of (A4). The exact zero-mean assumption (A4) was one of the assumptions that the reviewers questioned. On re-examination, we found that it can be dropped. The upper bounds of Theorem 3 hold with the same rates, and the lower bounds remain valid because the class only becomes larger (Appendix; Reviewers Xuvz, wSf4, y9Gr).
  • Any fixed sampling distribution. The lower bounds of Theorem 5 extend to any sampling distribution chosen before the reward is revealed. The separation therefore comes from adaptivity, not from the uniformity of the sampling distribution. Theorem 5 is now stated for this class, and the abstract, contributions and conclusion refer to a distribution fixed in advance (Section 5 and Appendix G; Reviewers Xuvz, wSf4, y9Gr).

New experiment

  • A synthetic experiment with six hierarchical levels and a Transformer critic 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, and on-policy sampling makes 1928 queries that can resolve the deepest level, against 4.8 for fixed sampling (Section 6 and Appendix H; Reviewers Xuvz, wSf4, y9Gr).

Other revisions

  • Standard RL view. Section 2 now begins with the setting as a deterministic tree-structured MDP. Its relation to combination locks, to coverage in offline RL and to adaptive exploration in block MDPs is discussed in Appendix A (Reviewers LZAv, y9Gr).
  • Empirical motivation. The introduction now cites empirical studies of related phenomena in LLM reasoning (Reviewers Xuvz, wSf4, y9Gr).
  • Scope of the claims. "When the regularization is weak" was added to the abstract. Section 5 and the contributions state the range of ρ\rho where the separation holds, and minimax optimality refers to a fixed number of prompts (Reviewers Xuvz, wSf4).
  • Role of the Transformer. Section 3.1 now states what is specific to a sequence-model critic (Reviewers Xuvz, y9Gr).
  • Limitations. Appendix B now lists adaptivity to unknown structural parameters, self-correction within a response, similarity of responses, and generalization across prompts (Reviewers Xuvz, LZAv).

We hope these revisions address the main concerns, and we would be happy to discuss any remaining questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.