PlanU: Large Language Model Reasoning through Planning under Uncertainty
Authors: Ziwei Deng
Mian Deng
Chenjing Liang
Zeming Gao
Chennan Ma
Chenxing Lin
Haipeng Zhang
Songzhu Mei
Siqi Shen
Cheng Wang
Venue: NeurIPS 2025 poster ()
Keywords: large language models; decision making; reasoning
Primary area: deep_learning
TL;DR: We propose PlanU, a method that enhances LLM-based decision-making under uncertainty by modeling value distributions via quantile regression and guiding MCTS exploration using a novel Upper Confidence Bounds with Curiosity (UCC) score.

Abstract: Large Language Models (LLMs) are increasingly being explored across a range of reasoning tasks. However, LLMs sometimes struggle with reasoning tasks under uncertainty that are relatively easy for humans, such as planning actions in stochastic environments. The adoption of LLMs for reasoning is impeded by uncertainty challenges, such as LLM uncertainty and environmental uncertainty. LLM uncertainty arises from the stochastic sampling process inherent to LLMs. Most LLM-based Decision-Making (LDM) approaches address LLM uncertainty through multiple reasoning chains or search trees. However, these approaches overlook environmental uncertainty, which leads to poor performance in environments with stochastic state transitions. 
Some recent LDM approaches deal with uncertainty by forecasting the probability of unknown variables. However, they are not designed for multi-step reasoning tasks that require interaction with the environment. To address uncertainty in LLM decision-making, we introduce PlanU, an LLM-based planning method that captures uncertainty within Monte Carlo Tree Search (MCTS). PlanU models the return of each node in the MCTS as a quantile distribution, which uses a set of quantiles to represent the return distribution. To balance exploration and exploitation during tree search, PlanU introduces an Upper Confidence Bounds with Curiosity (UCC) score which estimates the uncertainty of MCTS nodes. Through extensive experiments, we demonstrate the effectiveness of PlanU in LLM-based reasoning tasks under uncertainty.

