acceptodds
Under review as a conference paper at ICLR 2027

OPTS-TTPO: Enhancing Finite-Sample Policy Gradient Learning with Tree Search

Abstract

The policy-gradient theorem expresses the exact gradient as an expectation under the current policy, but practical methods estimate it from finitely many on-policy trajectories. Rare high-return trajectories may be missing from the policy-gradient estimate. We study whether tree search can improve their coverage under a finite budget while controlling the induced gradient bias. We introduce On-Policy Parallel Tree Search (OPTS) and Tree Trajectory Policy Optimization (TTPO) through on-policy tree trajectories, which sample new suffixes from the current policy at visited states. This requires no action-distribution correction, but branching changes state visitation. Our Branch Aggregation Lemma underpins TTPO: branch-weighted tree statistics recover chain expectations when branch choices and weights are fixed before outgoing transitions are sampled. OPTS selects expansion states using estimated performance differences. Under deterministic dynamics, exact values, and max-backup advantages, the induced search policy's expected return improves monotonically with the budget. Adaptive expansion violates the lemma's condition; we bound its gradient bias and show that max backup adds prefix credit to actions leading to better discovered suffixes. Against a finite chain reference, TTPG's measured bias stays near its no-branching level while NaivePG's bias grows from to . Exact-value search is monotone and learned-critic summaries improve in aggregate. At matched budgets, reward- and value-guided OPTS improve correct-answer coverage and majority-vote accuracy over i.i.d. baselines. The coverage–bias diagnostic shows a larger gain from OPTS + TTPG at a smaller bias shift than Fixed-branch + NaivePG. Under matched interaction or rollout budgets, OPTS-TTPO improves MuJoCo tail returns over PPO by up to , raises Atari-57 human-normalized IQM from to , and improves micro-averaged pass@32 across all four Qwen3 models.

Primary area:
reinforcement learning
Keywords:
tree search, policy gradients, on-policy reinforcement learning, credit assignment

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_DFoiOpenReview ↗
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
  1. 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.

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

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

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

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

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

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

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

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

W1 (excerpt): [...] 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.

Q1 (excerpt): [...] Is the main contribution finite-budget trajectory discovery itself, or more specifically chain-target-preserving aggregation plus posterior-adaptive branching analysis?

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:

  1. 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.

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

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

MethodUnbiasedness guaranteeMonotone search-return guaranteeFormal bias analysis
TreeRL (Hou et al., 2025)No (heuristic)No (heuristic)No
LATR (Xing et al., 2026)No (naive)No (heuristic)No
TreePO (Li et al., 2025)No (naive)No (heuristic)No
TRACE (Zou et al., 2026)No (naive)No (heuristic)No
PROPS (Corrado and Hanna, 2023)N/AN/AN/A
VinePPO (Kazemnejad et al., 2025)YesNoN/A
BPO (He et al., 2026)Yes (partial)No (heuristic)No
OPTS-TTPOYes (Lemma 1)Yes (Theorem 2)Yes (Proposition 2)

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.

MethodOvercounting biasPosterior-selection bias
TreeRL (Hou et al., 2025)UncorrectedUncorrected
LATR (Xing et al., 2026)UncorrectedUncorrected
TreePO (Li et al., 2025)UncorrectedUncorrected
TRACE (Zou et al., 2026)UncorrectedUncorrected
PROPS (Corrado and Hanna, 2023)N/AN/A
VinePPO (Kazemnejad et al., 2025)N/AN/A
BPO (He et al., 2026)UncorrectedUncorrected
OPTS-TTPOCorrectedUncorrected, 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.

SelectorRolloutsMicro coverage (%)Macro coverage (%)Relative biasRelative MSEMicro avg@32 Δ (pp)Macro avg@32 Δ (pp)
Random7,21671.6253.731.332612.7620+0.135+0.250
Entropy (EGB; 4 roots)7,55672.7354.231.12709.0498+0.298+0.563
Uncertainty (DTS; 8 roots)8,07173.1754.420.91795.5552+0.166+0.183
OPTS7,21674.0655.211.580310.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.

ModelMethodMacro avg@32Micro avg@32Macro pass@32Micro pass@32
Qwen3-1.7BTreeRL0.37990.60730.58320.7727
Qwen3-1.7BTreePO0.29460.48770.52320.7328
Qwen3-1.7BOPTS-TTPO0.39670.61190.60960.7882
Qwen3-8BTreeRL0.49180.68430.69990.8115
Qwen3-8BTreePO0.39390.62210.63230.7916
Qwen3-8BOPTS-TTPO0.49450.68820.71010.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.

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

