Empowering LLM Agents with Zero-Shot Optimal Decision-Making through Q-learning

Q1: What are the differences between MLAQ and decision-transformer?

A1: Decision Transformer and LLM, especially LLM agents, are fundamentally different approaches.

Similarity: Both decision-transformer and LLM use transformer architecture and autoregressive computation, requiring large amounts of offline data for pretraining.

Differences

• Input and Output: Decision-transformer requires inputs such as state, action, and return-to-go, at the tensor level. Each input type is mapped to features using specific embedding layers, with outputs are only for actions. In contrast, LLM (and agents) operates at the token level, converting natural language words or characters into tokens through a large embedding layer, with output as a probability distribution over all tokens.
• Optimization: Decision-transformer relies on a large amount of expert data for training and can only solve tasks present in the dataset. The decision-making capability of LLM agents primarily derives from the general comprehension capability acquired through pretraining on human data, without reliance on expert in decision-making for supervised learning.

---

Q2: What are environmental tools, and does MLAQ use them?

A2: Environmental tools refer to functions provided by the environment, such as the dynamics function, which predicts the next state after executing an action, and the available action function, which lists all available actions in the current state. MLAQ does not use any environmental tools, and achieve these by the proposed MLAQ framework.

Environmental tools trade-off generalization for performance, while MLAQ could maintain efficiency through domain description "T" (actually is \tau). The domain description, analogous to a game manual, provides only key information such as state and action space rather than "all information" (humans also need instructions or tutorials to play games). Experimental results show that the current LLM has sufficient capability to achieve the available actions exploration and next-state predictions.

---

Q3: What is the ground-truth available actions?

A3: The ground-truth available actions represent the set of actions an agent can choose to interact with the environment in a given state.

Available actions: Taking the Sort task in RoCo as an example, an agent can select to "pick one of three objects and place it on a panel". But not all actions are available, e.g., picking objects outside the agent's reach range are considered unavailable actions.

Methods like RAP obtain ground-truth available actions using environmental tools, but MLAQ explore them from scratch. During the node selection phase, each state node begins with an empty available action set. MLAQ alternates between exploiting existing child nodes and exploring new available actions (and corresponding child nodes), progressively expanding the available action set, denoted as \delta(s).

---

Q4: Is MLAQ a zero-shot method with a lot of engineering part?

A4: MLAQ is a zero-shot method, and it is a general algorithm rather than an engineering solution tailored to some specific scenarios.

Zero-shot: We found that there are some ambiguities in definitions, with zero-shot having two different definitions: making decisions without providing examples in LLM, and making optimal decisions without environmental interaction. Although the starting point of our study is the second goal, MLAQ actually satisfies both definitions. Furthermore, MLAQ requires feedback from the environment only when decision errors occur (MLAQ becomes few-shot), but the "Env replans" metric in Table 2 is very close to zero, which indicates that MLAQ achieves zero-shot decision-making in most cases.

Engineering part: MLAQ is a general LLM-based agent framework. To apply it in other domains, users only need to provide a domain description in natural language as a manual, without the need for environmental tools. For example, in gaming scenarios, users only need to provide the game tutorial (a manual) rather than source codes.

Citations of more related works about zero-shot planner

Although the paper mentioned by the reviewer explicitly indicates an approach for small language models in the title and does not mention zero-shot at all, we have cited it in the related work section of the revised manuscript and added references on zero-shot planners, including:

1. Huang, Wenlong, et al. "Language models as zero-shot planners: Extracting actionable knowledge for embodied agents." ICML, 2022.

2. Hashemzadeh, Maryam, et al. "Sub-goal Distillation: A Method to Improve Small Language Agents." CoLLAs, 2024.

3. Gkanatsios, Nikolaos, et al. "Energy-based Models are Zero-Shot Planners for Compositional Scene Rearrangement." RSS, 2023.

