Large Language Models as Commonsense Knowledge for Large-Scale Task Planning
Authors: Zirui Zhao
Wee Sun Lee
David Hsu
Venue: NeurIPS 2023 poster (2023)
Keywords: Embodied Task Planning
Large Language Models
Human-Robot Interaction
TL;DR: We use Large Language Models as both the commonsense world model and the heuristic policy within the Monte Carlo Tree Search framework, enabling better-reasoned decision-making for daily tasks.

Abstract: Large-scale task planning is a major challenge.  Recent work exploits large
  language models (LLMs) directly as a policy and shows surprisingly
  interesting results.  This paper shows that LLMs provide a
  commonsense model of the world in addition to a policy that acts on
 it.  The world model and the policy can be combined in a search
  algorithm, such as Monte Carlo Tree Search (MCTS), to scale up task
  planning.  In our new LLM-MCTS algorithm, the LLM-induced world model
  provides a commonsense prior belief for MCTS to achieve effective reasoning;
  the LLM-induced policy acts as a heuristic to guide the search, vastly
  improving search efficiency. Experiments show that LLM-MCTS outperforms
  both MCTS alone and policies induced by LLMs (GPT2 and GPT3.5) by a wide
  margin, for complex, novel tasks. 
  Further experiments and analyses on multiple tasks --
  multiplication, travel planning, object rearrangement --
  suggest minimum description length (MDL)
  as a general guiding principle: if the
  description length of the world model is substantially smaller than that of  the
  policy, using LLM as a world model for model-based planning is likely better
  than using LLM solely as a policy.

Large Language Models as Commonsense Knowledge for Large-Scale Task Planning
Zirui Zhao Wee Sun Lee David Hsu
National University of Singapore {ziruiz, leews, dyhsu] Syhsp. mus. w.w.uuu..uudude
Abstract
Large-scale task planning is major challenge. Recent work exploits large language models (LLMs) directly as policy and shows surprisingly interesting results. This paper shows that LLMS provide a commonsense model of the world in addition policy that acts it. The world model and the policy can be combined in a search algorithm, such as Monte Carlo Tree Search (MCTS), to scale up task planning. In provides commonsense prior belief for MCTS to achieve effective reasoning; the LLM-induced policy acts heuristic to guide the search, vastly improving search efficiency. Experiments show that LLM-MCTS outperforms both MCTS alone and policies induced by LLMs (GPT2 and GPT3.5) by wide margin for complex, novel tasks. Further experiments and analyses on multiple tasks mossssmmulppppiiionnn travel planning, object rearrangement- suggest minimum description length (MDL) as general guiding principle: if the description length of the world model is substantially smaller than that of the policy, using LLM as world model for model-based planning is likely better than using LLM solely as a policy.
LLM-MCTS algorithm, the LLM-induced world model
Introduction
Consider, for example, an autonomous robot butler in household environment. The human user sits in the living room and asks the robot to "Put fruits into the fridge." " The robot looks for fruits, such as apples, peaches, etc., which may be on a table in the dining room, on the kitchen counter, but unlikely in a wardrobe the bedroom. To complete the task, the robot has to consider fruits' likely locations well their spatial relations, traverse these locations efficiently, and finally put them into the fridge. A household environment typically contains hundreds of movable items and locations, resulting in huge search space that makes the task very challenging for the robot.
Recently, multiple attempts exploiting pre-trained large language models (LLMs) show surprisingly interesting results for such tasks [22, 18, 2, 19, 5, 44]. Their underlying idea is simple: treat the LLM as policy and query it directly for the next actions, given the history past actions and observations. We call this strategy L-Policy, which exploits LLMs' vast commonsense knowledge to circumvent the challenge of searching very large space. In our example task, L-Policy may simply instruct the robot to move to the hallway and then to the kitchen. Even though LLMs are trained on internet-scale data, this strategy shows limits generalization [10, 4], especially when encountering uncommon, complex tasks. Alternatively, we may use L.MSs knowledge to build world model and apply planning algorithm to the model. The world model may contain, c.g., a belief over the target object's location, which biases the search and drastically improves search efficiency. We call this strategy L-Model. L-Model's performance depends on two critical preconditions: the accuracy of the world model and the efficiency of the planning algorithm. The former is question of sample complexity for learning, and the latter is that of computational complexity.
The code and supplementary materials are available
github.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

