Knowing What Not to Do: Leverage Language Model Insights for Action Space Pruning in Multi-agent Reinforcement Learning

We thank the reviewer for the sincere comments. We hope we can address your concerns below.

W1: The experimental settings, though varied, may not fully represent truly complex real-world environments.

We disagree with the reviewer’s point. In our experiments, we aimed to evaluate our approach using simulators of real-world applications. Among our selected environments, MABIM is a multi-level inventory management simulator built on a real-world inventory dataset [1]. Our experimental scenarios tested up to 1500 agents, demonstrating high scalability. SUMO is a microscopic traffic simulation environment based on real-world road networks and traffic flow data, widely used in MARL research [2-4]. Additionally, in the attached PDF, we have included experiments conducted in the active voltage control environment [5], which are also built on real-world datasets.

Although gaps exist between simulated and real-world environments, we believe that the results obtained from these simulators still demonstrate the potential of our approach in real-world applications.

W2: The framework lacks a theoretical guarantee on how pruning actions with LLMs affects the optimality of learned policies, leaving open the possibility that some optimal actions may be discarded during exploration.

In Proposal 1, we prove the existence of an exploration function that can improve the performance of any given policy. The theoretical proof is detailed in Appendix A. However, when using an LLM to generate exploration functions—as with most LLM-integrated approaches—it's challenging to provide strict theoretical guarantees due to the unpredictable nature of LLM outputs. Nonetheless, our experimental results in Tables 1 and 2 demonstrate that our framework consistently outperforms all baselines in most scenarios. This empirically validates the LLM's effectiveness in pruning the action space within our framework.

W3: The computational efficiency comparisons may not be entirely fair, as different algorithms could have varying levels of computational complexity, especially with the use of LLMs, which are resource-intensive.

In Appendix E.1, we provide detailed comparisons of the training time, GPU utilization, and LLM resource consumption of eSpark versus baseline algorithms. As mentioned in Section 4.3, eSpark only invokes the LLM to generate or edit exploration functions based on feedback. Beyond these sparse invocations (limited to 10 times in our current settings), the exploration function interacts directly with the MARL policy.

Furthermore, in homogeneous MARL environments, a single exploration function is shared across all agents. This design ensures that the LLM invocation cost remains constant, regardless of the number of agents or training steps.

W4: The paper does not include comparisons with straightforward, rule-based action space pruning techniques, which could serve as useful baselines and provide clearer insights into the added value of the LLM-driven approach.

There may be a misunderstanding. We have indeed included comparisons with rule-based action space pruning methods in Section 5.3 of the paper. In addition to random pruning, we introduced Upbound pruning and (S,s) pruning for the MABIM task, and pruning methods based on MaxPressure for the SUMO task. Detailed descriptions of these methods are provided in Appendix D.3, and their performance comparisons with eSpark are presented in Tables 3 and 4.

W5: While the framework performs well with homogeneous agents, it is unclear how well it would generalize to heterogeneous agents or to tasks with sparse rewards. The lack of experiments in such scenarios limits the generalizability of the proposed method.

We acknowledge that these are limitations of our current work, which we have already stated on line 528. However, we have also proposed some potential solutions in Section 6, which we reiterate here.

For heterogeneous agent scenarios, we proposed to extend eSpark to by grouping agents based on their distinct action spaces and reward functions, then providing unique exploration functions for each group. This approach would enable eSpark to adapt to heterogeneous agent environments with minimal modifications.

For sparse reward settings, we could instruct the LLM to reference human-derived heuristics for such tasks. Using these heuristics, we could design intrinsic rewards to provide feedback for the LLM's pruning mechanism, as in [6] for instance.

Expanding eSpark to handle heterogeneous agents and sparse rewards presents an exciting avenue, and we will leave these questions for future research.

W6: The effectiveness of the eSpark framework depends heavily on the quality of the LLM outputs. Errors in exploration function generation or feedback handling could negatively impact performance, yet the paper provides limited discussion on handling these risks.

Please see the answer of Q2.

Thank you for your detailed feedback. We hope our responses can address your concerns.

Q1: Did authors test what will be the performance with other base MARL algorithms other than IPPO?

We have included the performance of eSpark combined with MAPPO in the 100 SKUs scenarios of MABIM in Figure 22 of the supplementary materials. The results demonstrate that, whether combined with IPPO or MAPPO, our proposed framework consistently outperforms all MARL baselines. It achieves stable improvement and the best performance across all scenarios, showcasing the strong generalization capability of our method.

Q2 : While the paper states that no complex prompt engineering is needed, did the authors experiment with different prompts, and how did that influence the exploration function quality?

Prompt engineering is crucial for tasks involving LLMs. During eSpark's development, we experimented with various prompt types (e.g., excluding the LLM checker, modifying feedback instructions, adding or removing task-related components). These modifications influenced the LLM's generation, comprehension, and refinement abilities, thereby impacting the quality of exploration functions.