4. Kwon, Teyun, Norman Di Palo, and Edward Johns. "Language models as zero-shot trajectory generators." IEEE RAL, 2024.

5. Wang, Lei, et al. "Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models." ACL, 2023.

---

More comparisons

We compared our method with many LLM agents on BlocksWorld and with the original RoCo algorithm on the RoCo-benchmark. Some algorithms (e.g., ReAd) have been tested on the RoCo-benchmark using evaluation methods different from ours. We commit to comparing our approach with theirs as soon as their code is open-source. Furthermore, we conduct an experiment on Crafter (please refer to the overall response for more detail) and compare our method with multiple LLM agents and RL agents to demonstrate its effectiveness.

Dear Reviewer,

Thank you once again for taking the time to review our manuscript and for considering our responses to your comments.

If you require any further clarification or would like additional points to be included in our response, we welcome any further discussion to ensure everything is clear and satisfactory. If we have adequately addressed your concerns, we would sincerely appreciate your re-evaluation and reconsideration of your rating.

Thank you for your consideration.

Best regards,

Authors

Dear Reviewer ZK4E,

We still sincerely thank you for your time to review our response. We would be grateful if you could provide more feedback.

---

Claim of the paper

• Zero-shot. We mentioned two definitions of zero-shot in the response, and explained that MLAQ meets these two definitions, but indeed in a very few cases it will need feedback from the environment, so we have been emphasizing in the manuscript that it is zero- or few-shot. We sincerely want to know which part of this claim does the reviewer specifically disagree with?

• Manual handling. We understand that the reviewer's opinion may come from the different research background, so we sincerely want to clarify that this is our general algorithm design, which does not introduce overly complex modules compared to traditional model-based RL.

  • The main framework of MLAQ is in the style of Dreamer, which is one of the most famous model-based RL methods. In order to adapt to LLM-based decision-making, we replace the world model that needs task-specific data training with a more general LLM. We also propose a novel planning approach that enables the LLMs to explore the available actions from scratch, and a mixed-examination to help the LLM-based world model approach the true MDP.

  • So we sincerely want to know what the reviewer specifically thinks are the "manual handling parts"? Is our Dreamer-style model-based RL framework too complex, or something else?

---

Writing

We sincerely hope to receive feedback from the reviewer on where exactly is not well-written, and which points are still unclear to the reviewer ZK4E?

Since Reviewer ouUC, 4yYK, and FSC6 all think that this paper is well-written, the feedback from the Reviewer ZK4E is critical for us to revise our manuscript when the readers do not have more patience to understand this paper. :)

---

Sincerely,

Authors

Dear Reviewer, thank you for your time to read our paper and provide useful comments. We carefully address your concerns as follows. Should our revisions adequately address your concerns, we would be most grateful for your positive re-evaluation.

---

Q1: What is the problem statement of this paper?

A1: This paper aims to address the challenge of empowering LLM agents with zero- or few-shot optimal decision-making capabilities.

MLAQ is a general algorithm designed for decision-making tasks. Leveraging terminology from the LLM reasoning domain, MLAQ is a test-time compute method in LLM-based decision-making, further enhancing the optimal decision-making capability of LLM-based basic policies through Q-learning in LLM-based imaginary transitions.

---

Q2: What is the environmental tools?

A2: Environmental tools refer to functions from the environment to enhance the LLM agents, such as using the environment's dynamics function for next-state prediction, available action function to obtain ground-truth available actions, and reward function for feedback on decisions. The reviewer correctly pointed out the similarity between "environmental tools" and LLM "tools". This is similar to an LLM agent using a calculator as a tool for mathematical computations.

---

Q3: how is the Q-function represented and is there a policy improvement step using the Q-function?

A3: The Q-function in MLAQ is in a tabular form, but it is not represented as a matrix, since the ground-truth available actions are unknown. Besides, MLAQ does not have a policy improvement step, and it directly uses the argmax actions supported by the Q-value function to make decisions.