This paper presents LLM-MCTS (shown in Fig 1), which combines the ideas of L-Model and L-Policy for large-scale task planning. Like L-Model, LLM-MCTS uses an LLM to build a commonsense world model; it then uses the model to perform Monte Carlo Tree Search (MCTS) [8] online for the next actions. During the tree search, LLMMMCTS chooses the promising action branches heuristically by querying the L.L.. This is similar in spirit to L-Policy. While L-Policy commits to the actions chosen by the LLM for execution, LLM-MCTS uses these choices only as a search heuristic.
We evaluate LLM-MCTS in VirtualHome [24], a standard household activity simulation platform widely used in earlier work [18, 22, 25, 33]. The evaluation set consists of 800 randomly generated large-scale, partially observable object rearrangement tasks. In each task, robot aims to fetch a common household item with an unknown location and place it in a designated container. Our main experimental findings are summarized below:
F1. I-Model performs poorly There two possible reasons. One is model inaccuracy: the robot has an incorrect belief of the target object's location. The other is huge search space size, beyond the reach of even the state-of-the-art MCTS algorithm. Further experiments indicate that search space size is the main cause.
F2. L- L-Policy performs reasonably with both GPT2 and GPT3.5, but the performance degrades quickly for novel, complex lasks. This generally corroborates with earlier results [22, 18, 2, 19].
F3. LLM-MCTS outperforms L-Model. This clearly shows the benefit of using the LLM as a
heuristic policy to guide the search.
F4. LLM-MCTS outperforms L-Policy, especially for novel, complex tasks. LLM-MCTS basically combines L-Model and I.-Policy. Since the L-Model performs very poorly on its own, why does the combination outperform L-Policy? One explanation is that search space size the main cause of L-Model's 's poor performance. The LLM-induced world model is sufficiently accurate; tree search with this world model, when limited to the neighbourhood of the LLM- induced policy, provides improved performance over L-Policy.
The explanation for (F4) begs new question: with an efficient planning algorithm for large search space, would L-Model outperform L-Policy? To answer this question, we study two related, simpler tasks: multiplication of two large numbers and multi-hop travel planning. We discuss multiplication here and travel planning in Section 4.1. A decimal number is described as a sequence of n digits, (dn-1,dn
do). There are two methods of implementing multiplication with an L.M.. The first one corresponds to L-PPolicy. We represent the multiplication function as a table. Each row or column corresponds to number. The table entry is the multiplication of two numbers, obtained by querying an LLM. Experimentally, GPT4 performs single-digit multiplication perfectly with 100% accuracy, 2-digit multiplication with 99% accuracy, 4-digit multiplication with merely 4% accuracy, and fails almost completely on 5-digit multiplication [10]. The second approach uses LLM-derived small single-digit multiplication tables, which GPT4 performs with 100% accuracy. To multiply multi-digit numbers, it applies the long multiplication algorithm with the single-digit table. This method corresponds to L-Model. While long multiplication differs from planning in algorithmic details, it plays the same role in L-Model and is highly efficiintt. Clearly, this second method achieves 100% accuracy for arbitrarily large numbers, provided that the single-digit multiplication table is accurate. So, the L-Model outperforms L-Policy for the multiplication task, contrary to the finding for object rearrangement tasks.
How do we choose between L-Model and L-Policy then? One idea is the minimum description length (MDL) principle. Theoretical analysis suggests that a hypothesis with a shorter description length has a smaller generalization error and is preferred [28]. For multiplication, the method corresponding to L-Policy uses a large table of O112²)) entries. It takes O(n102n) bits to represent it. The method corresponding to the L-Model uses a single-digit multiplication table of constant size. The long multiplication algorithm can be encoded in any reasonable programming language with constant size. So, the total representation size is constant. According MDL,, the L-Model has smaller generalization error than the L-Policy for multiplication, with sufficiently large n. This is fully consistent with experimental results [10]. The analysis of travel planning provides further evidence (Section 4.
In summary, LLM-MCTS combines the ideas of L-Model and L-Policy, outperforming either alone for complex task planning, particularly, object rearrangement (Sections and 3). To choose between L-Model and L-Policy, MDL provides useful guiding principle (Section 4). In essence, simplicity is preferred, a well-knn well-known general principle in machine learning.
2

---

Bellef
MCTS
b(s))
LLM World
Belief Update
Model
Prompts
LLM Policy
Search Hauristic
observation Action history
Output Action
Environment
Figure Overview of LLM-MCTS. For each simulation the MCTS, we sample from the com- monsense belief to obtain an initial state of the world and use the LLM as heuristics to guide the trajectory to promising parts of the search tree.
2 LLM-MCTS: Monte Carlo planning with commonsense knowledge
We aim to solve task-planning problems in large-scale domains with partial observation. One example object rearrangement tasks [3] in household environments. It is a meaningful and challenging problem with large-scale and long-term planning horizon. It has many practical implications in everyday life [3, 34, 39, 20, 17]. such as setting the table, tidying up the room, loading the dishwasher, etc.. To solve the problem, present LLM-MCTS (shown in Fig 1), which combines the L-Model and L-Policy for large-scale planning. It uses LLM to build a commonsense world model to perform MCTS for reasoned planning and uses L-Pollcy guide the MCTS and reduce the large search space.
2.1 Task planning
We focus on task task-planning problems with partial observation and large-scale domains. The problem can be formulated as Partially Observable Markov Decision Process (POMDP): (S, A, S2, T, O, 7). The state space S define the state the robot and its environment. The action space A defines the action that the robot can do. Ω is the observation space. T defines the transition function of states, which we assume to be given. information about state. R(s, a) is the reward function determined by the action taken at the state s. The discount factor is specified by y. The history trajectory h at time step t consists of a sequence of executed actions and received observations up to time - 1, ht (oo, ao 01, 01,.... Ot-1; a--)). The objective is to find an optimal policy x (h+) that maximize the expected cumulative rewards o (Ite) arg maxae A [E:= 7" R(8145; Or++) ) (a; = a).
the observation function that provides partial
In this work, we focus on the object rearrangement task, though our approach is general method for large-scale task planning. Object rearrangement is representative embodied AI task [3, 34, 39, 20, 17] with various daily applications, such as setting the table, tidying up the room, loading the dishwasher, and more. is challenging task [3] as the robot must navigate, locate target objects and positions, and execute multi-step planning. As with hundreds of items and containers in the domain, identifying target objects can be challenging. Even with known state information, requires long-horizon planning to achieve the goal. In addition, the vast number of domain objects leads to a large action space, given the actions are to interact with objects. The vast action space produces an exponentially large search tree, making the planning extremely challenging.
Following the approach of [22, 25, 33], we model the task POMDP as outlined above. The state 5 comprises variables denoting the positions of the robot, movable items, and contain- ers. Actions A encompass five predefined actions from VirtualHome, parameterized by objec- Vcontainer/rooms: (1) pick(object), where the robot collects an observed, proximate object; (2) place(object, placementt,. allowing the robot to a picked object nearby or inside an open container; (3) open( container) and (4) close(container). for interacting with an observed, nearby containers; and where the robot relocates within a room or near an observed objec- t/container. Given our assumption of the robot's 's familiarity with house structures and the manageable size of the house, the robot can move directly to designated rooms. The deterministic transition T' pre-defined by actions. Partial observation Ô enables the robot to discern object/container positions within its room or an opened container its location. The objective based on verbal instructions, represented by reward of R. for achieving the desired item arrangement.
(5) move coom/oojec///oooooiiiin
reorganize household items
3

---

2.2 LLM as commonsense world model
commonsense prior belief of states can improve the effectiveness of object and location searches by prioritizing the search to appropriate locations. Our approach utilizes LLM's commonsense knowledge to generate the initial belief of states, which is updated with each action and observation in the real world. MCTS samples from the belief in simulation to estimate the value of the action.
Initial belief of state. We use object-centric state representation and categorize the objects in the house as moveable objects (e.g., apples), containers (c.g., fridge), and surfaces (e.g., kitchen table). The states of a moveable object might be inside the containers or on the surfaces. The containers and surfaces should be inside a room. Similar to [22, 25], we maintain the belief in object-centric graphs, where nodes are objects and edges describe abstract-level relationships (e.g., apples are inside fridge, fridge is inside kitchen) between objects and rooms. Details are in the Appendix C.2.
Assume dataset D is accessible, containing expert actions and observations in similar household environments to solve daily tasks. L.MS can use the observations in the data to know what are the objects in the house and predict their positions, forming the commonsense belief of the state. To achieve this, we find all the objects, containers, and surfaces that appeared in the dataset D to form a list of objects Dobj using a unique name for all of them. To approximate b(so), we ask the LLMs to sample the positions of objects M times. For each sample, we ask the LLM to predict the position of objects using Dobj and a fixed prompt. For instance, we ask LLM to complete "The containers the apartment are: fridge.... .... The surfaces in the apartment are: kitchen counter, ....; Question: what are the possible positions of strawberry? Answer: inside fridge, inside pantry... Question: what are the possible positions of upple? Answer:_" " We use three prompt examples to provide example formats the response. The exact prompts we used are provided in the appendix. As the responses from LLM are free-form natural language, we have to precisely map those expressions to Dobj for consistent state representation. Thus, we encode the names of objects in the LLM's response into embeddings using Sustence-BERTT f()) [26] and examine their cosine similarity to the unique name f(e))
of objects in Dobj: CosineSim(e;,, e) = IT where e the name of objects, containers, or surfaces in the LLM's response, and e E Dobj are the unique names in the object list. We select the most similar expressions in Dabj to form the sampled state. For example, when querying the position of an apple, the LLM's s response is "on the kitchen table," we use the above technique to translate "the kitchen table" to "kitchentable," " a unique name in Dabj-
Goal. Similar to [40], we use L.MSs to translate the natural language goal into a formal goal for MCTS. We use fixed set of prompt examples for LLM to interpret natural language goals, such as "put one apple into the fridge" is translated as a tuple "(apple, inside, fridge)." For compositional instructions, it will translate it into multiple tuples, such as "put one apple on the kitchen table and one plate inside the dishwasher" is translated as "(apple, on, kitchentable), (plate, inside, dishwasher)." " We precisely map the LLM-generated goal into the admissible expressions in Dabj for search using the same representation as the state. In MCTS, the goal is used to identify the reward. As the representations the same, we can directly check whether the object's state is the same as the goal by string matching. If the goal is reached, it will receive a large positive reward, or 0 otherwise.
2.3 LLM as a heuristic policy
We use LLMs to play the role of T ((a(h) in PUCT to guide the action selection in the simulation procedure. In this procedure, the LLM takes as input the examples in the dataset, the goal description, the current observation, and the history of actions, and then outputs the suggested action plan (e.g.. "Next actions: move to the kitchen, open the fridge,.. ..."). Similar to [22], the observations and goal description are translated into English sentences. As the answer of LLM is from the conditional distribution of the following words given the context, it can also be viewed of actions to take conditioned on the context of tasks, observations, and completed actions. However, direct implementation and access to the probability value of the GPT-3.5 is not available. Thus, we propose an empirical policy distribution म that uses sampling to approximate the policy distribution.
commonsense policy
We sample the LLM for M times to approximate the policy probability distribution. For each sample, we query the LLM with prompt and trajectory history and receive an answer of the following actions to take og ~ LLM(h, prompt), where o; is the first action of the answer. The prompt examples are retrieved from the dataset according to the similarity to the current language instruction l. We use [26] to translate the instructions in the dataset E D into embedding and examine their

---

Algorithm LLM-MCTS
1: procedure SEARCH(h, b, NN)
20:
if < or done
True then
2: T. 1
21:
return
3: while < <No. do
22:
end if
4: 8 ~ b(s)
23:
h is not in T Tthen
5: SIMULATE(S, h, False, 0, T)
24:
T T TUh,N()) t- 0 Va E A, A,, a) +- 0, (h, a) + return ROLLOUT(s, h, done, d)
6: 1 6 n ++1
25:
7: end while
26:
8: return a Q(h, a)
27:
end if
9:
end procedure
28:
*(ahh) +
10: procedure ROLLOUT(s, h, done, d)
VN(A) argmaxx Q(h, a) (ct((a))))))))) N(ha)t1
if if' < e or done True then return 0 end if
29:
aEA
12:
30:
(s',0, r,,,cc) ~ g(s
31:
N' + PUSHBACK(,,, (a o), + d+1
14:
Trollout (ho,lout(h..) (s', done) ((s, a)
32:
R+++--SSMULATE
h done, d' 7)
33:
N(h,a")+= += N(h)
16:
h' < PUSSHBACK(A (h, la o)), d' + d+1 return r + 7 R-LLOOUU, hi, done, d') end procedure
34:
Q(h,a") + " + N(h.a*)
RhQ("a"))
17:
18:
35:
return R
19:
procedure SIMULATE(s; h, done, d)
36: end procedure
cosine similarity the current instruction: CosineSim(4,, f). In experiments, we use subset of D to show its performance when restricted to a small training set. We select the top K similar instructions and use the corresponding expert trajectories as K-shot prompt. However, the answer og is a free-formed natural language sentence that cannot be mapped to admissible actions for the agent directly. To ensure that the action can be executed, we follow the method in prior works [18] to represent the actions and admissible actions by embeddings from [26] and evaluate their cosine similarity CosineSim(ar, a). The empirical policy distribution formulated follows:
(a/h) = 1 + (1 - A)Softmax{{ {Σ CosineSim a) - 77, where 7j is the average value of Σ, CosineSim(a;, a) and |.A| is the size of the admissible action space. À is a hyper-parameter that adds randomness to the belief, as the sampled actions from LLM could be very deterministic. Therefore, the empirical policy distribution is a mixture of approximated policy from LLM and uniform distribution. The example prompts are provided in Appendix F.
2.4 Monte Carlo tree search
We integrate the commonsense world belief and policy from LLM in MCTS, presented in Alg 1. For each simulation, MCTS samples a state from the belief b(s) at the root (line 4). It independently samples one position for each object construct state This sampled state is then employed in the simulation, generating a new tree trajectory. An action a" is chosen during the simulation based on the Q value, visit counts, and LLM policy (lines 28 and 29). The observation and transition function, denoted as G (lines 15 and 30), predict the next state s' given the selected action a" and the sampled state s, thus progressing encountering leaf nodes in the tree, MCTS expands the tree and performs a random rollout for the corresponding node (lines 23 to 26). uniform policy employed sample actions the rollout, and the discounted reward is then returned (lines 14 to 17). Upon completing the task or reaching the maximum depth, the accumulated rewards are backpropagated, updating each node's estimated Q value (lines 32 to 35). Following N simulations, the output action is determined based on the estimated Q value (lines 3 to 8). Upon completion of the search process, the agent will execute an action and receive new observation. For simplicity, we assume that the observation and transition functions are deterministic and known. In cases where an object is detected, its corresponding position within the belief will be updated with the observed position. Conversely, if the object remains undetected at certain positions, the belief regarding its presence in those positions will be rendered null, denoted by zero value.
the subsequent step in the simulation (lines 30 and 31). When
5

---

3 Experiments
3.1 Experimental setup
VirtualHome. We proceed with our experiments in the VirtualHome [24], a large household simulated environment with a large domain, partial observations, and large action space. It contains hundreds of interactive items and containers with various types of rooms. It is a well-suited platform for evaluating embodied pocision-mmking for solving daily tasks in household environments.
Data. To generate data for prompting and baseline training, we follow [25] to create 2000 tasks with randomly initialized scenes and expert trajectories. There are several settings for the evaluation. Simple tasks are the tasks that only require the rearrangement of one item generated from the same distribution as the training dataset. Comp. refers to the composition of simple tasks in order to rearrange multiple objects sampled from the same distribution as the dataset (e.g.. "Put plate on kitchen table and chicken inside fridge" is the composition of "put plate on kitchen table" and "put chicken inside fridge,") ). The composition of tasks increases the planning horizon, making it more challenging to complete. In evaluation, we also use the Novel Simple tasks with seen items (e.g.. in the dataset, we have "put one plate on the kitchen table" and "put one chicken inside the fridge," and we use "put one plate inside the fridge" and "put one chicken the kitchen table" to evaluate; these tasks are not included in the training dataset). For compositional tasks, we include Novel Compositional tasks, with 2 or 3 primary tasks composed, denoted NovelComp(2) and NovelComp(3) (e.g.. we have "put plate on kitchen table" and "put chicken inside fridge," in dataset but their composition "Put plate kitchen table and chicken inside fridge" is not.) We also generate scenes at a Novel Apartment for testing, where the distribution of object positions differs from the dataset.
The expert data are generated by an Oracle agent implemented in [25]. The expert has the full knowledge of the environment (hence, does not need to understand where objects are likely to be placed) and uses handcrafted heuristics for completing various tasks. It uses regression planning to search for solutions to a task. We collect the actions and observations of the expert completing the tasks in the VirtualHome simulator as the dataset. There are 10,000 trajectories in total for training the baseline. To show the capability of LLMs when using a small training set, we only seleet 200 instances uniformly at random from the dataset as prompt candidates for the LLM model and policy when used in a sho- mode with no fine-tuning. We also generated 800 tasks in total for evaluation.
Evaluation. We evaluate the success rate of completing the tasks within 30 steps, while typical task can be finished within at most 15 steps. The task considered successful if all the requirements of object positions are satisfied. For example, given the instruction "Put one apple inside the fridge," the task successful if any apple is in the fridge. For simplicity, we don't consider the task of rearranging very specific object, e.g.. putting the leftmost apple in the fridge.
Baselines. We evaluate several baselines to compare. UCT [21]: We use the UCT algorithm to conduct planning without commonsense knowledge and use the ground-truth reward function in simulation. We use uniform distribution as the initial belief for states of objects. It is to provide evidence that commonsense knowledge improves planning efficiency. Finetuned GPT2 policy [22]: we use the training dataset with 10000 trajectories to fine-tune GPT-2 as the plan- ning policy. This is to show that larger pre-trained LLM without fine-tuning outperforms the smaller model fine-tuned in specific tasks. GPT3.5 Policy [18]: LLM takes as input the instruc- tions and history of actions and the currently visible objects to generate the next action. We use the LLM as the policy only, with a few examples as prompts to interact with the environments.
This baseline demonstrates the benefits of additional in- formation from the common- sense model and algorithmic benefits from MCTS.
Table Main results: mean standard error of success rate (%)
Seen Home
Method
Simple
Comp.
NovelSimple NovelComp.0. NovelComp.(3)
UCT [2]]
0.0:1:00
0.0:00.0
0.0:0..0
0.0=:0.0
0.0:1:0.0
fiactuned GPT2 policy [22]
81.3+24
59.0=6.7
41.247.11
30.9+28.
1.3
GPT3.5 Policy [1]]
83.4168
47.017.8
74.31140
48.2-18.8
5.4::2.0
GPT3.5-MCTS (Ours)
91.433.3 71.216.2
88.1144
72.61169
33.6=3.1
3.2 Results
Unseen Home
Methed
Simple
Comp.
NovelSimple NovelComp.(2) NovelComp.(3)
Main result. The main re- sults of the experiments are shown in Table 1, reporting the success rate of our method
UCT [2]]
0.0+10.0
0.0:0000
0.0-1.00
0.0:00.0
0.0:10.00
fiactuned GPT2 policy [22]
63.5+334
39.925.2
33.4::6.4
12.8:39
1.1::099
GPT3.5 Policy [18]
7..31:5.0
43.314.
6788149
54.01330
69112..1
GPT3.5-MCTS (Ours)
82.9432 71.955.6
79.3411.
70.4-66.4
38.8

---

and baselines in completing the tasks in VirtualHome environments. In this result, GPT3.5-MCTT outperforms all the compared baselines, especially for unseen situations. UCT works poorly all con- ditions, as the poor model and the huge search tree make the planning intractable. Thus, we focus our discussion on comparing the finetuned GPT2 policy and GPT3.5 policy. For Simple, in-distribution tasks, the planning horizon is relatively short. Finetuned GPT2 policy, GPT3.5 Policy, and our method work reasonably well, but our method still outperforms the baselines. For Novel Simple tasks, finetuned GPT2 policy works significantly worse than GPT3.5 Policy and GPT3. MPPT3.-MCTS.... This is because the fine-tuning of narrow tasks results in a biased distribution of the policy and compromises generalizability. GPT3.5 Policy and GPT3.5-MCTS work better due to the LLM's few-shot planning capability. GPT3,5-MCTS works better for both situations. It benefits from the MCTS' look-ahead search that explore possible states for potential outcomes in order to make reasoned decisions.
For the Compositional, in-distribution tasks, the finetuned GPT2 policy and GPT3.5 policy get significantly worse performance, while GPT3.5-MCTS works far better. The finetuned GPT2 policy trained by behavior cloning that suffers from compounding errors. Therefore, when the planning horizon gets longer, the influence of the errors accumulates and compromises the overall performance significantly. As for GPT3.5 Policy, the longer horizon potentially introduces more errors during planning, which might not be included in the prompt examples. Without suitable guidance from prompt, we cannot guarantee the GPT Policy will carry out suitable replanning when encountering errors. MCTS encourages exploration to certain extent of different possible actions during searching, introducing additional guidance to the GPT3.5 policy to look into other possible solutions. This is because the action selection procedure in EPT3.5-MCTS is not purely determined by GPT3.5 Policy but also by the Q value and visit counts. Thus, MCTS encourages GPT3.5 Policy to explore other possible search directions instead of excessively applying certain actions sampled by itself.
Ablation study. We conduct ablation studies to see the individual contributions of different com- ponents within the refers to the absence of PUCT guided by the GPT3.5 Policy for action selection. Instead, it solely relies on UCT with an initial commonsense belief derived from LLM. The variant employing the Uniform State Prior utilizes a uniform prior belief regarding states, in contrast to the LLM L-g-eeeertted initial belief employed during the search process. Lastly, the variant operating in Fully Observable environment aims to assess the accuracy of LLM's knowledge in modeling the world.
framework. The No Heuristic Policy version of GPT3.5-MCTT
Table 2 shows the re- sults of our ablation study. The outcomes obtained under the No Heuristic Policy ver- sion highlight the sig- nificance of heuristic policies in facilitating MCTS to conduct effi- cient searches for com- plex and large-scale planning tasks. Con- versely, the results of the Uniform State Prior row indicate that incorrect world models compromise search performance. This is because the model of the world determines the Q value. The wrong model results in an inaccurate estimation of the Q value, misleading the search process toward irrelevant locations. The Fully Observable results demonstrate that GPT3.5-MCTS with perfect knowledge of the environment only slightly outperforms its counterpart without it, implying that the commonsense knowledge of LLM regarding world modelling suffices for practical purposes.
Table 2: Ablation Study: mean + standard error of success rate (%)
Soen Home
Method
Simple
Comp.
NovelSimple NovelComp.(2) NovelComp.(3)
GPT3.5 MCTSS (No Heuristic Policy)) 0.0:1..0
0.0:10.0
0.0:1..0
0.0.1.0.0
0.0:10.0
GPT3.5 MCTS (Uniform State Prior)
3.2.1.11
0.0.1..0
1.110.4
0.0.1..0
0.0.1..00
GPT3.5-MCTS (Fully Observable)
94.0=2.1
80.7+3.3
94.3124
78.5444.00
34.0:14.4
GPT3.5-MCTS (Ours)
91,4=333
712266.
88.124.3
72.626.9
33.6#3.1
Unseen Home
Method
Simple
Comp.
NovelSimple NovelComp.(2) NovelComp.(3)
SUTT3.S-MCTS (No Heuristic Policy)
0.0:20.0
0.0:2:0.0
0.0::0.0
0.0::0.0
0.0:00.0
GPT3.5 MCTS (Uniferm State Prior)
1.110.2
0.010.00
0.0.1..0
0.0.1..0
0.0.1..0
GPT3 SPP3355-CTS (Fully Observable)
85.1=500
7755332
82.24333
766+3.11
37.9-+2.9
GPT3,5-MCTS (Ours)
82.9=3.2
7199556
79,3#3.3
70.426.4
38.8:13.4
Failure analysis. Policy, model, and translation errors are the primary causes of failures. Among these, policy errors are responsible for the majority of the failures. Oftentimes, the policy produces unreasonable behaviours that mislead the search procedure. For example, it usually outputs inad- missible actions, such as "walk to the cutleryfork" where the "cutleryfork" is not in the observation. It also produces back-and-forth behaviours, resulting in an unreasonable heuristic and slowing the search procedure. For example, when putting objects inside the microwave, it is sometimes struck by repeatedly opening and closing the microwave. For model error, the predicted positions of objects not always correct. Since a random rollout policy is employed, incorrect object states can result in higher Q-values than correct states, leading to misguided exploration. The wrong translation also
7

---

compromises the performance as we translate the response from LLM to admissible action or object names to ensure executability. This partly caused by the VirtualHome environments, as the policy might not understand the underlying logic of the actions in VirtualHome, such as you have to walk close to interact with the object. Thus, if the LLM outputs "open fridge" but is not close enough to the fridge, the action will be translated to other admissible actions ("open fridge" is not inside the admissible actions for this case as it is invalid due to the setting of VirtualHome).
4 LLM as a model or a policy?
When would using LLM as a model outperform using LLM as a policy, and vice versa? We propose using the minimum description length (MDL) principle, also known as Occam's Razor from the philosophy of science, to gain insights into the issue. The MDL principle suggests choosing the method that has a shorter description when both methods fit the training data well. MDL has been formalized in various ways. One formal statement (from section 7.3 of (28]) is provided here:
Theorem 4.1 (Occam's 's Razor), Let H. be a hypothesis class and let d : H. + 1) be a prefix-rree description language for H. Then, for every sample size, m, every confidence parameter, 5 >> 0, and every probability distribution, D, with probability greater than 1 1 8 over the choice of S S~ D we where Lg( the empirical loss of h on the S, (h) is the expected loss of h, and [h] is the length d(h).
have that, Th E H. LD(h) S [g) + /(hh + In (2/8))
According to Theorem 4.1, we can bound the expected loss of solution h by the description length |h| and the training loss (h). We do not know the LLM training loss for using it as a model or as policy, but for the purpose of gaining insights, it is reasonable to assume that they are both small. In that case, the MDL. principle suggests selecting between model or policy depending on which of them has the smaller description length given the description language.
Numerous caveats should be observed when using Theorem 4.1 to gain insights into the behaviour of LLM a model and policy. The theorem assumes that the training data is independent and identically distributed (iid), which is likely not true in practice. Nonetheless, the qualitative behaviour is often similar for non-iid data. As the training data of GPT is unknown, when comparing the description length, we also assume that the training data for each subproblem is roughly the same. In addition, using the theorem to gain insights requires major assumptions on the predictor classes H. for model and policy; here, we assume that H. is the model (or policy) class that we are analysing and assume that L.M training using powerful approximators such as transformers has similar behaviour to training using the model (or policy) class. Finally, depending on how the model and policy are used, error propagation may need to be analysed separately.
Besides the multiplication example described earlier, we discuss an air travel planning task and the VirtualHome object rearrangement task examined earlier.
4.1 Travel planning
Consider planning for air travel from a starting city to the destination city. To solve the problem through L-Model, we need to have the model the direct flights out of each city - together with a shortest path algorithm. The model can be represented as a graph, which is likely to be sparse in the real world. For sparse graph, an adjacency list will give a compact representation. Assuming that the total number of edges grows proportionally to the number of cities, O(n log n) bits would be sufficient to describe a graph with n cities, with approximately log n bits used to describe each city in the adjacency list structure. The shortest path algorithm can be described by any reasonable programming language with a constant size. The method regarding L-Policy can be represented as a 2-dimensional table, where each row and column denotes the current and destination city, and the table entry describes the next city to fly to on the shortest path from the current city to the destination. The next city in the table can be described with log n bits. As such, with cities in the rows and columns, there should be approximately n² log n bits in total. Thus, according to MDL, the L-Model has shorter description length and should make fewer generalization errors than the L-Policy for travel planning with sufficiently large n.
Experiment. We conducted experiments about planning for air travel from starting city to destination city, which we analyzed above. We utilized GPT-3.5 to generate flight paths between cities. We compare it to the GPT-3.5 model-based approach: we use GPT-3.5 to predict neighbouring
8

---

cities connected by a direct flight, which feeds into the uniform-cost search (i.e., replace node expansion by GPT-3.5 as the world model).
We use the data from the Kaggle World cities database, select 68 cities with populations exceeding 5 million in different countries and 62 middle-size cities with populations between 500 thousand and million, and use the Virtual Radar Server to get the flight routes dataset as ground truth. In our tests, we sampled 400 city pairs among large cities and 400 pairs among mid-size cities, evaluating path accuracy by verifying each direct flight exists. Paths were accepted if all flights were valid, even if they extended beyond our selected source and target cities. We evaluate the methods in two settings: predicting the flight route given two large cities and two mid-size cities.
Results. The main result shown in Fig 2 suggests that the LLM model + search algorithm consistently outperforms the LLM policy, supporting our analysis². Furthermore, the performance gaps for mid-size cities are larger than for large cities. This is consistent with the fact that there are more mid- size cities than large cities (the gap between the description lengths of n² log for policies vS n log n for models grows with the number of cities). Note that performance decreases as the path length increases for both methods. As the number of predictions required for each path
Large Cliis
LLMesmode SSarch
LiM vice Saarh
0.5
0.6-
0/6
0.0
Num
Figure 2: Flight planning results.
increases with path length, the probability of incorrect path prediction also increases.
4.2 Object rearrangement task
Consider a house with n movable objects. m containers, and k rooms. If we use L-Model, we must describe the model and search algorithm (i.e., MCTS). The model can be represented as a sparse graph with objects, containers, and rooms as nodes, and weighted directed edges signifying "located in" relation between the nodes, with the weights specifying the probabilities. Assume that each weight is specified with a constant number of bits. Each of the objects can be located within the m + & containers or rooms, so each object edge would require approximately log(m + k)) bits to describe. Each of the containers can be located in & rooms, each container edge would require approximately log(k) bits to describe. Assume further that the degree of each object and container node in the graph is bounded by constant; the entire graph then requires O log(mn + k) + m log(k)) = ((m + n) log(m + k)) bits to describe. The MCTS algorithm should be described by programming language with constant size. For the L-Policy, tasks can be designated using object-container pairs. Each object-containg
policy can be defined by a sequence of actions, e.g. "walk the fridge, open the fridge," until the object is found, followed by sequence of actions until the destination container is found. Each action takes O(m + k) bits to describe. Assuming search sequences and the size of each object-containet policy are bounded by constant. Describing the policies for all mn object-container pairs requires O (mn log(m + k)) bits.
The composed tasks provide further challenges for L-Policy. Composing tasks increases the descrip- tion complexity of policies to ((mm))* + where is the number of composed tasks if the composition is not exploited in the policies. For the L-Model, decomposition is automatically done in MCTS at the expense of more computation, whereas for the L-Policy, the LLM must learn to do the decomposition. This may make the problem of learning the decomposed policy computationally more difficult and less likely to be approximated by the LLM in practice.
This analysis indicates that the L-Model has shorter description length than the L-Policy. According to the MDL principle, the L-Model will likely have a lower error rate than the L-Policy. However, in this case, we do not have algorithm that is guaranteed to be efficient for solving L-Model. Instead, we use the L-Policy as a search heuristic to obtain a practically effective search algorithm. As predicted by the MDL principle, the search with the LLM-induced world model, when limited to the neighbourhood of the -induedd policy, provides improved performance over L-Policy.
4.3 Discussion
While we have discussed problems where the L-Model outperforms the L-Policy, we would also expect the L-Policy to outperform the L-Model when the description length of policies is shorter than
Single-edge results are omitted for mid-size cities there such routes in the experiments.