This paper investigates how tree search can improve high-return trajectory coverage in finite-sample on-policy reinforcement learning while controlling the resulting policy-gradient bias. It introduces OPTS-TTPO, combining On-Policy Parallel Tree Search (OPTS), which allocates rollout budgets using estimated performance differences, with Tree Trajectory Policy Optimization (TTPO), which uses branch-weighted aggregation and TreeGAE for PPO-style learning. The authors establish a Branch Aggregation Lemma under prefix-measurable branching, prove monotonic improvement of the induced search policy under idealized conditions, and analyze the bias introduced by adaptive expansion and max backup. Experiments across MuJoCo, Atari-57, and LLM mathematical reasoning report improved performance over PPO, including an average 18.7% improvement in MuJoCo tail returns and increases in Atari human-normalized IQM and LLM reasoning metrics.

The lemma assumes prefix-measurable branching, but Figure 2 uses the length of an already completed response to pick the branching midpoint. That depends on future tokens, so it violates the assumption. Figure 2 does not directly validate the lemma.

Figure 2 uses branch-weighted token-mass normalization, but the actual TTPO objective uses unweighted transition counts and advantage whitening. The paper admits this, so it is not a direct inconsistency, but the reported bias and MSE may not reflect the real training estimator. The link between theory, diagnostic experiment, and practical optimization is unclear.

The released PPO and OPTS-TTPO scripts use different actor minibatch sizes, 4096 vs. 512, and different Base/non-Base defaults. The fixed-branch code selects trees before filtering short responses and does not replace them, so actual expansions can differ. The stop condition also allows a negative mean-based baseline. This makes Table 3 and the coverage-bias comparison hard to verify.

On-policy tree sampling, shared-prefix exploration, and tree-structured credit assignment have already been studied in TreeRL, TreePO, and Branching Policy Optimization. OPTS-TTPO has a different theoretical formulation, but the main experiments mostly compare to PPO-family methods, and some gains are modest, e.g. Atari tail IQM 0.357 to 0.374 and Qwen3 micro pass@32 0.7384 to 0.7428. I need stronger evidence that this is more than combining established ideas.

Critical strengths
  1. The paper addresses a meaningful trade-off between high-return trajectory coverage and policy-gradient estimation bias under finite sampling budgets. This problem is relevant to both traditional RL and LLM post-training.

  2. The Branch Aggregation Lemma and the analysis of posterior-adaptive selection and max-backup prefix credit provide a structured theoretical treatment of biases often overlooked in tree-based policy optimization.

  3. The paper examines gradient bias, search-budget scaling, coverage–bias trade-offs, and downstream learning across three domains. The reported 18.7% average MuJoCo tail-return improvement is encouraging.

Critical weaknesses
  1. The Branch Aggregation Lemma (Section 3.1) requires prefix-measurable branching. However, the Figure 2 implementation (LLM/experiments/RQ1/estimation.py) determines the branching midpoint from the length of an already completed response. This makes the branching decision dependent on future sampled tokens, which generally violates the stated condition. As a result, Figure 2 does not directly validate the lemma under its assumptions. A genuinely prefix-measurable branching experiment, or an analysis of the current protocol, is needed.

  2. Figure 2 uses branch-weighted token-mass normalization (Equations D.2–D.3), whereas the practical TTPO objective uses the unweighted transition count and additional advantage whitening (Appendix A.5). The paper explicitly acknowledges these choices, so this is not a direct implementation inconsistency. However, the reported gradient bias and MSE do not necessarily reflect those of the actual training estimator. The connection between the theoretical identity, the diagnostic experiment, and practical optimization needs to be established more clearly.

  3. The released PPO and OPTS-TTPO scripts use different actor minibatch sizes (4096 vs. 512), potentially leading to different optimizer-update counts despite matching 4096 rollouts per training step. Their default Base/non-Base model configurations also differ. While these differences do not establish that Table 3 used unfair configurations, the released code does not make this verifiable. The actual initialization checkpoints, resolved configurations, and optimizer-update counts should be provided.

  4. Appendix D.3 states that fixed branching matches the number of OPTS expansions for each prompt and search round. However, LLM/experiments/RQ3/allocation.py selects candidate trees before filtering out short responses and does not replace ineligible selections. The corresponding unit test explicitly accepts this behavior. Thus, nominal branching counts may match while realized expansions differ. Reporting the actual expansion counts and skipped branches is necessary to verify the coverage–bias comparison.

  5. Section 3.2 specifies that search stops when no candidate exceeds a nonnegative baseline. However, the implementation allows a mean-based baseline that can become negative, and this option is used in the value-guided experiments (LLM/experiments/RQ2/run_guidance.sh). Consequently, states with negative estimated improvement may still be expanded. The authors should clarify this departure from the described algorithm and establish whether it affects the reported search results.

  6. Several core ideas, including on-policy tree sampling, shared-prefix exploration, and tree-structured credit assignment, have been studied in TreeRL, TreePO, and Branching Policy Optimization. Although OPTS-TTPO offers a different theoretical formulation, the main experiments primarily compare against PPO-family methods rather than closely related tree-based approaches. Moreover, some improvements are relatively modest, such as Atari tail IQM increasing from 0.357 to 0.374 and Qwen3-1.7B-Base micro pass@32 from 0.7384 to 0.7428 (Tables 2–3). The paper needs stronger evidence that its proposed mechanisms provide a meaningful advance beyond existing approaches, rather than mainly combining established ideas.

