Strategist: Self-improvement of LLM Decision Making via Bi-Level Tree Search

Some results measured have no or confusing error analysis. For example, in Table 1, the median scores and IQR of quantities measured are reported, but the error range of the median scores is not reported. I recommend the authors also to report median error, in which the error is introduced because number of experiments is limited. Moreover, I wonder if enough duplicated experiments are carried out to prove that Strategist is better than BFS with Thought w.r.t. Avalon Value Heuristic. Also the presentation in Figure 4 is a bit chaotic.

We thank the reviewer for the valuable suggestions. Based on your feedback, we have updated our error analysis and improved the presentation of results to provide greater clarity and robustness.

1. Revised Error Analysis:
   Following your suggestion, we now report standard error (SE) instead of the interquartile range (IQR) in the tables. SE better reflects the precision of our estimates, particularly given the large number of experiments conducted. Multi-agent, hidden-information decision-making settings like Avalon naturally exhibit high variance due to the stochastic nature of strategies and interactions between players. Reporting IQR alone did not capture the full scope of our experimental efforts to mitigate noise, and SE provides a more accurate depiction of the results.

2. Statistical Significance Tests:
   To ensure the robustness of our findings, we also conducted statistical significance tests for our key results:

   • Table 1: A one-way ANOVA test shows a statistically significant difference between the means of 'Our method' and other methods, with an F-statistic of 29.49 and a p-value < 0.001.
   • Table 2: A t-test comparing our 'LLM' method against 'RL' yields a t-statistic of 4.35 and a p-value < 0.001, indicating significant performance differences.
   • Table 3: A one-way ANOVA test confirms a significant difference between 'Our method' and other methods (F-statistic of 4.08, p-value ≈ 0.0299).

These results validate that STRATEGIST consistently outperforms baseline methods, including BFS with Thought, even in challenging and noisy environments like Avalon.

3. Improved Figure 4 Presentation:
   We have reworked the presentation and description of Figure 4 to enhance clarity and reduce any perceived chaos. The updated figure now includes a better structured explanation in the text. These changes aim to better communicate the insights derived from the scaling experiments and interaction effects between high-level search and low-level refinement.

By incorporating these revisions, we provide a more accurate and transparent depiction of STRATEGIST’s performance, emphasizing its robustness to noise and its consistent ability to outperform competing methods. Thank you for your thoughtful feedback, which has greatly improved the quality and presentation of our results.

What happens when the LLM generates syntactically correct but semantically inconsistent or illogical strategies? How does the framework detect and handle such cases?

Thank you for raising this important question. Detecting and addressing semantically inconsistent or illogical strategies is a critical aspect of STRATEGIST's robustness.

The framework incorporates several mechanisms to handle such cases effectively:

1. Filtering Through Self-Play:
   Strategies that are semantically inconsistent or illogical are naturally penalized during the self-play process. In STRATEGIST, the self-play simulations evaluate strategies based on their performance in actual gameplay scenarios. Illogical strategies typically result in poor outcomes (e.g., low win rates or ineffective dialogue interactions), and these poor-performing strategies are pruned out during the iterative improvement process. This ensures that only consistent and effective strategies remain by the end of the self-play refinement.

2. Feedback-Driven Improvement:
   STRATEGIST uses detailed feedback from self-play to guide the revision of strategies. The feedback signals include win rates, reward values, and discrepancies between predicted and actual outcomes during gameplay. For example, Monte Carlo Tree Search (MCTS) not only executes actions based on a strategy but also evaluates the outcomes to detect inconsistencies. When inconsistencies are identified (e.g., a strategy leading to nonsensical outcomes or contradicting earlier steps), this feedback informs the improvement process, prompting the LLM to revise the problematic parts of the strategy.

3. Idea Queue and Modular Refinement:
   The framework's modular refinement process ensures that strategy improvements are incremental and interpretable. Each iteration isolates specific components of a strategy for enhancement, which reduces the likelihood of introducing new inconsistencies. The idea queue maintains a library of successful refinements, helping guide the search process toward logical and effective strategies.

