Choices are More Important than Efforts: LLM Enables Efficient Multi-Agent Exploration

Thank you for your effort.

A) I want to strongly but decisively push back here. Many of the authors of SMAC are also authors of SMACv2. I have confirmed with one of the authors of SMACv2 that since open-loop policies solve many of the problems in SMAC, that benchmark should be seen as fundamentally broken by now and SMACv2 needs to be used instead. I acknowledge the additional experiments on SMACv2 in the Appendix. However, the authors have tested only on the simplest SMACv2 tasks (first row of figure 6 in https://arxiv.org/abs/2212.07489) and, more importantly, even on these simplest SMACv2 tasks, LEMAE performs worse than the baseline QMIX-DR that neither uses intrinsic rewards nor language abstractions or key states, thus putting in question the validity of the LEMAE method. "LEMAE achieves outstanding performance" is a gross misrepresentation of how these results should be interpreted.

B) I acknowledge the comment regarding OMNI and Motif, but I need to call out that the authors have completely ignored by request to compare to "[2] Mu et al. (2022). Improving Intrinsic Exploration with Language Abstractions. NeurIPS 2022. https://doi.org/10.48550/arXiv.2202.08938" which is probably the most related method and doesn't require costly LLM inference or offline annotation.

C & B) Thank you for providing additional comparisons with E3B. Please compare E3B, ProgressCounts, [2] (see previous comment), LEMAE all on the same set of benchmarks so that we can see an apples-to-apples comparison.

D) Thank you for providing additional results in the Appendix for non-symbolic environments. Again, LEMAE performs worse than the baseline IPPO-DR, questioning the validity of the proposed approach. At this point I don't suspect LEMAE to work here, but may I suggest an additional visual domain: Vizdoom which has been used in the E3B paper.

As it stands, despite the authors efforts, none of my concerns have been addressed and I maintain and, based on the negative results in A) and D) compared to baselines, even solidify my assessment of a strong reject.

We sincerely appreciate Reviewer 5ctA's efforts and feedback. The following addresses the concerns.

1.SMACv2(A)

We clarify that (1) SMAC is a standard benchmark in MARL exploration studies; (2) the fully sparse-reward SMAC remains far from saturated; (3) we have evaluated LEMAE on SMACv2 in Appendix F.1, revealing its potential for complex and stochastic scenarios.

2.LLM-based methods(B)

• Compared to prior single-agent LLM-based methods, LEMAE is a pioneering attempt to tackle the unique challenges of MARL with LLM for efficient exploration: (1) LLM-based key states discrimination to provide reliable priors, particularly for high-dimensional and partially observable MARL tasks; (2) Labor-division-oriented prompt designs to reduce manual effort and foster multi-agent cooperation; (3) Subspace-based Hindsight Intrisic Reward to improve RL guidance and alleviate manual reward design; and (4) Key States Memory Tree to organize exploration with memory, reducing complexity by focusing on a meaningful subspace within the exponentially expanded state space.
• We have demonstrated LEMAE's superiority over the most relevant LLM-based methods in Fig.3: LLM step-wise exploration goals generation, exemplified by ELLM[4]; LLM-based reward design, exemplified by Eureka[5]. Additionally, LEMAE outperformed ProgressCounts[6], a recent method combining LLM reward design and count-based exploration, in revised Appendix F.8.
• The suggested baselines are not suitable for our setup, as discussed in revised Sec.3: Motif[1] requires pre-collected annotated datasets and extensive LLM inferences; OMNI[2] focuses on task sampling for skill acquisition in open-endedness environments, unlike our focus on single-task efficient exploration without a task pool.

3.Significance of Key States(C)

As shown in Fig.1, key states play a crucial role in promoting efficient exploration in MARL. They serve as meaningful intermediate states that guide task completion and exhibit a division of labor in our design, enhancing multi-agent collaboration.
As suggested, we compare LEMAE with E3B[3] in revised Appendix F.8. LEMAE's superior exploration efficiency implies the effectiveness of key states over generic intrinsic reward methods. We clarify that the baselines also use distinct intrinsic reward mechanisms, and LEMAE's advantage emphasizes the importance of key states.

4.Application Scopes Clarification(D)

We clarify that LEMAE primarily focuses on achieving efficient exploration in tasks with symbolic state, a common assumption in prior methods[5,6].
LEMAE can also be extended to non-symbolic tasks. We have extended it to image-based tasks, Visual-Pass, in Appendix F.2(LEMAE:1.0±0.0; IPPO(dense reward):1.0±0.0 ;IPPO:0.0±0.0)
We have refined the statement. KSMT reduces exploration complexity in tasks with complex symbolic state spaces by focusing on a meaningful state subspace(Fig.1), revealing its potential for real-world applications.

