acceptodds
Under review as a conference paper at ICLR 2027

UMCTS-GRPO: Uncertainty-Aware Monte Carlo Tree Search for LLM Agent Reinforcement Learning

Abstract

Tool-using language agents make sequences of decisions but are typically rewarded only for the final outcome. Tree-structured rollouts expose alternative decisions at shared histories, turning terminal rewards into step-level credit, yet existing tree-based agent RL expands branches at random and trusts every comparison equally. We introduce UMCTS-GRPO, which uses a single backed-up branch uncertainty to decide both where to collect rollout evidence and how much to trust it. During collection, uncertainty-aware Monte Carlo tree search steers simulations toward unresolved branches; during optimization, the same statistic weights sibling comparisons through an uncertainty-weighted baseline and a confidence gate, yielding step-level advantages without a critic, process reward model, or step-level annotation. In short: explore what you doubt; learn from what you have resolved. Experiments on seven retrieval-based QA benchmarks and the interactive ALFWorld environment, across five backbones from the Qwen2.5 and Llama3.2 families, show that UMCTS-GRPO consistently improves over strong agent RL baselines and remains effective under tight rollout budgets.

Primary area:
reinforcement learning
Keywords:
LLM agents, reinforcement learning, uncertainty, GRPO

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_J6AmOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper proposes a method to use MCTS for training LLMs while accounting for evaluation uncertainty.

Critical strengths
  1. Much of the idea seems sound.

  2. Results seem promising.

Critical weaknesses

Novelty:

  1. Up until section 4.2, effectively nothing is novel - it's just a rehashing of the equations from Epistemic MCTS (EMCTS, [1]). While EMCTS is cited briefly in the related work, these sections (4, 4.1) are presented as novel, and they are almost entirely not.

  2. In the related work, other MCTS-for-LLM work is presented with "A separate line of work applies tree search at inference time to improve a single response (citations). UMCTS-GRPO searches only during training and evaluates the policy without test-time search. " The AlphaZero [2] line of work has shown us that there is effectively no difference between searching for acting (producing an improved policy at the root and selecting an action from it) and searching for learning (producing an improved policy at the root and learning from it). So I don't think this line is sufficient to cover the parallels between this work and the prior work in this area, which renders me unable to establish the remaining novelty of this work.

Soundness and theoretical motivation:

There is effectively no theoretical motivation for the way uncertainty is used, except for a little in 4.1 (which is not novel). This is part of a larger problem: a better framing of the uncertainty is very necessary, in my opinion. MCTS already addresses uncertainty in the returns with the visitation counts. That's the purpose of the PUCT search term: to trade off uncertainty (opt. in the face of unc.) vs probability of promising-ness under the policy prior. The uncertainty that EMCTS motivates is epistemic, and is not addressed by this PUCT term, which necessitate the second term (Eq 3 in this work, which is Eqs 10 and 11 in EMCTS). This work does not make it clear why it is correct to quantify and use the type of uncertainty raised by this work in this way.

In addition, the "confidence weighted advantages" are not theoretically motivated, nor do I find the theoretical results of section 4.3 convincing. If my understanding is correct, Proposition 1 shows properties of AlocA^{loc}. But it's not clear to me that AlocA^{loc} is itself sound: the advantage is usually computed Aπ(s,a)=Qπ(s,a)−Vπ(s)A^\pi (s,a) = Q^\pi(s,a) - V^\pi(s). A policy which selects advantage positive actions improves with respect to π\pi. However, AlocA^{loc} is defined with respect to an uncertainty weighting, instead of policy probabilities. As a result, it's not clear to me that it is sound as a quantity for improvement to start with.

Statistical Significance:

Is missing from the majority of results. When it is not missing, an +- 1 STD is used, which is not the appropriate metric to evaluate the stat. signif. of the mean. Please include a principled confidence interval, such as a 95% Gaussian CI (approx. +- 2 Standard Error of the Mean (SEM)).