---

the models. For example, when recommending a tourist itinerary for a city, the description length of the itinerary should be shorter than describing all the places of interest plus the reward and the length of time recommended for visiting each location. In such a case, the LLM may be able to do better in recommending an itinerary than in providing accurate information on all places of interest for planning itineraries.
In the multiplication problem, the model-based approach used a known efficient multiplication algorithm. In the air travel planning task, an efficient shortest-path algorithm is used. However, for the object rearrangement problem, we do not have an efficient search algorithm. In this case, we demonstrate another strength of LLMs as a policy, it can be used as a heuristic for improving the efficiency of search algorithms.
Related work
Task planning has long-standing history in the AI research community. In the early stage, many studies [1, 15, 14, 12] focused on task planning in a discrete state space with deterministic transitions. These methods are intractable for large-scale, long-horizon problems. Recently, researchers have used learning-basse
methods to learn planning policies directly [22] or to learn search heuristies to accelerate planning [32, 31, 41, 7, 29]. Those policies or heuristics are not generalizable to other unseen settings. Most recently, the pre-trained LLMs have been applied as few-shot policies for task planning [18, 2, 19]. However, the planning policy may not have good compositional generalizablity. In the roboties community, many studies proposed that task planning should be integrated with physical-level motion planning, i.e., task and motion planning (TAMP) [11, 12, 9J. This paper focuses on large-scale task planning with partial observations and large, object-centric domains, in which classical planning is intractable and learning- based methods require massive data.
Various approaches are proposed scale up to large-scale planning problems. Initially, the Monte Carlo method [21, 8, 6] is proposed to tackle intractable large-scale problems using random sampling in the tree search. However, further scaling up to the problem with a large domain with sparse rewards requires massive sampling. Silver et al. [32, 31] integrate MCTS with deep learning to bias the action selection and reduce sampling. The idea has been successfully applied in large-scale planning scenarios [32, 31, 7, 27]. Most recently, studies show that LLM can be few-shot open-loop [18, 2] and closed-loop [19, 37] planning policy in the large domain, while may suffer from hallucinations. In this paper, show that LLMs' commonsense knowledge can guide search algorithm, reducing the search space sufficiently for practical planning and producing reasoned results.
How to use LLMs for a planning problem? LLMs have been used as few-shot policy for language- conditioned task planning [18, 2, 19], or a policy for multi-step reasoning problems [38, 42]. However, recent research [10] also suggests that transformer LLMs are inherently limited for solving multi-step reasoning problems. In addition, some studies try to use LLMs as heuristics [43] or transition function [13] in MCTS, boosting the performance in coding or small-scale reasoning. However, the literature has not discussed utilizing LLMs as a world model in depth. We show the benefits of using LLM to model the world, well as using MDL analysis to decide how to use LLM for planning problems.
6 Conclusion
We use LLMs as the commonsense world model and the heuristic policy within MCTS to achieve better-reasoned decision-making for daily tasks. MCTS enables L.M to leverage its world modelling knowledge for informed reasoning and explore new combinations of actions to tackle novel tasks. LLM helps MCTS through the biased sampling of states and actions, improving its efficiency in resolving complex task-planning problems. Our analysis and empirical evidence suggest that, for certain real-world domains, if the description length of the world is substantially shorter than policy, using LLM as a model in a model- approach is a better option than using LLM as policy.
The runtime of LLM-MCTS is currently hindered by multiple LLM calls. The details of runtime performance are in Appendix E. While our method requires multiple LLM calls, it provides substantially improved results. There are also various ways to enhance runtime performance like using smaller M. like Ilama [35, 36] or distilling L.MM's knowledge into smaller model [30, 16, 23]. Those are interesting avenues for future research.
Limitations.
10

---

Broader impact. There might be concerns about the inherent biases of LLMs that may lead to unfair or risky decisions in some domains. Further study about the fairness and bias of LLMs' knowledge would be beneficial.
Acknowledgments and Disclosure of Funding
This research is supported in part by the National Research Foundation (NRF), Singapore and DSO National Laboratories under the Al Singapore Program (No. AISG2-RP-2020-011 and the Agency of Science, Technology and Research (A (AAR),,), Singapore, under the National Robotics Program (No. M23NBK0053).
References
[1] Constructions Acronautiques, Adele Howe, Craig Knoblock, ISI Drew McDermott, Ashwin Ram, Manuela Veloso, Daniel Weld, David Wilkins SRI, Anthony Barrett, Dave Christianson, al. Pddll the planning domain definition language. Technical Report, Tech. Rep., 1998. 10
[2] Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, et al. Do i can, not as say: Grounding language in robotic affordances. arXiv preprint arXiv:2204.0169) 2022. 1,
2, 10
[3] Dhruv Batra, Angel X Chang, Sonia Chernova, Andrew J Davison, Jia Deng, Vladlen Koltun, Sergey Levine, Jitendra Malik, Igor Mordatch, Roozbeh Mottaghi, et al. Rearrangement: A challenge for embodied ai. arXiv preprinl arXiv:201 1.01975, 2020.
[4] Lukas Berglund, Meg Tong, Max Kaufmann, Mikita Balesni, Asa Cooper Stickland, Tomasz Korbak, and Owain Evans. The reversal curse: Llms trained on" a is b" fail to learn" b is a". arXiv preprint arXiv:2309. 12288, 2023. 1
[5] Anthony Brohan, Noah Brown, Justice Carbajal, Yevgen Chebotar, Joseph Dabis, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Jasmine Hsu, et al. Rt-1: Robotics transformer for real-world control at scale. arXiv preprint arXiv:2222.0665
2022. 1
[6] Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and Al in games, 4(1):1-43, 2012. 10
[7] Panpan Cai, Yuanfu Luo, Aseem Saxena, David Hsu, and Wee Sun Lee. Lets-drive: Driving in a crowd by learning from tree search. arXiv preprint 1905. 2019. 10
[8] Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Computers and Games: 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006.
Revised Papers 5, pages 72-83. Springer, 2007. 2, 10
[9] Yan Ding, Xiaohan Zhang, Chris Paxton, and Shiqi Zhang. Task and motion planning with large language models for object rearrangement. arXiv preprint arXiv:2303.0622
2023. 10
[10] Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jian, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D Hwang, et al. Faith and fate: Limits of transformers on compositionality. arXiv preprint arXiv:2305. 18654, 2023. 1, 10
[11] Caclan Reed Garrett, Rohan Chitnis, Rachel Holladay, Beomjoon Kim, Tom Silver, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. Integrated task and motion planning. Annual review of control, robotics, and autonomous systems, 4:265-299 2021. 10
[12] Caelan Reed Garrett, Tomás Lozano-Pérez, and Leslie Pack Kaelbling. Pddistream: Integrating symbolic planners and blackbox samplers via optimistic adaptive planning. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, pages 440-448, 2020. 10
[13] Shibo Hao, Yi Gu, Haodi Ma, Joshua Jiahua Hong, Zhen Wang, Daisy Zhe Wang, and Zhit- ing Hu. Reasoning with language model planning with world model. arXiv preprint 11X49 2023. 10

---

[14] Malte Helmert. The fast downward planning system. Journal of Artificial Intelligence Research, 26:191-246, 2006. 10
[15] Jörg Hoffmann. Ff: The fast-forward planning system. Al magazine, 22(3):57-57, 2001. 10
[16] Cheng- Yu Hsich, Chun-Liang Li, Chih-kuan Yeh, Hootan Nakhost, Yasuhisa Fujii, Alex Ratner, Ranjay Krishna, Chen- Yu Lee, and Tomas Pfister. Distilling step-by-step! outperforming larger language models with less training data and smaller model sizes. In Findings of the Association for Computational Linguisties: ACI. 2023, pages 8003-8017, Toronto, Canada, July 2023. Association for Computational Linguisties. 10
[17] Eric Huang. Zhenzhong Jia, and Matthew T Mason. Large-scale multi-objeet rearrangement. In 2019 International Conference on Robotics and Automation (ICRA), pages 211-218. IEEE,
2019. 3
[18] Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. Language models as zero-shot planners:
Extracting actionable knowledge for embodied agents. In International Conference on Machine Learning, pages 1118-114.. PMLR, 2022. 1, 2, 5, 6, 10
[19] Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang. Pete Florence, Andy Zeng. Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al. Inner monologue: Embodied reasoning through planning with language models. arXiv preprint arXiv:2207.0566 2022. 1,
2, 10
[20] Yash Kant, Arun Ramachandran, Sriram Yenamandra, Igor Gilitschenski, Dhruv Batra, An- drew Szot, and Harsh Agrawal. Housekeep: Tidying virtual households using commonsense reasoning. In European Conference on Computer Vision, pages 355-373. Springer, 2022. 3
[21] Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In Machine Learning: ECML. 2006: 17th European Conference on Machine Learning Berlin, Germany, September 18-22, 2006 Proceedings 17, pages 282-293. Springer, 2006. 6, 10
[22] Shuang Li, Xavier Puig, Chris Paxton, Yilun Du, Clinton Wang, Linxi Fan, Tao Chen, De-An Huang, Ekin Akyürek, Anima Anandkumar, et al. Pre-trained language models for interactive decision-making Advances in Neural Information Processing Systems, 55:31199-312122 2022. 1, 3, 4, 6, 10, 15, 16
[23] Chen Liang, Simiao Zuo, Qingru Zhang, Pengcheng He, Weizhu Chen, and Tuo Zhao. Less is more: Task-aware layer-wise distillation for language model compression. In International Conference on Muchine Learning, pages 20852-20867 PMLR, 2023. 10
[24] 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 on Computer Vision and Pattern Recognition, pages 8494-8502, 2018. 2, 6, 14, 15
[25] Xavier Puig, Tianmin Shu, Shuang Li, Zilin Wang. Yuan-Hong Liao, Joshua B Tenenbaum, Sanja Fidler, and Antonio Torralba. Watch-and-help: A challenge for social perception and human-ai collaboration. arXiv preprint arXiv:2010.09890. 2020. 2, 3, 4, 6, 16
[26] Nils Reimers and Iryna Gurevych. Sentence- Sentence embeddings using siamese bert- networks. arXiv preprint arXiv: 10084, 2019. 4,5
[27] Julian Schritwieser,, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Si- mon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al. Mastering atari, go, chess and shogi by planning with a learned model. Nature, 588(7839):604-609, 2020. 10
[28] Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014. 2,
[29] Pratyusha Sharma, Antonio Torralba, and Jacob Andreas. Skill induction and planning with latent language. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers), pages 1713-1726, Dublin, Ireland, May 2022. Association for Computational Linguistics. 10
[30] Kumar Shridhar, Alessandro Stolfo, and Mrinmaya Sachan. Distilling reasoning capabilities into smaller language models. Findings of the Association for Computational Linguistics:
ACL 2023, pages 7059-7073, 2023. 10
12