PlanU: Large Language Model Reasoning through Planning under Uncertainty
Ziwei Dengah; Mian Deng"h, Chenjing Liang Zeming Gao Chennan Ma Chenxing Lin Haipeng Zhang Songzhu Mei', Cheng Wang" Siqi Shen
Fuujian Key Laboratory of Sensing and Computing for Smart Cities,
School of Informatics, Xiamen University (XMU), China
Keey Laboratory of Multimedia Trusted Perception and Efficient Computing, XMU, China
"School of Computer, National University of Defense Technology, China
{dengziwei, miandeen ,ariingg.nnngg liangej zeminggao, chennanma, wwllnnccllli 123, wwweeci112,.haaaaaiiiaaaa zhanghaipeng xmu. edu. cn, {siqishen, cwang) 0xmu. edu. cn, {sz. mei] @nudt. edu. cn
Abstract
Large Language Models (LLMs) are increasingly being explored across a range of reasoning tasks. However, LLMs sometimes struggle with reasoning tasks under uncertainty that are relatively easy for humans, such as planning actions in stochastic environments. The adoption of LLMs for reasoning impeded by uncertainty challenges, such as LLM uncertainty and environmental uncertainty. LLM uncertainty arises from the stochastic sampling process inherent to LLMs. Most LLM-based Decision-Making (LDM) approaches address LLM uncertainty through multiple reasoning chains or search trees. However, these approaches overlook environmental uncertainty, which leads to poor performance in environ- ments with stochastic state transitions. Some recent LDM approaches deal with uncertainty by forecasting the probability of unknown variables. However, they are not designed for multi-step reasoning tasks that require interaction with the environment. To address uncertainty in LLM decision-makes an LLM-based planning method that captures uncertainty within Monte Carlo Tree Search (MCTS). PlanU models the return of each node in the MCTS as a quantile distribution, which uses a set of quantiles to represent the return distribution. To balance exploration and exploitation during tree search, PlanU introduces an Upper Confidence Bounds with Curiosity (UCC) score which estimates the uncertainty of MCTS nodes. Through extensive experiments, we demonstrate the effectiveness of PlanU in LLM-based reasoning tasks under uncertainty.
introduce PlanU,
Introduction
Large language models (LLMs)) have demonstrated remarkable capabilities in various domains, such as reasoning and coding 3]. The success of LLMs in various domains has motivated researchers to apply them to decision-makinn tasks [4 where an agent selects actions based on the current state in order to achieve specific goals.
Prior work has explored leveraging LLMs for decision-making in three ways: (1) LLMs are used as policies [4] [] where the LLM is provided with necessary prompts to generate actions. (2) LLMs are used world models [5). where the LLM repurposed with appropriate prompts generate the next state and reward based on a given action. (3) LLMs are used as both the policy and the world
model 9) our work belongs to such category as it mimics human drcision-makingg process.
"qqual contribution Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Performance Different Methods Deterministic Stochastic
100
Mathods
Col [Detemmnnttc
CaT (Stochaatic)
(Deteminisdic)
(Stochoctic)
RAP (Detemetstkd)
505
RAP (Rochaotik)
Accuracy (%)
60-
20
Step 2
Step
Step 6
Step 5
Figure 1: Impact of Environmental Uncertainty on LDM tasks for Block Stacking. The results are grouped according to the least number of steps to finish tasks. "Deterministic" indicates deterministic state transitions. In "Stochastic" environment, with 20% probability, an action will fail.
simulating and anticipating future outcomes through internal world model and making plans based on it TT
The adoption of LLMs for decision makiing is impeded by uncertainty challenges, such as LLM uncertainty [T] 12 and environmental uncertainty [9] LLM uncertainty is caused by the stochastic nature of its generation process, which samples the next token through a distribution. A well-known form of LLM uncertainty is hallucinations [33,, where LLM generates inaccurate outputs. Most LLM-based bebision-maaing (LDM) approaches address LLM uncertainty by trading off computation samples multiple reasoning traces and selects the most consistent answer. ToT 3 and RAP g make plans during search inside trees representing LLM decision spaces.
for certainty 2 6 8
For example, Self-Consistency
2
Most existing LDM approaches overlook environmental uncertainty caused by stochastic transitions. In stochastic environments, the transition between states becomes stochastic rather than deterministic. That is, after taking action a; in state st, the environment could transition to multiple possible next states S1+1- Moreover, the reward ra can also be stochastic. As shown in Figure [ the performance of multiple LLM reasoning approaches drops significantly in the presence of environmental uncertainty. Environmental stochasticity is not rare, even in deterministic environments. State aliasing [14] (e.g..
caused by partial observability) could effectively introduce environmental stochasticity [15].
Only few LDM approaches [ consider environmental uncertainty. DeLLMa [9] deals with envi- ronmental uncertainty by enumerating hidden factors and forecasting their probabilities. However, does not consider environmental feedback, and thus, it is not suitable for tasks requiring multiple steps of decision- decision-making. In general. integrating LLM-based decision- decision-making methods with uncertainty handling remains challenging. We show that naive integrations, such prompting uncertainty consideration within LDM, lead to poor performance even on a simple task in Sec 5.2
In LDM, Monte Carlo Tree Search (MCTS) is widely adopted due to its effectiveness. Our work builds on recent advancements of LLM-based MCTS. When a policy is sampled probabilistically inside an LDM environment, the actions, state transitions, and rewards can cause randommess/uncertaingg in the return of the MCTS tree. LLM-MCTS algorithms [ average
randomness to estimate the return of an MCTS node. The key insight of our work is to model the return of node in MCTS quantile distribution rather than the mean value. PlanU builds an MCTS tree consisting of multiple state nodes and action nodes (st, at), whose return ((s ae) is modeled a quantile distribution [16). The quantile distribution [16), representing return distribution through quantile, is designed to capture the uncertainty in the returns intrinsic to LDM. A skewed quantile distribution indicates high uncertainty, whereas a uniform quantile distribution indicates the opposite.
During planning, PlanU encourages exploration in the face of uncertainty through an Upper Confi- dence Bounds with Curiosity (UCC) score. UCC measures curiosity based on the return of actions and uncertainty. Inspired by (17), UCC estimates the environmental uncertainty of a state 8, by comparing features predicted by neural network to features predicted by fixed randomly initialized neural network. To address LLM uncertainty that different text descriptions can be generated for the

---

same state St, UCC utilizes a text encoder to obtain text embeddings, and then it treats states as the same if their text embeddings are similar.
Through extensive experiments, we demonstrate the effectiveness of PlanU. It performs better than state-of-the-art methods in multiple environments thanks to its ability deal with uncertainty in LLM decision-making.
2 Background
2.1 LLM-based Decision Making (LDM) and Uncertainty
In this work, LDM process is modeled Markov Decision Process (MDP). Given current state 8t, an LLM agent generates an action based on policy ag ~ Tt]]s,, Cp), where Cp is a policy prompt (e.g., task description, in-context example). Once action is chosen, the state transits from 8, to 1 according to the state transition dynamics p(*++1|8: Cw.). where Cu is the world prompt specifying the world dynamics. A reward R(s;, at Cw) is given to the agent.
focus on two major types of LDM uncertainty: LLM uncertainty [T8 and environmental uncer- tainty [1]. Environment uncertainty is caused by the inherent randomness of the environment. For example, coin- woin-flipping action could lead to two outcomes (head or tail) of a coin. LLM uncertainty arises from the stochastic nature of its generation process [ which may produce different responses to the same prompt. For LLM-based policies, such generation uncertainty may lead to incorrect actions decisions. When using LLM world model, LLM uncertainty could lead to incorrect environmental transitions p( M($ 18,, a, Cw).
2.2 Quantile Distribution
To deal with environmental uncertainty, Distributional Reinforcement Learning 15
16
models the value of state-action pair (s, a) as a value distribution ((s, a). These methods model full value distribution (ss, a) instead an expectation value Q(s, a). The value distribution can be
modeled (approximated) as a quantile distribution [66 19] or categorical distribution [5].
In this work, the quantile distribution Z(s, a) is modeled by quantile functions 0 of random variable Z, which is defined as follows.
0z(s, a, T) = inf(z E R: T S Fz(2)), Vr E [0,
where Fz(2) is the eumulative distribution function of Z(s,a) a).
Following QR-DQN [6 and IQN 19 we model the value function ((s, a) as the mixture of n
Dirac functions.
The
7 0)
(Pt i=1
(2)
where )p(na.))) is Dirac Delta function whose value is 0(s, a, R.). is a quantile (e.g., 20%). ps(8, a, T;) is the corresponding probability of A(s, a, Tx), ng is the number of quantiles.
2.3 Monte Carlo Tree Search (MCTS)
Monte Carlo Tree Search (MCTS) 21 22 is widely used decision-making algorithm that explores the search tree smartly. In this tree, nodes represent states, and the edges represent actions. Specifi- cally, an edge between two nodes sj and 82, indicating after applying action a on state s1, the state transits to state The standard MCTS assumes deterministic state transition p(s++1|s a) 100%. That's once an action is taken on s,. will deterministically transit state 81+1. Each iteration of typical MCTS consists of the following four phases:
1. Selection: Starting from the root node, at each level i of the MCTS tree, child node s of the current node 8; is selected. This step ends when a leaf node is reached. The child node s' is selected according to the Upper Confidence applies Trees (UCT) 23 method.
Expansion: If the selected node 8; is not terminal state (leaf node), is expanded by generating child state node $1+1, which is then added to the search tree.
3

---

3. Simulation: From the newly expanded state node, multiple simulations or roll-outs are performed until a computation budget is reached and a reward is obtained.
4. Back-propagation: The result of the simulation operation propagated back to the root node 80-
3 Related Work
3.1 LLM Reasoning and Decision Making
LLM reasoning decomposes complex task into multiple intermediate steps to obtain the correct
answer/solution. Chain-of-Though((CT]] [
and Zero-shot CoT 24 prompt LLMs to generate
plans in a step-by-step manner. Least-to-Most
25 decomposes complex problems into a series of
sequential sub-questions. Self-Correction 26 performs reasoning through reasoner and corrector.
Self- Celf-Consistency (2]. Repeated Sampling
27 demonstrate that sampling diverse reasoning paths can significantly enhance reasoning effectiveness in tasks such as math reasoning. Researchers (28) find that scaling test-time compute can obtain better performance than scaling model parameters.
Due to the strong reasoning ability of LLMs, they are adopted for decision-making in multiple
domains, such as robotics [29] 30) games [1 7 and web shopping (6]. ReAct [32] extends
language models with interaction through external API calls (e.g. web search). Reflexion [3] and
Relf-Refine 34 explore self-evaluation mechanisms to refine reasoninggddcciiinn-akiig processes.
3.2 Tree-based LLM Reasoning and Decision Making
Studies have shown that tree search frameworks significantly improve decision-makin performance by breaking down the tasks into multiple steps and searching inside trees wherein each node/edge represents intermediate step
g 35
Tree Thoughts (ToT) 3 performs breadth-first-search (BFS) or depth-first-searce (DFS) to find solutions trees expanded by LLM. RoT (36] improves tree search performance through reflection. RAP 8 uses a L.LM-based policy and a LLM-based world model to perform Monte Carlo Tree Search (MCTS) for decision making. LATS (6) incorporates self-reflection and API-use (e.g.. ReAcT) into LLM-based MCTS. TS-LLM[4) is LLM-based MCTS method with finetuning.
Process Reward Model (PRM) methods have been used in combination of tree search methods, such as STaR 37 RFT 38 ReSTEM 39), V-STaR [40, ReST-MCTS 41 and AlphaLLLM [42]. For these methods, reward models assign rewards to each step of the tree search to guide the search.
None of the above tree-based LLM Decision Making/reasoning methods address environmental uncertainty explicitly.
3.3 Uncertainty in LLM Decision Making
Multiple methods have been proposed to deal with LLM uncertainty 18]. many of them can be categorized into Bayesian inference-based 43 44
ensemble-based (c.g.. BSDetector [45] and [6)). DeLLMa [9] is method for LLM decision-making under uncertainty based on classical decision theory. uses LLM to identify hidden factors and predict their possible outcomes, and then construct utility functions to build a policy that determines the best possible action. However, it does not use environmental feedback (e.g., rewards) to make decisions. Our work can utilize these LLM advancements to improve LLM decision-making.
As far we know, most existing L.M--bseed decision-making methods do not explicitly account for environmental uncertainty. The work most relevant to ours is RAP [8], an LLM-MCTS method, which queries the LLM-based world model multiple times reduce uncertainty and uses the most frequent outcome as the next state during planning. However, it is not specifically designed for environments with uncertainty.
4 PlanU: LLM-based Planning Under Uncertainty
PlanU is built upon Monte Carlo Tree Search (MCTS) powerful planning algorithm that efficiently explores the decision space to obtain high-reward plans. In the vanilla MCTS [22] tree,

---

select
backpropagation
Select
Backpropagation
To
((
9g
Z(x
argmax
Curiosity
S1+1
T
UCC Scores
QR Loss
(e)
(b)
(c)
Figure 2: Key stages of PlanU's uncertainty aware tree search: (a) select and backpropagation phases; (b) UCC-based action selection by combining value distribution (8, a) and state novelty, where v [ St; at)] maps quantile distribution scalar; (c) distributional updates during backpropagation based on received rewards.
nodes represent states, and edges between nodes represent actions. The value of an edge, denoted as Q(s, a), represents the expected cumulative reward of taking action a in state and following the optimal policy thereafter.
In stochastic environments, an action may lead to different outcomes. The vanilla MCTS cannot model such scenario. The core of PlanU is the use of quantile distribution capture uncertainty within an MCTS tree. As shown in Figure (a), besides modeling states as nodes, PlanU models action nodes, each of which represents state-action pair (s, a) in the decision space. PlanU models the return of each action node (s, a) as a quantile distribution rather than the expected value Q(8, a) in vanilla MCTS [22]
The quantile distribution (ss, a) models the overall uncertainty of the state-action pair (s, a). is used guide the tree search. An example is given in Figure (b). Z(s;, og) and Z(s;, an-1) the quantile distributions action dg and an-1 for state 8,, respectively. In terms of variance, the return for ag is more uncertain than that for Oę-1-
4.1 Tree Search under Uncertainty
During the tree search, actions available for state are added as child nodes of the state node in search tree. An action could lead to multiple states, which are added as the child node of the action node. Each PlanU iteration consists of four phases, which are described as follows.
Selection. Starting from the root node (e.g., the initial state so). the algorithm selects child action node based on its UCC values as follows.
a'' arg max UCC((s, az), (,)(
where s; is the current state, (s:)) ) is the set of actions available for 8t, is the action, UCC az) the UCC score which will be described in Section
The agent performs the selected action according to environment dynamics. s is not already represented in the search tree, it added as a child of the action node az; otherwise, the algorithm transitions directly to the existing node corresponding to 81+1- This phase ends upon reaching a leaf state node.
the state and then the state transits to obtain St+1
In this phase, a leaf state node 8, is expanded along with its corresponding action nodes. For each available action o, in St, an action node is created. In this work. an action o, is represented as a sequence of tokens to. é tn... For each action node, we initialize its quantile distribution Z(s,, a;) using the probability generated by the LLM, computed TT az) I. p(t:)c), where p(t.) denotes the LLM generation probability of token t; and is the prompt. Specifically, the quantile distribution is initialized by a set of ny identical quantile values, each initialized to xt (55), at). It is defined as follows.
Expansion.
Z (Sst. a+) {01, 02..... ... On E R",,, 0, = a(1 0t), Vi E
(4)
5

---

where (s(st, Qz. p) is the quantile value, and Ny is the number of quantiles. In this way, PlanU can utilize the common sense in LLM to initialize action selection probability.
Simulation. This phase simulates multiple trajectories from the newly expanded node to a terminal state estimate the expected future reward for the current state node 8t- Starting from st, rollout policy is used to determine the next action and its corresponding next state. In the actual environment, the state resulting from the same action and initial state may vary, making it essential to retrieve the actual next state from the environment at each step. There could be different rollout policies for simulation. For simplicity and efficiency. we use the same policy as the selection phase. trajectory ends when terminal state is reached or the depth limit is reached.
Back- proppaattpag...nn Once terminal state predefined step limit is reached, a path { an). (1,01))..., (#n,02)) 0z)} is traced from the root state node to the terminal state node 8n- Along this path, each action node ae receives reward rr provided by the environment. We use Quantile Regression (QR) [16] to update the quantile distribution 2(8t, Qe) of node. QR estimates the quantiles of the value distribution by minimizing the distance between ((s,, az) and its target distribution ((5++1 0(+1) _ (Z(+1.. The quantile regression loss is defined as follows.
CQn = EZ Ip a(+1) - (ss a.)ll.
(5)
where 7 is quantile sample and (m) = u((T - 1/44 < 0}). Since the quantile regression loss is not smooth, we use Quantile Huber loss [6] to implement p+()).
4.2 Upper Confidence Bounds with Curiosity
During tree search, PlanU chooses optimism in the face of uncertainty; it encourages exploration through the Upper Confidence Bound with Curiosity (UCC) score. It calculates the uncertainty of text-based states based on the value distribution and novelty of states. Specifically, the UCC score is defined as follows.
re(Se)
UCC(s;, L[Z(s;, a:) +
(6)
N(s
where (s,, at)] is a uncertainty-awant operator that maps quantile distribution into a real-value. Multiple implementations of va can be used. For example, it could be the expectation operator, v v[Z (sc; at)] = [[Z(( (t: 0t]] which is the expectation of value distribution of state-action pair (s, a). It could be defined as (st, az)l + (st, de, To.9) ((s, de, To.1). which consider the spread of return distribution. In default, we use the expectation operator IE as th. C₁ is a hyperparameter, N(s,, az) represents the visit count of the action node a,, and (s:) is novelty reward.
The novelty reward r: (s:) designed to encourage the agent to explore less-visited states from a global perspective through estimating the uncertainty of st. Inspired by [17]. (s:) calculates the feature difference among predictor network f and target network f. Specifically, it is defined as ri())) = f(e(s:)) - f(((s))) (((e)))))((((())))
where and f are both neural networks.
When estimating the state novelty, to reduce the interference of LLM uncertainty. PlanU uses a text encoder e(.) to map text-based state s, to feature vector. The text encoder can map slightly different baxt- descriptions into the similar feature vector, thus reducing exttbased uncertainty from LLM. For example, for the same state, LLM could generate text-based state as "the person is right to the table" or "the table is left to the person". These two texts are semantically the same but different. Through using the text encoder, PlanU can reduce such LLM uncertainty.
The target network f is a neural network that is initialized with random weights, and it is fixed. The parameters of the predictor network f are also randomly initialized, but it is different from that of f. Plan maintains buffer B of the visited states by the agent. After a few iterations, we sample a subset of states from this buffer B, which are then used to train the predictor network í through using rs(s) as the loss, while the target network ff remains fixed.

---

I'm investor planning which stock
largest end
Which stock should buy?
State Node
a: Buy Stock A
69
Action Mode
Averrgee profts
0.316.13
0:330.34
0.7
0.23..22
PCs Iaan1
xbb1)-11 -1
wislk)) Ag
0.9229.23
()
X
R|Z
10.9
CoToUl
DelLiN
RAP
RAP-U
Raflection
plant
PianU
Figure 3: Stock Investment Tasks. The agent faces two actions: buying stock which guarantees a profit (reward) of 0.9, or buying stock b with a 60% probability of earning a profit and 40% probability of zero- erooprofi.. The right part shows the average profits for different methods.
5
Evaluation
We study the performance of PlanU on five decision- decision-making benchmarks: Blocksworld, Overcooked, VirtualHome, Travelplanner and Webshop. We show that PlanU can obtain promising performance across multiple rrcision-maaingg scenarios under uncertainty. Ablation studies reveal the importance of measuring unceratinty using value distribution and the UCC score for achieving good performance.
5.1 Experimental Setup
Our selected baseline methods include:
(1) CoT M: prompt-based method that guide LLM to perform chain-of-thought reasoning. method performs deliberate decision decision-making inside search tree. improve its performance.
(2) ToT 3]: an prompt-based method that considers environmental feedback, which is used to
(3) Reflexion [33]
(4) DeLLMa [ an L.MM-bssed single-step decision- maaiin method under uncertainty based on
classical decision theory.
(5) RAP X an L.M--based method that utilizes MCTS for strategic exploration,
(6) RAP-D: a variant of RAP. It replaces the MCTS component in RAP by DMCTS 48 which
learns a posterior distribution over the utility of the different possible returns.
(7) RAP-E: variant of RAP. It replaces the MCTS component in RAP by EMCTS
49 method
that considers epistemic uncertainty decision-making.
(8) LATS an LLM-based method that integrates Monte Carlo Tree Search (MCTS) to coordinate
reasoning, action, and planning for complex decision maakng tasks. (9) QR-DQN[T]: Reinforcement Learning method using quantile distribution model uncertainty.
All the experiments are repeated times with different seeds.
A Simple Stock Investment Task
Considering a stock investment task for stock and B, person has fixed profit (i.e., 0.9) when investing stock A, but has different outcomes (profit of with 60% chance, otherwise 0) when investing stock B. We use COT, DcLLMa, RAP, and Reflexion for this task. We have prompted CoT and RAP to consider uncertainty during decision-make making, and they are named CoT+U, RAP+U, respectively. As it is reported in Figure 3 all these methods perform poorly. This indicates that simple integrations of deccision-making method with uncertainty estimation method do not work.
RAP cannot obtain the best decision. Vanilla MCTS, used in RAP, assumes deterministic environment transitions. To enforce such unrealistic assumption, when determining the child node for a node, MCTS will query the world model multiple times, and use most frequent state as the child node. Thus, when traveling from so through b, MCTS will use the most frequent state 82 (with reward 1) as the state, which leads to a suboptimal policy. We show in the left part of Figure 3 that PlanU can leamn the correct expected return (E]2(so, b) 0.6) while LLM-MCTS (i.c., RAP) fails. Thanks to

---

Table The Success Rate of the Blocksworld Benchmark. Tasks are organized according to minimal steps (n-step) to finish the task.
Tasks (n-stepp)
Model
Method
4
8
CoT
0.514 0.06
0.276 0.05
0.131
0.03
0.000 0.00
ToT
0.486 0.06
0.055
0.117 = 0.03
0.028 = 0.01
RAP
0.892 + 0.03
0.06
0.166
0.000:0.00
Mistral-7B
RAP-D
0.973 # 0.02
0.632
0.02
0.105 = 0.03
RAP-E
1.000 = 0.00
0.59
0.338
0.084 0.03
PlanU
1.000 0.00
0.803 0.04
0.559
0.217 0.03
CoT
0.351 + 0.05
0.03 0.05
0.014 0.01
ToT
0.459 + 0.06
0.005
0.131 0.03
0.056 0.02
RAP
0,946 + 0.02
0.005
0.255
0.175 # 0.03
LLama3.1-8B
RAP-D
0.973 + 0.02
0.004
0.008
0,070 # 0.02
RAP-E
0.946 + 0.02
0.004
0.01
0.140 0.03
PlanU
1.000 + 0.00
0.842
0.524
0.238 0.03
CoT
0.405 + 0.06
0.152 0.00
0.077 0.03
ToT
0.514 0.06
0.00
0.145 = 0.04
0.034 0.02
DeepSeek-RI-
RAP
1.000 + 0.00
0.004
0.200 0.04
0.196 = 0.03
RAP-D
0.973 + 0.02
0.400 0.04
0.140 = 0.03
RAP-E
1.000 + 0.00
0.697
0.448 0.05
0.175 0.03
PlanU
1.000 0.00
0.816 0.04
0.455 0.05
0.196 0.02
[+] Tomato salad
(b) Tomato lettuce saled
Entertainment
3.0
0.3
60
2000 30.00
2002
2000
12.00
6203
2008
8000
4200
Crvirommennaal
Figure 4: The Return on the Overcooked benchmark: (a) Tomato salad, (b) Tomato lettuce salad, and the VirtualHome benchmark: (c) Entertainment.
the ability to model environmental uncertainty, PlanU can make the optimal decision to obtain the highest profit (i.e., 0.9).
5.3 Blocksworld
In Blocksworld tasks 8 50), the goal is to stack blocks on table. this environment, all the states and actions text-based, and the environmental transition deterministic. We introduce environmental uncertainty by adding 20% failure rate for actions: STACK, UNSTACK, PUT, and PICKUP, Failed actions keep the state intact. The tasks categorized into three difficulty tiers according to the minimum required action steps: 2-step (37 tasks), 4-step (76 tasks), 6-step (145 tasks), and 8-step (143 tasks).
We conduct experiments on the Blocksworld tasks on three LLMs: Mistral-7B. Llama3. 1-8BB DeepSeck-RI-Diseee Lis-Disill--Llam--B1 As is shown in Table I PlanU performs the best across all the tasks for the three LLMs. RAP performs better than ToT. which performs better than COT. The RAP variants, which consider environmental uncertainty, perform the second. PlanU performs better than them, thanks to its ability to handle environmental uncertainty and LLM uncertainty.
5.4 Overcooked and Virtual Home
agents prepare and deliver tomato salad and tomato-lettuee salad using provided resources. The states and actions are text-based. There are two tasks in this environment: Tomato salad, and Tomato lettuce salad. The original environment assumes
Overcooked In the Overcooked environment 51

---

Table 2: Experimental results on TravelPlanner
Method
Task Completion Rate
Constraint Satisfaction Rate
CoT RAP
0.156 + 0,030
0.022 = 0,010
0.222 = 0.025
0,044 0.012
LATS
0.234 # 0.039
0.089 0.017
PlanU
0.378 # 0.020
0.222 = 0.015
Table 3: Experimental results on WebShop
Method
Average Reward
Success Rate
CoT
0,46 0.04
0.1
RAP
0.41 0.02
0.2
LATS
0.57 0.07
0.3
PlanU
0.73 + 0.07
0.5
deterministic transition, add uncertainty into the environments by adding 20% failure rate for the Chop action. A failed action leads the state unchanged.
The experimental results are presented in Figure Fa b). where the horizontal and vertical axes represent environmental steps and returns, respectively. PlanU achieves the best performance across both tasks. RAP and RAP-E rank second the Tomato Salad and Tomato Lettuce Salad tasks, respectively. Notably, on the Tomato Lettuce Salad task-which more complex than Tomato Salad-PlanU is the only method that successfully completes the task, owing to its strong capability in handling decision- makinn uncertainty. Compared to RAP-D and RAP-E, PlanU demonstrates greater efficiency in exploring novel states via the UCC score, well more effective backpropagation through value distributions, ultimately leading to optimal reasoning paths.
The VirtualHome benchmark 12 v models furnished house, where simulated em- bodied agent execute actions to complete tasks. We evaluate two tasks: Entertainment (coordinating snack preparation with TV viewing) and Food Preparation (heating a pancake in the microwave). To increase the uncertainty the tasks, we increase the failure rate for opening appliances (c.g.. microwave) as 50%. Failed actions do not impact the environment.
VirtualHome
The result for the Entertainment and the Food Preparation task is shown in Figure 4(c) and the Appendix, respectively. These results demonstrate the promising performance of PlanU. PlanU effectively handles task uncertainty, enabling the agent to balance exploitation and exploration, thereby finding the optimal path faster than others. Other methods, including MCTS-basee (e.g.. RAP) and the RL algorithm (i.e., QRDQN), fail to succeed this task.
5.5 TravelPlanner
We evaluated PlanU on 45 travel planning tasks of varying difficulty using the TravelPlanner bench- mark (53). The benchmark requires agents to generate comprehensive plans covering transportation, meals, and accommodation, with access to search capabilities for information gathering. To simulate real-world uncertainty, delay probabilities were injected for planes and trains based empirical aviation delay models (54] and national transportation statistics (80.76% on-time rate for flights; 2% delay rate for trains), where delays could invalidate subsequent itinerary segments. Evaluation metrics included Task Completion Rate (coverage of core travel elements) and Constraint Satisfaction Rate (average adherence to commonsense/hard constraints). Results are shown in Table
5.6
WebShop
PlanU was evaluated on 10 shopping tasks using the WebShop benchmark (55), where agents must fulfill specific user requirements (e.g., brand, price, size) by interacting with million-item online store clicks and searches. To mimic real-world conditions, web actions incurred network latency following long-tail log-normal distribution(mean 2s), with actions failing if latency exceeded 10s.
Performance was measured by average reward (percentage of satisfied user attributes) and success rate (frequency of full requirement fulfillment). Results presented in Table 3

---

(a) Tomato lettuce salad
(b) Entartainment
Entertainment
1-2
Fland proppt Milede
Borserss
-02
1890
2089
3006
4000
1900
6890
1080
2006
3000
40:0
5003
5008
1000
2008
2008
4089
5000
0008
Figure 5: The impact of (a) quantile distribution, (b) UCC score, and (c) LLM uncertainty PlanU.
5.7 Ablation Studies
Quantile Distribution and UCC Score. S(a.)) illustrate the impact of the quantile distribution and the UCC score for PlanU. PlanU w/o dist denotes the variant where the quantile distribution (i.e., the first term in Equation 8 is replaced by the mean value, and PlanU w/o ucc refers to the variant where the novelty reward (1.e., the second term in Equation (8) is replaced by the UCT exploration term. In Tomato Lettuce Salad, removing either the quantile distribution or the UCC term leads to failure in identifying the optimal path. Entertainment, PlanU and its variants can eventually reach the optimal path, PlanU learns faster than its variants. These experiments demonstrate the usefulness of quantile distributions and the UCC scores.
LLM Uncertainty and Environmental Uncertainty To evaluate our method's robustness to LLM types of perturbations to LLM prompts, which lead different outputs
uncertainty, we introduce from LLMs given the same state: (1) Prompt Shuffling: We shuffle the sentences in the provided prompt while preserving the sentence boundaries and semantic integrity of the task and environment description. (2) Prompt Injection: We inject iisklirrelevant but environment-related information into the prompt that does not aid in solving the task. These forms of uncertainty commonly arise when prompts include content generated by LLMs. Examples of such prompts and results for the Tomato Lettuce Salad task are provided in Appendix [D] while the results for the Entertainment task are shown in Figure5]cc These results demonstrate that LLM uncertainty only slightly affects the convergence speed of PlanU, This indicates that our method robust to LLM uncertainty. Moreover, we evaluate PlanU against increasing environment stochasticity in the appendix. We find that PlanU performs more robustly than other methods.
Conclusion
LLM-based decision-making suffers from LLM uncertainty and environmental uncertainty. this work, we propose PlanU, an LLM-based decision-making method that plans under uncertainty. It is an LLMM-basd Monte Carlo Tree Search (MCTS) method, where the return value of the MCTS node modeled quantile distribution to capture uncertainty. To balance exploration and exploitation inside the search tree, PlanU uses Upper Confidence Bounds with a Curiosity (UCC) score, which considers the uncertainty of state. Through extensive experiments, we show that PlanU is promising method for decision-making under uncertainty.
Acknowledgments
This work was partially supported by the Fundamental Research Funds for the Central Universities (No. 20720230033), by Xiaomi Young Talents Program. We would like to thank the anonymous reviewers for their valuable suggestions.
References
[1] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoe Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning large language models. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors,
10

---

Advances in Neural Information Processing Systems, volume 35, pages 44824-24837. Curran Associates, Inc., 2022.
[2] Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe V Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. In The Eleventh International Conference on Learning Representations, 2023.
[3] Shunyu Yao, Dian Yu, Jeffiey Zhao, Izhak Shafran, Thomas L. Griffiths, Yuan Cao, and Karthik R Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[4] Xidong Feng, Ziyu Wan, Muning Wen, Stephen Marcus McAleer, Ying Wen, Weinan Zhang, and Jun Wang. Alphazero-like tree-search can guide large language model decoding and training. 2024.
[5] Zirui Zhao, Wee Sun Lee, and David Hsu. Large language models as commonsense knowledge for large-scale task planning. In RSS 2023 Workshop on Learning for Task and Motion Planning, 2023.
[6] Andy Zhou, Kai Yan, Michal Shlapentokh- Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning, acting, and planning in language models. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.ned 2024.
[7] Weihao Tan, Wentao Zhang, Shanqi Liu, Longtao Zheng, Xinrun Wang, and Bo An. True knowl- edge comes from practice: Aligning large language models with embodied environments via reinforcement learning. In The Twelfth International Conference on Learning Representations, 2024.
[8] Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong. Zhen Wang, Daisy Zhe Wang, and Zhiting Hu. Reasoning with language model is planning with world model. In EMNLP, pages 8154 8173, 2023.
[9] Ollie Liu, Deqing Fu, Dani Yogatama, and Willie Neiswanger. Dellma: A framework for decision making under uncertainty with large language models. In ICLR. OpenReview.net, 2025.
[10] Philip N. Johnson-Laird. Mental models and human reasoning. Proceedings of the National Academy of Sciences, 107(43):18243-122)) 2010.
[11] Joris Baan, Nico Daheim, Evgenia Ilia, Dennis Ulmer, Haau-Sing Li, Raquel Fernández, Barbara Plank, Rico Sennrich, Chrysoula Zerva, and Wilker Aziz. Uncertainty in natural language generation: From theory to applications. CoRR, abs/2307. 15703, 2023.
[12] Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ B. Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Bryn- jolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri S. Chatterji, Annic S. Chen, Kathleen Creel, Jared Quincy Davis, Dorottya Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren E. Gillespie, Karan Goel, Noah D. Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark S. Krass, Ranjay Krishna, Rohith Kuditipudi, and et al. On the opportunities and risks of foundation models. CoRR, abs/2108.0725$. 2021.
[13] S. Farquhar, J. Kossen, L. Kuhn, et al. Detecting hallucinations in large language models using semantic entropy. Nature, 130:625-630 2024.
[14] Andrew Kachites Mccallum and Dana Ballard. Reinforcement learning with selective perception and hidden state. PhD thesis, 1996. AA19618237.
[15] Mare G. Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforce- ment learning. In ICML, volume 70, pages 449-458, 2017.

---

[16] Will Dabney. Mark Rowland, Mare G. Bellemare, and Rémi Munos. Distributional reinforce- ment learning with quantile regression. In AAAI, 2018.
[17] Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint arXiv:1810.12894 2018.
[18] Linyu Liu, Yu Pan, Xiaocheng Li, and Guanting Chen. Uncertainty estimation and quantification for llms: A simple supervised approach. CoRR, 0bss24044119933, 2024.
[19] Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. In ICML., volume 80, pages 110--113, 2018.
[20] Jingliang Duan, Yang Guan, Shengbo Eben Li, Yangang Ren, Qi Sun, and Bo Cheng. Distribu- tional soft actor-critic: Off-policy reinforcement learning for addressing value estimation errors. IEEE TNNLS, 2022.
[21] Maciej Swiechowski, Konrad Godlewski, Bartosz Sawicki, and Jacek Mandziuk. Monte carlo tree search: a review of recent modifications and applications. Artif. Intell. Rev., 56(3):2497- 2556, 2023.
[22] D. Silver, A. Huang, C. Maddison, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529:522944444 489, 2016.
[23] Levente Kocsis, Csaba Szepesvári, and Jan Willemson. Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 1:1-22, 2006.
[24] Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 222213, Curran Associates, Inc., 2022.
[25] Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, and Ed Chi. Least-to-most prompting enables complex reasoning large language models. In The Eleventh International Conference on Learning Representations, 2023.
[26] Sean Welleck, Ximing Lu, Peter West, Faeze Brahman, Tianxiao Shen, Daniel Khashabi, and Yejin Choi. Generating sequences by learning to self-correct. In The Eleventh International Conference Learning Representations, 2023.
[27] Bradley Brown, Jordan Juravsky, Ryan Ehrlich, Ronald Clark, Quoe V. Le, Christopher Ré, and Azalia Mirhoseini. Large language monkeys: Scaling inference compute with repeated sampling, 2024.
[28] Charlie Snell, Jachoon Lee, Kelvin Xu, and Aviral Kumar. Scaling I1m test-time compute optimally can be more effective than scaling parameters for reasoning. In ICLR. OpenReview.net, 2025.
[29] Danny Driess, Fei Xia, Mchdi S. M. Sajjadi, Corey Lynch, Aakanksha Chowdhery, Brian Ichter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong. Tianhe Yu, Wenlong Huang, Yevgen Chebotar, Pierre Sermanet, Daniel Duckworth, Sergey Levine, Vincent Vanhoucke, Karol Hausman, Marc Toussaint, Klaus Greff, Andy Zeng, Igor Mordatch, and Pete Florence. Palm-e: An embodied multimodal language model. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 8469-8488. PMLR, 2023.
[30] Brian Ichter, Anthony Brohan, Yevgen Chebotar, Chelsea Finn, Karol Hausman, Alexander Herzog, Daniel Ho, Julian Ibarz, Alex Irpan, Eric Jang, Ryan Julian, Dmitry Kalashnikov, Sergey Levine, Yao Lu, Carolina Parada, Kanishka Rao, Pierre Sermanet, Alexander Toshev, Vincent Vanhoucke, Fei Xia, Ted Xiao, Peng Xu, Mengyuan Yan, Noah Brown, Michael Ahn, Omar Cortes, Nicolas Sievers, Clayton Tan, Sichun Xu, Diego Reyes, Jarek Rettinghouse, Jornell Quiambao, Peter Pastor, Linda Luu, Kuang-Huei Lee, Yuheng Kuang, Sally Jesmonth, Nikhil J. Joshi, Kyle Jeffrey, Rosario Jauregui Ruano, Jasmine Hsu, Keerthana Gopalakrishnan,
12

---

Byron David, Andy Zeng, and Chuyuan Kelly Fu. Do as can, not as I say: Grounding language in robotic affordances. In Karen Liu, Dana Kulic, and Jeffrey Ichnowski, editors, Conference on Robot Learning, CoRI. 2022, 14-18 December 2022, Auckland, New Zealand, volume 205 of Proceedings of Machine Learning Research, pages 287-318. PMLR, 2022.
[31] Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. Trans. Mach. Learn. Res., 2024, 2024.
[32]
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik R. Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. In ICLR. OpenReview.net, 2023.
[33] Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik R Narasimhan, and Shunyu Yao. Reflexion: language agents with verbal reinforcement learning. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[34] Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao. Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang. Shashank Gupta, Bodhisattwa Prasad Majumder, Katherine Hermann, Sean Welleck, Amir Yazdanbakhssh, and Peter Clark. Self- Iterative refinement with self-feedback. In Advances in Neural Information Processing Systems 36: Annual Conference Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans. LA, USA, December 10 16, 2023, 2023.
refine:
[35] Zhenting Qi, Mingyuan Ma, Jiahang Xu, Li Lyna Zhang, Fan Yang, and Mao Yang. Mutual reasoning makes smaller ilms stronger problem-solvers 2024.
[36] Wenyang Hui, Yan Wang, Kewei Tu, and Chengyue Jiang. Rot: Enhancing large language models with reflection on search trees. arXiv preprint arXiv:2404.05444 2024.
[37] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D. Goodman. Star: Bootstrapping reasoning with reasoning. In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022.
[38] Zheng Yuan, Hongyi Yuan, Chengpeng Li, Guanting Dong, Chuanqi Tan, and Chang Zhou. Scaling relationship on learning mathematical reasoning with large language models. CoRR, abs/2308.0182. 2023.
[39] Avi Singh, John D. Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil, Xavier Garcia, Jeter Liu, James Harrison, Jachoon Lee, Kelvin Xu, Aaron T. Parisi, Abhishek Kumar, Alexan- der A. Alemi, Alex Rizkowsky, Azade Nova, Ben Adlam, Bernd Bohnet, Gamaleldin Fathy Elsayed, Hanie Sedghi, Igor Mordatch, Isabelle Simpson, Izzeddin Gur, Jasper Snoek, Jef- frey Pennington, Jiri Hron, Kathleen Kenealy, Kevin Swersky, Kshiteej Mahajan, Laura Culp, Lechao Xiao, Maxwell L. Bileschi, Noah Constant, Roman Novak, Rosanne Liu, Tris Warkentin, Yundi Qian, Yamini Bansal, Ethan Dyer, Behnam Neyshabur, Jascha Sohl- Dick-Dickstein, and Noah Fiedel. Beyond human data: Scaling self self-training for problem-solving with language models. Trans. Mach. Learn. Res,, 2024, 2024.
[40] Arian Hosseini, Xingdi Yuan, Nikolay Malkin, Aaron C. Courville, Alessandro Sordoni, and Rishabh Agarwal. V-star: Training verifiers for self-taught reasoners. CoRR, ab/2240.0065577 2024.
[41] Dan Zhang, Sining Zhoubian, Ziniu Hu, Yisong Yue, Yuxiao Dong, and Jie Tang. ReST- MCTS*: LLM self-training via process reward guided tree search. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[42] Ye Tian, Baolin Peng, Linfeng Song. Lifeng Jin, Dian Yu, Lei Han, Haitao Mi, and Dong Yu. Toward self-improvemmnt of LLMs via imagination. searching, and criticizing. In The eighth Annual Conference on Neural Information Processing Systems, 2024.
[43] Yu Feng, Ben Zhou, Weidong Lin, and Dan Roth. BIRD: A trustworthy bayesian inference framework for large language models. 2025.
13

---

[44] Fabian Falck, Ziyu Wang, and Christopher C Holmes. Are large language models bayesian? martingale perspective on in-context learning. In ICLR Workshop. OpenReview.net, 2024.
[45] Jiuhai Chen and Jonas Mueller. Quantifying uncertainty in answers from any language model and enhancing their trustworthiness. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 5186-5200 Bangkok, Thailand, August 2024, Association for Computational Linguistics.
[46] Hsiu-Yual Huang, Zichen Wu, Yutong Yang, Junzhao Zhang, and Yunfang Wu. Unlocking the power of IIm uncertainty for active in-context example selection, 2025.
[47] Cameron Browne, Edward Jack Powley, Daniel Whitchouse, Simon M. M. Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez Liebana, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in Games, 4:1-43, 2012.
[48] Conor F Hayes, Mathieu Reymond, Diederik M Roijers, Enda Howley, and Patrick Mannion. Distributional monte carlo tree search for risk-aware and multi-objective reinforcement learning. In Proceedings of the 20th international conference on autonomous agents and multiagent systems, pages 1530-1532. 2021.
[49] Yaniv Oren, Viliam Vadocz, Matthijs J. Spaan, and Wendelin Boehmer. Epistemic monte carlo tree search. In The Thirteenth International Conference Learning Representations, 2025.
[50] Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kambhampati. Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change. In Advances in Neural Information Processing Systems, volume 36, pages 38975 -389877 Curran Associates, Inc., 2023.
[51] Micah Carroll, Rohin Shah, Mark Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan. On the utility of learning about humans for human-ai coordination. In H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[52] Xavier Puig, Kevin Ra, Marko Boben, Jiaman Li, Tingwu Wang, Sanja Fidler, and Antonio Torralba. Virtualhome: Simulating household activities via programs. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), June 2018
[53] Jian Xie, Kai Zhang, Jiangjie Chen, Tinghui Zhu, Renze Lou, Yuandong Tian, Yanghua Xiao, and Yu Su. Travelplanner: A benchmark for real-world planning with language agents. In Forty-first International Conference on Machine Learning. 2024.
[54] Evangelos Mitsokapas, Benjamin Schäfer, Rosemary Harris, and Christian Beck. Statistical characterization of airplane delays. Scientific Reports, 1 (11):7885, 2021.
[55] Shunyu Yao, Howard Chen, John Yang. and Karthik R Narasimhan. Webshop: Towards scalable real-world web interaction with grounded language agents. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
14

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No], or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justificcton right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]", ", it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The main claims in the abstract and introduction align with the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
15