5.Methodology Explanations

We apologize for any confusion and have revised the manuscript for clarity. Below are the detailed explanations:

• Redundant Exploration: refers to exploration behaviors irrelevant to the corresponding tasks, as described in ELLM[4].
• LLM generation: (1) LLM takes in the prompt template and task information and generates $m$(determined by LLM) key states' definitions and disciminator functions, which are easily extracted from the predefined JSON response through key-value matching. (2) Each discriminator function $\mathcal{F}_i$(corresponding to the 'Iskeystate(s)' block in Fig.2) takes in the state $s_t$ and outputs a boolean value to tell whether $s_t$ is the key state $\kappa_i$, aligning with the annotation process from $s_t$ to $s_t^{\kappa_2}$ depicted in Fig.2. (3) The feedback, introduced in Line 226-232 (Self-Check), includes the prior response, rethinking queries, and execution errors.
• Asymmetric policy: As stated in Proposition 1, the initial policy is random, with a probability $p\in(0.5, 1)$ for moving right. This indicates an asymmetry between right and left movements.
• Manhattan distance: is adopted due to its empirical effectiveness. LEMAE is compatible with other distance metrics, like cosine similarity, which may perform better in other applications.

6.Other Typos

We appreciate your suggestions regarding the writing typos and have revised the manuscript accordingly.

[1]Motif: Intrinsic Motivation from Artificial Intelligence Feedback.
[2]OMNI: Open-endedness via Models of human Notions of Interestingness.
[3]Exploration via Elliptical Episodic Bonuses.
[4]Guiding pretraining in reinforcement learning with large language models
[5]Eureka: Human-level reward design via coding large language models
[6]Automated Rewards via LLM-Generated Progress Functions

Thank you for your active engagement. The following clarifies any potential misunderstandings.

1. We wish to clarify that it is the empirical results that highlight the significant performance gap in fully sparse-reward SMAC. In scientific research, we believe that conclusions should be drawn from empirical evidence, and that specific settings must be carefully analyzed, rather than relying on prior perspectives. Your point regarding the benchmark being 'broken' seems to stem from its ease in dense-reward scenarios. However, we have demonstrated that sparse-reward SMAC presents substantial challenges, which were not the settings discussed by the SMAC authors. Therefore, we believe the assertion that it is 'broken' may be not justified.
2. Additional baseline results on SMACv2 have been included in the updated manuscript as a supplement to demonstrate LEMAE's effectiveness in incorporating LLM for efficient multi-agent exploration, compared to previous LLM-based single-agent methods.
3. We do not overstate the 'superiority' of our method. In the manuscript, we objectively compare the performance of ELLM and LEMAE in multi-agent scenarios (the primary focus of this work), as shown in Fig. 3 and 5. We have made appropriate adaptations to ELLM for multi-agent scenarios to ensure a fair, apples-to-apples comparison.
4. We clarify that our comparisons are 'apples-to-apples'. The underlying MDP (excluding intrinsic reward) is the same across all methods, with a sparse reward function. Methods using dense rewards can be viewed as sparse-reward MDP + manually designed intrinsic rewards. We emphasized the unmodified transitions in the previous response to prevent any confusion. Introducing a human expert as an upper-bound baseline is a standard practice[1,2] to demonstrate the potential of the methods. Besides, the evaluation metric is test win rate, an objective and fair metric for all methods. Thank you for your suggestions. To avoid any confusion, we have provided additional clarification in the revised manuscript.
5. We have previously clarified that LEMAE is specifically designed to address the unique challenges of MARL with LLM for efficient exploration. Regarding multi-agent cooperation, we have clarified before that, as shown in Sec. 4.2, we explicitly prompt LLM to prioritize role division among agents to enhance multi-agent collaboration. This straightforward design yields impressive results: the visitation map in Fig.1(d) shows an organic division of labor. We appreciate your recognition of LEMAE's potential in single-agent scenarios. However, this is not the primary focus of this work, as stated in 4. We intend to further advance the core idea behind LEMAE in future research, i.e., leveraging LLM-based discrimination to incorporate knowledge into efficient RL algorithms.

We appreciate your kindness and efforts to improve the quality of our work. We hope our response provides a clearer and more comprehensive basis for evaluating our work without misunderstandings.