• Get the Q-value: For a given state, the Q-function stores its available actions and corresponding Q-values. These available actions are explored through UCB-guided planning in the imagination space, so they may not cover all ground-truth available actions. Therefore, we only output the argmax action from the explored available actions.
• The state space in tasks based on natural language is typically small, as the problem is inherently abstracted into natural language. Even for tasks like Crafter, the overhead of storing transitions using a tabular approach is relatively low. For future large-scale tasks, MLAQ can efficiently extend the current tabular Q-function to a neural network form using embedding networks like SentenceBert.

---

Q4: What concretely is the action space being considered?

A4: The output dimensions is equal to the number of explored available action under the given state.

The action space in this paper refers to the description of all actions in the domain description (such as pick or put, regardless of whether they are available or not). We believe the reviewer was actually asking about the Q-function's output dimension.

The potential actions for LLM-based basic policy is extremely huge, requiring token-level combinations, whereas MLAQ does not use any environmental tools to obtain ground-truth available actions. To this end, we propose a novel UCB variant that supports planning under an unknown available action set, enabling iterative exploration of all available actions from scratch. While the breadth of actions LLMs can take might appear infinite, we leverage an LLM-based action checker to retain only actions identified available by the LLM, thereby preventing unbounded expansion.

---

Q5: Is the website available?

A5: The correct link to the website is http://mlaq.site/ (HTTP rather than HTTPS), and the GitHub link for the open-source code is https://github.com/laq2024/MLAQ/tree/main. If the reviewer is unable to access the website, please try the original link: http://27.106.114.122:8501/.

---

Q6: What is the LLM used in MLAQ?

A6: The LLM used is GPT-4-0125-preview, with other hyperparameters also listed in Table 9 of the previous manuscript.

---

Overall response

This paper aims to introduce the model-based RL approach into LLM agents for zero- or few-shot optimal decision-making. Given the limited space, it strives to present relevant concepts to potential readers from both fields, which may lead to some imbalance in the coverage of some concepts. As a result, while some reviewers may find the paper well-written, others might feel the explanations lack clarity. We sincerely appreciate the reviewers' feedback on areas of confusion, which have been invaluable in improving the manuscript.

The detailed explanations regarding the reviewers' concerns are primarily located in the abstract and introduction sections. In the revised version, we have addressed all concerns raised by the reviewers and provided more definitions and explanations for key terms to ensure accessibility for readers from different backgrounds.

Motivation: This paper combines the general comprehension capability of LLMs and the optimal decision-making ability of RL to achieve zero- or few-shot optimal decision-making.

---

Contributions

Summary: The LLM-based basic policy and world model leverage the general comprehension capability of LLMs to generate imaginary transitions without interacting with the environment. Q-learning is used on transitions stored in memory to achieve optimal decision-making.

LLM-based Imagination Space: The basic policy outputs possible actions given a state, while the world model predicts the next state based on state-action pairs, generating imaginary transitions in a Dreamer-style for policy optimization.

• LLM-based imaginary transitions are generated for Q-function training without environmental tools. Considering the reviewer's background in model-based RL, this can be likened to Dreamer. However, we emphasize that LLM’s general capability allows it to replace RSSM-based world model.
• To address the hallucination issue, our LLM-based self-examination improves the accuracy of imaginary transitions, and env-examination uses ground-truth transition to correct the previously undetected errors.

Planning in the Imagination Space: A novel planning approach, driven by our UCB variant, is proposed to enable exploration in LLM-based imagination without ground-truth available actions. The regret bound for this approach is derived theoretically.

• Our planning approach enables iteratively exploration of available actions without environmental prior knowledge, enhancing the algorithm's generality.
• Exploration aims to discover potentially better decisions, and the resulting imaginary transitions are used to enhance the agent's decision-making performance via Q-learning. If the basic policy already provides optimal actions, MLAQ does not explore unnecessarily (though users can opt for continuous exploration).