Questions for authors
  1. The Branch Aggregation Lemma assumes prefix-measurable branching, but Figure 2 uses the midpoint of an already generated response. How does this satisfy the required assumption? Also, Figure 2 uses a different normalization from the practical TTPO objective in Appendix A.5. Could the authors clarify which theoretical properties carry over to the implemented training estimator, or provide evidence under a protocol consistent with the lemma?

  2. The released PPO and OPTS-TTPO scripts use different minibatch sizes and default model variants, raising questions about actual optimizer-update counts and checkpoint matching. Additionally, the fixed-branch implementation for Figure 5 can skip ineligible responses without replacing them, potentially changing the realized branching budget. Could the authors provide the actual optimizer-update counts, initialization checkpoints, resolved configurations, and realized expansion statistics? These details are important for interpreting the reported improvements.

  3. Methods such as TreeRL, TreePO, and Branching Policy Optimization already explore on-policy branching, shared-prefix sampling, and tree-based credit assignment. Beyond the different theoretical formulation, what specific mechanism or capability distinguishes OPTS-TTPO from these approaches? Since the main learning experiments primarily compare against PPO-family baselines, could the authors identify existing evidence that isolates the additional benefit of their proposed method? This would help clarify the significance and originality of the contribution.

8 comments

We thank the reviewer for the careful examination of our theoretical assumptions, implementation, and experimental comparisons. We address the concerns below.


W1/W2/Q1

W1 (excerpt): The Branch Aggregation Lemma (Section 3.1) requires prefix-measurable branching. […] As a result, Figure 2 does not directly validate the lemma under its assumptions.

W2 (excerpt): Figure 2 uses branch-weighted token-mass normalization (Equations D.2–D.3), whereas the practical TTPO objective uses the unweighted transition count and additional advantage whitening (Appendix A.5). […] The connection between the theoretical identity, the diagnostic experiment, and practical optimization needs to be established more clearly.

Q1 (excerpt): Could the authors clarify which theoretical properties carry over to the implemented training estimator, or provide evidence under a protocol consistent with the lemma?

Response: Branching at the midpoint of a completed response in the original Figure 2 indeed does not satisfy Lemma 1's conditions. We therefore fixed branching at response token 512, specified suffix counts before outcomes, and replaced the random normalization denominator with the fixed number of initial trajectories. We reran the theoretical-gradient analysis under the lemma's conditions, preserving the original finding: TTPG's finite-sample measured bias remains near the no-branching baseline, while NaivePG's bias grows with branching.

To examine the connection between theoretical and practical gradients, we additionally evaluated the implemented TTPO gradient on the same sampled trees, retaining TreeGAE, advantage whitening, and normalization by the unweighted transition count, and comparing against an independent chain-PPO reference gradient. TTPO has lower measured bias, variance, and MSE and higher cosine similarity than NaivePO at every nonzero branching budget and tested group size. The revised results are in Section 4.1, Figure 2; the full protocol is in Appendix D.1.