Presentation:

  1. I would like to preface this point by saying that I strongly approve of the choice to try to adhere to standard RL notation (states, rewards, transitions). It's not always done in LLM papers, and I think it's the right choice here and I commend the authors on taking it. That being said, there are a large number of issues with the notation, examples below:

    1. R is called reward but defined, described and treated as a return. They are not the same thing. The reward is defined for a transition, and the return is defined for a trajectory. Respectively, the value is the expected return, eg the expectation over the sum of (often) discounted rewards.
    2. The paper uses both observations and states, implying a POMDP (never defining either an MDP or a POMDP). Observations are usualy reserved specificaly to denote the information that is available to the agent and is not the complete state, and introduce a lot more complexity to (the already complex enough) MDPs. This does not seem to me to be necessary here, in which case I strongly recommend trying to change the notation around classical MDP notation, and defining MDPs. Otherwise, I would suggest defining POMDPs properly in the preliminaries section.
    3. The term advantage is well defined in RL: Aπ(s,a)=Qπ(s,a)−Vπ(s)A^\pi (s,a) = Q^\pi(s,a) - V^\pi(s). It sort of makes sense to me to call AoutA^{out} an advantage, except that it's not clear why it's normalized by the STD and why it's called Aout,A^{out}, as opposed to AπA^\pi.
    4. Q is presented as a return-estimate, which it is not. It is an expected return (eg the value, and specifically the action-value) estimate. The paper will benefit from defining all of this in the preliminaries section, which will also allow for a more natural definition of the advantage.
    5. The prior P, transition model PenvP_{env}, policy πbehavior\pi_{behavior} (which is never defined I believe) are all confusing choices for notation. The transition probabilities can safely be P. The "prior" is usually the "prior policy", eg the LLM, eg πθ\pi_\theta. It's not clear to me what πbehavior\pi_{behavior} is, how it's different from πθ\pi_\theta, how its different from the prior P, is P not πθ\pi_\theta, and if there is a reason to use these confusing terms.
    6. G is defined as a "group" of trajectories. What is a group? A set?
  2. Missing preliminaries:

    1. MCTS is not defined or presented, making it very hard to understand the terminology chosen by the authors. For example, what is a rollout? in MCTS, these are usually the rollouts from a leaf during expansion. But it can also be the trajectory from the root to a leaf during selection. As well as other things.
    2. MDPs, POMDPs and value functions are never defined, resulting in many of the notation problems mentioned above.
  3. Proofs are not linked to from the body of the paper (unless ive missed that).

  4. Evaluation metrics are cited but not explained.

  5. Policy optimization is placed structurally as part of "UMCTS", but if I understand correctly its explicitly applied to extract policy target from the search, once it has concluded. If this is the case, please consider changing the structure of the contribution sections, seperating how MCTS is modified from how its being used.

  6. "For each prompt we build M independent trees" sounds cool, not standard, and leaves me very unclear on how the algorithm actually works.

  7. "Because the language action space cannot be enumerated": can it not? I thought LLMs had a finite output space of size num. possible tokens. I assume the authors are correct and the misunderstanding is mine, but it's not clear to me what this means exactly.

  8. The results are presented in tables. Tables are the single least informative way to present results. If the most informative results to present are individual numerical scores (which seems unlikely to me for a learning algorithm), consider presenting them in bar charts instead.

  9. I personally find the diagrams confusing rather than clear. For example, why do the search / expansion / backup trajectories and / or the trees seem to be inconsistent within the same figures?

[1] Oren et. al., Epistemic Monte Carlo Tree Search. ICLR 2025.

[2] Silver et. al., A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 2018.

Questions for authors

Please see the weaknesses section.

4 comments
AuthorsOpenReview ↗

Author Response 1

Thank you for the careful reading. Your comments on notation and structure were helpful, and we have uploaded a revised PDF with the changes in blue. We reply in two parts. This part covers novelty and the role of UU; the next covers soundness, statistics and presentation.

(1) Relation to EMCTS.

You are right that §4.1 builds on EMCTS, and the text should have said so. Two elements come from prior work: the recursive uncertainty backup (Eq. 4), which follows the uncertainty Bellman equation, and the additive uncertainty bonus in the selection score (Eq. 3), which follows EMCTS. The submission cited EMCTS only in the related work. §4.1 now cites UBE and EMCTS at both places, and a new App. G compares the two methods.

That said, §4.1 differs from EMCTS in two respects. The first is where the uncertainty comes from. EMCTS propagates the uncertainty of learned value or dynamics models, and we have no learned model. Our UU is computed from the returns the environment actually gave: how much they disagree, plus the surprisal of the action and the uncertainty of the subtree below (Eq. 5). No critic or uncertainty estimator is trained. The second is the action space. Tree search needs to know the children of a node. A board game has a fixed list of legal moves, but an agent step is free text and has no such list, so we build one by sampling several next steps at the same prefix, merging near-duplicates, and using the cluster frequency as the prior.