---

Main Conclusions

LLMs can build a model-based framework, achieving performance far exceeding current LLM agents with minimal computational cost, fulfilling the motivation for zero- or few-shot optimal decision-making.

Dear Reviewer,

Thank you once again for taking the time to review our manuscript and for considering our responses to your comments.

If you require any further clarification or would like additional points to be included in our response, we welcome any further discussion to ensure everything is clear and satisfactory. If we have adequately addressed your concerns, we would sincerely appreciate your re-evaluation and reconsideration of your rating.

Thank you for your consideration.

Best regards,

Authors

Dear Reviewer XLz6,

We really want to understand why the reviewer cannot understand how MLAQ works, considering that the reviewer mentioned that he/she has published papers in the field of model-based RL, then the reviewer can fully understand the main framework of this paper.

The main framework of MLAQ is Dreamer-style (For all readers, Dreamer is one of the most famous model-based RL methods), but we have replaced the world model that needs task-specific data training with a more general LLM. Furthermore, in order to adapt to LLM-based decision-making, we have proposed a novel planning approach that enables the LLMs to explore the available actions from scratch, and a mixed-examination to help the LLM-based world model approach the true MDP. It DOES NOT add overly complex modules compared to the original model-based RL, and we have provided very detailed pseudo codes, open sourced our code, and even all experimental data.

We sincerely ask the reviewer to be more patient to review our manuscript and responses once again. Considering that Reviewer ouUC, 4yYK, and FSC6 all think that this paper is well-written, so we really need the feedback from reviewer XLz6 to see what description we have missed to make a researcher in model-based RL cannot understand MLAQ.

We have submitted a new revised version, trying to emphasize the points that the reviewer did not understand, and we sincerely ask for your feedback to address your concerns.

Sincerely,

Authors

Dear Reviewer, thank you for your time to read our paper and provide useful comments. We carefully address your concerns as follows:

Q: Can MLAQ be extended to more complex scenarios?

A: Yes. To evaluate MLAQ's performance in more complex scenarios, we conduct experiments on Crafter (a 2D version of MineCraft) as our experimental environment. Please refer to the overall response for more detail. Based on our experimental results, MLAQ can be demonstrated to have the opportunity to be extended to more complex stochastic problems, but it performs optimally in deterministic, fully observable environments.

• Deterministic, full observability means that LLMs can access complete state information and predict a unique next state based on state-action pairs. Our experiments in BlocksWorld and RoCo demonstrate that LLMs possess this capability, and MLAQ can leverage imaginary transitions to enhance LLM agents' optimal decision-making through test-time computation.
• Results in Crafter experiments indicate that MLAQ's performance decreases when facing environmental stochasticity. We conduct three experiments where the only difference lies in how the world model predict next observations for move actions, while all other modules remain consistent with the original MLAQ. MLAQ-gt, which uses ground-truth environment for state prediction under move actions, outperforms both script-based MLAQ-script and purely LLM-based MLAQ.
  • On the one hand, MLAQ is *difficult to adequately explore under limited test-time computation budget when facing stochastic environments, and the accumulated errors caused by stochasticity significantly impact estimation of Q-values.
  • On the other hand, current LLMs preforms poor in modeling stochastic environments, which further degrades the quality of imaginary transitions and consequently undermines MLAQ's performance. However, the performance of MLAQ is still better than other existing LLM agents.

Dear Reviewer,

Thank you once again for taking the time to review our manuscript and for considering our responses to your comments.

If you require any further clarification or would like additional points to be included in our response, we welcome any further discussion to ensure everything is clear and satisfactory. If we have adequately addressed your concerns, we would sincerely appreciate your re-evaluation and reconsideration of your rating.

Thank you for your consideration.

Best regards,

Authors

Dear Reviewer, thank you for your time to read our paper and provide useful comments. We carefully address your concerns as follows:

---

Q1: What are the computational and token costs of MLAQ?

A1: Although MLAQ requires exploration to find more optimal decisions, it consumes fewer tokens than existing methods while achieving better performance. MLAQ is a test-time compute method in LLM-based decision-making that combines planning with model-based RL.

Computational cost. This mainly involves MLAQ's planning in imagination space. MLAQ's planning in the imagination space is computationally efficient due to its UCB variant and transition re-utilization.

• Re-utilization of imagination results. 1) MLAQ re-utilizes transitions in memory during planning to avoid redundant imagination. 2) MLAQ interacts with the environment by using the Q-learning-derived argmax actions, eliminating the need to query the LLM per step.
• Efficiency. MLAQ is an efficient trade-off between basic policy and MCTS. It avoids unnecessary exploration when the base policy is already optimal, matching traditional agents' costs. For weaker policies, it uses UCB-guided exploration to improve performance. Compared to MCTS (in RAP), MLAQ is more similar to Dreamer, which uses Q-learning for computing state values.

Token cost. Due to the transition re-utilization and higher decision correctness, MLAQ has lower token costs than traditional LLM agents.

• Bigger memory, then lower token cost. The 40k token consumption in 8-steps BlockWorld is the average token per episode. In 12-steps, it is decreased to about 25k while the optimal rate significantly outperforming other methods, demonstrating MLAQ's effectiveness.
• Lower token cost, but better performance. Table 2 compares token consumption under RoCo-benchmark, showing that MLAQ uses significantly fewer tokens but achieves higher optimal rate. Unlike RoCo, which requires multiple reflections, MLAQ could output optimal actions even without querying the LLM (Figure 3).

Why do MLAQ aim to minimize environmental interactions?

• We believe that zero-shot optimal decision-making enables LLM agents to generalize across more scenarios, requiring neither accurate environmental information (such as source code) nor extensive environment interactions for RL training.
• Environmental interactions could be costly and raise safety concerns (such as robotic arm operations in real-world), while MLAQ constructs an LLM-based imagination space to derive an optimal policy.

---

Q2: How is the reward calculated in MLAQ?

A2: MLAQ achieves sparse rewards by determining whether the next state is equal to the target state and providing positive feedback only when they are equal.

Clarification of reward. In Figure 3, the world model is only used to predict the next state, not for reward prediction. Besides, the rewards in Algorithm 1 is obtained through environmental interactions, and we also show how sparse rewards are calculated during LLM-based imagination in Algorithm 2.

Other type of reward function is also available. We use sparse reward mainly to avoid accessing the ground-truth reward function, but MLAQ also support other reward settings. The experiment on Crafter adopt a reward function with multiple sub-goals, offering positive feedback upon completing sub-goals. Although untested, MLAQ should also have the potential to support dense rewards.

---

Q3: How does MLAQ handle situations where environmental complexity exceeds the capability of LLMs?

A3: MLAQ leverages both LLM's self-examination to improve transition accuracy and environmental feedback to rectify LLMs' output.

However, when the environment becomes much more complex (e.g. Crafter), although MLAQ can still outperforms existing LLM agents, using the LLM-based world model performs worse than directly using the ground-truth dynamics function (MLAQ-gt, please refer to the overall response for more detail about our experiment on Crafter).

LLM's self-examination ability has "thresholds". Current LLMs could fully understand deterministic environments like BlocksWorld, achieving high transition accuracy with LLM-based checkers, as detailed in Sections 4.4 and 4.5. However, LLMs face limitations in more complex environments such as Crafter, resulting in reduced examining accuracy.

Q4: Should MLAQ be called an LLM agent rather than a Q-learning agent?

A4: We believe the core of MLAQ still remains an LLM agent. MLAQ enhances the optimal decision-making capability of the basic policy through techniques in model-based RL and planning. We would like to maintain its original name rather than changing it to a Q-learning agent, but we greatly appreciate the reviewer's kind suggestions.