4. Population-Based Selection:
   STRATEGIST conducts population-based self-play, where multiple strategies are evaluated in a round-robin format. This evolutionary approach favors strategies that consistently perform well across diverse opponents and scenarios. Semantically inconsistent strategies tend to underperform in such competitive settings and are systematically eliminated.

By combining these mechanisms, STRATEGIST not only filters out illogical strategies but also actively improves strategy quality through iterative refinement. This ensures that the final strategies are both semantically coherent and practically effective in achieving desired outcomes. If you have further suggestions on enhancing these processes, we would be delighted to consider them.

How does the method prevent the idea queue from becoming dominated by similar or redundant improvement suggestions?

Thank you for this insightful question. Preventing the idea queue from becoming dominated by similar or redundant improvement suggestions is essential to ensure diverse and effective strategy refinement. STRATEGIST incorporates several mechanisms to address this challenge:

1. Diversity-Oriented Prompting:
   When generating ideas, the LLM is specifically prompted to produce a diverse set of improvement suggestions. These prompts encourage variation by asking the LLM to explore different aspects of strategy refinement, such as alternative approaches to value heuristics, new dialogue patterns, or novel ways to address partial observability. By explicitly steering the LLM toward diversity, this step reduces the likelihood of generating redundant or overly similar ideas.

2. Upper Confidence Bound (UCB) Selection:
   STRATEGIST employs UCB-based sampling to select ideas from the queue, which balances exploration and exploitation. This ensures that ideas with high potential impact (based on prior performance) are prioritized while still exploring less-tested ideas. UCB's mathematical formulation inherently promotes diversity by giving underexplored ideas opportunities for evaluation, preventing the process from converging too quickly on a narrow subset of ideas.

3. Feedback-Driven Idea Evaluation:
   Each idea's effectiveness is assessed based on the improvements it brings to strategies during self-play simulations. If an idea repeatedly shows limited effectiveness or leads to redundant refinements, its priority in the queue decreases. This dynamic evaluation mechanism helps prevent the queue from being clogged with redundant or low-value suggestions.

Together, these mechanisms promote diversity and innovation in the idea queue, ensuring a wide-ranging exploration of the strategy space while systematically improving performance.

Reliability of population-based self-play simulation: the authors use round-robin games between top-ten strategies to evaluate the performance of high-level strategies. Since games like Avalon have high uncertainty and the variance of the simulation result is large, it would require many simulations (like hundreds) to get a reliable evaluation of these strategies. However, these simulations would take a long time for LLM inferences. In addition, LLM usually cannot take so many trajectories as input due to the limited context length. It would be better if the authors could provide results to justify the reliability of population-based self-play simulation results.

Thank you for this thoughtful and important point regarding the reliability of population-based self-play simulations. We recognize that games like Avalon inherently involve high uncertainty, and ensuring reliable evaluations requires many simulations. This is precisely where the bi-level structure of our STRATEGIST framework offers a key advantage.

By abstracting low-level policy refinement to high-level strategies, our method significantly reduces the computational burden of repeated LLM inferences. The LLM operates at the level of strategic abstractions, which eliminates the need to process extensive game trajectories directly, effectively addressing the context length limitation you mentioned. Furthermore, the low-level executor, which employs Monte Carlo Tree Search (MCTS), can efficiently handle hundreds of simulated games in a short time. For instance, running 512 GOPS simulations typically takes under three minutes on standard hardware, ensuring robust statistical evaluation within a practical timeframe.

Additionally, the evolutionary nature of our population-based self-play process ensures that strategies are rigorously tested against diverse opponents, leading to robust and generalizable strategies. This not only mitigates variance but also leverages the ability of STRATEGIST to iteratively improve strategies through simulation feedback, as detailed in Section 2.4 of the paper.

We hope this explanation clarifies the reliability and efficiency of our approach and highlights the strategic benefits of the bi-level framework in managing the challenges of games like Avalon. We are happy to provide further details or additional analyses if needed.

