- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies finite-sample policy-gradient learning, where limited independent on-policy rollouts may miss rare high-return trajectories. It proposes OPTS-TTPO: TTPO uses branch-weighted aggregation to correct the sampling distortion caused by tree branching, while OPTS uses a performance-difference estimate to allocate additional suffix rollouts to promising visited states. The paper further analyzes the posterior-selection bias introduced by this adaptive branching. Experiments show clear improvements in gradient estimation and downstream performance across MuJoCo, Atari, and LLM reasoning.
Critical strengths
-
The paper provides a careful analysis of the statistical effects of tree sampling. The Branch Aggregation Lemma clearly characterizes when branch-weighted tree statistics can recover the original chain expectation, and the paper explicitly distinguishes this setting from posterior-adaptive OPTS, where the same guarantee no longer directly applies.
-
The mechanism-level experiments are well aligned with the proposed analysis. In particular, the controlled NaivePG-vs-TTPG experiment directly validates the branch-multiplicity issue: as branching increases, NaivePG accumulates substantially larger gradient bias, whereas TTPG remains close to the no-branching reference and achieves lower MSE and better gradient alignment.
-
The empirical evaluation is broad and generally positive. OPTS-TTPO is evaluated across continuous control, Atari, and LLM reasoning under matched interaction or rollout budgets, and the results consistently show that the proposed framework is effective.
Critical weaknesses
-
The broader problem addressed by the paper is not new, and the novelty boundary is weaker than currently presented. Allocating a limited rollout budget toward more informative intermediate states or promising trajectories has already been explored in related adaptive and tree-based methods, including PROPS, VinePPO, TreeRL, LATR, TreePO, BPO, TRACE, and others. Therefore, finite-budget high-return trajectory discovery or intermediate-prefix resampling should not itself be considered the main novelty. The more specific contribution appears to be a chain-target-preserving branch aggregation scheme together with a new performance-difference-based adaptive selector and an analysis of the bias induced by that selector.
-
The posterior-adaptive selection bias is analyzed but not actually resolved. TTPO corrects branch multiplicity under prefix-measurable branching, but OPTS selects expansion states using already observed outcomes and therefore violates the condition required by the strongest expectation-preservation result. The paper decomposes and bounds the resulting bias rather than eliminating it. Moreover, this bias is partly a consequence of using a stronger posterior selection signal; methods based on prefix-local entropy or uncertainty do not necessarily incur the same form of posterior-selection bias.
-
The experiments do not sufficiently establish that the OPTS selector is better than existing adaptive allocation strategies. The paper shows clear gains over PPO, IID sampling, naive aggregation, and internal ablations, but lacks sufficiently direct matched-budget comparisons with closely related methods. More importantly, there is no controlled comparison between performance-difference-based OPTS and alternative selectors such as entropy-, uncertainty-, or other adaptive branching criteria under the same TTPG learner. Therefore, the current evidence establishes that OPTS-TTPO is effective, but not that OPTS provides a clear advantage over existing allocation mechanisms. Although part of the OPTS-TTPO implementation is provided, some key implementation components required for the full set of experiments are absent from the main code package.
Questions for authors
-
Could the authors clarify the exact novelty of OPTS-TTPO relative to existing adaptive/tree-based methods such as PROPS, VinePPO, TreeRL, LATR, TreePO, BPO, and TRACE? Is the main contribution finite-budget trajectory discovery itself, or more specifically chain-target-preserving aggregation plus posterior-adaptive branching analysis?
-
Since OPTS violates the prefix-measurability condition required by the Branch Aggregation Lemma, what statistical guarantee does the final OPTS-TTPO gradient estimator retain relative to the ordinary on-policy policy gradient? Can the posterior-selection bias be corrected rather than only bounded?
-
Could the authors directly compare Random, entropy-based, uncertainty-based, and performance-difference-based branching while fixing TTPG, the policy, the rollout budget, and all optimization settings, and jointly report trajectory coverage, gradient bias/MSE, and downstream return?
-
Why are closely related adaptive/tree-based methods missing from the main matched-budget comparisons? In particular, can the authors include representative comparisons with methods targeting similar rollout-allocation or tree-based policy-learning objectives?
5 comments
W2/Q2
W2 (excerpt): The posterior-adaptive selection bias is analyzed but not actually resolved. [...] The paper decomposes and bounds the resulting bias rather than eliminating it. [...]
Q2: Since OPTS violates the prefix-measurability condition required by the Branch Aggregation Lemma, what statistical guarantee does the final OPTS-TTPO gradient estimator retain relative to the ordinary on-policy policy gradient? Can the posterior-selection bias be corrected rather than only bounded?
Response: Relative to the ordinary on-policy policy gradient, the final OPTS-TTPO gradient retains two statistical guarantees: it corrects overcounting bias through TTPO's branch weights, and it bounds posterior-selection bias, which Proposition 2 decomposes into trajectory reweighting and max-backup prefix credit (Eq. C.12).
Exactly correcting posterior-selection bias is challenging, so we currently provide an upper bound. An inverse-probability correction would require tractable selection probabilities and sufficient support, which are difficult to establish for posterior-adaptive selection. We leave exact correction to future work.
Even so, OPTS-TTPO substantially advances existing tree-gradient methods, which typically rely on naive or heuristic gradient aggregation without such statistical guarantees: these methods neither correct overcounting bias nor bound posterior-selection bias. Specifically:
- TreeRL (Hou et al., 2025): leaf-count normalization leaves unequal sampling multiplicities uncorrected; branch selection ranks tokens across an already sampled tree (Section 3.1).
- LATR (Xing et al., 2026): shared-prefix samples are aggregated without overcounting correction; pruning uses sampled continuations (Algorithm 1).
- TreePO (Li et al., 2025): subtree-relative advantages do not correct overcounting; branching eligibility depends on later termination outcomes (Section 2.2).
- TRACE (Zou et al., 2026): its experimental updates aggregate tree samples without overcounting correction (Appendix E.4); branch allocation uses observed terminal rewards (Equations 15-16).
- BPO (He et al., 2026): tree gradients are summed without overcounting correction (Equation 5); branch locations are ranked using the completed backbone (Section 4.2).
- PROPS (Corrado and Hanna, 2023) and VinePPO (Kazemnejad et al., 2025): PROPS is not tree-structured, and VinePPO updates the policy only on original chains, so neither tree-gradient bias applies.
Table B. Overcounting correction and posterior-selection bias across related methods.
| Method | Overcounting bias | Posterior-selection bias |
|---|---|---|
| TreeRL (Hou et al., 2025) | Uncorrected | Uncorrected |
| LATR (Xing et al., 2026) | Uncorrected | Uncorrected |
| TreePO (Li et al., 2025) | Uncorrected | Uncorrected |
| TRACE (Zou et al., 2026) | Uncorrected | Uncorrected |
| PROPS (Corrado and Hanna, 2023) | N/A | N/A |
| VinePPO (Kazemnejad et al., 2025) | N/A | N/A |
| BPO (He et al., 2026) | Uncorrected | Uncorrected |
| OPTS-TTPO | Corrected | Uncorrected, but Bounded (Proposition 2) |
W3/Q3
W3 (excerpt): […] More importantly, there is no controlled comparison between performance-difference-based OPTS and alternative selectors such as entropy-, uncertainty-, or other adaptive branching criteria under the same TTPG learner. […] Although part of the OPTS-TTPO implementation is provided, some key implementation components required for the full set of experiments are absent from the main code package.
Q3: Could the authors directly compare Random, entropy-based, uncertainty-based, and performance-difference-based branching while fixing TTPG, the policy, the rollout budget, and all optimization settings, and jointly report trajectory coverage, gradient bias/MSE, and downstream return?
Response: Compared with Random, entropy-based EGB, and uncertainty-based DTS, OPTS achieves higher correct-answer coverage and larger one-update avg@32 gains in both micro and macro averages.
We hold TTPG and the step-400 Qwen3-1.7B actor/critic fixed and compare the four selectors on 902 prompts, using one update with fresh AdamW state and 32 responses per prompt for before/after evaluation. To preserve prefix-measurability, EGB/DTS do not refill the budget based on observed outcomes, so realized rollout counts differ. Appendix N of the revised manuscript provides the full protocol.
As shown in Table C, OPTS achieves the highest micro/macro coverage, and yields the largest one-update avg@32 gains (+0.308/+0.705 percentage points): its micro gain is close to EGB's +0.298, while its macro gain exceeds EGB's +0.563. DTS has the lowest measured relative bias and MSE but smaller policy gains. Thus, OPTS trades some additional bias for broader correct-answer coverage and greater one-update policy improvement.
Table C. Coverage, gradient diagnostics, and one-update policy improvement. Coverage measures prompts with at least one correct response; micro/macro averages weight problems/benchmarks equally. Changes in avg@32 are percentage points; column bests are bold.
| Selector | Rollouts | Micro coverage (%) | Macro coverage (%) | Relative bias | Relative MSE | Micro avg@32 Δ (pp) | Macro avg@32 Δ (pp) |
|---|---|---|---|---|---|---|---|
| Random | 7,216 | 71.62 | 53.73 | 1.3326 | 12.7620 | +0.135 | +0.250 |
| Entropy (EGB; 4 roots) | 7,556 | 72.73 | 54.23 | 1.1270 | 9.0498 | +0.298 | +0.563 |
| Uncertainty (DTS; 8 roots) | 8,071 | 73.17 | 54.42 | 0.9179 | 5.5552 | +0.166 | +0.183 |
| OPTS | 7,216 | 74.06 | 55.21 | 1.5803 | 10.2399 | +0.308 | +0.705 |
References: Li et al. (2026), Entropy-Gated Branching for Efficient Test-Time Reasoning, EACL. Xu et al. (2025), DTS: Enhancing Large Reasoning Models via Decoding Tree Sketching, arXiv:2511.00640.
Code availability. Could the reviewer please specify which experiment is missing key components needed for reproduction?
Q4
Q4 (excerpt): […] In particular, can the authors include representative comparisons with methods targeting similar rollout-allocation or tree-based policy-learning objectives?
Response: We added comparisons with TreeRL and TreePO on Qwen3-1.7B and Qwen3-8B. OPTS-TTPO outperforms both methods on both models in macro and micro avg@32 and pass@32.
Table D. TreeRL and TreePO comparisons on Qwen3-1.7B and Qwen3-8B. All runs use 4,096 responses per update; step-400 checkpoints are evaluated with 32 independent responses per prompt. Macro averages weight six benchmarks equally; micro averages pool 902 problems. Column bests are bold. Per-benchmark results are in Table 4 of the revised manuscript.
| Model | Method | Macro avg@32 | Micro avg@32 | Macro pass@32 | Micro pass@32 |
|---|---|---|---|---|---|
| Qwen3-1.7B | TreeRL | 0.3799 | 0.6073 | 0.5832 | 0.7727 |
| Qwen3-1.7B | TreePO | 0.2946 | 0.4877 | 0.5232 | 0.7328 |
| Qwen3-1.7B | OPTS-TTPO | 0.3967 | 0.6119 | 0.6096 | 0.7882 |
| Qwen3-8B | TreeRL | 0.4918 | 0.6843 | 0.6999 | 0.8115 |
| Qwen3-8B | TreePO | 0.3939 | 0.6221 | 0.6323 | 0.7916 |
| Qwen3-8B | OPTS-TTPO | 0.4945 | 0.6882 | 0.7101 | 0.8126 |
Manuscript revisions
-
Updated: Section 2 / Table 1. Add a comparison of unbiased estimation, monotone search-return guarantees, and formal bias analysis across related methods.
-
Updated: Section 4.3 and Appendix D.3. Clarify the common analysis set and realized expansion matching for Figure 5.
-
Updated: Appendix N / Table N.1 and Section 4.4 / Table 4. Report the selector comparison and TreeRL/TreePO results on 1.7B and 8B. Base-model comparisons will be supplemented.
We thank the reviewer for the constructive discussion of the novelty boundary, posterior-adaptive selection bias, and matched-budget comparisons. We address the concerns below.
W1/Q1
Response: Our main contribution is to strengthen finite-budget trajectory discovery through tree search with provable guarantees: unbiased tree-gradient aggregation (Lemma 1), monotone search-return improvement (Theorem 2), and a decomposed and bounded posterior-selection bias (Proposition 2). This goal raises two challenges: (i) how should the learner aggregate a tree, and (ii) where should a finite search budget be spent? We address (i) with TTPO, which performs policy-gradient updates on tree-structured data correcting branching-induced overcounting, and (ii) with OPTS, which allocates the search budget by performance-difference estimates. Because OPTS selects branches using observed outcomes, combining the two raises a third issue, posterior-selection bias, which we analyze explicitly. Specifically, our advances over prior work are as follows:
Branch aggregation (Lemma 1; TTPO). We prove the Branch Aggregation Lemma: under conditional on-policy sampling and normalized, prefix-measurable branch weights, branch-weighted tree aggregation is an unbiased estimate of the original on-policy chain gradient. Its direct and recursive forms yield TTPG and TreeGAE, which underlie TTPO. By contrast, TreeRL, LATR, TreePO, and TRACE aggregate tree gradients heuristically or naively, without guaranteeing recovery of the chain target; BPO guarantees unbiased local advantages but not an unbiased full tree gradient; VinePPO uses branches only for value estimation and updates the policy on original chains; and PROPS is not tree-structured. To our knowledge, Lemma 1 is the first result to establish when and how tree aggregation recovers the original chain gradient.
On-policy tree search (Theorem 2; OPTS). OPTS selects expansion states by a critic-derived, policy-relative performance-difference estimate and samples new on-policy suffixes from them in parallel. Under deterministic dynamics, exact values, and max-backup advantages, the expected return of the search policy improves monotonically with the search budget. None of the branching procedures in TreeRL, LATR, TreePO, TRACE, VinePPO, or BPO provides a monotone search-return guarantee.
Bias analysis (Proposition 2; OPTS-TTPO). TreeRL, LATR, TreePO, TRACE, and BPO all branch on posterior information without analyzing the resulting bias. For OPTS-TTPO, TTPO's branch weights correct branching-induced overcounting, and we decompose the remaining posterior-selection bias into trajectory reweighting and max-backup prefix credit and bound it (Proposition 2).
Table A. Theoretical guarantees and bias analysis of related methods. Each "Yes" holds under the stated conditions of the corresponding result; the restricted scope of VinePPO and BPO is explained above. TRACE refers to the optimizer instances used in its experiments (Appendix E.4).