---

Justification:
The paper discusses the limitations in Appendix F, addressing potential constraints and areas for future improvement.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-ten system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [NA]
Justification: The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The paper includes detailed descriptions of the experimental setup, algo- rithms, model architectures, and datasets used, ensuring that necessary information for reproducing the main experimental results is provided in 5 and Appendix B.
16

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: We have included the code and experimental results in the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ctiips.cc/puulic/guuii
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
17

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Complete experimental parameters and implementation details are provided in Appendix C.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The paper reports error bars and explicitly states that all experiments were repeated with 5 random seeds ensure statistical significance.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided details the hardware configurations, including memory, CPU, and GPU information, in Appendix C.
18

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics htttossttttt::: btctts::/neurippe: httpa//wgw...ppuuo///aaaaeeeeeee
Answer: [Yes]
Justification: The research presented in this paper adheres to all the guidelines specified in the NeurIPS Code of Ethics. We have ensured that our methods and experiments are conducted responsibly and ethically.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have discussed this issue in the appendix F.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
19

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: We have included the source URLs for all baselines in Appendix C to ensure responsible usage and proper attribution.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All existing assets used this paper are properly credited. We have cited the original papers that produced the code packages and datasets. The specific versions of the assets used are mentioned, and URLs to the sources are provided in Appendix C.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We have provided the code in the supplementary materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
20

---

The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
Declaration LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: Our core methodology incorporates LLMs key component, directly impacting the research's 's originality and technical approach. This usage is explicitly declared in the paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, ntn-standard components.
Please refer to LLM for what should or should not be described.
21

---