Our main contribution is in §4.2, where the same statistic is used a second time with the opposite effect. In search, a high UU gives a branch more rollouts; in learning, a high UU gives its comparison less weight. EMCTS uses uncertainty for selection only, and to our knowledge neither EMCTS nor AlphaZero uses it to weight credit. This second use matters empirically: removing it lowers multi-hop EM from 20.2 ± 0.4 to 18.9 ± 0.5 (three runs each, and every run of the full method is above every run without it).

EMCTSUMCTS-GRPO
Source of uncertaintylearned value / dynamics modelsspread of real-environment returns and policy surprisal
Uncertainty used forselectionselection and credit
Tree outputroot action, root policy targetan advantage at every branching node
Action spaceenumerablesampled, clustered text actions

(2) Relation to AlphaZero.

We agree that searching to act and searching to learn are closely related. The related-work sentence you quote was meant for methods such as ToT (Yao et al., 2023) and LATS (Zhou et al., 2023), which run the search every time the model is used. We added a sentence on AlphaZero there and a comparison in App. G.

What separates us from AlphaZero is what we take from the tree. AlphaZero trains the policy toward the root visit distribution and also trains a value network. We instead use the Monte Carlo returns at every branching node, at any depth, to form advantages, apply a clipped policy-gradient update, and train no value network.

(3) Why UU in addition to visit counts.

Visit counts treat two branches with the same number of visits as equally well known, which is often not the case. Take two branches that have each been visited twice, one returning (1, 1) and the other (1, 0). With equal priors, PUCT gives both the same bonus, even though the second estimate is less certain. UU captures this difference. Variance-aware bounds such as UCB-V (Audibert et al., 2009) rest on the same idea, namely that a confidence width depends on the count and on the observed spread. In our score, PUCT supplies the count part and UU the spread part. §4.1 now states this.

On the kind of uncertainty: in EMCTS it is about a learned model. We have none, so what remains uncertain is whether the average of a few sampled returns (at most three in QA) is close to the true value, and the spread of those returns is what indicates this. We checked it with rollouts the tree never saw. Where UU is high, the tree's value is 3.1× further from the value those rollouts give (488 branches, up to 8 rollouts each; 95% Confidence Interval [1.6, 6.4], permutation p<0.001p<0.001).

We also tried the count-scaled form σ^/N\hat\sigma/\sqrt N. It lands within 0.7 points of the original (48.4 / 19.6 vs. 49.1 / 20.2 EM), which is what one would expect with so few visits per branch.

AuthorsOpenReview ↗

Author Response 2

(4) Soundness of AlocA^{\mathrm{loc}}.

We understand the concern to be that AlocA^{\mathrm{loc}} uses uncertainty weights where AπA^\pi uses policy probabilities. App. C now explains the construction in three steps.

First, b(s)b(s) plays the role of the state value. It is an estimate of VV from the siblings sampled at ss, just as the group mean is in GRPO, and subtracting it centers the comparison and reduces the variance of the update.

Second, the 1/U1/U weights. Sibling values are estimated with different precision, and inverse-uncertainty weighting is the standard way to average such estimates, since it gives the lowest-variance average. When all siblings are equally uncertain, b(s)b(s) reduces to the plain mean (Prop. 1iii).

Third, the gate. gg lies in (0,1](0,1], so it reduces the magnitude of an advantage and leaves its sign unchanged (Prop. 1i). Its role is similar to that of λ\lambda in GAE, where some magnitude is given up for less noise. For two siblings, the update always raises the better action relative to the worse one (Prop. 2).

As for the name, dividing by the sibling standard deviation is the per-group standardization of GRPO. We now call the quantity the standardized local advantage and relate it to Aπ=Qπ−VπA^\pi=Q^\pi-V^\pi in App. C.

(5) Statistical significance.

We give ±2 SEM intervals below. The tables keep mean ± std, because another reviewer asked for standard deviations, and App. D states the conversion (±2 SEM = 1.15 × std for three runs).

For QA, every setting in Table 1 now has three independent training runs. Training follows the Tree-GRPO configuration, including its source of randomness (unseeded data shuffling and tree expansion, as in their released code). With ±2 SEM over runs, Tree-GRPO lies below our interval in nine of ten settings, for example 49.1 ± 0.3 vs. 47.5 (1.5B single-hop) and 47.1 ± 0.3 vs. 45.3 (14B multi-hop). The exception is 7B multi-hop (38.0 ± 0.2 vs. 37.8), where the two methods are on par.

For ALFWorld at 7B (seeds 0, 1, 2), the intervals are UMCTS-GRPO 94.2 ± 2.2, GiGPO 90.8 ± 1.5, and Tree-GRPO 76.5 ± 2.9.