Results.

  • Theoretical gradient (top): from K=0K=0 to 7, TTPG's measured relative bias changes from 0.456 to 0.400, while NaivePG's rises to 2.757; TTPG's variance and MSE decrease at all tested group sizes.
  • Practical gradient (bottom): TTPO improves all four gradient metrics over NaivePO at every nonzero KK and tested MM. At K=7K=7, M=4M=4, relative MSE is 0.925 versus 1.705, and cosine similarity is 0.318 versus 0.286.

Connection to theory. Using the same sampled trees, we show that branch weighting both prevents branching-induced bias growth under the lemma’s conditions and remains beneficial in the implemented TTPO gradient.

W3/W4/Q2

W3 (excerpt): The released PPO and OPTS-TTPO scripts use different actor minibatch sizes (4096 vs. 512), potentially leading to different optimizer-update counts despite matching 4096 rollouts per training step. Their default Base/non-Base model configurations also differ. […]

W4 (excerpt): […] Thus, nominal branching counts may match while realized expansions differ. Reporting the actual expansion counts and skipped branches is necessary to verify the coverage–bias comparison.

Q2 (excerpt): Could the authors provide the actual optimizer-update counts, initialization checkpoints, resolved configurations, and realized expansion statistics?

Response: PPO and OPTS-TTPO use identical initial model checkpoints within each comparison and the same number of actor optimizer updates: one per training iteration, 400 in total. Figure 5 uses exactly matched expansion counts for each prompt and search round by randomly subsampling a larger fixed-128 baseline pool.

Optimizer-update matching (W3Q2). The effective global actor minibatch is actor_rollout_ref.actor.ppo_mini_batch_size × actor_rollout_ref.rollout.n: 4,096 × 1 for PPO and 512 × 8 for OPTS-TTPO. The FSDP worker applies this multiplication before converting to per-rank minibatches (LLM/verl/verl/workers/fsdp_workers.py, lines 240–243).

Initialization matching (W3Q2). Base/non-Base initialization is selectable in the scripts; separate 1.7B and 8B launchers accommodate size-dependent microbatch settings, which are shared by Base and non-Base variants of the same size. Table 4 reports both Base and non-Base results at both model sizes.

Realized expansion matching (W4Q2). We uniformly subsample a larger fixed-128 continuation pool to match OPTS's actual expansion count for every prompt and search round. Both methods use the same 16,366 prompts, and no selected expansion is skipped.

Table A. Fixed Branch expansions exactly match OPTS after subsampling. Counts are cumulative through round ss; pool counts include only generated, nonempty suffixes.

Search budgetFixed Branch generated poolFixed Branch retained expansionsOPTS expansions
s=0s=0000
s=1s=1130,39436,90236,902
s=3s=3391,18292,25692,256
s=7s=7912,758183,004183,004

W5

W5 (excerpt): […] Consequently, states with negative estimated improvement may still be expanded. The authors should clarify this departure from the described algorithm and establish whether it affects the reported search results.

Response: We thank the reviewer for identifying this implementation issue. We corrected the clipping-induced error in the mean baseline and reran the affected experiments. The corrected results preserve the original conclusions: value-guided search still outperforms IID at every tested rollout budget, and learned-critic return improvements remain positive and increase with the search budget.

The theoretical mean baseline is nonnegative because each path includes a zero-score terminal state (Appendix B, proof of Theorem 2). The implementation instead averaged scores at clipped positions, which could be negative. We now compute the baseline from pre-clipping path maxima and use clipped-position scores only for candidate admission and ranking (Appendix D.2).

The affected experiments are mean-baseline, value-guided test-time scaling and learned-critic search-budget scaling; fixed-zero-baseline experiments are unaffected. The rerun results in Tables B-C are incorporated into Section 4.2, Figure 3 (learned-critic panel), Figure 4(b), and Appendices E-F.

Table B. Value-guided test-time scaling before and after correction. Reruns use the frozen step-400 actor/critic, 902 problems, and Smax⁡=3S_{\max}=3. Changes are percentage points (pp).

Rollout budget kkIID cons@k (%)Original clipped mean (%)Corrected raw mean (%)Corrected − original (pp)Corrected − IID (pp)
865.5266.5266.08-0.44+0.55
1666.0867.6366.85-0.78+0.78
3267.0767.6367.74+0.11+0.67
6466.5267.9668.18+0.22+1.66
12866.8567.8568.29+0.44+1.44