Appendix
A PlanU Algorithm
A.1 Algorithm
The PlanU algorithm is described in Algorithm !
Algorithm 1 The PlanU Algorithm
1: Require: Initial state su. environment dynamics D, prior action probability S x A - R.
number of iterations I, number of quantiles Ng ,epthh limit L, prior weight a, {mI, T TN,
2: Initialize memory: Ca : A S, C,
A, quantile probabilities
3: Initialize: value distribution F: S x A
NR,, and state uncertainty networks f
4: EXPANSION(So)
5: for i + to do
6:
+
7: while 9; is not a leaf state node do
8:
at f- arg max UCC(ss a)
9:
(5,+1, )) + D(st, ac)
10:
1+t+1
if 8841 & calar; +) then calar, s1+1) t Sc+1
12:
end if end while
Selection
14:
while not done and t L do
16:
EXPANSION($:)
G₂ f- arg (ax UCC(ss,
18:
(s++1, done, rτ) + (()
19:
t +
Simulation
end while
21:
Update uncertainty estimation network f with {si....,
22: BACK PROPAGATTIO
23:
end for
A.2 Inference Scaling and Vanilla MCTS
Inference-tin scaling increases the performance of LLM through increasing computational resources and time used during the inference phase. Multiple inference-time scaling methods are proposed, such the majority voting, best-of-n, and tree searches. Among them, the Monte Carlo Tree Search (MCTS) technique is one of the most widely utilized tree search methods. It has been used for LLM decision-making and reasoning, such RAP 8 LATS (6), and TS-LLM (4.
In vanilla ICTTS-based LLM planning (i.e., g during planning, the LLM builds a search tree by iteratively selecting the most promising next steps (i.e., actions). It uses world model to predict future states and rewards. The estimated rewards are used to update the value of the search tree, which improves the planning ability of LLM. Although MCTS- LLM demonstrated remarkable planning capabilities through the use of MCTS methods, it may fail in simple planning problems with stochastic state transition dynamics.
Vanilla MCTS assumes a deterministic relationship among the next states and actions. When determining the child state node for state node, the child state node is determined deterministically rather than stochastically once an action a; is taken from the state st. Figure iilllstrates failure case of an ACTTS-baeed LLM agent for basketball shooting. In MCTS-based LLM 8 5), when adding state node into the search tree, an LLM-based world model is queried multiple times, and the most frequently appearing state is used the state. For Figure 6 the player has a 60% chance of scoring; thus, the scoring state is returned. However, this state transition not true, which could hurt MCTS performance. The deterministic state transitions assumption is valid in deterministic environments
22

---

LLM world model
Sp
The player has 60% chance of scoring and 40% chance of missing.
Basketballshootingg
Action
?
S/2
Action c
Action
Set the state the most possible state (scoring)
S4
$5
Figure 6: basketball shooting example, where MCTS fails to model the stochastic state transition. Shooting can lead to the scoring or the missing state, but the vanilla MCTS only models the scoring state.
such as Go but is not valid real-world environments. Due the simplified assumption, MCTS performs poorly for stochastic environments.
B Baseline Methods and PlanU variants
We consider five categories of methods used for comparison: (1) Prompt-based methods: Chain-of- Though (CoT) and Reflexion; (2) Tree-search methods: ToT, RAP, LATS; (3) Tree-search methods considering uncertainty: RAP-D, RAP-D-UCC, RAP-E; (4) LLM-based decision making method under uncertainty: MeI,MM;; (5) Reinforcement Learning method: QRDQN.
1. CoT prompt-based method that guide LLM to perform Sfain-of-thoughhe reasoning!
2. ToT 3 LLM-based method performs deliberate decision-making inside search tree? It searches inside a tree whose nodes represent thoughts.
3. Reflexion 33 a prompt-based method that considers environmental feedback, which is
used to improve its performance'.
4. DeLLMa 9 an LLM-based single-step decision-making method under uncertainty based classical decision theory*.
5. RAP []: an LLM-based method that utilizes MCTS for strategic exploration'.
6. RAP-D: variant RAP designed by us. We replaces the MCTS component in RAP by DMCTS 48), which learns posterior distribution over the utility of the different possible returns.
7. RAP-D-UCC: variant of RAP-D. We combines RAP-D with the UCC scores proposed in this work.
8. RAP-E: variant of RAP designed by us. We replaces the MCTS component in RAP by
EMCTS 49), method that considers epistemic uncertainty in decision-making"
9. LATS 6 an LLM-MCTS based decision making method which integrates reflection and API use into the MCTS search process?.
10. QRDQN[16: uncertainty
Reinforcement Learning method using quantile distribution to model
httpoh/hhhggggggg.ooooooooo/oo/a thought- 11m
3 "Reflexion: Petekon...tttss//ttaaooo//o/aaaa
*DeLLMa: httpp://ggthhb.cc///blllal//////
" http::/pww.....ooooo//cc/cc///aa
htt.://www.///ttttt...oooooo/ooa pytorch
23

---

In this work, we consider a few PlanU variants to evaluate impact of its design. These variants are listed follows.
1. PlanU w/o dist: variant of PlanU, where the quantile distribution removed. It does not capture environmental uncertainty through quantile distribution.
2. PlanU w/o UCC: variant of PlanU, where the UCC scores are removed, the second term in Equation 8 is replaced by the UCT exploration tern. It does not fully consider LLM uncertainty.
3. PlanU prompt shuffling: a variant of PlanU, where the prompt sentences for the policy and the world model are shuffled, respectively. This is used to evaluate the impact of LLM uncertainty caused by prompt shuffling.
4. PlanU prompt injection: variant of PlanU, its prompts are injected with task-irrelevant but peviironmentrellatee information. However, these environment-related information useless for the specific task. This is used to evaluate the impact of LLM uncertainty caused by prompt injection.
C Experiment Results
In this experiments, compare PlanU with 10 different methods, and show that PlanU performs better than all of them in 3 LLM decision making benchmarks. We show that the quantile distribution and the UCC scores play important roles for dealing environmental and LLM uncertainty.
C.1 Setup and Computing Resources
In this work, all the experiments are repeated with 5 different seeds. For the baseline methods, we their default configuration. We set the number of quantiles 50. The ei in Equation g is set to 0.25, and the update rate of the quantile distribution is fixed at 0.5.
The experiments were conducted high-performance computing clusters equipped with NVIDIA A40 GPU, each with 48GB memory. The CPUs used in the cluster are Intel(R) Xeon(R) Silver 4216 processors, each running 10GHz. The memory of each computing node is 1024GB.
C.2 Blocksworld
In Blocksworld tasks 8 50,, the goal is to stack blocks on a table. this environment, all the states and actions tast- and the environmental transition deterministic. We introduce environmental uncertainty by adding 20% failure rate for actions: STACK, UNSTACK, PUT, and PICKUP. Failed actions keep the state intact. The tasks are categorized into three difficulty tiers according to the minimum required action steps: 2-step (37 tasks), 4-step (76 tasks), 6-step (145 tasks), and 8-step (143 tasks).
C.2.1 Task Description
The agent is placed in Blocksworld environment, where the goal is stack blocks table. Only one block can be moved at a time, and a block cannot be moved if there are other blocks on top of it. Similarly, block cannot be stacked another block that already has a block top. The goal specifies the stacking order, which may include multiple stacks or require some blocks to remain on the table.
The environment world consisting of set of blocks, each identified by color. The agent can only observe the positions of the blocks and their clear status (whether block on top of another). The global state includes the positions and statuses of all blocks, and the agent can only observe limited set of blocks within a defined radius. The initial positions of all blocks are known to the agent. The observation data directly used as input for planning models such as LLMs, represented through symbolic data.
Observation Space:
Action Space: The task includes four fundamental actions that the agent can perform:
STACK: The agent stacks block onto another block.

---

Table 4: The Success Rate of the Blocksworld Benchmark. Tasks are organized according to minimal steps (n-step) to finish the task.
Tasks (n-stepp)
Model
Method
4
8
CoT
0.514 0.06
0.276 0.05
0.131
0.03
0.000 0.00
ToT
0.486 0.06
0.055
0.117 = 0.03
0.028 = 0.01
RAP
0.892 + 0.03
0.06
0.166
0.000 0.00
Mistral-7B
RAP-D
0.973 # 0.02
0.632
0.02
0.105 = 0.03
RAP-E
1.000 = 0.00
0.59
0.338
0.084 0.03
PlanU
1.000 0.00
0.803 0.04
0.559
0.217 0.03
CoT
0.351 + 0.05
0.03 0.05
0.014 0.01
ToT
0.459 + 0.06
0.005
0.131 0.03
0.056 0.02
RAP
0,946 + 0.02
0.005
0.255
0.175 # 0.03
LLama3.1-8B
RAP-D
0.973 + 0.02
0.004
0.00
0,070 # 0.02
RAP-E
0.946 + 0.02
0.004
0.01
0.140 0.03
PlanU
1.000 + 0.00
0.842
0.524
0.238 0.03
CoT
0.405 # 0.06
0.04
0.152
0.077 0.03
ToT
0.514 0.06
0.00
0.145
0.034 0.02
DeepSeek-RI- Distill-Llama
RAP
1.000 + 0.00
0.004
0.200 100000.0
0.196 = 0.03
RAP-D
0.973 + 0.02
0.00
0.40
0.140 = 0.03
RAP-E
1.000 + 0.00
0.09
0.448 0.05
0.175 0.03
PlanU
1.000 0.00
0.816
0.455 0.05
0.196 0.02
UNSTACK: The agent unstack a block from another block.
PUT: The agent places a block on the table.
PICKUP: The agent picks up block from the table.
Each action can only be executed if the preconditions are met (e.g., the block is clear or the agent is holding the block). The agent must learn to sequence these actions in order to achieve the goal.
The transitions in this environment are deterministic but with some stochasticity intro- duced in the Stochastic Blocksworld setting. In this setting, the four fundamental actions (STACK, UNSTACK, PUT, PICKUP) have a 20% chance of failure during execution. If an action fails, the state remains unchanged, introducing uncertainty into the state transitions.
Dynamics:
Reward: A sparse reward setting is used in which the agent only receives a +1 reward upon completing the goal. The task completion is defined achieving the specified stacking order or leaving certain blocks on the table as required.
Each episode terminates when the agent successfully completes the goal or reaches the maximum number of time steps. If the agent reaches the goal before the maximum time steps, it is rewarded, and the episode ends. If the maximum time steps are reached without completing the task, the episode ends without a reward.
Episode Termination:
C.2.2 Experimental Results for Blocksworld
We conduct experiments on the Blocksworld tasks on three large language models. They are Mistral- 7B, Alama3.1188 and DeepSeek-Re CeESScck-R-Disseee RI--istill-Llamm-- The experimental results are shown in Table Some of the results already shown in the main paper, for completeness and ease of reading, have placed the results together.
As it is shown in Table 4 PlanU performs the best across all the tasks for the three LLMs. RAP performs better than ToT. which performs better than COT. DeLLMa does consider environment feedback, thus it is not suitable for this task that requiring multiple steps of decision making. We have compared our approach against the four MCTS-base LLM approaches: RAP, RAP-D, RAP-E. The RAP variants (i.e., RAP-D, RAP-E), which consider environmental uncertainty, perform better than RAP. PlanU performs better than them, thanks to its ability to handle environmental uncertainty and LLM uncertainty.
25

---

Closed-Source and Open-Source Larger Model Evaluation in Blocksworld
We further evaluated larger models in Blocksworld, including Qwen//Wwen2.5-44---nnsttt (open- source), OpenAl GPT-4.1 (closed-source), and Google Gemini-22.5Prr (closed-source). These models cover both large-scale open-source and closed-source paradigms, enabling comprehensive assess- ment of our method's generalization across model types. The experimental results are summarized in and
Tables and 7 It be observed that PlanU achieves superior performance consistently on both large-scale open-source and closed-source models, verifying its strong adaptability to different model architectures.
Table 5: Performance Comparison on OpenAl GPT-4.1 (Closed-Source) in Blocksworid
Method
2-step
4-step
6-step
8-step
CoT
0.541 # 0.07
0,382 + 0.06
0.221 = 0.05
0.063 + 0.04
ToT
0.595 # 0.08
0.421 0.07
0.241 # 0.06
0.077 0.05
RAP
1.000 # 0.00
0.763
0.341 0.03
0.231 + 0.06
PlanU
1.000 = 0.00
0.821 0.04
0.648 = 0.03
0.392 0.04
Table 6: Performance Comparison on Google Gemini-2.5-Pro (Closed-Source) in Blocksworld
Method
2-step
4-step
6-step
8-step
CoT
0.568 + 0.08
0.395 + 0.07
0.228 + 0.06
0.056 0.05
ToT
0.622 + 0.07
0.408 + 0.08
0.248 + 0.07
0.070 0.06
RAP
1.000 + 0.00
0
0.328 = 0.04
0.238 0.05
PlanU
1.000 + 0.00
0.808
0.662 = 0.03
0.378 0.04
Table 7: Performance Comparison on Qwwen/Owen2.5-14--1nnsttt (open-Souree) Blocksworld
Method
2-step
4-step
6-step
8-step
CoT
0.405 + 0.06
0.178 + 0.05
0.138 + 0.04
0.028 0.03
ToT
0.486 # 0.05
0.247 # 0.06
0.131 # 0.05
0.042 + 0.04
RAP
0.973 + 0.02
0.605 0.03
0.219 = 0.03
0.161 0.05
PlanU
1.000 = 0.00
0.750
0.521 = 0.05
0.182 0.04
Comparing with LLM-based Decision-making method under uncertainty: DeLLMa
We evaluate DeLLMa in the Blocksworld environment with stochastic state transitions on Mistral-7B. As De is not specifically designed for multi-step decision-making we treat each planning task as a single-step decision problem. The prompt for DeLLMa is depicted in Appendix D DeLLMa performs multi-step reasoning by integrating recent inference-time techniques grounded in decision and utility theory to produce accurate and auditable outcomes.
As shown in Table 8. DeLLMa outperforms CoT and ToT in short-horizon tasks (e.g.. Step 2). demonstrating its effectiveness simple reasoning scenarios. However, its performance deteriorates significantly as the number of required steps increases, primarily due to its heavy reliance on the LLM's reasoning ability-Where uncertainty compounds over longer reasoning chains-and its lack of explicit modeling for multi-step decision-making (lack of considering environmental feedback).
Our method PlanU maintains consistently high accuracy across all steps, demonstrating superior capability in handling complex, long-horizon decision-making tasks.
Comparing with LLM-based MCTS Decision- Decision-making method: LATS
We evaluate the performance of LATS in the stochastic Blocksworld environment on Mistral-7B. As shown in Table LATS consistently outperforms RAP across different planning horizons. This improvement can be attributed its reflection mechanism, which allows the language model to reason over its past trajectories and revise future actions accordingly. Such a mechanism indeed enhances robustness in the face uncertainty. However, compared to our approach, which leverages value distribution modeling for uncertainty estimation, LATS still lacks the precision required
26

---

Table 8: The Success Rate of the Blocksworld Benchmark: DeLLMA, CoT, and ToT
Method
Step 2
Step 4
Step 6
Step 8
CoT
0.514 + 0.062
0.276 : 0.051
0,131 # 0.027
0,000 = 0.000
ToT
0,486 1 0.062
0.355 0.055
0.117 2 0.026
0.028 0.014
DeI.LMa
0.595 0.081
0.092 0.033
0.041 0.017
0.000 0.000
PlanU
1.000 = 0.000
0.803 = 0.045
0.559 = 0.041
0.217 = 0.034
Table 9: The Success Rate of the Blocksworld Benchmark: LATS and RAP variants
Method
Step
Step
Step
Step
RAP
0.892 0.050
0,513 = 0.057
0.166 0.031
0.000 0.000
RAP-D
0.973 = 0.022
0.632 = 0.053
0.324 = 0.049
0.105 + 0.030
RAP-E
1.000 = 0.000
0.592 = 0.054
0.338 = 0.052
0.084 = 0.031
LATS
0.946 0.037
0.684 = 0.053
0.352 0.040
0.077 0.023
PlanU
1.000 0.000
0.803 0.045
0.559 0.041
0.217 0.034
for long-horizon planning. The performance gap becomes more pronounced as the number of steps increases, highlighting the limitations of reflection-base reasoning in capturing fine- fine-grained stochastic dynamics.
C.3 Overcooked
In the Overcooked environment [51 7 agents prepare and deliver tomato salad and tomato-lettuce salad using provided resources. The states and actions are text-based. There are two tasks in this environment: Tomato salad, and Tomato lettuce salad. The original environment assumes deterministic transition, add uncertainty into the environments by adding 20% failure rate for the Chop action. A failed action leads the state unchanged.
C.3.1 Task Description
The agent is placed in the Overcooked kitchen and aims to cook specified dish using the provided ingredients and tools, delivering it to the "star" cell soon possible. The agent must learn the correct procedure, including picking raw vegetables, chopping them, combining the chopped ingredients in bowl, and then delivering the dish.
The environment a 7x7 grid world that includes ingredients, bowls, cutting boards, and a delivery counter. In the tomato salad task, the environment provides one tomato, one bowl, one cutting board, and one delivery counter. In the tomato-lettuce salad task, the environment provides tomato,
Observation Space:
lettuce, one onion, one bowl, two cutting boards, and one delivery counter. The onion serves as an interference, though it does not appear in the recipe. The global state information includes the positions of the agent and the objects, well as the status of each ingredient (chopped or unchopped). The environment is partially observable, and the agent can only observe the positions and statuses of objects within 5x5 square centered around the agent. Other unseen objects are masked in the observation. The initial positions of all objects are known to the agent. The raw observation data is converted into prompts through scripts, which are then used as input for the LLM.
This work mainly focuses on using high-level macro-actions, as they usually have richer semantics. Each macro-action may take several time steps to complete. The following is brief description of the macro-actions used in this study:
Action Space:
Chop: The agent stands next to a cutting board with an unchopped ingredient and chops into pieces.
Got-Tomato, Get-Lettuce, Get-Onion, Get-Bowl, Go-Cutting Boardd1,, and Deliver: These actions navigate the agent to the location of the corresponding object and execute the corresponding operation. In the tomato salad task, the available macro-actions are Get-Tomato, Get-Bowl, Go-Cutting-Boad Board-1, and Deliver. In the tomato-lettuce salad task, all macro-actions are valid.
27

---

Tomato salad
Tomato lettuce salad
Plant RAP
PaaUi
RAP
BAPO
RAP-O
RAP-
RAP-
ORDON
QADON
0.8
0.8
Returns
Returns
0.6
0.2
0.2
0.0
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
5000
6000
Environmental Steps
Environmental Steps
Figure 7: Experimental Results for Overcook: Tomato salad (left) and Tomato lettuce salad (right) in Overcooked.
Dynamics: The transitions this task are deterministic with some randomness. The Chop action has 20% chance of failing, in which case the state remains unchanged. If the agent delivers the wrong item, that item will be reset to its initial position.
+0.2 for chopping a correct ingredient, +1 terminal reward for delivering the correct dish, -0.1 for delivering the wrong dish, and -0.001 for every time step.
Reward:
Episode Termination: Each episode terminates when the agent successfully delivers the target dish to the delivery counter reaches the maximum time steps (200).
C.3.2 Experimental Results for Overcooked
For case of reading, we have partitioned the experimental results into Figure 7 and Figure 8 The experimental results for PlanU, RAP, RAP-D, RAP-E, and QRDQN are presented in Figure while the results for RAP-D-UCC, CoT, and ToT are shown in Figure X In these figures, the horizontal and vertical axes represent environmental steps and returns, respectively. PlanU achieves the best performance across both tasks.
In Figure 7 RAP and RAP-E rank second on the Tomato Salad and Tomato Lettuce Salad tasks, respectively. Notably, on the Tomato Lettuce Salad task-which is more complex than Tomato Salad-PlanU is the only method that successfully completes the task, owing its strong capability in handling decision -making uncertainty. Compared to RAP-D and RAP-E, PlanU demonstrates greater efficiency exploring novel states via the UCC score, as well more effective backpropagation through value distributions, ultimately leading to optimal reasoning paths.
In Figure X the results for CoT, ToT, and RAP-D-UCC. For COT and TOT, we adopt the same base prompt as used in PlanU, augmented with task-specific guiding prompts to enhance LLM reasoning. For each task, trials on the same task. The reported result is the average reward across these trials. RAP-D-UCC RAP variant designed by for this task. It considers environmental uncertainty by using DMCTS 4S and LLM uncertainty through using the UCC score (the state novelty part). As is shown in the left part of Figure it performs inferior RAP-D. However, it performs better than RAP-D in the right part of Figure 8 This indicates that simple integration of methods deal with environmental uncertainty and LLM uncertainty does not work effectively.
allow the LLM complete it within 15 steps and evaluate its performance
10
C.4 VirtualHome
The VirtualHome benchmark 52 7 models furnished house, where simulated embodied agent execute actions to complete tasks. evaluate two tasks: Food Preparation (heating pancake the microwave) and Entertainment (coordinating snack preparation with TV viewing). To increase the uncertainty of the tasks, we increase the failure rate for opening appliances (e.g., microwave) as 50%. Failed actions do not impact the environment.
28

---

Tomato salad
Tomato lettuce salad
Plant
Plani
RAP
RAP
BAPO
RAP-D
RAP-DUUCC
DAP-D-UCC
COT
0.8
0.8
Returns
Returns
0.6
0.2
0.2
0.0
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
5000
6000
Environmental Steps
Environmental Steps
Figure 8: Experimental Results for Overcooked benchmark: Tomato salad (left) and Tomato lettuce
salad (right).
C.4.1 Task Description
The agent, represented as a humanoid avatar, is placed in fully furnished household with various rich objects to interact with. For the Food Preparation task, the agent needs to find the pancake on the table in the kitchen and place in the mierowave heat, this relative simple task. For the Entertainment task, the agent needs to find and bring chips and milk from the kitchen to the living room and succeed in sitting on the sofa with the TV on and the chips and milk nearby. The challenge arises when the agent, already holding both the milk and chips, lacks an additional hand to turn on the TV. Consequently. the agent needs to learn to place at least one item on the nearby coffee table before operating the TV.
The environment is partially observable. The agent can only the objects in the current room and cannot see the objects in the other room. The observation consists of set of Boolean values, representing whether the agent sees the relative object, whether these objects close to the agent, and the status of the objects, such as whether the TV is on and whether the milk is on the coffee table. The symbolic raw observations are converted to prompts with scripts to serve as input for the LLMs.
Observation Space:
Action Space: This work mainly focuses using high-level macro-ace macro-actions, they usually have richer semantics. Each macro-action may take several time steps to complete. The following is brief description of the macro-actions used in this study:
Get-Pancake: The agent picks up the pancake from the table in the kitchen.
Place-PanakkeMMecrowaeee The agent places the pancake into the microwave and closes the microwave door.
Get-Chips: The agent retrieves the chips from the kitchen.
Get-Milk: The agent retrieves the milk from the kitchen.
Lefee--ooffeeTabbllee The agent places item the coffee table.
Sit-On-Soff The agent sits the sofa.
Turn-On-TV: The agent turns on the TV.
Walk-to-A place: The agent walks to a specific room including the living room, the bedroom, the kitchen and the bathroom.
The transitions in this task involve some randomness. In the food preparation task, due to its relative simplicity, there is a 50% failure probability when the agent attempts to open the microwave. In contrast, in the entertainment task, there a 20% failure probability when the agent tries to get chips get milk.
Dynamics:
We adopt a sparse reward setting in Food preparation, where the agent only receives reward upon completing the task. In Entertainment, there are three subtasks: get chips, get milk and turn on the TV. The agent will get a +0.1 reward upon completing each the sub task and reward if the agent sits on the sofa while every subtask is finished.
Reward:
29

---

Food preparation
Entertainment
PlanU
PaaU
RAP
RAP
RAP-
RAP-D
RMP-
RAP-
QADON
0.8
0.6
Returns
0.6
0.4
0.2
0.0
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
5000
6000
Environmental Steps
Environmental Steps
Figure 9: Experimental Results for VirtualHome: Food preparation (left) and Entertainmeentrigh))
Episode Termination: Each episode terminates when the agent successfully completes the task or reaches the maximum time steps (50), as each macro-action takes one time step to execute. In the pancake heating task, the agent succeeds when places the pancake in the microwave and closes the microwave door. In the TV watching task, the agent succeeds when it sits on the sofa, the TV is on, and the chips and milk are on the coffee table or held in hand.
C.4.2 Experimental Results for VirtualHome
Figure 9 shows that for both the Food preparation and the Entertainment tasks, PlanU performs the best for these two tasks. The left part of Figure 9 presents the performance of each algorithm on the Food Preparation task. As this task is relatively simple for large language models (LLMs), LLM-based methods able quickly discover the optimal path while RL method QRDQN fails to reach the optimal path in limited interactions with the environment. The Entertainment task is more diffieult than the Food Preparation task, As is shown the right part of Figure 9 RAP performs the second.
C.5
Token Usage
PlanU is a MCTS-based LLM decision making task under uncertainty. As MCTS is computational intensive, in this section, we evaluate the computational resource consumption of PlanU through using the Token Usage and the Query times metrics. Token usage is the number of tokens consumed during the task, while Query times refers to the number of time the agent queries a LLM.
We evaluate the performance of PlanU and its variants, RAP, CoT and, ToT over 10 trials on the Tomato Lettuce Salad task. For CoT' and ToT, we prompt the L.MM to find the optimal path within 15 steps. The Token Usage and the Query time are reported in Table [0
PlanU consumes the least number of tokens and number of queries among MCTS methods (e.g.. RAP), which demonstrates its ability to explore decision space and obtain the optimal path with less resource consumption. PlanUs consume nearly 3 times less tokens than RAP, vanilla MCTS-based decision making method.
Although PlanU consumes more tokens than CoT and ToT, it can find correct plan uncertainty, whereas CoT and ToT fail most of the time for the three benchmarks evaluated this work.
Table 10: Token usage for the Tomato Lettuce Salad task
Method
PlanU
PlanU w/o dist
PlanU w/o UCC
RAP
COT
TOT
Token Usage(k)
922.69 6.6
1197.99 7.6
1521 86 + 2.9
2643 443.88445 + 8.9
35.98 + 3.2
159.85 4.6
Query times
1389.6 + 10.0
2353.0 + 14.9
2289.2 # 4.5
4313.0 14.8
150.0 = 0.0
150.0 = 0.0
30

---

C.6 Ablation Study
We evaluate the impact the quantile distribution and the UCC score. The results are presented in Figure I0 PlanU w/o dist refers to the variant of PlanU where the quantile distribution is replaced with the mean value. PlanU w/o uce denotes the variant without the UCC score, in which the exploration term is replaced by that used in UCT.
Tomato lettuce salad
Entertainment
Planü
1.0
1.0
Returns
Returns
0.4
0.4
-0.2
-0.2
2000
4000
Environmental Stops
Stops
Figure 10: The impact of quantile distribution and UCC score.
C.6.1 Experimental Results on Operator Ablations
Learning approximate distribution rather than single expectated value preserves the mul- timodality in value distribution, which can lead to more stable learning. As we can see that PlanU using the mean value without the quantile distribution lead significantly poor performance than PlanU in the following table. Moreover, we have conducted experiments to evaluate the impact of different operators: 5o.5. E [s,, a;)l +variance, and (s,, dz]]+ To.9 To. 1- (s a.)] is the mean of the distribution, 70.5, and To.1 are the value for quantile 0.5, 0.9 and 0.1, respectively. As it is shown follows. In general, using the mean operator lead first second performance.
Tomato lettuce salad
Entertainment
Planti mncnndedauuti
Planti mesetddseutt
Pissil median
Manil medias
verlance
1.0
variance
mnenind 9.9immindees... 0.11
meee nnindex 33)- indes_0...
0.8
Returns
Returns
0.44
0.4
0.2
0.2
-0.2
-0.2
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
5000
6000
Environmental Steps
Environmental Stops
Tomato Lettuce Salad Scenario
Entertainment Scenario
Figure 11: The impact of different operators (70.5, (s,, az)] variance, and E|Z (st, at)]+ + To.1)) 1)) performance. Results confirm that preserving multimodality via quantile distributions enhances stability, while the mean operator consistently achieves top-tier performance.
C.6.2 Ablation Study on Sentence- Transformer Models
To investigate the impact of different sentence embedding models performance across distinct task settings, we conduct ablation experiments using three widely adopted Sentence-Transfoon models. The evaluated models include:
sentence-trrasffommerse http://allllmmeee-aa--eeeeeeeeee bbssev2 (used as the default model our main experiments)
31