[1] Lazy Agents: A New Perspective on Solving Sparse Reward Problem in Multi-agent Reinforcement Learning. ICML 2023
[2] Eureka: Human-level reward design via coding large language models. ICLR 2024

We thank Reviewer 5ctA's further discussion and post the rebuttal as follows.

1. Regarding the evaluation benchmark, we do not think your viewpoint consistently stands, given several of the latest existing works using SMAC-v1. We believe the RL community is inclusive enough unless severe bugs happen; otherwise, all recent publications with SMAC-v1 will be problematic according to your criteria. We have clarified that the success of open-loop policies heavily relies on manually designed rewards. Without such rewards, traditional methods, even those with sufficient information (e.g., QMIX, as shown in Fig. 5), struggle in environments with fully sparse rewards. This observation reveals the current performance gap and challenges your characterization of the benchmark as 'broken.' LEMAE achieves strong performance, comparable to results obtained with manually designed dense rewards, which convincingly demonstrates its effectiveness and contribution.

2. All setups are apple-to-apple, as we don't modify the MDP transition dynamics. Some baseline agents can access manually designed dense rewards, serving as an upper bound. This setup is appropriate for evaluating LEMAE's potential without relying on human-designed reward structures. Recognizing the empirical limitations of traditional methods like QMIX in fully sparse-reward SMAC, we exclude them and instead focus on demonstrating LEMAE's universal applicability and its ability to reduce manual effort in reward design, in the supplementary SMACv2 experiments. This is demonstrated through comparable performance to QMIX-DR(QMIX trained with dense rewards). However, to meet your request, we will evaluate ELLM, E3B, and ProgressCount on SMACv2 and report the results in the updated manuscript.

3. We have clarified previously that LEMAE is specifically designed to tackle the unique challenges of MARL with LLM for efficient exploration. These challenges include handling partial observability in MARL, enhancing multi-agent collaboration, alleviating the need for intricate manual reward design, and reducing the complexity of exponentially expanded state spaces. While the methodology of LEMAE can also be applied to single-agent scenarios, such as utilizing LLM-based discrimination, this is not the primary focus of our application or contributions.

4. In the manuscript and previous rebuttal, we've clearly clarified the scope of LEMAE in symbolic cases. We have demonstrated the potential of LEMAE in extending to image-based tasks, as shown in Appendix F.2. As for pursuing outstanding performance in non-symbolic cases, we admit it is a meaningful exploration; however, it is not the primary focus of this work and is difficult to investigate within the limited time available for the rebuttal.

Meanwhile, it would be appreciated if Reviewer 5ctA adjusted the separate rating, such as presentation, soundness, or contribution. It is kind of a favor to ensure objective and unbiased evaluation in the RL community. Thanks for your efforts.

We sincerely appreciate Reviewer AW9u's efforts and positive feedback on the importance, novelty, presentation, and impressive experiments. The following addresses the concerns.

1.Motivation Discussion

Proposition 4.1 provides a quantitative analysis of the efficacy of incorporating key states. For more realistic tasks, we illustrate using the Pass task as follows:
As illustrated in Fig.1(c), without key states (CMAE), agents must explore the entire room randomly from their initial positions until they reach a success state. This results in significant redundant exploration.
In contrast, with key states incorporated in LEMAE, exploration becomes more organized and targeted: Agents first focus on finding key state $\kappa_1$. Once $\kappa_1$ is located, agents can skip exploring areas preceding $\kappa_1$ and focus on states that follow it.
Both the visitation map in Fig.1(d) and the performance in Fig.3 illustrate that key states provide a significant advantage through reducing redundant exploration.
Moreover, in our MARL design, key states encourage role specialization among agents to enhance multi-agent collaboration: The visitation map in Fig.1(d) reveals an emergent division of labor, while the discrimination functions in Fig.4 provide an intuitive explanation of this phenomenon.

2.Implementation Details Explanation

We apologize for any confusion and have revised the manuscript for improved clarity. Below is an explanation of the implementation details for key state localization:

• Prompts and Generation: Due to page limits, detailed prompts and responses are in Appendix D. Specifically, as shown in Sec.4.3, we design a prompt template with role instructions to help LLM understand tasks and define key states, along with output constraints for responding in a specific JSON format. For each new task, LLM takes in the prompt template with task details (task description and state form) and generates key states definitions and discriminator functions. The discriminator functions can be easily extracted from the JSON response via key-value matching.