Table C. Learned-critic search-budget scaling before and after correction. Reruns use the same frozen checkpoint and 902 problems, with 32 initial trees per problem. Return changes are relative to s=0s=0; metric definitions follow Appendix F.

Search rounds ssOriginal opts-avg@32 (%)Corrected opts-avg@32 (%)Original ΔJλ\Delta J_\lambdaCorrected ΔJλ\Delta J_\lambdaOriginal ΔJ\Delta JCorrected ΔJ\Delta J
059.8759.870000
161.4361.42+0.00724+0.00727+0.01559+0.01549
362.0462.01+0.00977+0.00983+0.02176+0.02148
762.2862.16+0.01050+0.01035+0.02411+0.02290
1562.4062.23+0.01072+0.01046+0.02536+0.02363
Reviewer_aXAPOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies how tree-structured sampling can improve policy-gradient learning under finite sampling budgets. OPTS adaptively selects previously visited states for additional suffix sampling, while TTPO combines branch weighting, TreeGAE, and PPO-style updates to train on the resulting trees. The theoretical analysis identifies conditions under which branch aggregation preserves expectations, examines bias introduced by adaptive search, and characterizes the additional prefix credit produced by max backup.

Validation includes gradient-estimation diagnostics, search-budget experiments, component ablations, and policy-learning experiments on MuJoCo, Atari-57, and Qwen3 reasoning tasks. Under matched environment-interaction or rollout budgets, the paper reports improvements over PPO, including an average 18.7% increase in MuJoCo tail returns.

Critical strengths

A useful theoretical account of learning from tree-structured samples. The paper distinguishes conditions under which branch aggregation preserves expectations from the effects of adaptive selection and max backup. This is consequential because it clarifies what the proposed estimator can guarantee and how its practical learning signal differs from ordinary policy-gradient estimation. These insights remain valuable beyond the particular implementation.

Critical weaknesses
  1. The MuJoCo improvement may be substantially confounded by time-limit handling. In our independent reproduction of the five MuJoCo tasks, the main comparisons use 20 seeds, one million environment steps, and the paper’s tail metric—the final 100 of 488 logged points. With value bootstrapping at 1,000-step time-limit truncations, the full method improves over the original PPO baseline by 12.8%. However, adding the same bootstrapping to PPO alone yields a 10.8% improvement. Against this matched baseline, the full method adds only 1.9%, with a 95% bootstrap confidence interval of [−4.6%, +9.8%]. Although the paper’s reported 18.7% gain falls within the reproduction’s confidence interval against the original baseline, the controlled comparison does not establish a positive incremental benefit from the full method. This materially weakens the attribution of the reported gain to tree search. Whether the authors’ original implementation used asymmetric truncation handling remains to be clarified.

  2. The component-level conclusions are not robustly supported by the reproduction. Table 1 presents the complete method as the strongest configuration, supporting the combination of guided branching, max backup, and branch weighting. With consistent truncation bootstrapping, our reproduced Random+mean and Guided+mean variants achieve gains of 12.3% and 12.2% over the original PPO baseline, respectively, close to the full method’s 12.8%. Removing branch weights instead yields a 21.6% gain, or 10.0% over PPO with matched bootstrapping, with a 95% confidence interval of [1.1%, 21.3%]. These ablations use 10 seeds and do not reproduce the reported ordering. Consequently, the empirical evidence does not yet establish that the complete TTPO design, particularly its branch weighting, is responsible for the performance improvement.

Questions for authors
  1. Implementation clarification: How are time-limit truncations handled in PPO and each OPTS-TTPO variant? Specifically, do value targets bootstrap from the final observation at the 1,000-step limit, and are identical rules applied to both methods?
  2. Validation of the reported component contributions: Under identical truncation handling, does the full method outperform both PPO and the unweighted variant?
  3. Evaluation clarification: Do Figure 6 and Appendix H report returns from independent evaluation rollouts without search, ordinary training-episode averages, or branch-weighted returns?
  4. Hyperparameter-selection clarification: Were the final evaluation seeds independent of those used to select the hyperparameters?
5 comments

We sincerely thank the reviewer for independently reproducing our experiments and ablations, conducting careful controlled comparisons, and highlighting the questions about evaluation and seed selection.

In the result tables below, entries report percentage gains over the matched baseline (PPO or Unweighted): we first average returns across training seeds within each task, then compute the percentage improvement over that baseline, and finally average these improvements equally across the five tasks.


W1/Q1