Modular improvement Assumptions: the assumption that improvement ideas are universally applicable across different strategies requires further justification. Improvement ideas may interact with specific strategies in unique ways, possibly leading to unintended consequences or limited effectiveness when applied broadly. While the authors argue that improvements are additive and generalizable, empirical evidence demonstrating this across a variety of strategies would strengthen the claim.

We appreciate the reviewer’s insightful feedback regarding the assumption that improvement ideas are universally applicable across different strategies. To address this, we have conducted an additional ablation study in the GOPS environment to empirically evaluate whether modular improvement assumptions lead to better results. Below, we present the results:

The results demonstrate that modular improvement is indeed critical for achieving self-play enhancement, as the modular approach yields a significantly positive mean point difference compared to the non-modular approach, which shows a slight negative impact. This supports our argument that modular improvements are not only additive but also generalizable across different strategies.

We thank the reviewer for their suggestion, which has helped us strengthen our claim with additional empirical evidence.

Dear Reviewer u9ZM,

We hope this message finds you well. This is a gentle reminder that we are still awaiting your response regarding our submission.

We completely understand how demanding your schedule may be and deeply value the time and effort you dedicate to this important process. Your insights have been incredibly valuable, and we would be grateful for any additional feedback or clarifications you might be able to provide.

Thank you once again for your thoughtful review and support in strengthening our work. We look forward to hearing from you at your earliest convenience.

Warm regards,

The Authors

The differences and advantages of the self-play mechanisms of STRATEGIST in improving the strategy against previous related work on self-play for LLMs is unclear. It would be helpful to provide a clear comparison (e.g. a table) between the self-play mechanism in STRATEGIST and previous self-play methods for LLMs (e.g. [1] [2] ...) .

We thank the reviewer for the suggestion of a comparison table, which is an amazing addition to our paper. We have added the table to the paper as suggested (Table 5). This helps us highlight some of the core contributions of Strategist which may not be clear to the reader. We highlight some of the key differences and novelties of our paper in the next question.

What makes the self-play method in STRATEGIST better than previous self-play methods for LLMs, in terms of improving the LLM-induced strategy? I would expect a clear comparison against previous self-play methods in LLMs both in terms of the methodology (as mentioned in the weakness) and experiment study (For instance, ablation studies comparing STRATEGIST to other LLM self-play methods).

Thank you for your thoughtful feedback. We appreciate the opportunity to clarify and expand on the distinctions between STRATEGIST and previous self-play methods for LLMs, as well as to address your request for comparative analysis.

---

Key Differences Between STRATEGIST and Existing Self-Play Methods:

1. Hierarchical Strategy Improvement:
   STRATEGIST introduces a bi-level approach where high-level strategies (e.g., value heuristics or dialogue guides) are iteratively improved. This contrasts with other self-play methods that typically focus on refining low-level actions directly. The abstraction of high-level strategies enables more efficient exploration and generalization of strategic principles, as demonstrated in the evolutionary process described in Section 2.2.

2. Parameter-Free Framework:
   STRATEGIST eliminates the need for parameter tuning and human-annotated training data, making it a truly non-parametric framework. For example, unlike methods like Cicero that rely on large-scale human data for fine-tuning, STRATEGIST achieves superior performance solely through self-play and simulated feedback.

3. Advanced Low-Level Refinement with Tree Search:
   While other methods often prompt LLMs directly for actions, STRATEGIST incorporates Monte Carlo Tree Search (MCTS) to refine decisions informed by high-level strategies. This enhances the precision of decision-making, as elaborated in Section 2.3.

4. Partial Observability Handling:
   STRATEGIST explicitly models belief updates to address partial information settings, such as those in multi-agent games like Avalon. In contrast, many LLM-based agents, including ReAct and ReCon, do not explicitly handle such complexities, as detailed in Section 3.5.