Q5: How to train a Q-planner?

A5: The Q-planner is trained using tabular Q-learning based on transitions in the memory.

We adopt a training framework similar to Dreamer, where transitions are mainly generated in the LLM-based imagination space, with environmental transitions being stored only when MLAQ makes incorrect decisions. The reward signal is obtained in a sparse reward way for both enironmental and imaginary interactions.

Dear Reviewer,

Thank you once again for taking the time to review our manuscript and for considering our responses to your comments.

If you require any further clarification or would like additional points to be included in our response, we welcome any further discussion to ensure everything is clear and satisfactory. If we have adequately addressed your concerns, we would sincerely appreciate your re-evaluation and reconsideration of your rating.

Thank you for your consideration.

Best regards,

Authors

---

Q3: How does MLAQ adapt to continuous space tasks?

A3: The problem mentioned by the reviewer is a common problem with LLM agents. At present, almost all LLM agents cannot adapt well to continuous space tasks. We have not specifically tried this, so we only share our views with the reviewer for reference.

On the one hand, while keeping the LLM network structure unchanged, most of the existing methods try to convert continuous actions into discrete actions, such as abstracting movement and navigation into natural language instructions in LLM-based embodied agents [1, 2]. On the other hand, some works also try to introduce some embedding layers on the basis of LLM to handle different types of states and actions, but this requires additional data for training [3]. We believe this is still a challenge for LLM agents where there is significant room for improvement.

[1] Yijun Yang, et al. LLM-Planner: Few-Shot Grounded Planning for Embodied Agents with Large Language Models, ICCV, 2023

[2] Chan Hee Song, et al. Embodied multi-modal agent trained by an llm from a parallel textworld, CVPR, 2024

[3] Jing-Cheng Pang, et al. KALM: Knowledgeable Agents by Offline Reinforcement Learning from Large Language Model Rollouts, NeurIPS 2024

---

Thanks again for your response!

Sincerely,

Authors

Dear Reviewer,

We have provided more detailed discussions and responses to the reviewer's new questions, and provided our insights into MLAQ and the entire field. We sincerely hope to have in-depth discussions with the reviewer on this.