W1 (excerpt): The MuJoCo improvement may be substantially confounded by time-limit handling. […] Whether the authors' original implementation used asymmetric truncation handling remains to be clarified.

Q1: Implementation clarification: How are time-limit truncations handled in PPO and each OPTS-TTPO variant? Specifically, do value targets bootstrap from the final observation at the 1,000-step limit, and are identical rules applied to both methods?

Response: PPO and every OPTS-TTPO variant uniformly use zero bootstrap at the 1,000-step time limit, following the CleanRL continuous-action PPO default. We use this convention to keep truncation handling consistent across MuJoCo, Atari, and LLM RLVR, where zero bootstrap is commonly used at max response length.

Table A. Identical boundary handling for PPO and every OPTS-TTPO variant.

BoundaryPPOFull OPTS-TTPO and its ablations
True environment terminationSuccessor value = 0Successor value = 0
1,000-step time-limit truncationSuccessor value = 0Successor value = 0
Rollout collection ends within an ongoing episodeBootstrap from the next-state valueBootstrap from the next-state value

Reproduction and additional robustness checks. We note that the reviewer's reproduction uses value bootstrapping at the time limit, whereas our implementation uniformly uses zero bootstrapping (Table A). This difference in truncation handling alone can produce a substantial shift in absolute gains. To further assess robustness under matched zero-bootstrap handling, we reproduced the original 18.7% training-tail gain on seeds 1–10, extended the unchanged configuration to 40 additional seeds (11–50), and evaluated 4,096 / 2M and 8,192 / 4M across all 50 seeds. The larger settings increase rollout size and interaction budget proportionally while keeping the optimizer-update count fixed (see W2/Q2).

Table B. Full retains positive mean gains over PPO in both metrics across all reported seed groups and scales under matched zero-bootstrap handling (evaluation protocol in Q3).

Rollout / interaction budgetTraining seedsFull: training-tail gain vs PPOFull: independent-evaluation gain vs PPO
2,048 / 1M1–10 (original paper seeds)+18.73%+14.32%
2,048 / 1M11–50 (additional seeds)+7.26%+2.47%
2,048 / 1M1–50+9.56%+4.80%
4,096 / 2M1–50+6.20%+4.04%
8,192 / 4M1–50+9.84%+6.49%

W2/Q2

W2 (excerpt): These ablations use 10 seeds and do not reproduce the reported ordering. Consequently, the empirical evidence does not yet establish that the complete TTPO design, particularly its branch weighting, is responsible for the performance improvement.

Q2: Validation of the reported component contributions: Under identical truncation handling, does the full method outperform both PPO and the unweighted variant?

Response: Under identical zero-bootstrap handling, Full outperforms both PPO and Unweighted on the original seeds 1–10, confirming the reported component contributions:

Table C1. Seeds 1–10: Full outperforms both PPO and Unweighted under matched zero-bootstrap handling.

SettingSeedsUnweighted: training-tail gain vs PPOFull: training-tail gain vs PPOFull: training-tail gain vs Unweighted
2,048 / 1M1–10 (original paper seeds)+11.46%+18.73%+6.70%

However, extending to 40 additional seeds (11–50) reveals a gap. On seeds 11–50, Full still improves over PPO (+7.26%) but falls below Unweighted (−3.11%). Across all 50 seeds, Full's margin over Unweighted is slightly negative (−1.14%). The gap between seeds 1–10 (+18.73%) and 11–50 (+7.26%) likely reflects both the high variance inherent in 10-seed estimates and the hyperparameter overlap noted in Q4.

Table C2. Seeds 11–50 and 1–50: Full's margin over Unweighted turns slightly negative at the original 2,048 / 1M scale.

SettingSeedsUnweighted: training-tail gain vs PPOFull: training-tail gain vs PPOFull: training-tail gain vs Unweighted
2,048 / 1M11–50 (additional seeds)+10.78%+7.26%-3.11%
2,048 / 1M1–50+10.91%+9.56%-1.14%

We attribute this reversal to a finite-sample bias–variance trade-off. Nonuniform branch weights correct the over-counting bias identified in RQ1, but reduce effective sample size. Our LLM gradient analysis (RQ1, Section 4.1) shows that equal weighting reduces variance faster, yet the resulting squared bias can dominate MSE. At minibatch size 64, the variance cost of nonuniform weights may outweigh the bias correction benefit. We therefore expect that increasing minibatch size—while keeping training iterations and optimizer updates fixed—would allow Full to recover its advantage over Unweighted.