---

[31]
David Silver, Thomas Hubert. Julian Schrittwieser, loannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel. et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6411))1140-11444 2018. 10
[32] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al. Mastering the game of go without human knowledge. nature, 550(7676):354-399 2017. 10
[33] Ishika Singh, Valts Blukis, Arsalan Mousavian, Ankit Goyal, Danfei Xu, Jonathan Tremblay, Dieter Fox, Jesse Thomason, and Animesh Garg. Progprompt: Generating situated robot task plans using large language models. In 2023 IEÉE International Conference Robotics and Automation (ICRA), pages 1523-1 11530, 2023. 3,
[34] Andrew Szot, Alexander Clegg, Eric Undersander, Erik Wijmans, Yili Zhao, John Turner, Noah Maestre, Mustafa Mukadam, Devendra Singh Chaplot, Oleksandr Maksymets, et al. Habitat 2.0: Training home assistants to rearrange their habitat. Advances in Neural Information Processing Systems,
2021. 3
[35] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et Llama: Open and efficient foundation language models. arXiv preprini arXiv:2302. 13.-:2..2.1397,, 2023. 10
[36] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open
foundation and fine-tuned chat models. arXiv preprint arXiv:2307.0922: 09288, 2023. 10
[37] Zihao Wang, Shaofei Cai, Anji Liu, Xiaojian Ma, and Yitao Liang. Describe, explain, plan and select: Interactive planning with large language models enables open- world multi-task agents. arXiv preprini 23:02 5560, 2023. 10
[38] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe Le, Denny Zhou, et al. Chain-of-thougl! prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824-24837, 2022. 10
[39] Luca Weihs, Matt Deitke, Aniruddha Kembhavi, and Roozbeh Mottaghi. Visual room rearrange- ment. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition.
pages 5922-5931, 2021. 3
[40] Yaqi Xie, Chen Yu, Tongyao Zhu, Jinbin Bai, Ze Gong, and Harold Soh. Translating natural language to planning goals with large-language models. arXiv preprint arKiv:2302.05 /28, 2023.
4
[41] Danfei Xu, Roberto Martín-Martin, De-An Huang, Yuke Zhu, Silvio Savarese, and Li F Fei-Fei. Regression planning networks. Advances in Neural Information Processing Systems, 32, 2019. 10
[42] Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas I. Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305. 10601, 2023. 10
[43] Shun Zhang, Zhenfang Chen, Yikang Shen, Mingyu Ding, Joshua B Tenenbaum, and Chuang Gan. Planning with large language models for code generation. arXiv preprint arXiv:2303.05510, 2023. 10
[44] Brianna Zitkovich, Tianhe Yu, Sichun Xu, Peng Xu, Ted Xiao, Fei Xia, Jialin Wu, Paul Wohlhart, Stefan Welker, Ayzaan Wahid, et al. Rt-2: lasion-language-aa models transfer web knowledge to robotic control. In 7th Annual Conference on Robot Learning, 2023. 1
13

---

Appendix
A Virtualhome experimental environments
We use the VirtualHome simulator [24] evaluate our approach as well as the baseline methods. VirtualHome is 3D household environment with partial observation, large action space, and a long planning horizon. contains hundreds of interactive objects and containers, allowing it to perform various household object rearrangement tasks. This section introduces details of the tasks, the goal specifications, the actions, and the observations our experimental settings.
A.1 List of objects, containers, surfaces, and rooms in the apartment
We list all the objects that are included in our experimental environment. Here, we can put moveable objects into the Containers or the Surfaces. The Containers and Surfaces are located at Room in the apartment.
Containers: bathroom cabinet, kitchen cabinet, bathroom counter, fridge. oven, dishwasher, microwave, stove. bathroom cabinet
Surfaces: bed, bookshelf, cabinet, coffee table, cutting board, floor, fryingpan, kitchen counter,
kitchen table, nightstand, sofa, stove
moveable objects: alcohol, apple, banana, bar soap, bell pepper, boardgame, book, box, bread slice, bucket, candle, candy bar, carrot, cellphone, cereal, chicken, Chinese food, chips, chocolate syrup, clock, clothes pants, clothes pile, clothes shirt, coatrack, coffeepot, condiment bottle, condiment shaker, cooking pot, crackers, crayons, creamy buns, cupcake, cutlery fork, cutlery knife, cutlets, cutting board, dish bowl, dishwashing liquid, face cream, folder, fryingpan, glasses, globe, hair product, hanger, juice, keyboard, lime, lotion bottle, magazine, milk, milkshake, minced meat, mouse, mug, notes, oven tray. pancake, paper, pear, pie, pillow, plate, plum, poundcake, pudding, radio, remote control, salad, salmon, slippers, sports ball, sundae, teddybear, toilet paper, toothbrush, toothpaste, towel, towel rack, toy, washing sponge, water glass, whipped cream, wine, wineglass Rooms: bedroom, bathroom, living room, kitchen.
A.2 Tasks
We the object rearrangement tasks for evaluation. The task is search for more objects in the house and move them to the desired positions. We use natural language as the interface to specify the tasks. Thus, the agent should take input the natural language instruction and observations, and then output actions.
The tasks are randomly sampled from different distributions. We define various types of object rearrangement tasks for evaluation:
Simple: this task is to move one object in the house to the desired location. The combination of the object and desired location has appeared in the training dataset.
Novel Simple: this task is to move one object in the house to the desired location. The combination of the object and desired location hasnot appeared the training dataset.
Comp.: this task is composed of 2 Simple tasks, moving more than one object in the house to their desired location. This kind of task has longer planning horizon as requires moving multiple objects to complete. The combinations of Simple tasks have appeared in the training dataset.
Novel Comp. (2): this task is composed of 2 Simple tasks, moving more than object in the house to their desired location. The combinations of Simple tasks have not appeared in the training dataset.
Novel Comp. (3): this task is composed of 3 Simple tasks, moving more than one object in the house their desired location. This kind of task has the longest planning horizon. The combinations of Simple tasks have not appeared in the training dataset.
We also have different houschold environments:
14