When finalizing the prompt design, we adhered to two key principles:

1. Minimal manual input: Users need only provide essential environment-specific information. The framework automatically handles exploration function generation, evolutionary search, and function refinement through fixed prompts, ensuring quick adaptability across different environments.
2. High-quality generation: The LLM must understand task requirements, conditions, and feedback to produce exploration functions that are executable, task-compliant, and effective in guiding MARL to explore redundant action spaces.

In our final design, users input only a few RL formulations (mostly derivable from the environment) and a task description. Our framework then automatically generates exploration functions, trains models, and builds feedback loops. Experimental results show that our method consistently outperforms baselines across most scenarios.

Q3 :It seems like the authors only compare their method against the random pruning and heuristic pruning methods. There are other works that the authors have mentioned in the related work section for pruning. Have authors considered comparing with those baselines?

We mention several approaches in the Related Work section, but these methods face significant challenges when directly applied to our task. The method in [1] requires an elimination signal from the environment to learn the action elimination module, which is typically unavailable. The approach in [2] requires a high-quality offline dataset for pretraining. The method in [3] uses LLM knowledge to filter actions in text-based environments, but such pruning strategies are difficult to transfer directly to data-driven MARL environments. The approaches in [4-6] rely on manually designed data structures based on prior knowledge to filter actions, which lack generalizability. To the best of our knowledge, we have not found any pruning methods sufficiently generalizable for our task.

We thank the reviewer for the insightful comments! We hope we can address your concerns below.

W1: Only compare with MARL and heuristic methods, lack comparisons with existing LLM-based methods

We agree with the reviewer’s perspective on the importance of comparing eSpark with existing LLM-based methods. However, we find it challenging to adapt existing LLM-based methods to our task. Most existing LLM-based systems focus on textual-related tasks, and our task presents the following difficulties:

1. No Abstract Actions: The environments used in prior studies [1,2,4] generally include well-designed textual action interfaces or directly utilize text as actions. These abstract actions always consist of a series of low-level actions contain explicit meaning, reducing the cost of LLM calls while being easy to evaluate. In contrast, most data-driven RL environments provide only single-step action interface, making it difficult for an LLM to evaluate the consequences of each individual action effectively and increasing the calling cost.
2. Multi-Agent Environments: The environments considered in [1-4] are primarily single-agent settings. In such scenarios, LLM-based methods only need to evaluate actions and observations for a single agent, avoiding the complexity of joint action spaces. However, in MARL tasks, the action space and the number of actions to output grow significantly as the number of agents increases. Directly using LLM-based methods to assist in action selection for MARL tasks would result in prohibitive computational costs.

To the best of our knowledge, we have not found any existing algorithms that can be directly applied to our task. We would greatly appreciate it if the reviewers could point us toward any existing methods that might address these challenges. Besides, we will conclude the relevant literature and challenges in the revised version the paper.

W2: The environments chosen in the paper do not include classical MARL benchmarks, such as SMAC.

Please refer to the answer of Q4.

W3: The paper does not provide detailed analysis or case studies of the action masks generated by the LLM; it mainly focuses on overall performance

In Section 5.3, Figure 2 illustrates the policy action distribution, which effectively analyzes the action masks. These masks, edited based on policy feedback and integrated with specific policies, cannot be evaluated in isolation. However, they significantly influence policy exploration. Consequently, we assess the effectiveness of the action masks by examining the behavior of the final learned policies. Additionally, Appendix J presents a case study that demonstrates how eSpark interprets policy feedback and refines exploration functions accordingly.

Q1: How can eSpark be extended to continuous action spaces? Does this limit its usage?

Extending eSpark to continuous action spaces is feasible. We propose modifying the exploration function in eSpark to define upper and lower bounds for the clipped action space. Agents can then restrict their action outputs to this clipped space, similar to existing continuous action space clipping methods. Two potential approaches are:

1. Clipping actions: Define upper and lower bounds for the actions, and clip any out-of-range actions to these boundary values.
2. Projection: Normalize the sampled action to [0, 1] and project it back to the specified upper and lower bounds.

We plan to implement and experiment with these approaches in future work.

Q2: In the current eSpark framework, each agent independently generates its action mask without considering collaboration between agents. Could this limit eSpark's utility in tasks requiring strong cooperation?

Our current design for generating action masks in eSpark is based on two key considerations:

1. Task-specific collaboration complexity: Complex collaboration between agents often involves task-specific topological structures. These structures can be challenging to describe linguistically (e.g., in the MABIM environment, the cooperative relationships between different SKU types are unclear) and may change dynamically over time. This complexity adds significant difficulty to prompt design and reduces eSpark's generalizability. Rather than aiming for LLMs to solve all MARL challenges, eSpark focuses on pruning the joint action space, while leaving the learning of complex inter-agent cooperation to the MARL algorithm and its interactions with the environment.
2. Iterative improvement via feedback: Although the exploration function generates action masks based solely on individual agents' observations, each iteration refines the exploration function using feedback from the overall policy reward. This approach allows the exploration function to maximize the total reward while abstracting away the underlying complexity of inter-agent structures.