To test this hypothesis, we increase rollout size and interaction budget proportionally while keeping num_minibatches (32) and update_epochs (10) fixed, so that only the per-update minibatch size grows (64 → 128 → 256). Training iterations (488), optimizer updates (156,160), and seeds (1–50) are identical across all three settings. As shown in Table C, Full's margin over Unweighted reverses from −1.14% at minibatch size 64 to +7.17% at 128 and +8.65% at 256, with the same pattern in independent evaluation (Table D). This supports the interpretation that branch weighting's bias correction becomes net-beneficial once the per-update sample size is large enough to absorb the associated variance cost. In summary, the full OPTS-TTPO design outperforms both PPO and Unweighted across 50 seeds once the minibatch size is large enough (128 or 256), which supports attributing the improvement to the complete design.

Table C3. At larger minibatch sizes, Full outperforms both PPO and Unweighted across 50 seeds, consistent with the predicted bias–variance trade-off. Independent evaluation is reported in Table D (Q3).

SettingSeedsUnweighted: training-tail gain vs PPOFull: training-tail gain vs PPOFull: training-tail gain vs Unweighted
2,048 / 1M1–50+10.91%+9.56%-1.14%
4,096 / 2M1–50-0.53%+6.20%+7.17%
8,192 / 4M1–50+1.19%+9.84%+8.65%

Q3

Q3: Evaluation clarification: Do Figure 6 and Appendix H report returns from independent evaluation rollouts without search, ordinary training-episode averages, or branch-weighted returns?

Response: Branch-weighted training-returns. Figure 6 and the MuJoCo hyperparameter-grid results in Appendix H report returns collected during training. PPO averages episode returns, while OPTS-TTPO aggregates branch-weighted returns within each tree and then averages trees equally, so a tree with more branches does not receive greater weight. Appendix H reports both full-training and training-tail averages; training-tail return averages the final 100 of 488 logged points.

Independent evaluation. For the additional MuJoCo comparisons in W1/Q1 and W2/Q2, we evaluate each final checkpoint in fresh environments using 10 episodes per training seed, with new evaluation seeds matched across methods. The actor and observation-normalization statistics are frozen, and actions use the deterministic actor mean, without search or parameter updates. Episodes end at true termination or the 1,000-step limit. Returns are raw, undiscounted reward sums without an added terminal value; the ten episodes are averaged within each training seed.

Table D. Independent evaluation confirms the training-tail pattern from W2/Q2. Each checkpoint is evaluated without search over 10 fresh episodes.

SettingSeedsUnweighted: independent-evaluation gain vs PPOFull: independent-evaluation gain vs PPOFull: independent-evaluation gain vs Unweighted
2,048 / 1M1–10 (original paper seeds)+6.93%+14.32%+6.97%
2,048 / 1M11–50 (additional seeds)+6.59%+2.47%-3.56%
2,048 / 1M1–50+6.65%+4.80%-1.49%
4,096 / 2M1–50-1.96%+4.04%+6.53%
8,192 / 4M1–50+0.94%+6.49%+5.62%

Q4

Q4: Hyperparameter-selection clarification: Were the final evaluation seeds independent of those used to select the hyperparameters?

Response: Hyperparameter selection on Hopper-v4 and Humanoid-v4 and the original five-task comparison both used seeds 1–10, so the tuning and reporting seeds overlapped on those two tasks. To assess robustness, we froze the selected hyperparameters and evaluated all methods on 40 additional training seeds (11–50). W1/Q1 and W2/Q2 report the seed-extension results and supplementary larger-scale comparisons.


Manuscript revisions

Changes are highlighted in blue:

  • Section 4.4 (p. 8) and Figure 6 (p. 9): main-text seeds, training-return reporting, and expanded component comparisons.
  • Appendix D.4 (p. 34): return aggregation, shared zero-bootstrap handling and its two motivations, and tuning/reporting seed overlap.
  • Appendix H (p. 39): branch-weighted training returns and seeds 1–10 for the hyperparameter grid.
  • Appendix I (p. 40, Tables I.1–I.2): matched scaling settings with fixed optimizer updates, independent evaluation, expanded-seed gains vs PPO/Unweighted, and the gain calculation and RQ1-based interpretation.

Comments on the paper

1 comment

Dear Area Chair and Reviewers,