---

Seen Apartment: the map of the apartment is shown in Figure 3. These household environments are the same the ones in the training set, while the object positions are randomly initialized
according to a pre-defined commonsense distribution in VirtualHome [24].
Unseen Apartment: the map of the apartment is shown in Figure 4. These household environ- ments are not the same as the ones in the training set. The object positions are also sampled
from a different pre-defined commonsense distribution in VirtualHome [24].
a
(b)
Figure 3: The map of the seen apartments in our setting. These household environments are the same as the ones in the training set, while the object positions randomly initialized according to commonsense distribution.
(a)
(b)
Figure 4: The map of the unseen apartments in our setting. These household environments are not the same as the ones in the training set. The object positions are also sampled from a different commonsense distribution.
A.3 Goal specification
Similar to prior works [22], we define the goal in the VirtualHome system by a set of predicates. For instance, a goal can be defined by Insidetapple, fridge):2; Inside(plate, dishwasher):l, meaning "put two apples inside the fridge and put one plate inside the dishwasher." For Simple and Novel Simple tasks, only requires moving one object, while Comp. and Novel Comp. have more than one object to move.
A.4 Actions
In VirtualHome, the agent able to navigate the environment, grab an object, put an object inside the containers (e.g., fridge) the surfaces (c.g., table), open and close the container, etc. The
15

---