• Key States Number $m$: We do not strictly constrain $m$, allowing LLM to determine it while using prompts to discourage overly low values. Specific details and values are in Appendix D.

• Applied to states: Each discriminator function $\mathcal{F}_i$ takes the state $s_t$ at timestep $t$ as input and outputs a boolean value to tell whether $s_t$ is the corresponding key state $\kappa_i$(Sec.4.3).

• Response Quality Assurance: As detailed in Sec.4.3, we introduce a Self-Check mechanism to ensure LLM response quality. It involves two steps: LLM rethinking for self-assessment with a set of queries and code verification to test discriminator function executability on actual inputs, iterating until successful. Table 1 shows the proposed mechanism's effectiveness and high LLM response quality.

3.Baselines Clarification

We want to clarify that all the MARL baselines we adopted, except for IPPO and QMIX, are widely recognized multi-agent exploration methods in prior works[1,2]. As suggested, we have added discussions on WToE [2] and LLaMAC [3] in Sec. 3 and evaluated WToE in Appendix F.8. Below, we provide additional discussions and explain the rationale for not evaluating LLaMAC:

A recent influential work, WToE, focuses on when to explore by identifying discrepancies between the actor policy and a short-term inferred policy that adapts to environmental changes, which does not employ intrinsic rewards for guidance. LLaMAC employs multiple LLMs to balance exploration and exploitation, emphasizing step-wise decision-making via frequent LLM calls with rewards as feedback rather than RL-based low-level exploration with sparse rewards(our setup).

[1]Lazy agents: a new perspective on solving sparse reward problem in multi-agent reinforcement learning.
[2]Learning When to Explore in Multi-Agent Reinforcement Learning. TCYB 2023.
[3]Controlling Large Language Model-based Agents for Large-Scale Decision-Making: An Actor-Critic Approach.

We sincerely appreciate Reviewer kuvr's efforts and some positive feedback. The following addresses the concerns.

1.Connection with LLM-based Methods

• Connections:
  (1)We evaluated the most relevant LLM-based methods in Fig.3: LLM step-wise exploration goals generation, exemplified by ELLM[1], and LLM-based reward design, exemplified by Eureka[2]. LEMAE utilizes LLM's discrimination and coding capabilities, eliminating the need for state captioner and frequent LLM calls in ELLM, as well as the high information demands(e.g., environment codes in Eureka) and reliability issues(as discussed in Appendix B.1) associated with reward design.
  (2)As suggested, we evaluate ProgressCounts[3], a recent LLM-based method, in revised Appendix F.8, which combines LLM reward design and count-based exploration. LEMAE consistently outperforms it, highlighting the effectiveness of LEMAE in better bridging LLM with MARL |task|LEMAE|ProgressCounts| |-|-|-| |Pass|1.0±0.0|0.20±0.40| |Push-Box|1.0±0.0|0.71±0.41|

• Fair Information: We keep consistent prompt information across all LLM-based methods to ensure fairness, including task descriptions and state forms. This has been clarified in the manuscript.

• Reward Generation Failure: In Appendix B.1, we discussed the insights behind LLM discrimination and the challenges of direct reward generation: Discrimination is preferable to generation as it requires less task information requirements and allows for easier error detection and correction. Intuitively, in partially observable tasks like Pass, key state/reward generation is unreliable and even infeasible due to missing information, such as hidden switch positions, explaining Eureka's poor performance.

2.Applications in Robotics Control

As suggested, we evaluate LEMAE on MaMuJoCo[4], a MARL robotics benchmark, in Appendix F.7 of the revised manuscript. We adapt the tasks to emphasize exploration with sparse rewards for achieving high velocity.

LEMAE is comparable to the baseline trained with human-designed dense rewards. This aligns with previous conclusions and indicates its potential for complex tasks, owing to the reliability of LLM key state discrimination. Notably, the extensions to single-agent RL(Appendix F.4), image-based tasks(Appendix F.2) and robotics applications(here) demonstrate LEMAE is a general method for bridging LLM and RL for efficient exploration, with potential applicability to diverse and complex tasks.

3.Explanation for MA

We clarify that this work represents a pioneering attempt to address efficient exploration in MARL with LLM, an important domain with broad applications and a current research gap. Compared to prior LLM-based methods that primarily target single-agent scenarios, LEMAE is designed to tackle the unique challenges in MARL: (1) LLM-based key states discrimination to provide reliable priors during training, particularly for high-dimensional and partially observable MARL tasks; (2) Labor-division-oriented prompt designs to reduce manual effort and foster multi-agent cooperation; (3) Subspace-based Hindsight Intrisic Reward to improve policy guidance and alleviate manual reward design; and (4) Key States Memory Tree to organize exploration with memory, reducing complexity by focusing on a meaningful state subspace within the exponentially expanded state space.