We thank the reviewers for their careful reviews and valuable comments.

1. Our contributions and research significance

Policy-gradient methods learn from finite samples and can miss rare, high-return trajectories. Tree search can uncover these trajectories, but learning naively from search tree makes gradient deviate from original objective. We propose an on-policy tree search algorithm whose expected search return improves monotonically and an unbiased method for aggregating policy gradients from tree trajectories. The details are as follows:

  • OPTS: where to spend a finite budget. Uniform branching wastes the budget on states where resampling rarely helps. OPTS scores visited states with a performance-difference estimate and samples on-policy suffixes from the highest-scoring ones. Prior tree-based methods (TreeRL, TreePO, LATR, TRACE, BPO) branch by heuristics; OPTS is the first to guarantee that expected search return improves monotonically with the budget.
  • TTPO: correcting the overcounting bias of tree. Naively summing gradient from tree gives the suffixes too much weight relative to the prefix. TTPO corrects this overcounting bias. It is built on our Branch Aggregation Lemma, which states when branch-weighted tree statistics recover the ordinary on-policy chain expectation, and applies these branch weights in a PPO-style objective. Prior methods aggregate tree gradients naively or heuristically and leave this bias uncorrected. For adaptive OPTS trees, we bound the gradient bias arising from adaptive branch.

2. Reviewer concerns and our responses

Reviewers aXAP and DFoi indicated that all their concerns have been addressed. DFoi’s rating rose from 2 to 3, and aXAP’s remained at 3. We have also addressed Reviewer hM3o’s original concerns. However, in a follow-up, hM3o raised new concerns about the benefit of branch weighting and the statistical significance of gains over related methods, and thus kept the rating. We examined both issues in additional experiments and reported the results; hM3o has not yet replied to our follow-up.

C1. Novelty and comparisons relative to tree-based methods (DFoi, hM3o; see responses to DFoi's W1/Q1, W3/Q3 and Q4, hM3o's W6-1/Q3-1 and W6-2/Q3-2, and the follow-up response to hM3o, points 3–4). The reviewers asked what distinguishes OPTS-TTPO from existing tree-based methods and requested comparisons with them. We clarified that our novelty lies in theoretically grounded bias control: OPTS-TTPO corrects the overcounting bias induced by branching and bounds the posterior-selection bias induced by adaptive search, whereas prior tree-based methods rely on heuristics that leave both biases uncontrolled. Our additional experiments show that OPTS-TTPO outperforms TreeRL and TreePO.

C2. Gap between the Branch Aggregation Lemma's conditions and practice (DFoi, hM3o; see responses to DFoi's W2/Q2 and hM3o's W1/W2/Q1). The reviewers noted that the lemma's prefix-measurability condition is not met in two places: the original gradient experiment, and OPTS's adaptive selection itself. For the experiment, we reran it under the lemma's conditions and also evaluated the gradient actually used in training; both confirm the original finding. For OPTS, we clarified that because its adaptive selection does not fully satisfy the lemma's conditions, a posterior-selection bias remains; but we still bound this bias explicitly and leave its exact correction to future work.

C3. Whether branch weighting consistently improves returns (aXAP, hM3o; see responses to aXAP's W2/Q2 and the follow-up response to hM3o, points 1–2). The reviewers noted that, at the original MuJoCo budget, the gain from branch weighting is not consistently maintained. We clarified that this reflects a bias–variance trade-off: branch weighting reduces bias but increases gradient variance, so its gain should become more pronounced with larger budgets. Our additional experiments confirm this: at 4,096/2M and 8,192/4M, the full method clearly outperforms the unweighted variant. Our exact-gradient experiment further showed that both naive and heuristic aggregation can reverse the ascent direction and shift stationary points, while branch weighting consistently reached the optimum by correcting the overcounting bias.

C4. Evaluation and implementation details (aXAP, hM3o; see responses to aXAP's W1/Q1, Q3 and Q4, and hM3o's W3/W4/Q2 and W5). aXAP asked about truncation handling, evaluation protocol and seed overlap in MuJoCo. hM3o raised questions about matched configurations in the LLM experiments and found a bug in the search baseline. We confirmed that truncation is handled identically for all methods and acknowledged the seed overlap; with 40 fresh seeds and independent evaluation, OPTS-TTPO still beats PPO. We also clarified that the LLM configurations are matched, fixed the bug, and reran the affected experiments; the conclusions hold.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.