(6) Notation, preliminaries and structure.

We revised the following as you suggested:

TopicChange
Return vs. reward§3 now calls R(H)R(H) the return and states that the reward is non-zero only at termination
Background§3 now gives the MDP formulation and introduces MCTS. A new App. H defines VπV^\pi, QπQ^\pi, AπA^\pi
QQDescribed as an estimate of the action value
"Rollout"Defined in §3: a simulation is one select–expand–rollout–backup cycle, and a rollout is the continuation from a new node to the end
AdvantageAlocA^{\mathrm{loc}} is named the standardized local advantage; App. C relates it to AπA^\pi and explains the division by the sibling std
Proofs and metricsThe main text now links Proposition 1 to its proof (App. C) and defines EM and success rate in §5

For the remaining points:

  • States and observations. The setting is a fully observed MDP. The state is the whole interaction history, st=(x,H<t)s_t=(x,H_{<t}) (§3.1). "Observation" is the ReAct term for the tool's output, which becomes part of that history; it is not a partial view of a hidden state. §3 now says this explicitly.
  • Symbols. The notation table (App. A) lists every symbol: πθ\pi_\theta is the policy being trained; πold\pi_{\mathrm{old}} is what the text calls the behavior policy, a frozen copy of πθ\pi_\theta used to collect data; πref\pi_{\mathrm{ref}} is the reference policy of the KL term; P(s,a)P(s,a) is the search prior; and PenvP_{\mathrm{env}} is the transition model. §4.1 now says this where πold\pi_{\mathrm{old}} first appears, and App. H restates these roles in one place.
  • Enumerating actions. An action is a complete agent step: a thought followed by a textual action (§3.1) of up to 500 tokens (App. D). A single token is only a fragment of it. The number of possible steps is about ∣V∣L|\mathcal V|^{L} with ∣V∣≈1.5×105|\mathcal V|\approx1.5\times10^{5}, so the children of a node cannot be listed and have to be obtained by sampling.
  • MM independent trees. This is the Tree-GRPO setup we build on (§3.2): each prompt gets MM separate trees. Outcome advantages compare the leaves of all trees, and local advantages are computed inside each tree. The full procedure is Algorithm 1 in App. B, referenced at the start of §4.
  • "Group". Gx\mathcal G_x follows GRPO's usage (§3.2): the set of trajectories sampled for one prompt.
  • Structure. The search is §4.1. Policy optimization is the last paragraph of §4.2, with its own title, because it takes the advantages defined there as input.

On the tables, we keep Table 1 in the main text because prior work on these seven benchmarks is compared through per-dataset numbers.

If the revised §3–§4 and Appendices C and H address your concerns on soundness and presentation, we would be grateful if you would reconsider those scores.

I thank the authors for their rebuttal and the improvements to the paper.

My concerns remain, unfortunately, for the most part unaddressed.

Soundness and theoretical motivation:

MCTS is already designed to account for return variance (aleatoric uncertainty in return). It enters the theoretically motivated search policies (UCT, PUCT) in the count-based coefficient, under the assumption that leaves have the same variance.

The authors observe that in fact, the leaves do not have the same variance, and that EMCTS provides an alternative approach for propagating uncertainty.

However, EMCTS's (along with UBE's) uncertainty propagation mechanism is motivated specifically under the assumption that this uncertainty is not aleatoric, so this approach is not suited (or at least, not well motivated) for propagating this type of uncertainty.

Here is a paper that treats non-uniform leaf uncertainty, if memory serves:

[1] Tesauro, G., Rajan, V. T., & Segal, R. (2010). Bayesian Inference in Monte-Carlo Tree Search. UAI 2010.

I think it should be contrasted with, discussed, and perhaps even adopted into the authors method.

Statistical significance:

Every result presented in the paper needs to be paired with the appropriate metric for statistical significant. It is always unfortunate when reviewers appear to have conflicting requests. That being said, I cannot recommend the paper for acceptance until all quantities are paired with the appropriate metric of statistical significance, or it is explained connivingly why one need not, or cannot, be included. The appropriate metric for statistical significance depends on the purpose of the result presented, but when mean's presented, these are generally confidence intervals over the mean, such as 2*SEM based. STD is not a confidence interval.

Unless I misread (in which case, please correct me), the vast majority of the results presented in the paper are still not paired with a metric of statistical significance (Tables 1-5, Figure 4, for example).

Until both of these issues are fully addressed, I will not be able to raise my score. That being said, I think the underlying idea and method have promise, and even if the paper does not get accepted at this submission cycle, I would like to encourage the authors to keep following this direction.