Despite primarily focusing on multi-agent tasks, LEMAE is a general method for improving efficient exploration in RL and can also be easily extended to single-agent settings, as shown in Appendix F.4.

4.Connections with Go-Explore

Thanks for the suggestion. Go-Explore[5] is an influential work tackling exploration in RL.

• The similarities between our KSMT and the archive in Go-Explore lie in both methods organizing exploration through memory, i.e., by selecting possible historical states to explore.\
• The differences and partial contributions of LEMAE are as follows: (1) Key states are semantically meaningful and task-critical, whereas the archived states in Go-Explore are randomly explored; (2) Our KSMT samples key states based on actual key states transitions, enhancing its reliability; (3) We propose Explore with KSMT to balance exploration and exploitation, thereby reducing exploration complexity by focusing on a more meaningful state subspace.

We've cited Go-Explore and added the above discussion in updated manuscript Appendix F.5.1.

[1]Guiding pretraining in reinforcement learning with large language models
[2]Eureka: Human-level reward design via coding large language models
[3]Automated Rewards via LLM-Generated Progress Functions
[4]Facmac: Factored multi-agent centralised policy gradients
[5]Go-explore: a new approach for hard-exploration problems

Dear Reviewer kuvr,

We greatly appreciate your time and effort in reviewing our paper. We want to check if responses have addressed your concerns as the deadline is approaching.

Your engagements mean a lot to us, and it would be appreciated if you reconsider the evaluation after reading the rebuttal and the updated manuscript. Importantly, thanks for your constructive suggestions.

Best regards,

Authors

We sincerely appreciate Reviewer Kmbo's efforts and positive feedback on the importance, broad application, and comprehensive experiments. The following addresses the concerns.

1.Applications in Robotics Control

Following your suggestion, we evaluate LEMAE on MaMuJoCo [1], a MARL robotics benchmark. We adapt the tasks to emphasize exploration with sparse rewards for achieving high velocity.

LEMAE achieves performance comparable to the baseline trained with human-designed dense rewards. This observation is consistent with previous conclusions. LEMAE benefits from the reliability of the proposed LLM key states discrimination, and the results underscore LEMAE’s potential for handling complex tasks. Additional details have been added into the revised manuscript(Appendix F.7).

In fact, the use of discrimination instead of direct generation has relaxed the application assumption to only state semantics(which can be further eliminated with multi-modal models), eliminating the need for environment codes or state captioners required by prior methods, as discussed in Appendix B. LEMAE has been extended to single-agent RL(Appendix F.4), image-based tasks(Appendix F.2) and robotics applications(here), implying that it is a general method for bridging LLM and RL for efficient exploration, with potential applicability to diverse and complex tasks.

2.Clarification of MARL Consideration

We clarify that this work represents a pioneering attempt to address efficient exploration in MARL with LLM, an important domain with broad applications and a current research gap. Compared to prior LLM-based methods that primarily target single-agent scenarios, LEMAE is designed to tackle the unique challenges in MARL: (1) LLM-based key states discrimination to provide reliable priors during training, particularly for high-dimensional and partially observable MARL tasks; (2) prompt designs to reduce manual effort and foster multi-agent cooperation through encouraging labor division among agents; (3) Subspace-based Hindsight Intrisic Reward to improve policy guidance and alleviate manual reward design; and (4) Key States Memory Tree to organize exploration with memory, reducing complexity by focusing on a meaningful state subspace within the exponentially expanded state space.

Specifically, regarding (2), as shown in Sec. 4.2, we explicitly prompt LLM to prioritize role division among agents to enhance multi-agent collaboration. This straightforward design yields impressive results: Fig. 1(d)'s visitation map shows an organic division of labor emerging, while the discrimination functions in Fig. 4 provide an intuitive explanation of this formation.

3.Writing improvement

Thanks for your suggestions. We have polished the method introduction in Sec.1.
Regarding the phrase Choices are More Important than Efforts in the title, we used it to emphasize our idea that choosing task-relevant guidance is better for exploration efficiency in RL than expending aimless or redundant effort. LLM is chosen as a tool to provide this guidance, as it has been shown to possess priors for task understanding across various tasks.

References:

[1] Facmac: Factored multi-agent centralised policy gradients