If the discussion effectively resolves the reviewer's concerns, we're sincerely hoping for a positive re-evaluation of our work. (Sigh :(

Sincerely,

Authors

Dear Reviewer, thank you for your time to read our paper and provide useful comments. We carefully address your concerns as follows:

---

Q1: What are the scope and limitations of the MLAQ algorithm? Can MLAQ be applied in complex and unstructed environments?

Scope. MLAQ performs best in deterministic & fully observable scenarios. When applied to new scenarios, users only need to provide prompts for the LLM-based modules. Our experimental results have demonstrated this.

Experiments in complex environments. MLAQ also performs well in complex environments with stochasticity and partial observability. We evaluate MLAQ on Crafter (a 2D version of Minecraft), an environment featuring high partial observability and complexity. The player has 16 sub-goals, and its final goal is to mine diamonds. Experimental results shows that MLAQ significantly outperforms existing algorithms. Please refer to the overall response for more detail about this experiment.

Limitations. While the results on Crafter validates MLAQ's capability in handling complex, stochastic scenarios, we also identified a major limitation: MLAQ have limitations in addressing scenarios with stochasticity and partial observability.

• For stochastic environments, the same state-action pair may lead to multiple next states, which significantly increases MLAQ's exploration demands in the imagination space, making it difficult for MLAQ to achieve optimal decision-making under limited test-time compute budget.
• Although MLAQ outperforms other LLM agents, its performance remains lower than MLAQ-gt, which uses the ground truth dynamics function to eliminate stochasticity of Crafter. Please refer to the overall response for more details of the experiments.

---

Q2: To what extent can MLAQ's self-examination mechanism mitigate the hallucination problem in LLMs?

Hallucination of LLM is detrimental to MLAQ because the LLM-based world model may imagine wrong transitions. MLAQ mitigates its impact on optimal decision-making capability through three approaches, rather than solely relying on self-examination.

• Self-examination. The first line of defense against erroneous outputs. It leverages the LLM to verify outputs. Results demonstrate its nearly 99% accuracy in deterministic, fully observable domains (see Section 4.5). Nevertheless, erroneous transitions may still occur in memory, as evidenced by the non-zero (though very close to zero) Env Replans data in Table 2. In such cases, MLAQ employs other mechanisms.
• Env-examination. For erroneous transitions emerged during imaginary interaction, environmental corrections can be made using ground-truth transitions to correct the memory and saved in the LLM-based module's prompt to prevent similar issues.
• RL-based optimization. As mentioned in our manuscript, MLAQ's additional reliance on RL further enhances its robustness. Trajectories originating from error states mostly fail to complete the given task in Q-learning, resulting in significantly lower state values compared to correct states (unless multiple cascading errors coincidentally lead back to the correct trajectory, which has an extremely low probability).

---

Q3: What are the computational demands of MLAQ relative to traditional LLM agents?

Using terminology from LLM reasoning, MLAQ is a test-time compute approach in LLM-based decision-making, enhancing zero-shot optimal decision-making by combining the exploration in LLM-based imagination space with the RL-based optimization. The main computational demands include:

• Exploration in LLM-based imagination space (majority, about 95%). MLAQ's planning in the imagination space is computationally efficient due to its UCB variant and transition re-utilization.
  • Re-utilization of imagination results. 1) MLAQ re-utilizes transitions in memory during planning to avoid redundant imagination. 2) MLAQ interacts with the environment by using Q-learning-derived argmax actions, eliminating the need to query the LLM per step.
  • Efficiency. MLAQ is an efficient trade-off between basic policy and MCTS. It avoids unnecessary exploration when the base policy is already optimal, matching transitional agents' costs. For weaker policies, it uses UCB-guided exploration to improve performance. Compared to MCTS (in RAP), MLAQ is more similar to Dreamer, which uses Q-learning for computing state values.
  • Compared to traditional LLM agents, MLAQ requires more exploration than search-free methods like RoCo for optimal decisions. However, results in Table 2 shows that agents like RoCo requires higher token usage due to their low correctness in decision-making.
• Q-learning Process (< 5%). Given that natural language tasks typically have small state spaces (rarely exceeding 10,000 states), MLAQ employs a tabular approach for storing transitions and executing Q-learning iterations. This computational demand is negligible compared to the planning phase.

Q4: Can authors provide more theoretical analysis about MLAQ's convergence?

MLAQ employs the Q-learning algorithm, whose convergence has been well established. We conjecture that the reviewer is interested in the performance gap between the converged policy in the true environment versus that in the imagination space, which depends on the accuracy of the LLM-based world model.

Analyzing MLAQ's convergence at the token level is quite complex. Given that MLAQ is a Dreamer-style model-based RL method, we can directly apply theories from previous works. Drawing from Theorem 4.1 in [1], we present the following conclusion.

Bound Theorem. Let the expected TV-distance between two transition distributions be bounded at each timestep by $\epsilon_m$ and the policy divergence be bounded by $\epsilon_\pi$. Then the true returns and model returns of the policy are bounded as:

$\eta[\pi] \ge \hat{\eta}[\pi] - [\frac{2\gamma(\epsilon_m+2\epsilon_\pi)}{(1-\gamma)^2}+\frac{4r_{\rm max}\epsilon_\pi}{(1-\gamma)}]$