actions in VoreualHome are grounded to moveable objects, containers, or rooms in the environment. For example, Open(5) open an object with index (5). The list of available actions in our setting are listed below:
Walk (<item>>: walk to the <item>. The <item> can be moveable object, container, or a room. The precondition of this action is that the <item> is visible. The effect of this action is that the agent is close the <item> if the <item> an object inside the <item> if the <item> is a room. The action is translated into the sentence "walk to the <name of item>" when feeding into LLMs.
Open (<item>): : open the <item>. The <item> can be moveable object or container. The precondition of this action is that the agent should be close <item>. The effect of this action is that the <item> is opened. The action is translated into the sentence "open the <name
of item>" when feeding into L.M.s.
Close (<item>): close the <item>. The <item> can be a moveable object or container. The precondition of this action is that the agent should be close <item>. The effect of this action is that the <item> is closed. The action is translated into the sentence "close the <name of item>" when feeding into LLMs.
Grab (<itte>): grab the <item>. The <item> should be a moveable object. The precondi- tion of this action is that the agent should be close to the <item>, and the agent is not holding any objects. The effect of this action is that the agent will hold the <item>. The action is translated into the sentence "grab the <name of item>" when feeding into LLMs.
PutIn (aiinniittenn (<itemi>, <item2>): put the moveable object <item1> inside the container <item2>. The precondition of this action that the agent should be close to the <item2> and holding <item1>. The effect of this action is that the agent is not holding any objects, and the <item1> is inside the <item2>, The action is translated into the sentence "put the <name of item1> inside the <name of item2>" when feeding into LLMs.
PutBack (<itemi>, <item2>): put the moveable object <item1> on the surface <item2>, The precondition of this action is that the agent should be close the <item2> and holding <item1>. The effect of this action is that the agent is not holding any objects, and the <iteml> on the <item2>. The action is translated into the sentence "put the <name of item1> on the <name of item2>" when feeding into LLMs.
A.5 Observations
We use the same representation as [22] for partial observation. The observation is a list of visible objects and relationships between those objects. Each object or container has state: open close. The fine-tuned GPT2 policy [22] also uses the 3d coordinates of the object. We also use relationships to connect different objects, such Inside (apple, fridge). Those relationships are translated to natural language descriptions when feeding into LLMs, such as "an apple is inside the fridge."
B
Data gathering
Similar to prior works [25, 22], we collect expert trajectories in VirtualHome using regression planning with handcrafted heuristics The expert has full observation of the environment. Given the goal predicates and full observation. the agent will use the handcrafted heuristics for each task to effectively search for the solutions. The expert also has a handcrafted mechanism for compositional tasks to decompose one task into subtasks and finish them progressively. For each trajectory, we include the goal predicates (used by the VirtualHome system and the expert agent), the goal instruction (used by the agent), the partial observation for each time step (not used by the expert agent, the expert agent uses full observation), and the expert actions.
C Implementation details of belief in LLM-MCTS
This section introduces our implementation details for the belief of states in GPT3.5-MCTS. The source code will be released at httpp::///// hatp::::///mmmmmmaa/// git..bitttuuu.. io before the publication.
Theii implementation is available
and and_ha mnd_help..a git
16

---

C.1 State representation
We represent the states by a list of objects and their relationships. Each object has a unique name and id the simulator, as well as the state the object. We use the same unique name and id in our state representation. The relationships connect different objects, containers, surfaces, and rooms. The VirtualHome contains different types of relationships, including Inside, On, Close, Facing, etc. We use the same type of relationships in our state representation.
C.2 Belief
The belief of the state also contains a list of objects and their relationships. However, we parameterize the relationships by a vector, representing the probability that the relationship is true. This vector affiliated with the object representation. For simplicity, we only include the relationships Inside, On in our belief, as we only query LLM about the object positions to build up the commonsense belief of the state.
When building up state's belief, we query LLM predict the position of each moveable object, container, and surface. The position of a moveable object is specified by the relationships (i.e., Inside or On) between itself and a container or surface. The position of a container or a surface is specified by its relationship (i.e., Inside) to the room. We use sampling to approximate the distribution of the position. The moveable objects' belief of position represented by vector whose dimension is the same as the total number of containers and surfaces in the house. Each vector entry denotes the probability that whether the object is inside a specific container or on a specific surface is true. When asking LLM to predict the object positions, we asked LLM for M times and received multiple responses from LLM. We then count each entry's s total number of predictions and normalize them to become probability distribution. We initialize the value of other unsampled entries in the vector by a lower bound of the probability X 10 to ensure that the model will not eliminate other possibilities when the commonsense model is wrong.
The agent will receive new observations to update their belief when interacting with the environment. We will first predict the next state of the agent by the transition function and then update the belief of the object positions by new observations. Suppose the object is inside the current observation. that case, the other entry of the relations between objects will be masked out by zero, and the entry of the relationships in observation will be replaced by the value of one. However, if a relationship is not inside the observation, the value of the corresponding entry will be replaced by zero, and the vector will be normalized again.
D Visualized examples
We provide a set of successful (shown in Figure 5) and failed trajectories (shown in Figure 6) to give better understanding of the tasks and our method. Policy, model, and translation errors the primary causes of failures. Among these, policy errors are responsible for the majority of the failures. Often time, the policy produces unreasonable behaviors that mislead the search procedure. For example, it usually outputs inadmissible actions, such as "walk to the cutlery fork"" where the "cutlery fork" is not in the observation (shown in Figure 6 (a)). It also produces hack-and-forth behaviors, resulting in an unreasonable heuristic and slowing the search procedure. For example, when putting objects inside the microwave, it sometimes struck by repeatedly opening and closing the microwave. For model error, the predicted positions of objects are not always correct. Since a random rollout policy is employed, incorrect object states can result in higher Q-values than correct states, leading to misguided exploration (shown in Figure 6 (b)). The wrong translation also compromises the performance as we translate the response from LLM to admissible action or object names to ensure executability. This is caused in part by the VirtualHome environments, as the policy might not understand the underlying logic of the actions in VirtualHome, such as you have to walk close to interact with the object. Thus, if the LLM outputs "open fridge" but is not close enough to the fridge, the action will translated to other admissible actions ("open fridge" is not inside the admissible actions for this case as it is invalid due to the setting of VirtualHome).
17

---

Instruction: Put one plate inside the kitchen cabinet and one chicken inside microwave.
1: Walk to kitchen
Walk to plate
3: Grab plate
10
4: Walk to kitchen cabinet
5: Open kitchen cabinet
Put plate inside kitchen cabinet
Move fridge
8: Open fridge
9: Grab chicken
10: Walk microwave
Open microwave
Put chicken inside microwave
Instruction: Put one apple on the
kitchen table and one toothbrush inside the bathroom cabinet.
20
1: Walk to fridge
Open fridge
3: Walk to apple
4: Grab apple
5: Walk to kitchen table
Put apple kitchen table
Walk to bathroom
8: Walk to toothbrush
9: Grab toothbrush
10: Open bathroom cabinet
Put toothbrush inside bathroom cabinet
18
Walk to kitchen table
8: Put cutlery fork on kitchen table
9: Walk to apple
10: Grab apple
Instruction: Put cutlery fork the kitchen table and one apple the fridge one chips to the coffee table.
11: Walk fridge
Open fridge
13: Put apple inside fridge
14: Close fridge
1
I: Walk to kitchen
15: Walk to kitchen cabinet
2: Walk kitchen cabinet
16: Open kitchen cabinet (Failed)
Open kitchen cabinet
Grab chips
4: Walk to dishwasher
18: Walk living room
5: Open dishwasher
19: Walk to coffee table
6: Grab cutlery fork
20: Put chips coffee table
Figure 5: Successful examples
18

---

(a)
Instruction: Put one cutlery fork
the coffee table
1: Walk to kitchen
2: Walk to cutlery knife
3: Walk to cutlery knife
4: Walk to cutlery knife
(b)
Instruction: Put one apple inside the
fridge
1: Walk to living room
2: Walk to coffee table
3: Walk to bedroom
4: Walk to nightstand
5: Walk to kitchen
6: Walk to kitchen cabinet
7: Open kitchen cabinet
Figure 6: Failed examples. (a) Policy and translation error. LLM outputs walk to the cutlery fork, but the cutlery fork is not in observation. We use embeddings to evaluate the most similar valid actions. Therefore it translates the action to similar action "walk to cutlery knife." The action has an incorrect semantic meaning and causes failure. (b) model error. The LLM predicts the apple is on the nightstand in the bedroom and the coffee table in the living room. As rollout to get the estimation the reward, there will be situations when the incorrect actions result in higher estimated Q value, thereby misleading the exploration.
using random
19

---

Table 3: Runtime performance (second + standard error)
GPT3.5-MCTS
GPT3.5 Policy
UCT
GPT2 Policy
Runtime 67.83 = 18.92
1.19 + 0.81
120.0 + 0.0
0.33 + 0.07
E
Runtime performance
The runtime performance to make one-step decisions for simple rejeat-rarranggmment tasks is reported Fig E. The experimental setup the same as our main experiments VirtualHome. The simple tasks are the tasks that only require the rearrangement of one item generated from the same distribution as the training dataset. We used 100 times simulation during the tree search for GPT3.5-MCTS in our experiments. For UCT, we bound the runtime by 120 seconds. The details of our hardware for experiments are enclosed below:
CPU: Intel(R) Xeon(R) Gold 6240 CPU @ 2.60GHz (72 cores)
NVIDIA GeForce RTX 2080 Ti
F
Prompts
One example prompt for the LLM policy and the exact prompt we used for building up the common- sense belief shown below.
Listing I: Example prompt for the heuristic policy
You need to generata high-level for completing household task using the alloved actions and visible objects.
Allozed actiona: walk to <object>, salk <rean>, walk <container>, valk <surface>, grab <object>, open <container>, close <container>, put <object> on <aurface>, put <object> inside <container>. house: bedroom, bathrocm, living room, You need to strictly follow the format in the following examples:
one apple inside fridge
Completed actions: valk the kitchen, salk the apple
Current Observation: a kitchen table is inside the kitchen, a kitchen counter is inside the kitchen, an kitchen counter, plate
apple
the kitchen table, a. fridge is inside the kitchen and fridge is closed, a kitchen cabinet is inside the kitchea and closed, cutlery knife on and microwave is closed, dishvasher is inside the kitchen and dishuusher is closed.
kitchen
kitchen
table, nicrovave inside
Next actions: grab the appla, salk the fridge, open the fridge, put the appla inside tridge, closs the fridge, done.
Now, finish the next following task.
11 Goal: Put one apple on the kitchen table
Completed actions:
13 Current observation: kitchen table is inside the kitchen, apple is on the kitchen table, kitchen
counter inaide the kitchen, an apple is the kitchen counter, cutlery knife on the kitchen counter, fridge inside the kitchen and fridge is closed, kitchen cabinet is inside the kitchen and kitchen cabinet is clased, a kitchen table inside the kitchen, plate is on the kitchen table, a pounding
on kitchen table, nicrovave inside kitchen microwave is closed, a dishvasher is inside the kitchen and dishvather is closed.
actions:
Listing Example prompt for the commonsense world model
You need to predict the positions of the noveable objects, contsinere, and surfaces in the spartment comousense.
according
Bocas in the apartment: bedroon, bathroon, living roon, kitchen.
Containers in the apartment: bathroom cabinet, kitchen cabinet, bathroon counter, fridge, oven, dishvasher, microvave, stove, bathroon cabinet.
Surfaces the apartment: bed, bookshelf, cabinet, coffee table, cutting board, floor, fryingpan, kitchen counter, kitchen table. nightetand, sofa, stove.
You need to strictly follor the format in the folloving examples: the poseible positione strawberry? Answer: Inside fridge, Ou kitchen table.
Question:
the possible positions seap?
Ansver: On bathroon counter.
10 Question: what are the possible positions of water cup?
11 Answer: Cn kitchen table, Inside dishvacher.
12 Now, ansxer the next following question.
Queetion:
the poseible positione apple?
20

---

Answer:
Listing 3: Example prompt for the natural language instruction interpretation
You need interpret the natural language goal into formal geal representation
For axample,
Goal: put 1 toothbrush inside the bathromccabinet.
geal: (INSIDE, toothbrush, bathrosscabimet,
Goal: put 1 toothbrush inside the bathrommcabinet, put 1 apple on the kitchentable.
goal: (INSIDE, toothbrush, bathroomcabinat, 1)- (0N, apple, kitchentable,
Goal: put 1 toothbrush inside the bathroomcabinet, the fridge.
apple the kitchentable, chicken inside
Formal goal: (INSIDE, toothbrush, bathroomcabinet, (0,, apple, kitchentable, 1)-(INSIDE, chicken, Iridge, 1)
interpret folloving goals:
21


Reviews:
[{"review_id": "5VbXSi0go9", "reviewer": "Reviewer_3x3m", "summary": "This paper introduces a technique to incorporate large language models' commonsense knowledge into Monte Carlo Tree Search to guide planning. It uses LLMs to obtain probabilities over the initial belief of the state, and as a heuristic policy to guide simulation. Evaluation on household object rearrangement tasks in VirtualHomes demonstrates that the method is empirically more effective than search algorithms that don’t incorporate LLMs (UCT), or just having LLMs generate a policy through direct prompting (GPT3.5 Policy). The paper also makes a theoretical argument in favor of using model-based methods rather than model-free methods with LLMs.", "questions": "1. Instead of performing similarity search, can you just constrain generation and/or prompt the model explicitly to choose amongst a limited set of available actions/object? This may help avoid translation errors.\n2. Can you clarify the connection between LLM knowledge and description lengths?", "limitations": "Some limitations were mentioned in conclusion, though there is no explicit limitations section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Novel approach to planning with LLMs that doesn’t just entail having the LLM directly generate a policy, but as part of a search algorithm \n2. Technique significantly outperforms both vanilla search algorithms and using LLMs directly to generate policies on household object rearrangement tasks\n3. Ablation study and analysis give good insight into what helps, and where there is still room for improvement\n", "weaknesses": "1. The paper evaluated this technique in only occurred in one domain -- VirtualHome -- and it is unclear whether it can generalize to other embodied domains.\n2. The main barrier to using this approach in practice is that it entails making multiple calls to GPT3.5 when computing each action, alongside having to do additional search on top -- making it less efficient than both vanilla search and vanilla LLM generation methods. Though computational expense was noted as a limitation in the conclusion, it may also be valuable to additionally report runtimes in the paper\n3. The theoretical arguments for “knowledge of LLMs regarding states of world is more complete than their knowledge of policies for accomplishing daily tasks” (L58-59, Section 5.3), whereby description length of policies vs. world models is used to justify this claim, is not entirely convincing to me. First, it is unclear whether the argument the authors put forth that “learning about the world would likely require less training data than learning policies to do all tasks in the domain” (L62) applies to LLMs, which have been trained on an abundance of data and are not at all limited by data scarcity. This argument also makes assumptions about the way LLMs represent policies vs. models which seem not at all obvious to me — why is description length the best way to characterize LLM knowledge? LLMs are not trained to be efficient compressors, they are trained to imitate the training set.\n    * Is there a way to empirically validate this claim in particular?\n\n---\nMissing citations:\n-  https://aclanthology.org/2022.acl-long.120/", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThank you very much for your valuable feedback. We are grateful for the many suggestions for improvement, which we will incorporate in the revised manuscript. We would like to further clarify the questions and concerns you raised.\n\nQ1: \n> The paper evaluated this technique in only occurred in one domain -- VirtualHome -- and it is unclear whether it can generalize to other embodied domains.\n\nA1: We chose VirtualHome, as it is an established domain well used in prior work [1-3]. Our method is domain-agnostic and should be able to generalize to other common household domains, as LLMs have vast general knowledge that should be widely applicable [4-6]. We will explore those distinct datasets for further evaluation.\n\nQ2: \n> The main barrier to using this approach in practice is that it entails making multiple calls to GPT3.5 when computing each action, alongside having to do additional search on top -- making it less efficient than both vanilla search and vanilla LLM generation methods.\n\nA2: There is a trade-off between accuracy and computational efficiency. While our method requires multiple LLM calls, it provides substantially improved results (Table 1). One objective of our study is to identify this possibility and highlight the trade-off. There are also various ways to enhance runtime performance, such as using a smaller LLM like Llama or distilling domain knowledge into a smaller model [7-9]. We are keen to explore these avenues in future research.\n\nQ3: \n> it may also be valuable to additionally report runtimes in the paper\n\nA3: The actual runtime to finish MCTS and make one decision depends on the number of simulations and internet connection latency. We used 100 times simulation during the tree search for GPT3.5-MCTS in our experiments, and it takes 1 to 2 minutes on average to make one decision. We will report the details in the paper and appendix in the final version.\n\nQ4: \n> Can you just constrain generation and/or prompt the model explicitly to choose amongst a limited set of available actions/object? This may help avoid translation errors.\n\nA4: We have tried various methods to restrict the action generation. We have put the list of pre-defined actions and observed object list in the prompt. However, there are still remaining errors in LLM’s policy, such as opening the fridge when it is still far away. This is likely because the LLM cannot guarantee the effective use of all the information and preconditions in the prompt when making decisions. \n\nQ5: \n> Can you clarify the connection between LLM knowledge and description lengths?\n\nA5: The assumption that LLM's training data is unlimited and can cover all domains and tasks is something we respectfully disagree with. While LLM is trained on vast datasets encompassing many disciplines, it's not guaranteed to cover all situations in all possible tasks. An extreme but representative example is large-number multiplication. If we wish to learn the policy, we need to have a dataset that covers all possible multiplications of two numbers and remember the results. It is impossible to have such a dataset as there are an infinite number of cases. On the other hand, describing a world model (0-9 digits and multiplication rule) is much simpler. Therefore, LLM does have data scarcity issues for learning the policy of some tasks.  \n\nThe description length, reflecting the space complexity to represent full knowledge, determines the data needed to cover situations in a task or domain. It is often used in learning theory to analyze sample complexity, e.g., see Chapter 2 of Kearns and Vazirani (link: https://www.cis.upenn.edu/~mkearns/teaching/CIS625/KearnsVaziraniChapter2.pdf). Our analysis in the paper shows that the world model may require far less training data to learn than the policy in some situations, and our experiments show that this may happen in common household tasks. LLM essentially imitates the dataset. Thus, when the data is limited, the LLM’s knowledge of the world model is likely more complete than the policy. \n\n[1] I. Singh et al., “ProgPrompt: Generating Situated Robot Task Plans using Large Language Models”, ICRA 2023.\n\n[2] S. Li et al., “Pre-trained language models for interactive decision-making,” Neurips 2022. \n\n[3] Huang et al. Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents, ICML 2022.\n\n[4] T. Silver et al. Generalized Planning in PDDL Domains with Pretrained Large Language Models. 2023.\n\n[5] B. Liu et al. \"Llm+ p: Empowering large language models with optimal planning proficiency.\" 2023.\n\n[6] S. Bubeck et al. \"Sparks of artificial general intelligence: Early experiments with gpt-4.\" 2023.\n\n[7] C.-Y. Hsieh et al. \"Distilling step-by-step! outperforming larger language models with less training data and smaller model sizes.\" 2023.\n\n[8] C. Liang et al. \"Less is more: Task-aware layer-wise distillation for language model compression.\" ICML 2023.\n\n[9] K. Shridhar et al. \"Distilling reasoning capabilities into smaller language models.\" ACL 2023."}, {"review_id": "SMj432R3xR", "reviewer": "Reviewer_jShB", "summary": "This work demonstrates that LLMs can be used as the commonsense models of the world and serve as the heuristic policy in search algorithms. Specifically this paper uses Monte Carlo Tree search to explore word states sampled from the output of LLMs and commonsense policy from LLMs can effectively guide the search, which reduces the search complexity. Experimental results on daily planning tasks again verify the advantages over using LLMs solely as policies. \n", "questions": "(a) Just curious about why the baseline of UCT achieves zero success rate in Table 1 and can you explain more about this? Due to huge search space, UCT might fail to solve in a given time limit. But are there any improved search methods that can achieve better success rates, i.e., stronger baselines? \n", "limitations": "n.a.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "a). Novel idea by incorporating commonsense knowledge from LLMs into search algorithms instead of LLMs solely as policies. This work also points out that doing the search with the help of LLMs as a model may be better and more efficient than using LLMs directly as a policy. \n\nb). Comprehensive evaluation of the proposed methods including simple tasks, compositional tasks or in-distribution, out-of-distribution tasks. \n\nc). Good insights that improvements might come from the MCTS’s look-ahead search and more explorations of other possible search directions. Overall this work might motivate more research utilizing LLM’s world knowledge for decision-making problems.\n", "weaknesses": "a). This work argues that planning policy may suffer from hallucination issues of LLMs in the related work. However this work did not justify how their proposed methods can help relieve the issues. It can add some context to discuss this. \n\nb). As discussed in the paper, the proposed method might face the efficiency problem.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable feedback. We will carefully revise our paper to incorporate your suggestions. The following are our responses to your questions. \n\nQ1: \n> This work argues that planning policy may suffer from hallucination issues of LLMs in the related work. However this work did not justify how their proposed methods can help relieve the issues. It can add some context to discuss this.\n\nA1:  We leverage MCTS for model-based reasoning, thus basing decisions on LLMs' world model knowledge rather than being fully dependent on the policy. Assuming that the world model is correct, MCTS then deduces the decision through search. In this sense, our approach improves decision-making over incorrect predictions that are similar to hallucinations. \n\nThe world model of LLM could also suffer from hallucination, but is updated with observations as the agent takes action in the real world, making it more accurate over time. In addition, MCTS looks ahead multiple steps, allowing it to correct some of the hallucinations in the set of actions proposed by the LLM during the search process. \n\nWe will revise the manuscript and add this discussion. \n\nQ2: \n> As discussed in the paper, the proposed method might face the efficiency problem.\n\nA2: Our study shows the trade-off between accuracy and efficiency and explores the feasibility of our approach. See the full answer in the **runtime performance** of our global responses.\n\nQ3: \n> Just curious about why the baseline of UCT achieves zero success rate in Table 1 and can you explain more about this? Due to the huge search space, UCT might fail to solve in a given time limit. But are there any improved search methods that can achieve better success rates, i.e., stronger baselines?\n\nA3: This intractability stems from the large state and action spaces coupled with sparse rewards. These factors result in a wide and deep search tree, with the size growing exponentially and leading to intractable planning. Even though MCTS [4] is among the top online planners in POMDP, it suffers from these complexities, much like other SOTA model-based methods such as DESPOT [5], which we also tried. Due to time constraints, we are unable to include all methods in our formal experiments. \n\n[1] C.-Y. Hsieh et al. \"Distilling step-by-step! outperforming larger language models with less training data and smaller model sizes.\" 2023.\n\n[2] C. Liang et al. \"Less is more: Task-aware layer-wise distillation for language model compression.\" ICML 2023.\n\n[3] K. Shridhar et al. \"Distilling reasoning capabilities into smaller language models.\" ACL 2023.\n\n[4] D. Silver et al. \"Monte-Carlo planning in large POMDPs.\" NeurIPS, 2010. Link: https://proceedings.neurips.cc/paper_files/paper/2010/file/edfbe1afcf9246bb0d40eb4d8027d90f-Paper.pdf \n\n[5] S. Adhiraj et al. \"DESPOT: Online POMDP planning with regularization.\" NeurIPS, 2013. Link: https://proceedings.neurips.cc/paper/2013/file/c2aee86157b4a40b78132f1e71a9e6f1-Paper.pdf "}, {"review_id": "JRwjbjuSiY", "reviewer": "Reviewer_RKS5", "summary": "The paper introduces a new methodology _Monte Carlo planning with common sense knowledge_. The idea is to rely on LLMs to integrate common background knowledge into Monte Carlo Tree Search algorithm with application to language-instructed object rearrangement tasks. \n\nAssuming access to a dataset of expert actions and observations, a list of all objects, containers and surfaces appearing in the dataset are retrieved. Similar to [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf) an LLM is used to approximate the belief of the state, containing the list of objects and their relationship. For instance, the fridge is likely to be in the kitchen. \n\nTo derive a policy, an LLM is also used, building on the work of [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf). Relying on PUCT, the model takes as input the examples in the dataset, the goal description, the current observations and the history of actions and outputs the list of next actions to take. \n\nThe method developed is evaluated on the Virtual Home, where the task is to rearrange objects in different apartments. The complexity of the task depends on the novelty of the apartment and the object considered (could be observed or not in the training data). The benchmark includes four methodologies, UCT, two baselines based on [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf) and the proposed methodology. The results demonstrate the improvement induced by _Monte Carlo planning with commonsense knowledge_ independently of the complexity of the task. An ablation study demonstrates the improvement induced by the initial approximation of the belief of the state. Finally an analysis of failures is conducted and demonstrates that most of them are linked to inadmissible actions outputted by the LLMs and back-and-forth behavior.", "questions": "The parameters $c_{puct}$ and $c_{uct}$ can have a huge impact on the performance of the algorithm. How did you select the parameters?\n\nPUCT can struggle with large state spaces, did it motivate the choice to keep only 2 types of relationship instead of 59 proposed in the task. Getting insights on the potential drop in performance induced by an increase in the size of the state space would be interesting.\n\n200 expert trajectories are used in the training set. Having an idea of the impact of the number of trajectories on the performance of the methodology could be of great interest.", "limitations": "The two main limitations of the methodology are the non admissible outputs produced by the model and the back and forth behavior. The two were acknowledged by the authors.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The work builds on [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf), relying on an LLM to approximate the belief of the state and to derive a policy. The novelty is to rely on MCTS and PUCT to derive the policy instead of DT. The approach is evaluated on a broader task than [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf), including compositional task that are supposed to be more complex than simple task to solve.\n\nFinally, the ablation study provides insights on the added value of each block of the proposed methodology.", "weaknesses": "The paper mostly relies on experiments and ideas from [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf) and would gain clarity if clearly stated. For instance, the use of LLMs to initialize the belief state was already used in [S.Li 2022](https://arxiv.org/pdf/2202.01771.pdf). \n\nAdditionally, the code is not public and the implementation of LLM_MCTS is not super clear form pseudo code available in _Algorithm 1_. The paper would gain clarity by making the code public or available in supplementary materials.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate your effort in reviewing our paper and providing feedback. Please see our responses below. \n\nQ1: \n> The paper mostly relies on experiments and ideas from S.Li 2022. and would gain clarity if clearly stated. For instance, using LLMs to initialize the belief state was already used in S.Li 2022.\n\nA1: We believe that the reviewer may have missed out on our paper's main contribution and misunderstood the method of Li et al. [2]:\n* While our research mainly contributes to using GPT-3.5 as a commonsense world model for **model-based search** with MCTS, Li et al. [2] use behavior cloning to finetune GPT-2 as a **model-free policy**. There are fundamental differences between the model-based and the model-free approaches, conceptually and algorithmically. In particular, the power of the model-based approach lies in its ability to compose elementary pieces of (commonsense) world knowledge through a reasoning/planning procedure (MCTS, in our case) and achieve compositional generalization. This is often one key weakness of the model-free approach. \n* Li et al.'s approach [2], by its nature, would not employ belief states in planning, contradicting RKS5's assertion. \n* Li et al. [2] only mentioned belief states in expert data collection (Appendix E.1.). It clearly states that they use the code of [1] for implementation, in which the belief of the initial state is a uniform distribution rather than initialized by LLM. \n\nWe hope that our response can clarify the misunderstanding. \n\nQ2:\n> To derive a policy, an LLM is also used, building on the work of S.Li 2022.\n\nA2: Our heuristic policy uses LLM but is not built on Li et al. [2] as we do not finetune the LLM using behavior cloning. \n\nQ3: \n> The benchmark includes…, two baselines based on S.Li 2022 ...\n\nA3: We only use one baseline from Li et al [2], i.e., finetuned GPT-2 policy using behavior cloning. Other baselines are UCT and the few-shot GPT3.5 policy adapted from [3]. Please take a look at [3], as it is substantially different from [2] as it does not fine-tune the LLM, but uses prompts to conduct few-shot/zero-shot planning. \n\nQ4: \n> Additionally, the code is not public and the implementation of LLM_MCTS is not super clear form pseudo code available in Algorithm 1. The paper would gain clarity by making the code public or available in supplementary materials.\n\nA4: We intend to make the code publicly available for the camera-ready version of the paper. In the meantime, we provide some implementation details here. Our dataset generation is adapted from the code in the paper [1]. The fine-tuned GPT2 and few-shot GPT3.5 policies are from [2] and [3]. Our UCT and LLM-MCTS implementations are adapted from [4].\n\nQ5: \n> The parameters $c_{puct}$ and $c_{uct}$ can have a huge impact on the performance of the algorithm. How did you select the parameters?\n\nA5: We do limited tuning of the parameters within a range, initially testing UCT and LLM-MCTS in a small domain to verify correctness. After efficiently solving the problem in this small domain, we applied the method to a larger domain, increasing and continually tuning parameters to balance the exploration and exploitation. Lack of access to OpenAI GPT-3.5 and time constraints hindered more advanced tuning methods like Bayesian Optimization, leaving potential room for performance improvement.\n\nQ6: \n> PUCT can struggle with large state spaces, did it motivate the choice to keep only 2 types of relationship instead of 59 proposed in the task. Getting insights on the potential drop in performance induced by an increase in the size of the state space would be interesting.\n\nA6: The larger belief space could compromise the performance. Thus, we didn’t consider all 59 relationships in belief initialization and made a trade-off between efficiency and accuracy. Investigating the potential drop in performance as more relationships are used would be interesting. \n\nQ7: \n> 200 expert trajectories are used in the training set. Having an idea of the impact of the number of trajectories on the performance of the methodology could be of great interest.\n\nA7: This will certainly affect the results. However, 200 expert trajectories, compared to Li et al. [2], are already significantly smaller. And our performance is considerably better. We are happy to conduct additional experiments in the revisions to enrich our conclusions. \n\nQ8: \n> The two main limitations of the methodology are the non admissible outputs produced by the model and the back and forth behavior. The two were acknowledged by the authors.\n\nA8: We clarify that these are two cases of actions generated by the heuristic policy, which is caused by LLM policy errors that are similar to hallucinations. We admit that it affects the performance of the MCTS, but it is not LLM-MCTS that generates back-and-forth behaviors and non-admissible outputs. We will revise this part of the paper to make it clear.\n\nOur contribution is to improve decision-making. We leverage MCTS to base decisions on LLMs' world model knowledge rather than fully rely on the LLM policy. The world model of LLM could also be incorrect but is updated with observations as the agent takes action in the real world, making it more accurate over time. In addition, MCTS looks ahead multiple steps, allowing it to correct some of the errors in the set of actions proposed by the LLM during the search process. This is the reason why we outperform the GPT3.5 policy. \n\n[1] X. Puig et al, “Watch-and-help: A challenge for social perception and human-ai collaboration,” ICLR 2021.\n\n[2] S. Li et al., “Pre-trained language models for interactive decision-making,” Neurips 2022. \n\n[3] W. Huang et al. \"Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.\" ICML 2022.\n\n[4] Jang, Youngsoo, et al. \"Monte-carlo planning and learning with language action value estimates.\" ICLR. 2020."}, {"review_id": "NXQuUAzVZT", "reviewer": "Reviewer_Mf2f", "summary": "This paper proposed to leverage LLMs both as a (commonsense) world model and heuristic policy within the MCTS search algorithm to tackle household planning tasks namely object rearrangements. The main idea is that for each simulation phase in MCTS, the algorithm sample from LLM to obtain the initial belief of states (of objects) and then use the LLM as a heuristic policy to guide action selection and finding promising trajectories. \n[Some details of when and how often the LLM is used as a world model is missing from the main paper (see questions)]\n\nThe paper evaluated their approach using a subset of VirtualHome tasks– object rearrangement. They tested models on simple and compositional (rearranging multiple objects) tasks, as well as in-distribution and out-of-distribution settings. They use the `success rate’ of completing the tasks within 30 steps as evaluation metrics for comparison. They demonstrate significant improvements over baselines including a variant of the MCTS wo/ commonsense world model, a supervised GPT-2 model, and using GPT-3.5 only as the action policy. The improvements are larger for compositional and OOD setups where their method benefits from the MCTSC’s lookahead and LLM’s commonsense knowledge of the world. \n", "questions": "1– From my understanding the LLM is only used once (per simulation) to get the initial state of the objects. How do you use that to estimate the value of selected actions (line 175)? Do you get different world states for different simulation iterations? is the commonsense model used at any other stage in the MCTS search algo? I think a more organized description of the process with a running example would be helpful.\n\n\n2- During MCTS, to sample state from the belief, do you sample the position of all available objects or task-related objects?\n\n3- Some notations are undefined in Algorithm 1: d, tau, d’, …\n\n4- Why did the author limit themselves to only object rearrangement tasks with only a few object relationships (on, inside)? Did the author explore their method on other household or planning tasks?\n\n5- For compositional tasks, are models provided with 1 few-shot compositional example or a simple example?\n\n6- Line 291: how is the ground-truth reward function obtained? It's unclear how the ground-truth reward function is different from the one used in the proposed final model\n\n7- An interesting observation is that sometimes GPT3.5 and MCTS outperform in the unseen apartment setup compared to the seen one (on some tasks). Do authors have any insight/speculation on this?\n", "limitations": "Yes, briefly in conclusion.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Interesting/timely approach to leveraging LLM both as a world model and policy within the MCTS framework for the important task of planning\n- Significant improvements over baselines\n- Thorough and insightful ablation study to analyze the functioning of different components\n", "weaknesses": "- The paper only tested on object rearrangement task with limited object relationships (on, inside). More complex and realistic tasks are left unexplored.\n- The paper benefits from the rewriting of Sec 4.2 to add technical details. At its current state, it’s unclear how often the LLM is used as a world model (see questions).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable feedback. We will carefully consider and incorporate your comments and suggestions into our manuscript. The reply to the questions is enclosed below. \n\nQ1: \n> The paper only tested on object rearrangement tasks with limited object relationships (on, inside). More complex and realistic tasks are left unexplored.\n\nA1: While our experiments focus on object rearrangement, we believe that it is appropriate as object rearrangement is a representative embodied AI task [1-7] with practical implications in everyday life, such as setting the table, tidying up the room, loading the dishwasher, and more. Thus, we believe that object rearrangement experiments reasonably support our claims in the paper. \n\nObject relationships (on, inside) are only used to initialize the belief of the world. Using an imperfect but reasonable world model and object positioning is a trade-off between efficiency and accuracy. As the agent navigates and receives new observations, its beliefs of states and relationships of objects will be updated.\n\nQ2: \n> The paper benefits from the rewriting of Sec 4.2 to add technical details. At its current state, it’s unclear how often the LLM is used as a world model (see questions).\n\nA2: We will revise Sec 4.2 according to your questions. Please see our responses below. \n\nQ3: \n> How do you use that to estimate the value of selected actions (line 175)? Do you get different world states for different simulation iterations? \n\nA3: In MCTS, we sample a world for each simulation, and the sampled world could be different for each simulation. In one simulation, the agent selects actions and sample observations according to the world in the root until it reaches the leaf node of the tree for expansion and rollout. It results in a trajectory of the tree with a reward. The root will sample a different world in different simulations, resulting in different trajectories in the same tree. We back up all the rewards from all the obtained trajectories to get the approximated Q-function at the root (Alg1, line 34 recursively updates to the root). The original paper on MCTS for the POMDP [11] may provide additional understanding. \n\n> is the commonsense model used at any other stage in the MCTS search algo?\n\nThe LLM is used not only in sampling possible worlds but also as a search heuristic (in Alg1, line 29, LLM is used as heuristic policy: $\\hat{\\pi}(a|h)$).  \n\nQ4: \n> do you sample the position of all available objects or task-related objects?\n\nA4: We sample all available objects of the world. \n\nQ5: \n> Some notations are undefined in Algorithm 1: d, tau, d’, …\n\nA5: $d$ and $d’$ is the current depth of the tree, and $\\mathcal{T}$ denotes the current tree. We will explain the notations in future revisions.  \n\nQ6: \n> Why did the author limit themselves to only object rearrangement tasks with only a few object relationships (on, inside)? Did the author explore their method on other household or planning tasks?\n\nA6: See our response A1. \n\nQ7: \n> For compositional tasks, are models provided with 1 few-shot compositional example or a simple example?\n\nA7: The semantic similarity determines the selection of examples. If the cosine similarity between the embeddings of current instruction and instruction in the dataset is higher than the others, the instruction in the dataset and its corresponding trajectory are then selected as the example. The dataset contains examples of compositional tasks; thus, the compositional example will likely be selected if the current task is compositional.  \n\nQ8: \n> Line 291: how is the ground-truth reward function obtained? It's unclear how the ground-truth reward function is different from the one used in the proposed final model\n\nA8: We assume that the baseline UCT method has the ground-truth reward function. Otherwise, it will not be able to plan. For each task, we have the ground-truth goal, which we use to determine the reward in the UCT baseline. The proposed method uses LLM to interpret the natural language instructions into the goal state, and the goal state determines the reward function, i.e., there will be a positive reward if the goal is achieved. \n\nQ9: \n> An interesting observation is that sometimes GPT3.5 and MCTS outperform in the unseen apartment setup compared to the seen one (on some tasks). Do authors have any insight/speculation on this?\n\nA9: Some unseen domains are not as large as the example domains. There might be some variance due to the uncertainty of sampling in both the GPT3.5 and MCTS. Occasionally, it has a higher success rate when the actual performance difference is small. \n\n[1] B. Dhruv et al., “Rearrangement: A Challenge for Embodied AI.” 2020.\n\n[2] L. Weihs et al. \"Visual room rearrangement.\" CVPR 2021.\n\n[3] A. Szot et al. \"Habitat 2.0: Training home assistants to rearrange their habitat.\" NeurIPS 2021.\n\n[4] Y. Kant et al. \"Housekeep: Tidying virtual households using commonsense reasoning.\" ECCV 2022.\n\n[5] A. Khandelwal et al. \"Simple but effective: Clip embeddings for embodied ai.\" CVPR 2022.\n\n[6] E. Huang et al.,  \"Large-scale multi-object rearrangement.\" ICRA 2019.\n\n[7] A. Krontiris et al. \"Dealing with Difficult Instances of Object Rearrangement.\" RSS 2015.\n\n[8] S. Bubeck et al. \"Sparks of artificial general intelligence: Early experiments with gpt-4.\" 2023.\n\n[9] T. Silver et al. Generalized Planning in PDDL Domains with Pretrained Large Language Models. 2023.\n\n[10] B. Liu et al. Llm+ p: Empowering large language models with optimal planning proficiency. 2023.\n\n[11] D. Silver et al. Monte-Carlo planning in large POMDPs. NeurIPS, 2010.\n\n[12] I. Singh et al. ProgPrompt: Generating Situated Robot Task Plans using Large Language Models. ICRA 2023.\n\n[13] S. Li et al. Pre-trained language models for interactive decision-making. Neurips 2022. \n\n[14] W. Huang et al. Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents, ICML 2022."}, {"review_id": "j0JdSleBBK", "reviewer": "Reviewer_euNw", "summary": "The paper proposes to use large language models (LLMs) as a world model instead of a policy for task planning. Specifically, the LLM is used to approximate the state of the world and acts as a heuristic policy in Monte-Carlo Tree Search (MCTS). Experimental results demonstrate the effectiveness of the method, outperforming a finetuned small model and a LLM policy.", "questions": "LLM-MCTS retrieves in-context examplars from a dataset. Does the baseline model also do this?", "limitations": "Seems that I don't see a limitation section in the paper? Also, broader societal impacts are not included, which should typically be consider for a generation model like large language models. Please refer to weakness section for improvement.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper innovatively proposes to use language model as world model instead of policy model for task planning. The idea is quite interesting and the motivation is convincing, i.e., this can lower the complexity of the problem and better utilize the encoded commonsense knowledge in language models.\n2. The experimental results demonstrates the effectiveness of the proposed method.", "weaknesses": "1. It is better to include more baselines that employ special design for task planning, e.g., SayCan [1], Zero-Shot Planner [2], etc.\n2. Only simple settings are considered in this work, i.e., object re-arranging task in a household environment. I would be interested in seeing if the method will still work when applied to more complex environments, which contain more diverse objects making it harder to predict world state.\n\n\n\n[1] Ahn et al. Do As I Can, Not As I Say: Grounding Language in Robotic Affordances\n[2] Huang et al. Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your valuable feedback. We will improve and revise the paper according to your suggestions. Our reply to your question is enclosed below.\n\nQ1: \n> It is better to include more baselines that employ special design for task planning, e.g., SayCan [1], Zero-Shot Planner [2], etc.\n\nA1: The key idea of SayCan is to learn physical-level affordance from raw observation when executing physical actions. In high-level task planning, the affordance is determined by the precondition of the pre-defined actions. We are keen to compare with SayCan when combining our method with physical-level action policy. Our GPT-3.5 policy baseline is essentially [2] with a one-shot example prompt and observation feedback, as we want to provide the same information for a fair comparison. \n\nQ2: \n> Only simple settings are considered in this work, i.e., object re-arranging task in a household environment. I would be interested in seeing if the method will still work when applied to more complex environments, which contain more diverse objects making it harder to predict world state.\n\nA2: Object rearrangement is a representative embodied AI task [3-9] with many practical implications in everyday life, such as setting the table, tidying up the room, loading the dishwasher, and more. Thus, object rearrangement experiments are an interesting setting to investigate a fairly large set of planning capabilities required in embodied AI. We chose VirtualHome, as it is an established domain well used in prior work [2,13,14]. Our method is domain-agnostic and should be able to generalize to other common household domains, as LLMs have vast general knowledge that should be widely applicable [10-12]. We will explore those distinct datasets for further evaluation.\n\nQ3: \n> LLM-MCTS retrieves in-context exemplars from a dataset. Does the baseline model also do this?\n\nA3: Yes, the baseline GPT-3.5 policy has the same mechanism as the heuristic policy in GPT3.5-MCTS. GPT2 policy, however, is fine-tuned by the entire training dataset using behavior cloning. \n\nQ4: \n> Seems that I don't see a limitation section in the paper? Also, broader societal impacts are not included, which should typically be consider for a generation model like large language models.\n\nA4: Due to the page limit, we briefly introduce the limitation in the failure analysis and conclusion. We will consider the potential broader impact and add it to the manuscript during revision. \n\n[1] Ahn et al. Do As I Can, Not As I Say: Grounding Language in Robotic Affordances \n\n[2] Huang et al. Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents\n\n[3] B. Dhruv et al., “Rearrangement: A Challenge for Embodied AI.” 2020.\n\n[4] L. Weihs et al. \"Visual room rearrangement.\" CVPR 2021.\n\n[5] A. Szot et al. \"Habitat 2.0: Training home assistants to rearrange their habitat.\" NeurIPS 2021.\n\n[6] Y. Kant et al. \"Housekeep: Tidying virtual households using commonsense reasoning.\" ECCV 2022.\n\n[7] A. Khandelwal et al. \"Simple but effective: Clip embeddings for embodied ai.\" CVPR 2022.\n\n[8] E. Huang et al.,  \"Large-scale multi-object rearrangement.\" ICRA 2019.\n\n[9] A. Krontiris et al. \"Dealing with Difficult Instances of Object Rearrangement.\" RSS 2015.\n\n[10] S. Bubeck et al. \"Sparks of artificial general intelligence: Early experiments with gpt-4.\" arXiv preprint arXiv:2303.12712 (2023).\n\n[11] T. Silver et al. Generalized Planning in PDDL Domains with Pretrained Large Language Models. arXiv preprint 2023.\n\n[12] B. Liu et al. \"Llm+ p: Empowering large language models with optimal planning proficiency.\" arXiv preprint arXiv:2304.11477 (2023).\n\n[13] I. Singh et al., “ProgPrompt: Generating Situated Robot Task Plans using Large Language Models”, ICRA 2023.\n\n[14] S. Li et al., “Pre-trained language models for interactive decision-making,” Neurips 2022. \n"}]

Author rebuttal:
# Global response

We thank all the reviewers' efforts invested in reviewing our work and providing valuable feedback. We summarize the main concerns raised by reviewers and our corresponding responses. 

One review (RKS5) states that 
> The paper mostly relies on experiments and ideas from S.Li 2022. and would gain clarity if clearly stated. For instance, using LLMs to initialize the belief state was already used in S.Li 2022. 

We believe this is a severe misunderstanding and mischaracterization of our method. Our research utilizes GPT-3.5 as a commonsense world model for **model-based search** with MCTS, while Li et al. [1] use behavior cloning to finetune GPT-2 as a **model-free policy**. There are fundamental differences between the model-based and the model-free approaches, conceptually and algorithmically. In particular, the power of the model-based approach lies in its ability to compose elementary pieces of (commonsense) world knowledge through a reasoning/planning procedure (MCTS, in our case) and achieve compositional generalization. This is often one key weakness of the model-free approach. We made this argument in the introduction as well as in Sect 5.3. We will try to further clarify this issue during the revision. 

Further,  unlike what the review  (RKS5) asserts, Li et al.'s approach [1], by its nature, does not track belief states.

In responding to the main weaknesses raised by the reviewers, we appreciate the opportunity to address the concerns:
* **The domain and task of the experiments**: Reviewers noted that our experiments are restricted to object rearrangement in the VirtualHome simulator. Object rearrangement is a representative embodied AI task [3-9] with many practical implications in everyday life, such as setting the table, tidying up the room, loading the dishwasher, and more. Thus, object rearrangement experiments are an interesting setting to investigate a fairly large set of planning capabilities required in embodied AI. We chose VirtualHome, as it is an established domain well used in prior work [1,2,18,19]. Our method is domain-agnostic and should be able to generalize to other common household domains, as LLMs have vast general knowledge that should be widely applicable [15-17]. We will explore those distinct datasets for further evaluation.
* **Runtime performance**: There is a trade-off between accuracy and computational efficiency. While our method requires multiple LLM calls, it provides substantially improved results (Table 1). One objective of our study is to identify this possibility and highlight the trade-off. There are also various ways to enhance runtime performance, such as using a smaller LLM like Llama [10,11] or distilling domain knowledge into a smaller model [12-14]. We are keen to explore these avenues in future research.

We thank the reviewers for their constructive criticism, and we hope our rebuttal has clarified the issues.

[1] S. Li et al., “Pre-trained language models for interactive decision-making,” NeurIPS 2022. 

[2] X. Puig et al., “Watch-and-help: A challenge for social perception and human-ai collaboration,” ICLR 2021.

[3] B. Dhruv et al., “Rearrangement: A Challenge for Embodied AI.” 2020.

[4] L. Weihs et al. "Visual room rearrangement." CVPR 2021.

[5] A. Szot et al. "Habitat 2.0: Training home assistants to rearrange their habitat." NeurIPS 2021.

[6] Y. Kant et al. "Housekeep: Tidying virtual households using commonsense reasoning." ECCV 2022.

[7] A. Khandelwal et al. "Simple but effective: Clip embeddings for embodied ai." CVPR 2022.

[8] E. Huang et al.,  "Large-scale multi-object rearrangement." ICRA 2019.

[9] A. Krontiris et al. "Dealing with Difficult Instances of Object Rearrangement." RSS 2015.

[10] H. Touvron et al. "Llama: Open and efficient foundation language models." 2023.

[11] H. Touvron et al. "Llama 2: Open foundation and fine-tuned chat models." 2023.

[12] C.-Y. Hsieh et al. "Distilling step-by-step! outperforming larger language models with less training data and smaller model sizes." 2023.

[13] C. Liang et al. "Less is more: Task-aware layer-wise distillation for language model compression." ICML 2023.

[14] K. Shridhar et al. "Distilling reasoning capabilities into smaller language models." ACL 2023.

[15] S. Bubeck et al. "Sparks of artificial general intelligence: Early experiments with gpt-4." 2023.

[16] T. Silver et al. Generalized Planning in PDDL Domains with Pretrained Large Language Models. 2023.

[17] B. Liu et al. "Llm+ p: Empowering large language models with optimal planning proficiency." 2023.

[18] I. Singh et al., “ProgPrompt: Generating Situated Robot Task Plans using Large Language Models”, ICRA 2023.

[19] Huang et al. Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents, ICML 2022.

Meta-review: The paper introduces how LLMs can be used to accelerate search. It shows that they can both be initial models of the world and heuristics to guide search with MCTS. The results are algorithm is demonstrated with household rearrangement tasks in VirtualHome.

The reviewers generally found the paper clear and novel, and the results impressive and thoroughly ablated. Generally, the reviewers were positive with the exception of RKS5, whom after a detailed discussion in rebuttal is weak reject. As such I recommend acceptance. 

Still, there are a few improvements that should be made for a final version, primarily cleaning up the code, finishing the air travel experiments, and a few clarifications. The clarification are in regards to (1) the first figure and (2) generally the use of world model throughout. 

For (1), showing where the LLM is used would be informative and generally more algorithmic information, as the current one is so sparse it has essentially no information value. Showing each place the LLM is used very clearly would be great, e.g., showing the LLM output the initial state distribution given the task.

For (2), it should be more clearly stated many times (including the abstract, the intro) that the world model in this case is just the initial belief state rather than the transition and new states, which are instead handled by the environment. It would also help to have a pseudocode algorithm box, under ten lines (maybe five) in the method section that tracks with a figure to very clearly deliver the message.
Decision: Accept (poster)