---

sentence- Saataattetrrassffrrrrrraaaaalaa-
We evaluate these models on two representative tasks: the Tomato Salad task and the Tomato Lettuce Salad task. The results, visualized in Figure 12 demonstrate how embedding model choices affect performance metrics (e.g., success rate, efficiency) across the tasks.
Tomato salad
Tomato lettuce salad
1.2
1.2
Mini v22
MiniM-112-4
Returns
0.6
Returns
0.6
0.0
0.0
-0.2
-0.2
2000
4000
6000
2000
4000
5000
6000
Environmental Steps
Steps
Tomato Salad Task
Tomato Lettuce Salad Task
Figure 12: Performance comparison of different and Tomato Lettuce Salad tasks. The results highlight variations in task adaptation based on model architecture (e.g., parameter size, layer count).
Transformer models the Tomato Salad
As shown in Figure 12 the default all- wwt--mmpetb---e-eee base-vbbbeev222 model generally achieves superior perfor- mance, particularly on the more complex Tomato Lettuce Salad task, which may benefit from its larger capacity. Meanwhile, the lighter all-MiniLM variants exhibit competitive results in the simpler Tomato Salad task, suggesting a potential trade-off between model efficiency and task complexity.
C.6.3 Ablation Study number of quantiles
To examine the sensitivity of method the number of quantiles used in modeling the value distribution, we conduct ablation experiments with three different number of quantiles: 41, 51 (default), and 61. These experiments are performed across both the Tomato Salad and Tomato Lettuce Salad tasks, with results visualized in Figure
Tomato salad
Tomato lettuce salad
PlanttStefauh)
Mantiidefost)
p-atom-41
2-stemm41
1.0
mattomal
1.0
n-thom-11
Returns
Returns
0.4
0.4
0.2
-0.2
-0.2
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
5000
6000
Environmental Steps
Environmental Steps
Tomato Salad Task
Tomato Lettuce Salad Task
Figure 13:
Performance comparison across different number of quantiles (1, 61) on the Tomato Salad and Tomato Lettuce Salad tasks.
the default setting of 51 quantiles (n=51) outperforms both n=41 and n=61 most iterations, particularly in later stages. Performance differences across quantile choices are minor, indicating that the method is robust to changes in this parameter, with the default providing
As observed in Figure 13
32

---

the best results in our experiments. This robustness suggests that the approach does not require linegrained tuning of the quantile count, simplifying its practical deployment.
C.7 Impact Uncertainty
In this section, evaluate whether PlanU matches the design goal that making good decision under uncertainty. We evaluate the impact environmental uncertainty for PlanU in Appendix [C.7.I] and the impact of LLM uncertainty in Appendix [C7.2] We find that PlanU can deal with environmental uncertainty well thanks to the use of quantile distributions; that PlanU is robust in the face of LLM uncertainty with different prompts and temperatures.
C.7.1 Impact of Environment Uncertainty
Figure 14 shows the performance for PlanU and PlanU w/o dist, a PlanU variant without value distribution under increased environmental randomness. With increased randomness (increased Action Failure Rate), the success rate of both methods decreases, With quantile distribution, PlanU enjoys a higher success rate than without.
Environmental Stochasticity on Planning
0.8
0.6
0.4
Rani (Step-2)
Nanu dat (Ssse2)
Nari dut (Suped)
0.0
0.6
0.2
0.4
0.6
0.5
Action Fallure Rate
Figure 14: Impact of Environmental Uncertainty for PlanU and PlanU w/o dist. The horizontal axis depicts the action failure rate (AFR). The increase of the AFR lead to the increase of environmental uncertainty.
C.7.2 Impact of LLM Uncertainty
To evaluate the impact of LLM uncertainty, we evaluate the impact of using different prompts and the impact of using different LLM temperatures.
LLM Uncertainty:
Changing Prompts
Tomato lettuce salad
Entertainment
1.2
1.2
Planil promst Injection
Panni Injection
Returns
0.6
Returns
0.6
0.4
0.0
0.0
-0.2
-0.2
2000
4000
6000
2000
4000
5000
6000
Environmental Steps
Steps
Figure 15: The impact of LLM uncertainty caused by changing prompts.
To evaluate our method's robustness to LLM uncertainty, we introduce two types of perturbations to LLM prompts, which lead to different outputs from LLMs given the same state: (1) Prompt
33

---