AuthorsOpenReview ↗

Author Response

Thank you for the comments, the reference, and the encouragement. We address your two issues in order; the first has two parts.

1a. The EMCTS/UBE backup is motivated for epistemic uncertainty, while ours is variance in the return.

Propagating return variance does not need an epistemic assumption. The variance of the return has its own recursion, the law of total variance (Sobel, 1982). For a policy π\pi and deterministic transitions,

Var[G∣s]=∑aπ(a∣s)(Qπ(s,a)−Vπ(s))2+∑aπ(a∣s) Var[G∣s,a],Var[G∣s,a]=γ2 Var[G∣s′].\mathrm{Var}[G\mid s]=\sum_a\pi(a\mid s)\big(Q^\pi(s,a)-V^\pi(s)\big)^2+\sum_a\pi(a\mid s)\,\mathrm{Var}[G\mid s,a],\qquad \mathrm{Var}[G\mid s,a]=\gamma^2\,\mathrm{Var}[G\mid s'].

Our backup has the same two parts: Eq. 19 adds the disagreement between child values, and Eq. 4 carries the subtree statistic upward with γ2\gamma^2. In QA the retriever is deterministic, so this variance comes entirely from the later choices of the policy. §4.1 states this motivation, App. G gives the recursion, and UBE is cited only for the recursive form.

1b. Tesauro et al. (2010) should be contrasted, discussed, and perhaps adopted.

We discuss Tesauro et al. (2010) in §2, contrast it with our method in App. G, and test its exploration rule below. They explore with a posterior standard deviation that shrinks with the visit count, which in our setting is the return dispersion scaled by the count, σ^/N\hat\sigma/\sqrt{N} (Table 10):

BonusSingle-hop EMMulti-hop EM
σ^/N\hat\sigma/\sqrt{N} (count-scaled, one run)48.419.6
σ^\hat\sigma (no count scaling, one run)48.519.5
Our full statistic (three runs, ±2 SEM)49.1 ± 0.320.2 ± 0.5

Count scaling makes no measurable difference here: an edge holds at most three returns, so the scaling changes the bonus by a factor of at most 3\sqrt{3}. We therefore keep the unscaled form. We did not adopt the full Bayesian backup because it targets the value of best play, while an advantage needs the value under the current policy.

2. Every result should be paired with a measure of statistical significance.

Every main result and every ablation of UMCTS-GRPO reports a mean with a ±2 SEM interval over three independent runs, in the table itself:

ResultWhat is reported
Table 1±2 SEM on all ten UMCTS-GRPO category averages, three independent training runs each. Baseline rows are the numbers reported in the Tree-GRPO paper, which gives one value per setting.
Table 2±2 SEM on the overall success rate of every RL method, three seeds each.
Table 4±2 SEM on the full method and all four ablations, three runs each.
Table 3, Figures 4 and 5Single-run budget, training-dynamics, and sensitivity analyses, used for trends. A training run takes 8 to 48 hours on 4 GH200 gpus/8 H200 gpus, so the repeated runs went to the main results and the ablations.
Table 5Notation table.

Per-run values for QA and the ablations are in App. I.

Under these intervals, Tree-GRPO lies below ours in nine of ten settings of Table 1, and the tenth (7B multi-hop, 38.0 ± 0.2 vs. 37.8) is on par. On ALFWorld at 7B, UMCTS-GRPO reaches 94.2 ± 2.2 against 76.5 ± 2.9 for Tree-GRPO.

We believe this addresses both issues and would be grateful if you would reconsider your rating.

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

This paper proposes UMCTS-GRPO, a reinforcement learning approach for tool-using LLM agents. Built upon tree-structured rollouts, the method prioritizes uncertain branches during exploration and applies explicit weighting to local value comparisons between sibling actions for training. The approach is evaluated on seven benchmarks using five backbone models.

Critical strengths
  1. Building upon existing tree-structured rollout methods, the proposed method leverages U to direct additional search toward highly uncertain branches and mitigates the impact of uncertain local comparisons on training updates.
  2. The empirical evaluation covers seven QA benchmarks, ALFWorld, and five backbone models, including strong baselines, rollout budget comparisons, and component ablations.
Critical weaknesses
  1. The work does not demonstrate how different signals collectively represent uncertainty. The direct evidence justifying the rationale for prioritizing high-U branch exploration is absent.
  2. Most main QA results and ablation studies only report scalar scores without accompanying standard deviations, making it difficult to verify the stability of the proposed method.
Questions for authors
  1. Clarify why the individual components of U described in the paper reflect uncertainty. What do branches with higher U produce more unstable downstream outcomes?
  2. Under the same rollout budget, compare the subsequent returns of high-U and low-U branches.
  3. Report the means and standard deviations for the main QA results and ablations. Are the improvements over Tree-GRPO stable?
4 comments
AuthorsOpenReview ↗

Author Response

Thank you for the questions. We ran all three experiments that related, and the results are in the revised PDF (changes in blue).

Q2. Same rollout budget: high-UU vs. low-UU branches.

We ran this comparison at the final multi-hop checkpoint (Qwen2.5-1.5B). We sampled 512 internal edges at random and gave every edge the same budget of 8 new continuations, none of which was fed back into the tree. The 488 edges that produced scored outcomes (7.9 per edge on average) are split at the median UU. The error of the tree's QQ below is its distance from the mean of these 8 new returns.

EdgesStd of new returnsError of the tree's QQP(new outcomes disagree)
Low-UU half0.0190.0127.0%
High-UU half0.0490.03813.9%

High-UU branches have 2.5× the return dispersion (95% bootstrap CI [1.5, 4.5]) and 3.1× the value-estimation error (CI [1.6, 6.4]), both with permutation p<0.001p<0.001, and their outcomes disagree 6.9 points more often (CI [1.2, 12.5], p=0.008p=0.008). So under the same budget, high-UU branches do give less stable outcomes, and they are where one more rollout changes the estimate most.

W1 / Q1. Why do the components reflect uncertainty?

UU is the sum of three terms, and each one captures a different reason a branch may still be unsettled. Return dispersion asks whether the continuations observed so far disagree, and it carries most of the signal. Propagated uncertainty asks whether the states below are still unsettled, so that an unresolved subtree keeps its ancestors uncertain. Action surprisal is the only signal available on the first visit, before any dispersion can be measured; removing it lowers EM by 0.6–0.7 points (one run).

The trees saved during training (steps 1–180; new App. F) agree with the table above. No branch in the lowest UU quintile has descendants that disagree in correctness (0% in all three runs), while in the highest quintile the share is 13.4% (1.5B multi-hop), 38.3% (1.5B single-hop) and 10.3% (3B single-hop).

W2 / Q3. Repeated runs; is the gain over Tree-GRPO stable?

Every QA setting now has three independent training runs:

BackboneMethodSingle-hop Avg.Multi-hop Avg.
Qwen2.5-1.5BTree-GRPO47.519.1
UMCTS-GRPO49.1 ± 0.3 (49.1 / 49.4 / 48.9)20.2 ± 0.4 (20.5 / 20.3 / 19.7)
Qwen2.5-3BTree-GRPO50.036.8
UMCTS-GRPO50.8 ± 0.4 (50.4 / 51.1 / 50.9)37.6 ± 0.2 (37.8 / 37.5 / 37.6)
Llama3.2-3BTree-GRPO50.036.8
UMCTS-GRPO52.2 ± 0.4 (52.6 / 52.1 / 51.9)37.8 ± 0.3 (38.0 / 37.4 / 37.9)
Qwen2.5-7BTree-GRPO52.237.8
UMCTS-GRPO53.5 ± 0.3 (53.8 / 53.2 / 53.6)38.0 ± 0.2 (38.0 / 38.2 / 37.8)
Qwen2.5-14BTree-GRPO55.745.3
UMCTS-GRPO56.2 ± 0.3 (56.4 / 55.9 / 56.3)47.1 ± 0.3 (47.2 / 46.8 / 47.3)

Macro-averaged EM (%), mean ± std over three independent training runs, per-run values in parentheses.

The mean is above Tree-GRPO in all ten settings. On ALFWorld (three random seeds) the margin is larger.

We repeated the ablations in the same way (Qwen2.5-1.5B multi-hop, three runs each):

VariantThree runsMean ± stdvs. full
UMCTS-GRPO (full)20.5 / 20.3 / 19.720.2 ± 0.4
w/o local credit19.3 / 19.1 / 19.019.1 ± 0.2−1.1
w/o uncertainty weighting19.4 / 18.4 / 18.918.9 ± 0.5−1.3
w/o uncertainty bonus (cu=0c_u=0)12.2 / 12.3 / 12.212.2 ± 0.1−8.0
Random selection11.0 / 11.9 / 11.411.4 ± 0.5−8.8

Tables 1 and 4 of the revision report these three-run means. Every run of the full method is above every run of every ablation. Within UMCTS-GRPO, removing uncertainty guidance from the search costs about 8 points, and removing confidence-weighted credit costs a further 1.1–1.3.

Reviewer_zdJBOpenReview ↗

Response to Author 50350.

Thank you for the authors' response. There is the core issue raised in Q2 non-resolved. The experimental results presented in response to Q2 only demonstrate that high-U branches are indeed more uncertain. They do not directly compare the actual performance difference between exploring high-U and low-U branches under the same rollout budget to claim the exploring value of high-U branches.

AuthorsOpenReview ↗

Author Response

Thank you for the clarification. We ran this direct comparison.

We flipped the sign of the uncertainty term in Eq. 3, so the search sends its rollouts to the branches with the lowest UU. Everything else is unchanged: the rollout budget, the tree configuration, the credit assignment, and the number of training steps.

Qwen2.5-1.5B, multi-hop EM (%), mean over three runs:

Rollouts sent toHotpotQA2WikiMuSiQueBamboogleAvg. (± std)
High-UU branches (ours)29.226.27.418.120.2 ± 0.4
Low-UU branches15.519.83.19.311.9 ± 0.8

Under the same budget, exploring high-UU branches is ~8 points higher on average and higher on all four datasets. Sending the rollouts to low-UU branches gives an average at the level of search without UU (12.2) and random selection (11.4).

Low-UU branches are mostly near-copies of the policy's usual choice: late in training, only 1.2–3.6% of low-surprisal sibling pairs differ in value, against 9.9–16.0% of high-surprisal pairs (Appendix F). High-UU branches have 3.1× the value-estimation error, so a new rollout changes the estimate most there.

Thank you for the additional experiments. Regarding Q1, the authors primarily explain the roles of the individual components intuitively. However, the observed correlation between aggregate U and estimation error does not sufficiently establish why these heterogeneous signals jointly characterize uncertainty in action values. Meanwhile, the gains over Tree-GRPO are small in some settings. Considering the remaining concerns about the method's interpretation and its gains over the baseline, I will maintain my score for now.

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

The paper introduces UMCTS-GRPO, a reinforcement learning method for multi-step LLM agents . It constructs rollout trees to compare alternative actions at shared interaction histories. A branch uncertainty statistic, combining action-token surprisal, propagated uncertainty, and variation in backed-up values, guides exploration during Monte Carlo tree search. The same statistic weights sibling comparisons and scales local advantages, which are combined with trajectory-level GRPO advantages for policy optimization. The method requires no critic, process reward model, or step-level annotations, and tree search is used only during training. Experiments cover seven retrieval-based QA benchmarks and ALFWorld across five model backbones, with comparisons against agent-training baselines, component ablations, and rollout-budget analyses.

Critical strengths
  • Assigning credit to intermediate agent actions when only terminal rewards are available. Comparing alternative actions at shared histories provides step-level training signals without a critic, process reward model, or step-level annotations.

  • The evaluation covers seven retrieval-based QA benchmarks and ALFWorld across five backbones, with additional ablations and rollout-budget experiments.

Critical weaknesses
  • The uncertainty measure lacks a clear statistical interpretation. It combines action-token surprisal, propagated uncertainty, and variance in backed-up value targets. These capture different phenomena and do not necessarily measure uncertainty in the estimated action value. Low-probability text may simply reflect unusual wording, while variable returns may reflect randomness in subsequent actions. The paper does not establish that this combined statistic predicts value-estimation errors or the reliability of sibling comparisons.

  • The uncertainty bonus may remain high even after sufficient exploration. The sample variance of returns need not decrease as more evidence is collected, and the surprisal of a fixed action does not automatically decrease with additional visits. A branch could therefore keep attracting exploration and receiving weaker local updates even when its expected value is accurately estimated. Comparisons against count-adjusted uncertainty estimates would help justify the proposed additive bonus.

  • The gains over the stronger baseline are limited. On ALFWorld, the method improves over GiGPO by only 1.3 percentage points at 1.5B and 3.4 points at 7B. In particular, the 1.5B improvement is comparable in magnitude to the reported variation across seeds.

Questions for authors

The additive uncertainty bonus encourages exploration, but it does not explicitly decrease with visit counts. Token surprisal and return variance may remain high even after a branch’s expected value has been estimated accurately. How does the method avoid repeatedly exploring such branches? Have the authors tried removing token surprisal and using return variability to scale a count-dependent exploration bonus, such as a term proportional to (\hat{\sigma}_R/\sqrt{N(s,a)})?

1 comment
AuthorsOpenReview ↗

Author Response

Thank you for the concrete suggestions. We ran each of them, and the results are in the revised PDF (changes in blue).

W1. Does UU predict value-estimation error and the reliability of comparisons?

As we understand it, the question is whether a high UU means that the tree's QQ is far from the true value of the branch. Since the true value is unknown, we estimated it independently. At the final multi-hop checkpoint (Qwen2.5-1.5B) we sampled 512 internal branches at random and ran up to 8 additional rollouts from each. 488 of them produced scored outcomes (7.9 per branch on average), and we used the mean return of those rollouts as a reference value. These rollouts were never added to the tree, so neither QQ nor UU had access to them, and any relation between UU and the error cannot come from the way UU is computed. We take the error of a branch to be the distance between the tree's QQ and the reference, and split the branches at the median UU:

Low-UU halfHigh-UU halfRatio (95% CI)
Std of the new returns0.0190.0492.5× ([1.5, 4.5])
Error of the tree's QQ0.0120.0383.1× ([1.6, 6.4])

Both differences are significant (permutation p<0.001p<0.001). In the high-UU half the tree's estimate is about three times further from the reference, so sibling comparisons made there are indeed less reliable.

We see the same pattern in the trees built during training. Over steps 1–180, no branch in the lowest-UU quintile has descendants that disagree on correctness (0% in all three runs we analyzed), while in the highest quintile the share is 13.4% (1.5B multi-hop), 38.3% (1.5B single-hop) and 10.3% (3B single-hop). The full table is in the new App. F.

You also questioned the two components separately.

On surprisal: it flags steps that depart from the policy's usual choice, and these turn out to be the steps where siblings actually differ. Over the whole run, 20.5–26.4% of high-surprisal sibling pairs differ in value, against 8.0–10.3% of low-surprisal pairs (2.3–3.0×, in all three runs). The gap grows late in training (steps 121–180: 9.9–16.0% against 1.2–3.6%), because by then low-surprisal siblings are close to copies of one action. Surprisal matters most on the first visit to an edge, when there is a single return and no spread to measure. Removing it costs 0.6–0.7 EM (48.5 / 19.5 vs. 49.1 / 20.2; see the table under W2), so it helps, although the method does not depend on it.

On return variance: we agree that variable returns come from the randomness of later actions. That randomness is also the reason the estimate is uncertain. QQ is the average of at most three sampled outcomes, and the more those outcomes vary, the less we can trust the average. The 3.1× larger error in the table above is a direct measurement of this.

W2 / Q1. Repeated exploration and the σ^R/N(s,a)\hat\sigma_R/\sqrt{N(s,a)} variant.

In our QA experiments a branch cannot be explored over and over, for two reasons. The first is the budget: a tree holds at most three complete trajectories (one initial rollout plus two simulations), so N(s,a)≤3N(s,a)\le 3 for every edge. The second is that Eq. (3) still has the PUCT term, which shrinks every time an edge is visited; UU is added to this term and does not replace it. On ALFWorld, where a tree runs 8 simulations, it is this count term that limits re-selection.

We also ran the variant you suggested (Qwen2.5-1.5B, EM):

VariantSingle-hopMulti-hop
Original UU, three runs (mean ± std)49.1 / 49.4 / 48.9 (49.1 ± 0.3)20.5 / 20.3 / 19.7 (20.2 ± 0.4)
No surprisal, σ^/N\hat\sigma/\sqrt N48.419.6
No surprisal, no count scaling48.519.5

Your variant reaches 48.4 / 19.6, which is 0.7 and 0.6 points below the original. Count scaling is therefore a reasonable alternative, but it brings no gain in this setting. The two are this close because with N≤3N\le 3, dividing by N\sqrt N changes the bonus by at most a factor of 3≈1.7\sqrt 3\approx 1.7. We added the comparison as Table 10 in App. F.

W3. ALFWorld gains over GiGPO.

We agree with you on 1.5B: the difference to GiGPO (88.0 vs. 86.7) is within seed variation. The other comparisons on ALFWorld are clearer. Against Tree-GRPO the gain is +14.6 at 1.5B and +17.7 at 7B, more than four times the larger seed standard deviation of the two methods (3.3). Against GiGPO at 7B it is 94.2 vs. 90.8 (+3.4), and UMCTS-GRPO also learns faster, reaching 85% training success after 60 steps where GiGPO needs 98 (Fig. 4c). We would add that GiGPO relies on environment states that recur across trajectories, whereas UMCTS-GRPO creates its comparisons by branching, which is why the same method can also train the retrieval agents in Table 1.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.