where $\eta$ is the returns of the policy in the true environment, $\hat{\eta}$ is the returns of the policy under the LLM-based world model. $r_{\rm max}$ is the maximum value of rewards, $\epsilon_m = \max_{(s, a) \sim \mathcal{M}} [D_{\rm TV}(\mathbb{T}(\cdot|s, a))||(\mathbb{T}(\cdot|s, a; \theta))]$ is the generalization error of the LLM-based world model, $(s, a)$ is sampled from MLAQ's memory module $\mathcal{M}$, and $\mathbb{T}(\cdot|s, a))$ and $\mathbb{T}(\cdot|s, a; \theta))$ are the transition distribution of the true environment and LLM-based world model, respectively. $\epsilon_\pi \ge D_{\rm TV}(\pi||\pi_\mathcal{M})$ is the policy divergence between greedy policy $\pi$ derived from Q-learning (output argmax actions) and the data-collecting policy from the memory $\pi_\mathcal{M}$.

From the definitions of $\epsilon_\pi$ and $\epsilon_m$, we can observe that $\epsilon_\pi$ increases as $\pi$ deviates further from $\pi_\mathcal{M}$, while $\epsilon_m$ increases as the domain becomes more challenging to simulate (larger prediction errors in LLM-based world model). Consequently, the greedy policy derived from Q-learning yields a larger return gap when interacting with the true MDP (environment), indicating that policies optimal in the imagination space may not be optimal in the true MDP. MLAQ primarily mitigates the bias between imagination space and true MDP by preventing excessive $\epsilon_m$ values through mixed-examination.

[1] Janner, Michael, et al. "When to trust your model: Model-based policy optimization." NeurIPS, 2019.

---

Q5: Can self-examination use a non-LLM-based Checker?

Of course! Actually, both action and prediction verification can be implemented using non-LLM-based checkers. However, training them would require substantial ground-truth data, which contradicts MLAQ's zero/few-shot motivation. If users do not specifically require this, non-LLM-based checkers might be more effective.

---

Q6: How sensitive is MLAQ's performance to the hyperparameter used in the UCB variant (e.g., coefficients and confidence bounds)?

I would like to clarify to the reviewers that the only hyperparameter in our UCB variant is $w$, while the form of confidence bound remains consistent with the original UCB. Furthermore, we tested scenarios with $w$ values of 1, 4 (orginal value), and 16 in the 2-step BlocksWorld environment, with results as follows.

The results indicate that different values of $w$ have small impact on the optimal rate. However, significant differences are observed in token consumption. When $w$ equals 1, the token consumption is comparable to when $w$ equals 4. However, when $w$ increases to 16, the token consumption is approximately 1.5 times higher than cases where $w$ is 1 or 4. This is primarily attributed to the fact that with larger w values, the planning process tends to favor exploration of new actions rather than exploiting existing actions.

Furthermore, table 9 in the appendix presents other hyperparameters of MLAQ. In table 9, only the environmental horizon varies across different domains, while other hyperparameters do not require tuning. However, users can adjust these parameters according to their computational budget and problem complexity.

Dear Reviewer,

Thank you once again for taking the time to review our manuscript and for considering our responses to your comments.

If you require any further clarification or would like additional points to be included in our response, we welcome any further discussion to ensure everything is clear and satisfactory. If we have adequately addressed your concerns, we would sincerely appreciate your re-evaluation and reconsideration of your rating.

Thank you for your consideration.

Best regards,

Authors

Dear Area Chair and Readers,

In the Camera-Ready version, we have revised the original text according to the suggestions from the reviewers and the Area Chair. The main modifications include clarifying unclear expressions and providing necessary definitions for mentioned terms or variables, hoping that readers can fully comprehend the contributions of this paper. Additionally, experiments conducted on Crafter have been added to Appendix E, which effectively demonstrate the effectiveness of the proposed approach in more complex and practical benchmarks.

Lastly, we would like to express our gratitude to all the reviewers and the Area Chair for dedicating their time and effort to our paper. We also hope that all readers in the community will engage with us in discussions, aiming to further enhance the optimal decision-making capabilities of LLM agents in future work.

Sincerely,

Authors