5. Advanced Skill-Learning Process:
   STRATEGIST uses an innovative approach involving a strategy library and idea queue to guide incremental improvements. The strategy library maintains a tree structure of evolving strategies, while the idea queue enables modular, targeted refinements by tracking the effectiveness of improvement ideas. This approach avoids confounding factors in strategy development and ensures that the most impactful ideas are systematically explored, as described in Section 2.3.3.

---

Comparative Experiments and Ablation Studies:

We have conducted comprehensive ablation studies comparing STRATEGIST to related methods, including ReCon and DeepRole, in partially observable, multi-agent settings. Tables 1, 2, and 4 in the paper provide detailed comparisons across various metrics such as win rate, dialogue generation accuracy, and strategy evolution efficiency. These results highlight STRATEGIST's superior ability to balance generalization (via high-level strategies) and precision (via tree search refinement).

---

Additional Human Experiments:

To ensure broad applicability, we also evaluated STRATEGIST against LLM-agents implemented in different experimental settings. These experiments included human-player interactions, where STRATEGIST achieved comparable results against humans as shown in Section 3.1. This directly addresses the need for comparative performance studies against other agents in real-world scenarios.

---

We hope this addresses your concerns regarding the methodological and experimental comparisons.

[1] Yao Fu, Hao Peng, Tushar Khot, and Mirella Lapata. Improving language model negotiation with self-play and in-context learning from ai feedback. arXiv preprint arXiv:2305.10142, 2023.

[2] Cheng, Pengyu, et al. "Self-playing Adversarial Language Game Enhances LLM Reasoning." arXiv preprint arXiv:2404.10642 (2024)

The results provided compelling insights:

1. Win Rate: STRATEGIST achieved a win rate comparable to human players, demonstrating that it is competitive in a mixed human-AI setting. Specifically, STRATEGIST maintained a win rate of approximately 33.3%, while humans achieved 36.7%, within the standard error bounds.

2. Concealment and Randomization: STRATEGIST outperformed human players in its ability to conceal its identity. Analysis of voting patterns revealed that human players exhibited role-specific behavior, which made their identities easier to deduce. In contrast, STRATEGIST employed strategic randomization in its actions, resulting in more uniform patterns that reduced information leakage and made it significantly harder for other players to infer its role. This advantage is particularly beneficial in a game like Avalon, where identity concealment is a critical component of success.

3. Reasoning and Cooperation: While STRATEGIST excelled in concealment, it slightly lagged behind human players in reasoning and cooperative play. Participants noted that STRATEGIST's reasoning process sometimes lacked the nuanced social and deductive elements of human interactions. For example, STRATEGIST struggled to anticipate and adapt to complex, nonlinear reasoning strategies employed by human players.

4. Adaptability: STRATEGIST demonstrated strong adaptability to human playstyles over repeated games. Post-game surveys indicated that participants found the agent’s responses increasingly tailored to their strategies, highlighting its ability to learn and improve even in ad-hoc scenarios.

5. Role-specific Performance: In its role as Merlin, STRATEGIST minimized information leakage by employing randomized voting strategies, aligning with its concealment strengths. However, as a Servant of Arthur or Minion of Mordred, it occasionally failed to coordinate effectively with teammates, reflecting a gap in understanding team dynamics compared to human players.

The survey results, summarized in Table 1 and visualized in Figures 3 and 4 of the revised paper, corroborate these findings. Participants expressed that STRATEGIST's unique strengths in adaptability and concealment made it a challenging and engaging opponent, although they noted areas for improvement in social reasoning and team-oriented behaviors.

We believe these human evaluation results significantly strengthen the paper by providing a well-rounded assessment of STRATEGIST’s real-world performance and offering valuable directions for future research. Thank you again for your excellent suggestion, which helped us enhance the scope and depth of our study.

Comparison of Bi-Level Structure: Cicero also uses a bi-level structure, although in a different way as this paper proposes: In Cicero, it uses iterative learning methods to choose the intent at the high-level, and uses LLM to generate low-level actions. Cicero's bi-level structures ensures strategic randomization at the high level. In this paper, it is not well explained why this paper's bi-level structure is more effective than Cicero's.