Shuffling: We shuffle the sentences in the provided prompt while preserving the sentence boundaries within the task and environment description. (2) Prompt Injection: We inject task-irrelevant but environment-related information into the prompt that does not aid in solving the task. These forms of uncertainty commonly arise when prompts include content generated by L.Mss. Examples of such prompts and results for the Tomato Lettuce Salad task are provided in Appendix [ The experimental results are shown Figure [15, As it is shown in the picture, the performance of PlanU does not significantly affected by the changed prompts. These results demonstrate that LLM uncertainty only slightly affects the convergence speed PlanU. PlanU is robust to LLM uncertainty caused by changed prompts.
LLM uncertainty: Generation Temperatures
To assess the robustness of planning strategies against the inherent uncertainty of large language models (LL.Ms), examine the effect of varying the temperature parameter-a key factor influencing output stochasticity- task success rates. The temperature 7 modulates the softmax distribution over token logits 2; follows:
exp(z//) P(x))= E, exp(2,/T))
where higher values of lead to flatter distributions, increasing randomness generated outputs.
Impact Temperatures on Planning
Panu
RAP
Success
0.40
0.30
0.20
0.10
0.00
1.0
1.2
1.4
1.6
1.8
LLM Temperature
Figure 16: LLM Temperature for PlanU and RAP
As illustrated Figure T6 PlanU exhibits a high degree of resilience to temperature variation. Across range of temperature settings, the success rates remain largely stable, indicating that both methods are capable of maintaining consistent performance despite increasing randomness in LLM generations. PlanU consistently outperforms RAP under all temperature settings with shows lower variance, demonstrating its stronger robustness in uncertain generation environments.
34

---

D Prompts for LLM
In this section, we describe the prompt for LLM-based methods for the Blocksworld, Over- cooked(Fig [7 and Virtualhome(Fig 18).
Overcooked and Virtualhome. For both environments, basically follow the experimental settings of [7]. with additional uncertainty introduced in the prompts to evaluate our methods' capability to model such uncertainty.
EXAMPLE PROMPT FOR OVERCOOKED
Basic Prompt:
There is fixed cutting board room. Currently you don't have anything in hand. You notice tomato on the table. Your goal serve dish of bowl only containing chopped tomato. Your next step is to
Prompt After shuffling:
Currently you don't have anything in hand. Your goal is serve the dish of bowl only containing chopped tomato. There is fixed cutting board the room. You notice a tomato on the table. Your next step is to
Prompt after injection: There are two fixed cutting boards in the room. Earlier this day, you made dish with chopped potatoes. Currently you don't have anything in hand. You notice a tomato on the table. Your goal is to serve the dish of bowl only containing chopped tomato. Your next step is to
Figure 17: Example Prompt for Overcooked
EXAMPLE PROMPT FOR OVERCOOKED
Basic Prompt:
There are four rooms: the kitchen, bathroom, bedroom, and living room. You are in the living room and you notice coffee table, TV and a sofa. Currently, you are not grabbing anything hand. Your goal is to enjoy the chips and the milk while watching TV. Your next step is to
Prompt after shuffling:
Your goal is to enjoy the chips and the milk while watching TV. There are four rooms: the kitchen, bathroom, bedroom, and living room. Your goal is to enjoy the chips and the milk while watching TV. You are in the living room and you notice a coffee table, a TV and sofa. Your next step is
Prompt after injection:
There are four rooms: the kitchen, bathroom, bedroom, and living room. Earlier the day, you were in the bedroom and sowe cookies on the table. You are in the living room and you notice coffee table, anything in hand. Your goal is to enjoy the chips and the milk while watching TV. Your next step
and sofa. Currently, you are not grabbing
Figure 18: Example Prompt for Virtualhome.
35

---

EXAMPLE DELLMA PROMPT FOR BLOCKSWORLD
Prompt 1
Blocksworld environment. need make optimal decisions about which action to perform next (e.g., pick up, stack, unstack, or put down block).
interacting
My goal is to place the blue block on top of the orange block. Today's 's environment is partially observable, and I must reason under uncertainty.
Here is the current observation:
The blue block is clear.
The orange block is clear.
The hand is empty.
The blue block is the red block.
The red block and the orange block are on the table.
The full world state is hidden and contains 16 latent variables (e.g., hand status, block locations, perception errors, etc.). First, think about the unknoum factors in the current environment that could affect my decision.
Prompt 2
<SAME CONTEXT>
Now I have enumerated the unknown variables that affect my decision:
"block visibility", "block on block stability", "perception error", "hand grip strength",
Given these unknowns, think about the belief distribution over their most likely values, with verbal confidences such as: "very likely", "likely", etc.
Example format: {"block visibility"; {"blue": "very likely", "orange"; "very likely"), ...)
Prompt
<SAME CONTEIT>
Now, given the belief distribution over the environment state and the goal ("blue block on orange block"), devise step-by-step plan.
You may the following actions:
(1) pick up block
(2) unstack block from top of another block
(3) put down a block
(4) stack block top of another block
Output action per line. End the plan with [PLAN END]
Example Output: unstack the blue block from top of the red block stack the blue block on top of the orange block [PLAN END]
36

---

ENVIRONMENT
Target
Fou (2
(6. los 6
Predictor
Figure 19: The Schematic Plot for the UCC score
E
UCC Score
During tree search, PlanU chooses optimism the face uncertainty; it encourages exploration through the Upper Confidence Bound with Curiosity (UCC) score. It calculates the uncertainty of text-based states based on the value distribution and novelty of states. The schematic plot for the selection phase using the UCC score is depicted in Figure 19] To estimate the novelty of given state, we first encode the natural language description of the state using a sentence-level encoder. Specifically, utilize Sentence Transformers to encode textual states into dense embeddings. These embeddings are fed into a fixed target network and learnable predictor network, with their output discrepancy quantifying the state's novelty measure of epistemic uncertainty. Specifically, the UCC score is defined follows.
(((ss) UCC(st, a:) (i at) + N(s,, 4:)
where (sr,,,, at)] is uncertainty-awant operator that maps quantile distribution into real-value. Multiple implementations ei can be used. default, we use the expectation operator as th or is hyperparameter, N(st, 0e) represents the visit count of the action node a,, and (s:) is novelty reward.
The novelty reward r; (s:) is designed to encourage the agent to explore less-visited states from global perspective through estimating the uncertainty 8t. Inspired by [17] ri (8t) calculates the feature difference among predictor network and target network f. Specifically, it defined as ri(s)) f(e(s))) f(e(s))) where f and are both three-layer Multi-Layer Perceptron (MLP)
networks.
Following [17,, the hyperparameters used for the predictor network of are listed in Table ry as the loss to train the predictor network.
11
We use
Table 11: Hyperparameter Settings for UCC
Hyper-parameter
Value
learning rate hidden size list update lic__peerlleeeeeee collect obs_norm
le-5 [64, 64, 128]
True
obs jos__nor___ wwwmp_lammaaaaaee
intrinsic reward, weight
0.01
37

---

Broader Impact and Limitation
The goal of PlanU is to advance the field of Machine Learning technique for Decision Making. Our work can be applied in multiple domains. However, we do not feel any thing must be highlighted here.
There are two limitations of PlanU. Firstly, PlanU does not use another tool (e.g., web search) during Docision-makkng. This may limit its ability for problems requiring external knowledge. In such cases, a web search could help make the decision. We plan to combine PlanU and ReAcT to strengthen its ability. Secondly, PlanU is MCTS- decision-making method. It faces challenges when applied to problems with nigh-dimensional action. PlanU may struggle to explore sufficient paths with practical time constraints, leading suboptimal performance. We plan explore hierarchical MCTS, which decomposes the problem into hierarchical layers or combine PlanU with progressive widening techniques, which dynamically limit the number of actions explored per node.
38


Reviews:
[{"review_id": "NqeAO4U1Gf", "reviewer": "Reviewer_c3qH", "summary": "The paper introduces PlanU, an MCTS-based decision-making framework for LLM agents that explicitly handles both LLM generation uncertainty and environmental stochasticity. It models each action-node return as a quantile distribution instead of a mean value, and guides exploration with an Upper Confidence Bounds with Curiosity (UCC) score that combines distributional value estimates and a novelty bonus computed via random-network distillation on text embeddings. PlanU is evaluated on stochastic variants of Blocksworld, Overcooked, and VirtualHome.", "questions": "1. Can you report wall-clock time, tokens for PlanU vs RAP/ToT?\n2. Can PlanU perform well on some real-world tasks?\n3. Can PlanU been adapted to Web agent? \n4. I think it'll be better if the authors include PlanU's performance into figure 1.\n5. Can PlanU been extended to closed-source models?\n6. Can you provide a deeper comparison between PlanU and RAP since they are all MCTS-based methods?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n1. The motivation is clear. \n2. The clarity is good and the paper provides intuitive figures to help understanding.\n\nWeakness:\n1. The three datasets the paper use are toy, textual and simulated. There're no real-world, long-horizon tasks with rich observations or actuation. And the model sizes are small.\n2. Compute cost and token/runtime overhead haven't been discussed.\n3. The paper lacks enough details about experiment setup in the main text.", "was_revised": true, "final_justification": "My concerns about more experiments have been mostly addressed.", "rebuttal": "> W1: The three datasets the paper use are toy, textual and simulated. There're no real-world, long-horizon tasks with rich observations or actuation. And the model sizes are small.\n\n> Q2: Can PlanU perform well on some real-world tasks? \n> Q3: Can PlanU been adapted to Web agent?\n\nIn this rebuttal, we evaluate PlanU on two real-world planning benchmarks: a travel planning benchmark and a web agent benchmark using Qwen3-14B as the underlying LLM.\n\n1. Travel Planning Benchmark (TravelPlanner [1]): This benchmark requires an agent to generate a comprehensive plan encompassing transportation, meals, and accommodation based on a user query. The agent can perform various search actions to gather necessary information before making decisions. To simulate real-world uncertainty, we inject delay probabilities for planes and trains. The injecting delay probabilities are derived from the empirical probability density function (PDF) modeling [2] and a National Transportation statistics. Consequently, delays can invalidate subsequent segments of the generated plan. We evaluated 45 tasks of easy/medium/hard difficulty with TravelPlanner. The evaluation metrics includes Task Completion Rate (covers core travel elements) and Constraint Satisfaction Rate (average of satisfying TravelPlanner’s commonsense + hard constraints, e.g., no repeated attractions, meeting budget). Results show PlanU outperforms others (table below).\n\n|Method|Task Completion Rate|Constraint Satisfaction Rate|\n|-|-|-|\n|CoT|0.156±0.030|0.022±0.010|\n|RAP|0.222±0.025|0.044±0.012|\n|PlanU|0.378±0.020|0.222±0.015|\n\n2. Web Agent Benchmark (WebShop [3]): This benchmark evaluates agents tasked with purchasing products in an online shop with over one million items, meeting specific user requirements (e.g., brand, price, size). Agents interact via web clicks and searches, making decisions based on observed pages and interaction history. Crucially, to mimic real-world conditions, web actions incur network latency following a long-tail log-normal distribution [4] (mean 2s), with actions failing if latency exceeds 10 seconds. Performance is measured by reward (percentage of user-specified attributes satisfied) and success rate (frequency of fully meeting all requirements) across 10 shopping instructions. Experimental results (below) demonstrate that PlanU achieves superior performance compared to several baselines.\n\n|Method|Average reward|Success rate|\n|-|-|-|\n|CoT|0.46±0.04|0.1|\n|RAP|0.41±0.02|0.2|\n|LATS[5]|0.57±0.07|0.3|\n|PlanU|0.73±0.07|0.5|\n\n\nThese evaluations on TravelPlanner and WebShop, incorporating realistic uncertainty like transportation delays and internet latency, highlight PlanU's effectiveness in complex, real-world planning scenarios.\n\n[1]TravelPlanner: A Benchmark for Real-World Planning with Language Agents, ICML 2024\n\n[2]Statistical characterization of airplane delays, Scientific Reports 2021\n\n[3]WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agents, NeurIPS 2022\n\n[4]On the log-normal distribution of network traffic,Physica D: Nonlinear Phenomena\n\n[5]Language agent tree search unifies reasoning, acting, and planning in language models, ICML 2024\n\n> Q5: Can PlanU been extended to closed-source models?\n\nWe evaluate in Blocksworld on OpenAI GPT-4.1 and Google Gemini-2.5-Pro. For closed-source models (e.g., GPT-4.1 and Gemini-2.5-Pro), as the token probability cannot be obtained, we initialized the quantiles using a uniform distribution instead of using the token probability. The results are summarized in the following table. The results show that PlanU perform well on closed-source models (GPT-4.1 and Gemini-2.5-Pro). Besides PlanU perform well on a 14B open source models (Qwen2.5-14B).\n\n**Openai/GPT-4.1** \n|Method|2-step|4-step|6-step|8-step|\n|-|-|-|-|-|\n|CoT|0.541±0.07|0.382±0.06|0.221±0.05|0.063±0.04|\n|ToT|0.595±0.08|0.421±0.07|0.241±0.06|0.077±0.05|\n|RAP|1.000±0.00|0.763±0.05|0.341±0.03|0.231±0.06|\n|PlanU|1.000±0.00|0.821±0.04|0.648±0.03|0.392±0.04|\n\n**Google/Gemini-2.5-pro**\n|Method|2-step|4-step|6-step|8-step|\n|-|-|-|-|-|\n|CoT|0.568±0.08|0.395±0.07|0.228±0.06|0.056±0.05|\n|ToT|0.622±0.07|0.408±0.08|0.248±0.07|0.070±0.06|\n|RAP|1.000±0.00|0.776±0.03|0.328±0.04|0.238±0.05|\n|PlanU|1.000±0.00|0.808±0.05|0.662±0.03|0.378±0.04|\n\n**Qwen/Qwen2.5-14B-Instruct**\n|Method|2-step|4-step|6-step|8-step|\n|-|-|-|-|-|\n|CoT|0.405±0.06|0.178±0.05|0.138±0.04|0.028±0.03|\n|ToT|0.486±0.05|0.247±0.06|0.131±0.05|0.042±0.04|\n|RAP|0.973±0.02|0.605±0.03|0.219±0.03|0.161±0.05|\n|PlanU|1.000±0.00|0.750±0.02|0.521±0.05|0.182±0.04|\n\n\n> W2: Compute cost and token/runtime overhead haven't been discussed. \n> Q1: Can you report wall-clock time, tokens for PlanU vs RAP/ToT?\n\nWe had placed a detailed analysis of the computational overhead in Appendix C.5. We study the token usages, query times, wall-clock time, and rewards for the Tomato Lettuce Salad task. The results are shown as follows.\n\n|Method|PlanU|PlanU w/o dist|PlanU w/o UCC|RAP|COT|TOT|\n|-|-|-|-|-|-|-|\n|Token Usage(k)|922.69±6.6|1197.99±7.6|1521.86±2.9|2643.84±8.9|35.98±3.2|159.85±4.6|\n|Query times|1389.6±10.0|2353.0±14.9|2289.2±4.5|4313.0±14.8|150.0±0.0|150.0±0.0|\n|Wall clock time(s)|524.47±13.65|989.45±19.81|931.21±17.41|1447.20±25.11|183.46±3.11|206.38±4.95|\n|Rewards|1.1±0.01|0.35±0.02|0.71±0.08|0.26+0.01|0.11+0.00|0.23±0.00|\n\n\nAs it is shown, PlanU is highly resource-efficient compared to other MCTS-based methods. It consumes **nearly three times fewer** tokens than RAP, demonstrating its superior ability to navigate the search space effectively. In general, MCTS-based methods performs better than CoT and ToT at the cost of most token consumption. The higher token requirement when compared to non-search methods like CoT and ToT is an expected trade-off, which allows PlanU to robustly handle complex planning problems under uncertainty, a domain where simpler methods like CoT and ToT frequently fail.\n\n>W3: The paper lacks enough details about experiment setup in the main text.\n\nThe details of our experimental setup had been **described in Appendix C**. This includes our general setup and computing resources in Appendix C.1. The setup for the Blocksworld, Overcooked, and VirtualHome environment are detailed in Appendix C.2, C.3, and C.4, respectively. Each of these sections covers the complete task description,  observation/action spaces, environment dynamics, and reward structure, ensuring full reproducibility.\n\n>Q4: I think it'll be better if the authors include PlanU's performance into figure 1.\n\nWe have put the results of the new Figure 1 as follows. It shows that PlanU performs better than CoT, ToT, and RAP **both in deterministic and stochastic environments**. \n\n**Deterministic**\n|Method|2-step|4-step|6-step|8-step|\n|-|-|-|-|-|\n|CoT|0.541±0.05|0.276±0.04|0.152±0.03|0.028±0.01|\n|ToT|0.541±0.05|0.316±0.05|0.152±0.03|0.063±0.02|\n|RAP|0.973±0.02|0.882±0.03|0.634±0.04|0.357±0.05|\n|PlanU|1.000±0.00|0.921±0.03|0.848±0.03|0.503±0.04|\n\n\n**Stochastic**\n|Method|2-step|4-step|6-step|8-step|\n|--------|---------------|---------------|--------------|--------------|\n|CoT|0.351±0.06|0.237±0.05|0.124±0.04|0.014±0.05|\n|ToT|0.459±0.05|0.263±0.04|0.131±0.03|0.056±0.02|\n|RAP|0.946±0.03|0.553±0.05|0.255±0.04|0.175±0.03|\n|PlanU|1.000±0.00|0.803±0.05|0.524±0.04|0.238±0.03|\n\n\n>Q6: Can you provide a deeper comparison between PlanU and RAP since they are all MCTS-based methods?\n\nWe can view PlanU and RAP from four different angles: visual comparison, algorithmic design, performance, and resource consumption.\n\n1. In Section 5.2, Figure 3 visually describes the difference among the trees used by RAP (written as LLM-MCTS) and PlanU. RAP cannot model the Q value for even such a simple task due to the limitation of vanilla MCTS, whereas PlanU models environmental stochastic using quantile distribution.  We have described the drawbacks of vanilla MCTS in Appendix A2 in detail.\n\n2. Regarding algorithmic design, PlanU differs from RAP mainly in two aspects:\n(1) **Environmental Uncertainty**— RAP uses the vanilla MCTS with UCT. The vanilla MCT+UCT assumes deterministic state transitions, while PlanU does not assume such simplification. It considers environmental stochastic through  modeling returns as quantile distributions, which better capture environmental uncertainty during planning;\n(2) **LLM uncertainty** — PlanU uses the UCC score, which considers LLM uncertainty, whereas RAP does not explicitly consider such uncertainty.\n3. Regarding performance, as we have shown in the new Figure 1 in the previous response, *PlanU performs better than RAP both in deterministic and stochastic environments.\n4. Regarding resource consumption on stochastic environments, **PlanU consumes fewer tokens and wall clock times than RAP**, as we have reported in previous responses. We further report the number of expanded nodes (lower indicates higher efficiency) on Overcooked tasks. PlanU consume a significantly lower cost than RAP, demonstrating both effectiveness and efficiency. Moreover, we show that each component of PlanU contributes its low number of expanded nodes.\n\n| Method|Tomato Lettuce Salad|Tomato Salad|\n|-|-|-|\n| PlanU| 10244±33.7| 5170±10.8 |\n| PlanU w/o Dist| 18920±50.6| 6715±25.4|\n| PlanU w/o UCC| 12783±39.1|5225±14.4|\n| RAP| 26208±64.1| 6945±29.8|"}, {"review_id": "eCkdKWsU21", "reviewer": "Reviewer_bLkk", "summary": "This paper introduces PlanU, a planning algorithm for LLM-based agents that integrates a distributional reinforcement learning approach into an MCTS framework. The core contribution is the representation of state-action values as a probability distribution rather than a scalar estimate. The authors argue that this allows the planner to more effectively handle decision-making in environments with stochastic state transitions. The method is evaluated on modified versions of some language-based planning tasks, where it is shown to outperform several baseline MCTS-based LLM planners.", "questions": "1. Related to the point discussed in weaknesses, canonical MCTS algorithms like UCT can handle stochastic environments. Could you please clarify why they are insufficient for the problems you are tackling, thereby requiring a distributional value function? Could you for example directly extend an UCT algorithm to LLMs and use it as a baseline?\n\n2. Could you justify the specific choice of initializing the value distribution Z based on the policy's action probability during expansion? An ablation study on this initialization choice would be helpful.", "limitations": "I would suggest the authors discuss the following points:\n\n* Generalization and scope: The evaluation is confined to planning tasks with artificially injected, simplistic stochasticity. The authors should discuss the challenges and potential performance implications of applying PlanU to domains with more complex and naturalistic uncertainty.\n\n* Failure modes: A discussion of potential failure modes would be valuable.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "__Strengths__\n\n* Significance & originality: The paper addresses the important and challenging problem of enabling LLMs to plan robustly under uncertainty. The primary idea of incorporating a distributional value representation into an LLM-based planner is novel. In principle, a value distribution can carry more information than a scalar mean, potentially allowing for more sophisticated and risk-aware planning. This represents an interesting direction for research in LLM agents.\n\n__Weaknesses__\n\n* Flawed motivation and positioning: The paper's motivation is built on a questionable framing of the problem. The argument has two primary weaknesses:\n  * Incorrect claims about MCTS: The paper repeatedly asserts that standard MCTS is unsuitable for stochastic environments (e.g., Lines 104, 161). This is factually incorrect. The canonical UCT algorithm was explicitly designed for and is proven to be asymptotically optimal in stochastic settings (MDPs).\n  * Mischaracterizing a design choice as a fundamental limitation: While it may be true that the specific LLM-based MCTS baselines compared against in the paper were not designed for stochastic outcomes, this ---- in my opinion --- should be viewed as a simplifying implementation choice, likely because their original target tasks were deterministic. It is not, as this paper implies, a fundamental limitation of the MCTS framework itself when applied to LLMs.\n\n* Quality of evaluation: The choice of benchmarks and the method of introducing stochasticity feel contrived. Introducing stochasticity by, for example, having a random chance of an action failing, feels artificial and does not necessarily represent the kinds of uncertainty LLM agents will face in more naturalistic settings (e.g., ambiguous instructions, partially observable states, etc). This choice of evaluation makes it difficult to assess the true generalizability and impact of the proposed method on problems with genuine, inherent uncertainty.\n\n* The rationale for initializing the value distribution Z during the expansion phase using the policy's sampling probability is not justified. It is unclear why this is a sensible choice or how sensitive the algorithm's performance is to this specific initialization strategy.", "was_revised": true, "final_justification": "I've raised my score to Borderline Accept based on the author rebuttal. The authors provided crucial new experiments that addressed the original submission's weak comparisons and evaluation. My recommendation is contingent on these results being fully integrated into the revised paper, which would make the work strong enough for acceptance.", "rebuttal": "> W1: Incorrect claims about MCTS: ...standard MCTS is unsuitable for stochastic environments...canonical UCT algorithm was explicitly designed for...stochastic settings.\n\nSorry for the misunderstanding about the motivation and positioning. We will make them clearer.\n\n1. We agree with the reviewer that canonical UCT [1] guarantees convergence probability 100% for selecting optimal actions (i.e., action stochasticity $p(a|s)$), as established in the original UCT analysis. However, this action selection stochasticity ($p(a|s)$) is fundamentally distinct from environmental stochasticity ($p(s'|s,a)$) considered in this work. The former governs exploration/exploitation trade-offs during decision-making, while the latter characterizes transition uncertainty inherent to the environment itself.\n\n2. The canonical UCT algorithm is unsuitable for stochastic environments, as discussed in [2].  We have shown in Figure 3 that UCT (written as LLM-MCTS) cannot model the true tree structure, which lead to wrong Q value estimation. Sparse UCT [2] addresses this drawback by allowing multiple child nodes per action (corresponding to different stochastic outcomes), while retaining the UCT action selection policy. Conceptually, Sparse UCT can be viewed as a simplified variant of our PlanU method, lacking its quantile distribution and UCC components. pUCT [3] improve planning through incorporating action priors (i.e., LLM priors). Our results (detailed below) demonstrate PlanU's superior performance compared to UCT, Sparse UCT, pUCT for LLM planning. \n\n**Tomato salad**\n||0|1000|2000|3000|4000|5000|6000|\n|-----------------|-------------|-------------|-------------|-------------|-------------|-------------|-------------|\n|PlanU|0.2941±0.0099|0.3696±0.0335|0.9644±0.2569|1.0568±0.0709|1.1509±0.1067|1.11±0.0978|1.2079±0.0324|\n|RAP (LLM+UCT)|0.0516±0.0128|0.3675±0.0729|0.4756±0.0678|0.2687±0.0736|0.679±0.0618|0.5844±0.064|0.2588±0.0804|\n|LLM+Sparse UCT|0.1053±0.0469|0.2046±0.073|0.5546±0.0836|0.5415±0.0748|0.5491±0.0816|0.5522±0.0809|0.5453±0.076|\n|RAP(LLM+pUCT)|-0.0645±0.0588|-0.0143±0.0878|0.9895±0.0755|0.941±0.0662|0.9678±0.0533|0.9868±0.058|0.9603±0.0453|\n\n\n**Tomato lettuce salad**\n|                   | 0             | 1000          | 2000          | 3000          | 4000          | 5000          | 6000          |\n| ----------------- | ------------- | ------------- | ------------- | ------------- | ------------- | ------------- | ------------- |\n| PlanU             | -0.083±0.0415 | 0.8995±0.0832 | 1.1069±0.0032 | 1.096±0.0132  | 1.1045±0.0032 | 1.0955±0.0173 | 1.105±0.0039  |\n| RAP (LLM+UCT)      | -0.0315±0.0268 | -0.0374±0.0362 | 0.3184±0.0847 | 0.245±0.0826  | 0.2676±0.0812 | 0.3081±0.0786 | 0.2741±0.0786 |\n| LLM+Sparse UCT | 0.0142±0.0538 | 0.8732±0.1182 | 0.8909±0.0927 | 0.8203±0.1212 | 0.8987±0.0868 | 0.8453±0.1085 | 0.8684±0.1167 |\n| RAP(LLM+pUCT)     | 0.1391±0.0318  | 0.2967±0.0347  | 0.3185±0.01   | 0.3205±0.0174 | 0.3183±0.0046 | 0.3278±0.0101 | 0.3242±0.0122 |\n\n3. In line with the reviewer's suggestion, we had already compared our work with RAP (LLM+UCT), a method designed for LLM-based planning. Our evaluation shows that RAP's performance drops significantly in stochastic environments (Figure 1). Critically, and as detailed in Figures 3, 4, and Table 1, our method significantly outperforms RAP. This performance advantage also holds against the RAP variants incorporating uncertainty-dealing mechanisms, RAP-D and RAP-E (Figures 3, 4, Table 1). \n\n> W1: Mischaracterizing a design choice as a fundamental limitation: ...LLM-based MCTS baselines...not designed for stochastic outcomes...It is not...a fundamental limitation of the MCTS framework...\n\n4. **It is a limitation when applying vanilla MCTS for LLM even if the environment is deterministic**. As we have stated in the introduction, LLM planning suffers from LLM generation uncertainty, when using LLM as the world model (as we do in this work), LLM may generate different text descriptions even for the same state. This may be interpreted as different stochastic states. Moreover, state aliasing (e.g., caused by partial observability) could effectively introduce environmental stochasticity for a deterministic environment. \n\n5. **We agree with the reviewer that the drawback of vanilla MCTS can be viewed as a \"simplifying implementation choice\"**. For example, Sparse UCT [2] can be viewed as a non-simplified version of UCT for stochastic environments. We will add such discussion into the main text and present the results of MCTS with modeling stochastic environment outcomes (Sparse UCT).\n\n[1]Improved monte-carlo search. Univ. Tartu, Estonia, Tech. Rep, 2006\n\n[2]Lower bounding Klondike solitaire with Monte-Carlo planning, Conf. Autom. Plan. 2009\n\n[3]Combining online and offline knowledge in UCT. ICML 2007\n\n>W2: Quality of evaluation: ...Introducing stochasticity by...having a random chance of an action failing...on problems with genuine, inherent uncertainty.\n\n>L1: Generalization and scope: The evaluation is confined to planning tasks with artificially injected, simplistic stochasticity... more complex and naturalistic uncertainty.\n\nIn this rebuttal, we evaluate PlanU on two real-world planning benchmarks: a travel planning benchmark and a web agent benchmark using more realistic failure models. Please refer them to our response to Reviewer c3qH.\n\n>W3: The rationale for initializing the value distribution Z during the expansion phase using the policy's sampling probability is not justified...\n\n>Q2: ...specific choice of initializing the value distribution Z based on the policy's action probability during expansion? An ablation study...\n\nThe proposed initialization serves as a **warm start** for the policy. We have studied different initialization strategies: random and uniform. The random choice initialize the distribution randomly, whereas the uniform choice assign a uniformly spaced set of points within the interval [0, 1] to the distribution. Their results, obtained from the Blockworld experiment where Mistral-7B was used as the underlying LLM, are listed as follows. It is shown that using the prior from LLM for initilization can significantly speed up learning.\n\n**Blockworld**\n|Method|2-step|4-step|6-step|\n|-|-|-|-|\n|RAP|0.892±0.03|0.514±0.06|0.166±0.04|\n|PlanU_random|0.972±0.02|0.632±0.03|0.324±0.03|\n|PlanU_uniform|0.946±0.03|0.553±0.05|0.359±0.03|\n|PlanU|1.000±0.00|0.803±0.04|0.559±0.04|\n\n\nFor closed-source model the prior probability of LLM cannot be obtained, we choose initialize the distribution using the uniform strategy. As it is depicted in our response to Reviewer c3qH regarding GPT-4.1 and Gemini-2.5-Pro, PlanU performs better than RAP significantly. \n\n>Q1: ...canonical MCTS algorithms like UCT can handle stochastic environments...why they are insufficient for the problems...directly extend an UCT algorithm to LLMs and use it as a baseline?\n\nWe had compared our work with RAP, an algorithm that extend UCT algorithm to LLMs. It performs poorly in stochastic environments on 7-8B LLMs, as depicted in Figure 3, 4 and Table 1. We shows the results between PlanU and RAP on Blocksworld on large LLMs as follows.\n\n**Openai/GPT-4.1**\n|Method|2-step|4-step|6-step|8-step|\n|-|-|-|-|-|\n|RAP|1.000±0.00|0.763±0.05|0.341±0.03|0.231±0.06|\n|PlanU|1.000±0.00|0.821±0.04|0.648±0.03|0.392±0.04|\n\n\n**Google/Gemini-2.5-pro** \n|Method|2-step|4-step|6-step|8-step|\n|-|-|-|-|-|\n|RAP|1.000±0.00|0.776±0.03|0.328±0.04|0.238±0.05|\n|PlanU|1.000±0.00|0.808±0.05|0.662±0.03|0.378±0.04|\n\n\n**Qwen/Qwen2.5-14B-Instruct**\n|Method|2-step|4-step|6-step|8-step|\n|-|-|-|-|-|\n|RAP|0.973±0.02|0.605±0.03|0.219±0.03|0.161±0.05|\n|PlanU|1.000±0.00|0.750±0.02|0.521±0.05|0.182±0.04|\n\n\n>L2:Failure modes: A discussion of potential failure modes would be valuable.\n\n1. In the WebShop benchmark, we inject internet latency into web-related actions. An action is considered failed if the latency exceeds a predefined timeout period.\n\n2. For the TravelPlanner benchmark, we simulate real-world uncertainty — a critical challenge in travel planning where transportation delays often disrupt itineraries — by injecting realistic delay probabilities into planes and trains. These probabilities are derived from two sources: empirical probability density function (PDF) modeling [4] and a National Transportation statistics. Specifically, the delay probabilities for flights are as follows:\n\n| Delay Duration Range       | Probability (%) |\n| :------------------------- | :-------------- |\n| On-time (-5 to 5 minutes)  | 80.76|\n| Delayed (> 5 - 15 minutes) | 5.62|\n| 15 - 30 minutes delayed    | 5.54|\n| 30 - 60 minutes delayed    | 5.01|\n| Over 60 minutes delayed    | 3.07|\n\nFor trains, the delay probability is set to 2% based on the average of the past 5 years from a National Transportation. Such delays can invalidate subsequent segments of generated travel plans, regarding as failure modes, mirroring how real-world disruptions (e.g., a delayed flight causing missed train connections) impact trip feasibility.\n\n[4]Statistical characterization of airplane delays, Scientific Reports 2021"}, {"review_id": "xOjftx7pA8", "reviewer": "Reviewer_QuAk", "summary": "This paper proposes the PlanU framework, which combines the large language model (LLM) and tree search (MCTS) to find the best planning path in an uncertain environment. It uses distributed (rather than average) rewards to represent uncertainty and introduces curiosity to encourage exploration.", "questions": "1. In the setting of this paper, the introduction of uncertainty seems to be limited to the possibility that an action may fail. However, in most cases, wouldn’t simply re-executing the same action suffice? What is the intuitive benefit of introducing a reward distribution in this context? Moreover, given the vast optimization space, it raises concerns about what kind of distribution is actually being learned.\n\n2. In Figure 5 (a), we observe that removing any single component results in almost no return improvement for the baseline. Why is this the case? Could the authors provide more explanation or insights? In Figure 5 (b) and (c), we see that the proposed method and the baseline do not seem to be clearly distinguishable, which reinforces my doubts about the validity of the experiment.", "limitations": "Yes", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strength**\n1. The current mainstream exploration is indeed mainly concentrated in deterministic environments. LLM decision-making in uncertain environments is realistic and meaningful.\n\n2. The experiments in this article prove the effectiveness of PlanU, which is more effective than other MCTS and RL baselines.\n\n**Weakness**\n1. The main technical contributions of this paper largely stem from prior works, such as Monte Carlo Tree Search (MCTS), Quantile Regression DQN (QRDQN) [1], and using LLMs as action priors. The novelty of estimating novelty via the discrepancy between two neural networks also follows the idea proposed in [2].\n\n2. The experimental setup appears to be overly toy-like. Most of the failure cases are manually injected, which may not reflect the challenges of real-world environments.\n\n3. In Equation (6), the authors mention that they use the expectation operator \\( \\mathbb{E} \\) as the default \\( \\psi \\). This raises strong concerns about the necessity of learning the full distribution \\( Z(s_t, a_t) \\), as this essentially reduces to using the mean reward. In my view, this significantly undermines the novelty of the method.\n\n4. The proposed UCC score lacks theoretical justification, whereas classical UCT formulations offer well-established theoretical guarantees.\n\n5. I believe the proposed framework does not truly exploit the capability of LLMs as agents. The LLM is only used for initializing probabilities. A more powerful and effective usage would be to adopt LLMs as ReAct-style agents that can dynamically reason and decide the next action based on environmental feedback.\n\n**References:**\n\n[1] Dabney, Will, et al. \"Distributional reinforcement learning with quantile regression.\" *Proceedings of the AAAI Conference on Artificial Intelligence*. Vol. 32. No. 1. 2018.\n\n[2] Burda, Yuri, et al. \"Exploration by random network distillation.\" *arXiv preprint arXiv:1810.12894* (2018).\n\n[3] Yao, Shunyu, et al. \"ReAct: Synergizing reasoning and acting in language models.\" *International Conference on Learning Representations (ICLR)*. 2023.", "was_revised": false, "final_justification": "", "rebuttal": "> W1:The main technical contributions of this paper largely stem from prior works, such as MCTS, QRDQN...\n\nRegarding the technical contribution and novelty, we hold a different opinion from the reviewer.\n\n1. It is common to address a problem through the integration of existing approaches. DQN is an integration of Q-Learning with a deep neural network. Self-consistency is a combination of CoT with majority voting. ToT extends CoT with a tree structure. RAP combines MCTS with LLM. Rainbow combines double Q-learning, prioritized replay, dueling networks, multi-step learning, distributional RL, and noisy nets. These works make a significant contribution to research advancement.\n2. Our contribution is threefold. We are **the first to identify the common uncertainty pitfall when using vanilla MCTS for LLM planning**. Second, we are the first to integrate the quantile distribution into MCTS-based LLM planning. Third, we are the first to integrate random network distillation into MCTS-based LLM planning. \n3. **Addressing the uncertainty pitfall when using MCTS for LLM planning is non-trivial**, none of the existing LLM-based planning approaches addresses the environmental uncertainty and the LLM uncertainty together. We address the uncertainty pitfall through **a novel integration of existing approaches**. We had shown in Figure 3 that adding uncertainty consideration in CoT, DeLLMa, RAP, and Reflextion fail for stochastic environments.\n4. We have conducted multiple experiments combining existing uncertainty-aware methods into LLM planning. RAP-D and RAP-E combine RAP with DMCTS and EMCTS, respectively. DMCTS and EMCTS are methods dealing with uncertainty. RAP-D-UCC replaces the UCT used in RAP-D with the UCC score. As it is shown in the following tables, **simple integrations of existing methods that deal with uncertainty do not work effectively**.\n\n**Tomato salad**\n||0|1000|2000|3000|4000|5000|6000|\n|-|-|-|-|-|-|-|-|\n|PlanU|0.083±0.041|0.8995±0.083|1.1069±0.003|1.096±0.013|1.104±0.003|1.095±0.017|1.105±0.003|\n|RAP(LLM+UCT)|0.051±0.012|0.367±0.072|0.475±0.067|0.268±0.073|0.679±0.061|0.584±0.064|0.258±0.080|\n|RAP(LLM+pUCT)|0.064±0.058|0.014±0.087|0.989±0.075|0.941±0.066|0.967±0.053|0.987±0.058|0.960±0.045|\n|RAP-D (DMCTS+pUCT)|0.158±0.00|0.128±0.006|0.139±0.006|0.149±0.003|0.153±0.003|0.149±0.007|0.151±0.004|\n|RAP-E (EMCTS+pUCT)|0.104±0.047|0.118±0.023|0.357±0.059|0.393±0.109|0.346±0.118|0.465±0.113|0.319±0.113|\n|RAP-D-UCC|0.044±0.076|0.691±0.188|0.886±0.277|0.898±0.229|0.875±0.292|0.882±0.254|0.896±0.225|\n\n**Tomato lettuce salad**\n||0|1000|2000|3000|4000|5000|6000|\n|-|-|-|-|-|-|-|-|\n|PlanU|0.294±0.009|0.369±0.033|0.964±0.256|1.056±0.070|1.150±0.106|1.11±0.097|1.207±0.032|\n|RAP(LLM+UCT)|-0.031±0.026|-0.037±0.036|0.318±0.084|0.245±0.082|0.267±0.081|0.308±0.078|0.274±0.078|\n|RAP(LLM+pUCT)|0.139±0.031|0.296±0.034|0.318±0.01|0.320±0.017|0.318±0.004|0.327±0.010|0.324±0.012|\n|RAP-D (DMCTS+pUCT)|0.030±0.004|0.110±0.019|0.140±0.01|0.142±0.011|0.142±0.009|0.19±0.016|0.261±0.018|\n|RAP-E (EMCTS+pUCT)|0.104±0.0|0.252±0.065|0.533±0.282|0.603±0.34|0.562±0.279|0.521±0.24|0.508±0.244|\n|RAP-D-UCC|0.116±0.007|0.284±0.039|0.334±0.006|0.971±0.092|0.952±0.118|0.991±0.105|1.065±0.132|\n\n> W2:...Most of the failure cases are manually injected..\n\nWe have evaluated PlanU on real-world tasks with more realistic failures. Please refer to our response to Reviewer c3qH and bLkk.\n\n> W3:...the expectation operator ( \\mathbb{E} ) as the default ( \\psi )...the necessity of learning the full distribution ( Z(s_t, a_t) )...\n\nIn distributional RL, **learning an approximate distribution rather than a single expected value can preserve the multimodality in value distribution, which can lead to more stable learning.** As shown in the following tables, PlanU w/o dist—a variant using mean value without learning quantile distribution—performs significantly worse than PlanU. \n\nWe also evaluated impacts of different operators: $\\tau_ {0.5}$, $\\mathbb{E}[Z(s_ t,a_ t)]$ +variance, and $\\mathbb{E}[Z(s_ t,a_ t)]$+ $\\tau_ {0.9} - \\tau_ {0.1}$. $\\mathbb{E}[Z(s_ t,a_ t)]$ is the mean operator, $\\tau_ {0.5}$, $\\tau_ {0.9}$ and $\\tau_ {0.1}$ are the value for quantile 0.5, 0.9 and 0.1, respectively. The mean operator (below tables) can lead to first or the second performance.\n\n**Tomato lettuce salad**\n||0|1000|2000|3000|4000|5000|6000|\n|-|-|-|-|-|-|-|-|\n|PlanU|0.294±0.009|0.369±0.033|0.964±0.256|1.056±0.070|1.150±0.106|1.11±0.097|1.207±0.032|\n|PlanU w/o dist|0.213±0.007|0.333±0.007|0.335±0.003|0.345±0.003|0.338±0.004|0.344±0.003|0.347±0.001|\n|$\\tau_{0.5}$|0.051±0.046|0.524±0.074|0.567±0.077|0.729±0.105|0.765±0.09|0.626±0.101|1.027±0.092|\n|$\\mathbb{E}[Z(s_ t,a_ t)]$+variance|0.102±0.058|0.192±0.069|0.234±0.056|0.210±0.059|0.867±0.113|0.966±0.115|0.922±0.088|\n|$\\mathbb{E}[Z(s_ t,a_ t)]$+$\\tau_ {0.9}-\\tau_ {0.1}$|0.090±0.073|0.916±0.102|0.929±0.087|0.889±0.098|1.022±0.108|0.905±0.097|1.067±0.089|\n\n **Entertainment**\n||0|1000|2000|3000|4000|5000|6000|\n|-|-|-|-|-|-|-|-|\n|PlanU|0.008±0.004|0.46±0.279|0.877±0.091|0.945±0.073|0.948±0.057|0.991±0.085|0.982±0.011|\n|PlanU w/o dist|0.001±0.0|0.070±0.0|0.085±0.0|0.1871±0.005|0.7159±0.115|0.906±0.062|0.977±0.081|\n|$\\tau_ {0.5}$|0.004±0.007|0.22±0.009|0.234±0.004|0.849±0.24|0.858±0.239|0.804±0.018|0.983±0.024|\n|$\\mathbb{E}[Z(s_ t,a_ t)]$+variance|-0.004±0.01|0.0607±0.009|0.293±0.079|0.773±0.239|0.712±0.239|0.932±0.021|0.975±0.031|\n|$\\mathbb{E}[Z(s_ t,a_ t)]$+$\\tau_ {0.9}-\\tau_ {0.1}$|-0.016±0.001|0.033±0.005|0.485±0.112|0.785±0.223|0.887±0.077|1.012±0.007|0.940±0.059|\n\n> W5:...The LLM is only used for initializing probabilities... ReAct-style agents...  based on environmental feedback.\n\n1. As stated (Lines 29-32), PlanU leverages LLMs beyond simple initialization: it explicitly uses **them as a world model** to simulate outcomes for planning, similar to humans predicting consequences before execution.\n\n2. PlanU **does incorporate environmental feedback**. As detailed in Figure 2 and Lines 199-206, our backpropagation mechanism dynamically updates action probabilities based on real-world outcomes.\n\n3. In line with the reviewer's suggestion, **we did compare our work with powerful agents** in Figure 3 and Appendix C2.2: a ReAct-style MCTS agent (LATS, ICML 24) and an uncertainty-aware agent (DeLLMa, ICLR 25). LATS uses ReAct agent and reflection during MCTS planning. DeLLMa infers and predicts hidden factors to make decision. The results (below table) show that PlanU performs better than such powerful agents.\n\n|Method|2-step|4-step|6-step|8-step|\n|-|-|-|-|-|\n|LATS|0.946±0.037|0.684±0.053|0.352±0.04|0.077±0.023\n|DeLLMa|0.595±0.081|0.092±0.033|0.041±0.017|0.000±0.000|\n|PlanU|1.000±0.0|0.808±0.05|0.662±0.03|0.378±0.04|\n\n> Q1:...wouldn’t simply re-executing the same action suffice? What is the intuitive benefit of introducing a reward distribution...\n\nIf an action is optimal, re-executing it suffices, but the agent must learn to know which action is the optimal. Thus, introducing a quantile distribution is necessary to better model potential multimodality in the value distribution. We have explored more realistic failure models. Please refer to our response to Reviewer c3qH and bLkk.\n\n> Q2:...removing any single component results in almost no return improvement for the baseline...the proposed method and the baseline do not seem to be clearly distinguishable...\n\nSorry for the misunderstanding. \n\n1. There are not results for any baselines in Figures 5 (a) and (b). For comparison, we additionally show the results of RAP in below tables. **The results show that each component of PlanU leads to performance improvement thanks to their ability to deal with uncertainty.**\n\n**Tomato lettuce salad**\n||0|1000|2000|3000|4000|5000|6000|\n|-|-|-|-|-|-|-|-|\n|PlanU|0.294±0.009|0.369±0.033|0.964±0.256|1.056±0.070|1.150±0.106|1.11±0.097|1.207±0.032|\n|PlanU w/o dist|0.213±0.007|0.333±0.007|0.335±0.003|0.345±0.003|0.338±0.004|0.344±0.003|0.347±0.001|\n|PlanU w/o ucc|0.1183±0.0|0.3081±0.012|0.332±0.003|0.333±0.007|0.337±0.005|0.339±0.006|0.702±0.174|\n|RAP|0.139±0.031|0.296±0.034|0.318±0.01|0.320±0.017|0.318±0.004|0.327±0.01|0.324±0.012|\n\n**Entertainment**\n||0|1000|2000|3000|4000|5000|6000|\n|-|-|-|-|-|-|-|-|\n|PlanU|0.008±0.004|0.46±0.28|0.877±0.091|0.945±0.073|0.949±0.058|0.991±0.085|0.982±0.011|\n|PlanU w/o dist|0.001±0.0|0.07±0.0|0.085±0.0|0.187±0.005|0.716±0.115|0.906±0.062|0.978±0.081|\n|PlanU w/o ucc|0.000±0.007|0.132±0.031|0.143±0.036|0.562±0.294|0.832±0.247|1.029±0.12|0.951±0.158|\n|RAP|-0.004±0.0|0.070±0.0|0.094±0.0|0.542±0.232|0.896±0.045|0.728±0.012|0.828±0.022|\n\n2. For Figure 5c, **we demonstrate that PlanU deals with LLM uncertainty well, even for ambiguous instructions**. To augment Figure 5c, we evaluated RAP under prompt shuffling (randomly shuffling task/environment description sentences) and injection (adding task-irrelevant but environment-related text)—uncertainties common when prompts include LLM-generated content. Results (below table) show PlanU consistently outperforms RAP in handling LLM uncertainty.\n\n**Entertainment**\n||0|1000|2000|3000|4000|5000|6000|\n|-|-|-|-|-|-|-|-|\n|PlanU|0.008±0.004|0.460±0.279|0.877±0.091|0.945±0.073|0.949±0.058|0.991±0.085|0.982±0.011|\n|PlanU prompt shuffling|0.0138±0.011|0.442±0.345|0.602±0.310|0.906±0.090|0.986±0.0997|1.017±0.060|1.065±0.046|\n|PlanU prompt injection|0.011±0.006|0.341±0.179|0.376±0.232|0.839±0.042|0.888±0.048|0.898±0.106|0.997±0.088|\n|RAP|-0.004±0.0|0.07±0.0|0.094±0.0|0.542±0.232|0.896±0.045|0.728±0.012|0.828±0.022|\n|RAP prompt shuffling|0.077±0.037|0.058±0.044|0.059±0.038|0.087±0.025|0.094±0.029|0.482±0.041|0.464±0.027|\n|RAP prompt injection|0.039±0.031|0.071±0.022|0.104±0.017|0.172±0.011|0.144±0.036|0.212±0.039|0.261±0.05|\n\n> W4:The proposed UCC score lacks theoretical justification...\n\nUCT converges to optimal actions for the tabular case with finite states. However, it is not guaranteed that UCT will converge for neural networks. We leave the theoretical guarantees of UCC as future work."}, {"review_id": "ZOlxGpjzdE", "reviewer": "Reviewer_6Yh1", "summary": "This paper proposes PlanU, an LLM-based planning framework that addresses both LLM and environmental uncertainty (e.g., stochastic state transitions). It combines quantile distribution modeling of return values and a UCC (Upper Confidence Bounds with Curiosity) exploration strategy within MCTS. The approach is evaluated on multiple benchmarks, including Blocksworld, Overcooked, and VirtualHome, using several LLM backbones. Experimental results show that PlanU consistently outperforms strong baselines.", "questions": "•  See the weakness section.\n•  line 212: a uncertainty-aware - an uncertainty-aware", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n• PlanU is the first to introduce quantile-based value estimation into LLM-driven MCTS, which is a notable step toward enabling more robust and uncertainty-aware planning in real-world LLM agents.\n• Thorough testing across multiple benchmarks. The inclusion of variations such as prompt injection and prompt shuffling further strengthens the experimental credibility.\n\nWeaknesses\n• All tested backbones are in the 7–8B parameter range. Evaluating across more diverse model scales (e.g., smaller or larger LLMs) would improve the generality of the claims.\n• The ablation study could be more fine-grained. For example, testing hybrid configurations such as quantile + standard UCT or mean value + UCC would better isolate the individual contributions of each module.", "was_revised": true, "final_justification": "After considering the rebuttal and the discussions with the authors and other reviewers, my recommended score is borderline accept. My main concern was the lack of thorough experiments, which has been largely addressed.", "rebuttal": "> All tested backbones are in the 7–8B parameter range. Evaluating across more diverse model scales (e.g., smaller or larger LLMs) would improve the generality of the claims.\n\nWe further evaluated larger models in Blocksworld, including Qwen2.5-14B-Instruct, OpenAI GPT-4.1, and Google Gemini-2.5-Pro. These cover both larger-scale open-source and closed-source models. The results are summarized in the following table. PlanU performs well both on larger-scale open-source and closed-source models.\n\n**OpenAI/GPT-4.1**\n| Method | 2-step          | 4-step          | 6-step          | 8-step          |  \n|--------|-----------------|-----------------|-----------------|-----------------|  \n| CoT    | 0.541 ± 0.07    | 0.382 ± 0.06    | 0.221 ± 0.05    | 0.063 ± 0.04    |  \n| ToT    | 0.595 ± 0.08    | 0.421 ± 0.07    | 0.241 ± 0.06    | 0.077 ± 0.05    |  \n| RAP    | 1.000 ± 0.00    | 0.763 ± 0.05    | 0.341 ± 0.03    | 0.231 ± 0.06    |  \n| PlanU  | 1.000 ± 0.00    | 0.821 ± 0.04    | 0.648 ± 0.03    | 0.392 ± 0.04    | \n\n**Google/Gemini-2.5-Pro**  \n| Method | 2-step          | 4-step          | 6-step          | 8-step          | \n|--------|-----------------|-----------------|-----------------|-----------------| \n| CoT    | 0.568 ± 0.08    | 0.395 ± 0.07    | 0.228 ± 0.06    | 0.056 ± 0.05    |\n| ToT    | 0.622 ± 0.07    | 0.408 ± 0.08    | 0.248 ± 0.07    | 0.070 ± 0.06    |  \n| RAP    | 1.000 ± 0.00    | 0.776 ± 0.03    | 0.328 ± 0.04    | 0.238 ± 0.05    |  \n| PlanU  | 1.000 ± 0.00    | 0.808 ± 0.05    | 0.662 ± 0.03    | 0.378 ± 0.04    |\n\n**Qwen/Qwen2.5-14B-Instruct**\n| Method | 2-step          | 4-step          | 6-step          | 8-step          | \n|--------|-----------------|-----------------|-----------------|-----------------| \n| CoT    | 0.405 ± 0.06     | 0.178 ± 0.05     | 0.138 ± 0.04     | 0.028 ± 0.03     |\n| ToT    | 0.486 ± 0.05     | 0.247 ± 0.06     | 0.131 ± 0.05     | 0.042 ± 0.04     |\n| RAP    | 0.973 ± 0.02     | 0.605 ± 0.03     | 0.219 ± 0.03     | 0.161 ± 0.05     |\n| PlanU  | 1.000 ± 0.00     | 0.750 ± 0.02     | 0.521 ± 0.05     | 0.182 ± 0.04     |\n\n\n> The ablation study could be more fine-grained. For example, testing hybrid configurations such as quantile + standard UCT or mean value + UCC would better isolate the individual contributions of each module.\n\nThanks for your valuable advice. We have conducted such fine-grained ablation studies. Specifically, the hybrid configurations suggested are clearly presented in Appendix Figure 10:\n1. For the mean value + UCC, it is depicted as 'PlanU w/o dist'.\n2. The quantile + standard UCT is depicted as 'PlanU w/o UCC'.\n\n**Tomato lettuce salad**\n|                | 0              | 1000           | 2000           | 3000           | 4000          | 5000           | 6000           |\n| -------------- | -------------- | -------------- | -------------- | -------------- | ------------- | -------------- | -------------- |\n| PlanU          | 0.2941±0.0099  | 0.3696±0.0335  | 0.9644±0.2569  | 1.0568±0.0709  | 1.1509±0.1067 | 1.11±0.0978    | 1.2079±0.0324  |\n| PlanU w/o dist | 0.2134±0.0074  | 0.3339±0.0074  | 0.3358±0.003   | 0.3455±0.003   | 0.3383±0.0048 | 0.3441±0.0037  | 0.3477±0.0002  |\n| PlanU w/o UCC  | 0.1183±0.0     | 0.3081±0.0127  | 0.3326±0.0038  | 0.3339±0.0074  | 0.3371±0.0056 | 0.339±0.0067   | 0.7025±0.1744  |\n\n**Entertainment**\n|                | 0             | 1000          | 2000          | 3000          | 4000          | 5000          | 6000          |\n| -------------- | ------------- | ------------- | ------------- | ------------- | ------------- | ------------- | ------------- |\n| PlanU          | 0.0084±0.0044 | 0.46±0.2798   | 0.877±0.0911  | 0.9453±0.073  | 0.9487±0.0575 | 0.9914±0.0851 | 0.9822±0.0114 |\n| PlanU w/o dist | 0.0009±0.0    | 0.0701±0.0    | 0.085±0.0     | 0.1871±0.005  | 0.7159±0.1152 | 0.9062±0.0623 | 0.9779±0.0813 |\n| PlanU w/o UCC  | 0.0001±0.0074 | 0.1322±0.0314 | 0.1425±0.0356 | 0.562±0.2937  | 0.8316±0.2473 | 1.0291±0.1195 | 0.9509±0.1575 |\n\nAblation results show PlanU outperforms PlanU w/o dist and PlanU w/o UCC in both scenarios, with faster convergence and better optimal performance—confirming the critical role of both components.\n\nTo provide more information to the reviewer, we have conducted experiments to evaluate the impact of the text encoder used in UCC, and evaluate the impact of the number of quantiles. \n\nFor text encoders, the default PlanU performs better in medium-to-high iterations across both scenarios. While the two all-MiniLM variants show slightly lower overall performance, their gap with the default narrows in later iterations, indicating UCC's compatibility with different encoders.\n\n**The different sentence-transformer models in Tomato salad**\n|                         | 0              | 1000          | 2000          | 3000          | 4000          | 5000          | 6000          |\n| ----------------------- | -------------- | ------------- | ------------- | ------------- | ------------- | ------------- | ------------- |\n| PlanU（default，all-mpnet-base-v2）        | -0.083±0.0415  | 0.8995±0.0832 | 1.1069±0.0032 | 1.096±0.0132  | 1.1045±0.0032 | 1.0955±0.0173 | 1.105±0.0039  |\n| PlanU_all-MiniLM-L6-v2  | -0.1089±0.0232 | 0.2991±0.0557 | 0.9031±0.0912 | 0.8501±0.1061 | 0.8632±0.1234 | 0.8748±0.0888 | 0.8627±0.1072 |\n| PlanU_all-MiniLM-L12-v2 | -0.0926±0.0317 | 0.1556±0.0282 | 0.8808±0.0938 | 0.8008±0.1062 | 0.8764±0.1031 | 0.8897±0.0898 | 0.8837±0.0896 |\n\n**The different sentence-transformer models in Tomato lettuce salad**\n|                         | 0             | 1000          | 2000          | 3000          | 4000          | 5000          | 6000          |\n| ----------------------- | ------------- | ------------- | ------------- | ------------- | ------------- | ------------- | ------------- |\n| PlanU（default）        | 0.2941±0.0099 | 0.3696±0.0335 | 0.9644±0.2569 | 1.0568±0.0709 | 1.1509±0.1067 | 1.11±0.0978   | 1.2079±0.0324 |\n| PlanU (all-MiniLM-L6-v2)  | 0.132±0.0531  | 0.6347±0.1836 | 0.7467±0.0918 | 0.9486±0.0978 | 0.7599±0.0919 | 0.9085±0.0928 | 0.9751±0.1106 |\n| PlanU (all-MiniLM-L12-v2) | 0.1802±0.0411 | 0.4936±0.13   | 0.7907±0.0819 | 0.8845±0.1031 | 1.1068±0.0956 | 0.8613±0.1147 | 1.0757±0.1077 |\n\nThe default setting of 51 quantiles (n=51) outperforms both n=41 and n=61 in most iterations, particularly in later stages. Performance differences across quantile choices are minor, indicating that the method is robust to changes in this parameter, with the default providing the best results in our experiments.\n\n**The different number of quantiles in Tomato salad**\n|                  | 0              | 1000          | 2000          | 3000          | 4000          | 5000          | 6000          |\n| ---------------- | -------------- | ------------- | ------------- | ------------- | ------------- | ------------- | ------------- |\n| PlanU(default,n=51) | -0.0926±0.0317 | 0.1556±0.0282 | 0.8808±0.0938 | 0.8008±0.1062 | 0.8764±0.1031 | 0.8897±0.0898 | 0.8837±0.0896 |\n| PlanU(n=41)  | -0.0934±0.0305 | 0.2481±0.0407 | 0.8822±0.104  | 0.9154±0.0972 | 0.9159±0.0942 | 0.8274±0.0763 | 0.8577±0.1107 |\n| PlanU(n=61) | -0.0936±0.0262 | 0.2078±0.0573 | 0.9045±0.0887 | 0.9063±0.1    | 0.8844±0.0968 | 0.8028±0.0869 | 0.8631±0.0989 |\n\n**The different number of quantiles in Tomato lettuce salad**\n|                  | 0             | 1000          | 2000          | 3000          | 4000          | 5000          | 6000          |\n| ---------------- | ------------- | ------------- | ------------- | ------------- | ------------- | ------------- | ------------- |\n| PlanU (default, n=51) | 0.2941±0.0099 | 0.3696±0.0335 | 0.9644±0.2569 | 1.0568±0.0709 | 1.1509±0.1067 | 1.11±0.0978   | 1.2079±0.0324 |\n| PlanU (n=41)  | 0.1163±0.0539 | 0.5403±0.159  | 0.865±0.0882  | 0.8721±0.0956 | 1.04±0.1082   | 0.9891±0.0962 | 0.9802±0.1093 |\n| PlanU (n=61)  | 0.1656±0.0429 | 0.5706±0.1551 | 0.8318±0.1019 | 0.8276±0.1099 | 1.043±0.0982  | 0.9755±0.107  | 0.9901±0.1003 |\n\n\n>• line 212: a uncertainty-aware - an uncertainty-aware\n\nThanks for your help. We will check the writing of the paper carefully by using a grammar checker."}]

Author rebuttal:

Meta-review: The paper considers decision making under uncertainty, such as planning in stochastic environment; proposes PlanU, an LLM-based planning method that captures uncertainty within MCTS. PlanU models the return of each node in the MCTS as a quantile distribution, which uses a set of quantiles to represent the return distribution. To balance exploration and exploitation during tree search, PlanU introduces an UCC score which estimates the uncertainty of MCTS nodes. 

Strength

The paper addresses a timely and important problem. considers various scenarios both in deterministic and stochastic settings. considers a number of benchmarks. includes ablation studies.

The compute cost and experiment details were added during discussion period. The authors also added comparison to other MCTS forms.

The authors added various experiments and addressed the *meaningful concerns*.
I removed reviewer QuAK due to lack of engagement in the discussion process (despite my various efforts) from the final judgement call.

I ask the authors to please add the experiments, comparisons and clarifications that were discussed during the discussion period to the final version of the paper.
Decision: Accept (poster)