Thank you for your detailed feedback and review! Below we give the response to your concerns.

W1: High Training Costs

Finding (near)-optimal policies in MARL incurs high training costs, primarily due to its inherent complexity, especially when involving numerous agents. We demonstrated in our paper that simply increasing resource consumption doesn't significantly improve performance, indicating the need for a smarter exploration strategy to accelerate training. As shown in Tables 5 and 6 in Section 5.4, our ablation study of eSpark without LLM reveals that merely increasing computational resources without action space pruning offers limited—and potentially detrimental—performance benefits. Conversely, with identical training steps and GPU usage, eSpark's unique action space pruning approach effectively leverages increased computational resources, outperforming all baselines in most scenarios.

W2: Lack of Theoretical Guarantees

In Proposal 1, we demonstrate that for any MARL policy, there exists an exploration function that can enhance its performance. However, the inherently stochastic nature of LLM outputs presents a challenge in providing theoretical guarantees on the resulting exploitation policies and their impact on optimality. This is particularly true in the MARL domain, where the optimal policy is often unknown.

Despite the lack of theoretical guarantees, we can evaluate the effectiveness of exploration functions by examining policy behaviors and experimental results. Our case study (Figure 2) comparing eSpark with baselines demonstrates that eSpark learns more interpretable and superior policies. Moreover, the results presented in Sections 5.2 and 5.3 show that eSpark consistently outperforms all baselines. These findings collectively validate the effectiveness of LLM-based pruning in MARL without compromising the pursuit of optimality.

W3: Limited Experimental Environments

To address this concern, we have evaluated all approaches on another environment: active voltage control environment [1]. We benchmarked eSpark against other MARL baselines across three provided scenarios. To evaluate performance, we adopted two indicators proposed in the paper: Control Rate (CR) and Power Loss (PL). Figure 23 of the attached PDF showcases the results. Our proposed eSpark outperforms the baselines in all experimental scenarios within this environment, demonstrating its strong generalizability across various tasks. We plan to continue exploring other MARL benchmarks in the future and would be happy to evaluate on additional environments that interest the reviewer.

Q1: Could a more compelling example be introduced to illustrate the advantages of using LLMs for generating exploration functions?

The primary advantage of using LLMs to generate exploration functions stems from their human-level reasoning ability and robust coding capabilities [2-5]. This reasoning allows LLMs to comprehend the structure and variables involved in a task and make performance-enhancing pruning decisions—the core of LLM-based pruning. Their coding capability enables the implementation of this reasoning in code form, facilitating seamless interaction with MARL policies. To address the reviewer’s concern, we have designed a more challenging sequential decision-making example, where agents collaborate at each time step to allocate resources, while the sum of resource allocation is constrained. In the attached PDF, we provide the complete problem definition and the LLM’s response. Leveraging its powerful reasoning and encoding capabilities, the LLM successfully understood the problem structure and variables, and designed a reasonable exploration function.

Q2: Specific details regarding the number of iterations required by eSpark and how the iteration count affects its performance remain unaddressed. Would it be feasible to include these additional visualizations?

We appreciate the reviewer's suggestion. In response, we have included the training curves for eSpark and the MARL baselines in Figures 22 and 23 of the attached PDF. These curves demonstrate that eSpark's performance steadily improves as feedback is collected after each iteration, coupled with evolutionary search and the regeneration of exploration functions. eSpark's performance stabilizes after approximately 10 iterations. Compared to the baselines, eSpark exhibits smoother improvement and consistently outperforms all MARL baselines across all test scenarios.

We have incorporated all changes in the supplementary material. In response to your concerns, we gave the following answers:

1. For weakness 1: While simply increasing resource consumption did not significantly improve performance, we demonstrated that eSpark could benefit from the increased computational resources (Tables 5 and 6).
2. For weakness 2: While theoretical guarantees are difficult due to LLM stochasticity, we provided experimental evidence (Sections 5.2 and 5.3, Figure 2) showing eSpark learns interpretable and superior policies, validating its effectiveness.
3. For weakness 3: We added experiments on an active voltage control environment, demonstrating strong generalizability and consistent superiority of eSpark (Figure 23).
4. For question 1: We designed a more compelling example to illustrate the advantages of using LLMs for generating exploration functions.
5. For question 2: We include training curves showing the performance of eSpark with respect of the iterations (Figures 22 and 23).
6. For question 3: We clarified some misunderstandings.

We hope our answers can address your concerns, and we look forward to your feedback.