Thank you for highlighting the comparison with Cicero’s bi-level structure. We recognize the importance of clarifying the unique motivations and applications of the bi-modular structure in our framework compared to Cicero. Below, we detail the distinctions and provide further justification for the choices in our approach.

In Cicero, the bi-modular structure serves a specific purpose: integrating strategic reasoning with dialogue generation. Cicero’s Intent Model is responsible for proposing action intents, which are then passed to the Dialogue Model to generate natural language outputs. This design allows Cicero to handle both discrete actions that require planning and reasoning, as well as dialogue which requires language abilities. (Continued on the next comment due to word count constraints.)

Conclusion

We hope this explanation clarifies our design decisions and addresses the reviewer’s concerns. By incorporating the suggested works into our discussion, providing additional baselines, and presenting new quantitative comparisons, we aim to strengthen the rigor and contextualization of our contributions.

Thank you again for the thoughtful feedback, and we look forward to any additional suggestions for improvement.

Limited Analysis on Strategic Randomization: Strategic randomization is essential in hidden-role games like Avalon. However, the experiment section does not show how well STRATEGIST presents deceptive behavior in a properly randomized fashion.

That is an excellent suggestion and we agree that randomization is important in these games. We have included an additional analysis of actions taken by the Strategist agent, which we show in Figure 3 in the paper. We also produce the results of Figure 3 in a table below, also the figure is way easier to understand:

Voting Action Distribution and % Correct Vote

Voting Action Distribution

% Correct Vote

We see that indeed the Strategist chooses a random mixture of actions to take. Moreover, the action distribution is similar no matter whether Strategist is playing as Merlin, a good Servant, or a Evil character, meaning that opponents cannot easily discern the identity of the Strategist agent based on the actions it takes.

Absence of Human Evaluation: Despite STRATEGIST's applicability to discussion-based games, there is no reported evaluation of the model's interactions with human players, which would provide insights into its performance in realistic scenarios.

Thank you for your insightful comment regarding the absence of human evaluation in the original submission. We completely agree that evaluating STRATEGIST's interactions with human players is crucial to understanding its performance in realistic scenarios. In response to your feedback, we conducted extensive human experiments in the six-player Avalon setting and have included the results in the revised paper.

For these experiments, we recruited ten participants who were randomly assigned to play alongside or against STRATEGIST agents across 30 games. Each game involved roles such as Merlin, Assassin, Minion of Mordred, and Servants of Arthur, with STRATEGIST controlling five out of the six players. The human players evaluated STRATEGIST's performance on key metrics, including reasoning, deduction, cooperation, concealment, and adaptability. (Continued on the next comment due to word count constraints.)

Lack of Competitive Baselines: The paper compares with methods that do not use LLM at all (like DeepRole) and methods that only uses LLM but no RL. However, the comparisons exclude more recent RL-LLM hybrid methods that would provide a fairer benchmark for STRATEGIST's effectiveness. In fact, in the past two years, there are a number of papers that combines RL with LLM to play complex strategic multi-agent games that involve natural-language based communication. For example, the paper mentioned the Cicero paper by FAIR, but there is no comparison with the method used in the Cicero paper. There are a lot more papers following up the Cicero paper, and can potentially be used for games like Avalon. Here are a few example papers: 1). Exploring large language models for communication games: An empirical study on werewolf. 2). Language agents with reinforcement learning for strategic play in the werewolf game; 3). Enhance reasoning for large language models in the game werewolf; 4). Agent-pro: Learning to evolve via policy-level reflection and optimization.

We sincerely appreciate the reviewer’s detailed comments. Below, we provide a detailed explanation of our choice of baselines, the distinctions between our approach and Cicero-like methods, and additional steps we have taken to address this concern.

Parameter-Free vs. Data-Dependent Approaches

Our work focuses on a parameter-free approach that does not require access to human-annotated data or large-scale fine-tuning of LLMs. This design decision aligns with our goal of proposing a lightweight, training-free framework that demonstrates the emergent strategic capabilities of LLMs through self-play without additional training.

In contrast, Cicero and related methods rely heavily on extensive human gameplay datasets to fine-tune models to mimic human behavior, often requiring millions of annotated samples. For example:

• Cicero leverages human data to train both its dialogue and planning modules, combining supervised learning and reinforcement learning (RL) in a resource-intensive pipeline.
• Follow-up works, such as "Enhance Reasoning for Large Language Models in the Game Werewolf" and "Language Agents with Reinforcement Learning for Strategic Play in the Werewolf Game," adopt similar methodologies, relying on data and parameter tuning to learn strategies specific to those games.

While these approaches are undoubtedly impressive, their reliance on data-heavy pipelines makes them fundamentally different from our training-free approach, which only assumes access to the LLM and the rules of the game. Consequently, a direct comparison would not be entirely fair or aligned with the scope of our work. This distinction has been clarified in the updated manuscript.

Baselines and Justification for Comparisons

To ensure meaningful evaluations, we compare against other parameter-free or minimally parameterized methods, such as:

1. DeepRole: A reinforcement learning-based approach designed for Avalon, which does not use LLMs or human data.
2. ReCon: A parameter-free approach that uses an LLM to think about what other players are thinking before acting
3. ReAct: A parameter-free approach that uses an LLM to reflect before acting
4. AlphaGo-like Methods: These methods leverage self-play for strategy optimization without human annotations, serving as a closer conceptual comparison.

These baselines allow us to isolate the effectiveness of our framework in a resource-constrained setup, showcasing its ability to achieve human-level performance without additional training or data. Results of these comparisons are presented in Tables 2 and 4 of the manuscript.

Addressing the Reviewer's Concern: Additional Baselines

To address the reviewer’s suggestion, we agree that a broader contextualization of our work is valuable, and we have taken the following steps:

1. Added Related Work Discussion: We have included a detailed discussion of Cicero and the reviewer-suggested works, such as:

   • Exploring Large Language Models for Communication Games: An Empirical Study on Werewolf
   • Language Agents with Reinforcement Learning for Strategic Play in the Werewolf Game
   • Enhance Reasoning for Large Language Models in the Game Werewolf
   • Agent-Pro: Learning to Evolve via Policy-Level Reflection and Optimization

   These discussions now appear in the updated Related Works section, providing readers with a comprehensive overview of recent advancements and highlighting distinctions between our framework and these methods.

2. Inclusion of Human-Level Baselines: To facilitate easier comparison with prior work, we have included a new human baseline for performance comparison, as the reviewer suggested. We elaborate more on this later. (Continued on the next page due to word count constraints.)

Dear Reviewer XeVt,

We hope this message finds you well. We recently submitted our rebuttal and would greatly appreciate your feedback on our responses, which include human evaluation experiments and strategic randomization analysis. Additionally, we have provided a web application to allow you to experience the agent firsthand.

We understand your schedule is demanding and deeply appreciate the time and effort you dedicate to the review process. Your insights are invaluable to us, and we are eager to address any additional questions or concerns you may have.

Thank you again for your thoughtful review, and we wish you a very Happy Thanksgiving! We look forward to hearing from you.

Best regards,

Authors

We have also conducted additional experiments to evaluate our Strategist framework against Agent-Pro. The results of this comparative analysis are presented below:

Analysis of Results

As shown above, Strategist outperforms Agent-Pro in win rate by a significant margin, demonstrating its superior strategic reasoning and adaptability in partial information settings like Avalon. Moreover, the average number of tokens per round—a proxy for computational efficiency—indicates that Strategist achieves this improved performance without a significant increase in token usage, highlighting its efficiency.

The improved win rate can be attributed to the training-free, bi-level framework employed by Strategist, which leverages the emergent reasoning capabilities of large language models (LLMs) without relying on belief modeling or parameterized updates. By contrast, Agent-Pro’s reliance on policy-level reflection and belief optimization introduces computational overhead and may limit its adaptability to new scenarios without additional training.