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

## Abstract

Abstract In this paper, we propose a new method \method that utilizes LLMs to acquire new skills for playing multi-agent games through a self-improvement process.
Our method gathers quality feedback through self-play simulations with Monte Carlo tree search and LLM-based reflection, which can then be used to learn high-level strategic skills such as how to evaluate states that guide the low-level execution.
We showcase how our method can be used in both action planning and dialogue generation in the context of games, achieving good performance on both tasks.
Specifically, we demonstrate that our method can help train agents with better performance than both traditional reinforcement learning-based approaches and other LLM-based skill learning approaches in games including the Game of Pure Strategy (GOPS) and The Resistance: Avalon. \method helps bridge the gap between foundation models and symbolic decision-making methods through its bi-level approach, leading to more robust decision-making.

## 1 Introduction

Figure: Figure 1: Overview of \method. We use a LLM to generate and improve high-level strategy abstractions using environment feedback, then refine strategy into a policy using tree search or CoT.
Refer to caption: extracted/5921100/graphics/neurips_quarter-02.png

Recent studies have shown the potential of Large Language Models (LLMs) for learning skills and improving decision-making in interactive environments Wang et al. (; ; ); Xi et al. (); Zhao et al. (); Liu et al. (). However, adversarial, multi-agent environments present a significant challenge. LLMs must reason about opponent actions, plan ahead strategically, and navigate a vast policy space Kambhampati et al. (); Valmeekam et al. (); Kambhampati (). This complexity hinders the LLM’s ability to identify, understand, and translate optimal policies into effective actions.
Simply generating decision rules by querying the LLM proves inefficient and impractical in such settings. This raises two critical questions: *(1) How can LLMs effectively learn complex policies in adversarial multi-agent environments? (2) What is the best approach to improve these policies?*

This paper introduces \method, a novel framework that leverages LLMs to develop high-level strategies, represented as interpretable text, which are then refined and translated into executable policies using a low-level executor (Figure 1). Our approach combines LLM self-improvement with a hierarchical search process, operating on both a high-level strategy space and a low-level action space.

At the high level, \methodconstructs a strategy tree through an evolutionary process, iteratively testing and improving strategies via LLM-guided revisions based on self-play feedback. This process fosters the emergence of robust, adaptable strategies. To further enhance strategy improvement, we maintain a queue of "improvement ideas" sampled via a bandit algorithm to guide LLM revisions. At the low level, we employ fine-grained tree search techniques (e.g., MCTS) guided by the high-level strategy to refine the agent’s policy. We can run the policy against itself through self-play in the multi-agent strategic game, and use win-rate as final outcome reward. The reward can be backpropagated to help update the strategy.
This bi-level approach effectively integrates the generalization capabilities of LLMs with the precise planning of MCTS. Both levels are updated through simulated self-play, eliminating the need for extensive training data.

We demonstrate the effectiveness of \methodin two challenging games: the Game of Pure Strategy (GOPS) and Resistance: Avalon (Ross, ; Light et al., ), chosen for their strategic complexity and differing levels of natural language interaction. Our results show that \methodoutperforms existing LLM-based self-improvement methods and traditional RL approaches, achieving superior performance within the same computational and data budget. Furthermore, we highlight the successful integration of feedback across the different levels of our framework, demonstrating the synergistic interplay between high-level strategy improvement and low-level policy refinement.

To summarize, our main contributions are as follows:

- •
We propose a general non-parametric LLM bilevel skill-learning framework \methodin which we learn high level strategy abstractions using a LLM, that are then refined and translated into a low level policy using a low level executor. The strategy abstractions can be used to construct a strategic profile for all players in the game.
- •
We introduce a modular method of improving high level strategies using population based self-play, without any training data. We demonstrate through experiments that our improvement method outperforms other LLM improvement and skill learning methods.
- •
We apply this framework to GOPS and Avalon, complex competitive multi-turn games, and show how we can learn good policies for both dialogue and non-dialogue actions, outperforming existing agents. Some examples of good strategies learned through our method are shown in H.3 and I.3, which achieve higher win-rates against other agents.

## 2 Methodology

We cover the problem formulation, how we create high level strategy abstractions, and how we improve strategies using LLMs and self-play in the following sections.

### 2.1 Decision making setting and games

The general goal in our decision-making setting is to learn a good policy function in a sequential decision-making setting (generally formulated as a partially observable Markov decision game (POMDG)). Our strategy-learning framework is generalizable to any decision making setting.

Problem definition. Given state space $\mathcal{S}$ and action space $\mathcal{A}$, a policy function $\phi$ in policy space $\Phi$ is a mapping $\phi:\mathcal{S}\rightarrow\Delta\mathcal{A}$ where we allow $\phi$ to output a probability distribution over the actions ($\Delta\mathcal{A}$). An environment $\mathcal{E}=\langle\mathcal{S},\mathcal{A},\mathcal{N},T,R,A,\phi_{\epsilon}\rangle$ defines the state space $\mathcal{S}$, the action space $\mathcal{A}$, a set of actors $\mathcal{N}$, a transition function $T:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$, a reward function $R:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{|\mathcal{N}|}$ that specifies intermediate rewards for each actor, an action function $A:\mathcal{S}\rightarrow\mathcal{N},\mathcal{P}(\mathcal{A})$ that specifies which actor may take what legal actions at some state where $\mathcal{P}$ is power set, and $\phi_{\epsilon}$, the policy function for the environment actor. Note that transitions are deterministic in our notation, and stochastic transitions are handled by the environment actor $\epsilon\in\mathcal{N}$ instead, so we cover stochastic, deterministic, multi-agent, and single agent cases. For a partial information setting, we also have a space of information sets $\mathcal{I}$ and a function $H:\mathcal{S}\times\mathcal{N}\rightarrow\mathcal{I}$ that maps from hidden states and actors to hidden information sets. Hence, $\phi:\mathcal{I}\rightarrow\Delta\mathcal{A}$ is a function from information sets to action distributions instead. A strategic profile $\boldsymbol{\phi}=[\phi_{i}]_{|\mathcal{N}|}$ describes the policies for every player $i\in\mathcal{N}$.

Let $f:\Sigma\rightarrow\Phi$ be the function that maps strategies to policies. A high-level strategy $\sigma\in\Sigma$ helps parameterize policies so that we can search over the lower dimension $\Sigma$ space instead of $\Phi$. Let $\Phi_{-i}$ denote the space of possible opponent policies, where $-i$ are the indices of players other than i.
Then our goal is to find the optimal strategy $\sigma_{i}$ that approximates finding the optimal policy given the policies of the other agents $\phi_{-i}$, i.e.

$$ $\mathop{argmax}_{\sigma_{i}}\underset{\tau\sim(f(\sigma_{i}),\phi_{-i})}{ \mathbb{E}}\left[\sum_{(s,a)\in\tau}R_{i}(s,a)\right]\approx\mathop{argmax}_{ \tau\sim(\phi_{i},\phi_{-i})}{\mathbb{E}}\left[\sum_{(s,a)\in\tau}R_{i}(s,a)\right]$ $$

where $\tau=(s_{0},a_{0},...)$ is the simulated trajectory according to the strategic profile $(\phi_{i},\phi_{-i})$ and the transition function $T$, with $a_{t}\sim\phi(a_{t}|s_{t})$ and $s_{t+1}=T(s_{t},a_{t})$. Thus, a key part of these settings involves learning the probable strategic profile of other players, usually by assuming that they play optimally like in a Nash equilibrium  (Perolat et al., ).

The state space, action space, and actor space are different depending on the setting. In non-stochastic, single agent settings such as question answering  (Yang et al., ; Wang et al., ; Shridhar et al., ; Thorne et al., ), $\mathcal{N}=\{0\}$. In stochastic single agent settings such as web browsing  (Yao et al., ; Deng et al., ; Zhou et al., ), $\mathcal{N}=\{\epsilon,0\}$ where we add an environment agent $\epsilon$. We specifically focus on adversarial, multi-agent stochastic game ($\mathcal{N}=\{\epsilon,0,1,...\}$)
settings where the other agents are actively working against each other. In non-dialogue-based card games such as GOPS (see B for rules) for example, $\mathcal{S}$ consists of the cards played so far, $\mathcal{N}=\{\epsilon,0,1\}$ for players 1 and 2 respectively, and $\mathcal{A}$ consists of the cards you can play. In dialogue-based games such as Avalon (see A for rules), $\mathcal{A}$ consists of both the discrete actions (moves) such as voting, and also all possible natural language texts of a given length. Similarly, $\mathcal{S}$ consists of both the historical moves and historical dialogue record, and $\mathcal{N}=\{\epsilon,0,1,...\}$ depending on the number of players involved, with $|\mathcal{N}|\geq 6$.

### 2.2 Abstracting high level strategies as processes

A key part of our framework abstracts key features of the policy $\phi$, representing them as a high-level strategy $\sigma$, which is more suitable for LLM-driven improvement. $\sigma$ is then executed and refined by a low-level executor, often during inference, resulting in the execution policy $\phi_{\sigma}$.

$$ $\text{feedback from environment}\rightarrow\texttt{LLM-Improver}\rightarrow \sigma\rightarrow\texttt{Executor}(\sigma)\rightarrow\phi_{\sigma}$ $$

Abstraction offers two key benefits: (1) High-level strategies provide a more abstract, compressed, and intuitive representation of the problem, which the LLM better understands, enabling its generalization and reasoning capabilities. (2) Searching over high-level strategies is more efficient than low-level policy exploration, as it simplifies the search space by focusing on core principles rather than fine details. This approach guides the search toward promising areas more quickly, leveraging domain knowledge, patterns, or heuristics that generalize across scenarios.

For non-dialogue actions, while the action spaces $\mathcal{A}$ and state spaces $\mathcal{S}$ are typically discrete and finite, the number of possible functions $\Phi$ mapping state to action is vast. Most LLM-agents query the LLM directly with state information to decide the next action in decision-making environments  (Yao et al., ; Shinn et al., ; Zhao et al., ). However, this is costly because the LLM must be queried for every move, and in Avalon, each player makes at least 20 moves. This becomes even more expensive when incorporating look-ahead search, which requires querying the LLM for future actions and states. Traditionally, policy-gradient reinforcement learning addresses the large policy space by parameterizing the policy and optimizing these parameters, reducing the search space.

We abstract and “parameterize” the policy $\phi$ as a value heuristic (VH) $\sigma:=v:\mathcal{S}\rightarrow\mathbb{R}^{|\mathcal{N}|}$ that estimates the expected cumulative returns for each player at a given state, typically the expected probability of winning for each player. Using a value heuristic simplifies reasoning, as it’s easier to describe how good a state is than to specify the optimal action. This makes it intuitive for the LLM to reason about winning probabilities. Additionally, we represent the value heuristic as Python code, allowing the LLM to easily process and modify the logic for *computing the value* for each state.

### 2.3 Modular search for high-Level strategy improvement

The framework for our high-level strategy improvement process is shown in Figure 2 with corresponding pseudo-code in 1 and more detailed diagram in Figure 9. Each improvement cycle has two steps: (1) reflection and idea generation, and (2) strategy improvement. In the idea generation step, we prompt the LLM to reflect on simulated self-play feedback from previous strategies and generate improvement ideas, which are added to the idea queue. In the strategy improvement step, we select a strategy from the strategy tree and an idea from the queue, prompting the LLM to refine the strategy. The improved strategy is then evaluated through self-play simulations, with feedback and reward signals guiding future improvements.

Figure: Figure 2: Overview of our high-level strategy improvement method: The process alternates between two steps—idea generation and strategy improvement. For more details see Figure 9.
Refer to caption: extracted/5921100/graphics/neurips_third-14.png

The improvement process maintains a strategy library, starting with seed strategies, along with each strategy’s performance score and raw feedback. It also keeps a queue of improvement ideas, tracking how much each idea improves strategies on average (score). Strategies are connected in a tree structure, showing how they evolved and which improvement ideas were used. The process alternates between two loops: the reflection and idea generation step and the strategy improvement step, running for a fixed number of cycles. An adaptive selection policy, such as UCB or BFS, is used to choose strategies and ideas for improvement.

#### 2.3.1 Idea Generation

A sampled strategy $\sigma$ and its simulated feedback trajectory $\tau_{\sigma}$ are selected from the strategy tree using the adaptive selection policy. The feedback consists of trajectories from previous self-play simulations, including visited states, actions taken, estimated win-rates, final outcomes, and intermediate values. Since these trajectories can be lengthy, we select key states to translate into natural language. The LLM is then prompted to reflect on this feedback and propose new improvement ideas, which are added to the idea queue with a prior score estimating their potential effectiveness.

$$ $\texttt{Idea-queue}\leftarrow\texttt{LLM-idea-inventor}(\text{Sampled strategy , strategy feedback})$ $$

#### 2.3.2 Strategy Improvement

We first sample a strategy and an idea from the libraries using a method that balances exploration and exploitation such as UCB. We then prompt the LLM to implement the idea of the strategy, generating a new improved strategy. We then evaluate the strategy using the evaluator, which conducts self-play simulations with the strategy, and records the simulated trajectory data. During simulations, players conduct an MCTS tree search to estimate the expected win-rate at different states, which provides additional feedback. We add the improved strategy (and its performance) to the strategy tree, and update the improvement score for the idea that was used.

$$ $\texttt{Strategy-library}\leftarrow\texttt{LLM-reviser}(\text{Sampled idea, sampled prior strategy})$ $$

#### 2.3.3 Search Modularization

A key challenge in the improvement process is evaluating whether a new strategy is better than the previous one and understanding why. Simply prompting the LLM to improve based on feedback without a clear idea often leads to changes across all parts of the strategy, making it difficult to pinpoint which changes had an impact. To address this, we use an idea queue to modularize the search process. Instead of improving everything at once, we *incrementally refine the strategy, ceteris paribus*, enabling a more *scientific* approach that avoids confounding factors.

The idea queue also helps track successful improvements, which are likely to be useful in the future. Since strategies are similar and used in the same context, improvements from one strategy can be transferred to another. These improvements, often involving additive adjustments like penalties or extra questions, are generalizable across strategies.
We also prompt for high-level, generalizable ideas.
For example, in a dialogue guide, an idea might be to add a certain question. For value heuristics generation, an idea might be to add a dynamic penalty term based on high-value cards. These general ideas apply to various strategies. Empirically, we found that transferable and additive improvements boost performance, as shown in Table 1.

UCB (upper confidence bound) sampling from the idea library helps us both explore new improvement ideas, and exploit old ones. Our UCB equation is

$$ $UCB(\text{improvement idea})=\overline{z}_{\text{improvement idea}}+c\sqrt{ \frac{\ln(N_{\text{total}})}{N_{\text{improvement idea}}}}$ $$

where $\overline{z}$ is the empirical average improvement score, $N_{\text{total}}$ is the total number of idea implementations, and $N_{\text{improvement idea}}$ is the number of times we have implemented this improvement idea specifically.

To make the improvement process more manageable, we optimize the policy for dialogue generation and moves separately in Avalon. We then integrate the two parts (refer to Appendix E), which together produces an agent fully capable of playing games with discussion.
This type of integration of separate components has seen success in other settings such as Diplomacy † et al.(2022)(FAIR)†, Bakhtin, Brown, Dinan, Farina, Flaherty, Fried, Goff, Gray, Hu, et al. ().

### 2.4 Population based self-play simulation

Recent works focus on using either another LLM for critique-based feedback  (Madaan et al., ; Shinn et al., ), real environment interactions  (Nottingham et al., ), or a combination of both  (Wang et al., ) during the LLM-improvement process.
Our method improves on this by simulating opponents using the learned high-level strategy, enabling higher-quality feedback.
Since our high-level strategies can be refined into a policy for any player, we can easily pit different strategies against each other by refining them into specific policies for different players.
Specifically, we use population based self-play, where we conduct round-robin games among the top ten strategies generated and use the average performance as the strategy score for each strategy.
During round-robin games, strategies are given the same level of low-level refinement to ensure fairness.
This evolutionary approach makes the final improved strategy more robust to different opponent policies, since it will have survived multiple round-robin tournaments.
We demonstrate the effectiveness of this method in section 3.4.

## 3 Experiments

Figure: Figure 3: Left: Example performance of value heuristics strategy tree for GOPS. Points indicate the final evaluation scores and the generation of improved functions, with lines showing the evolutionary path between functions. Our method successfully escapes local maxima and continues exploring the strategy space. These scores reflect final gameplay results against a fixed set of opponents, differing from the intermediate self-play scores used to guide strategy improvements. Right: Comparison of different improvement methods on 6-card GOPS, where 9 functions generated by each method play against one another over 1024 total games.
Refer to caption: extracted/5921100/graphics/improvement.png

We demonstrate the effectiveness of our bi-level framework and improvement method through (1) showing how \methodcan outperform existing RL-based deep learning methods, (2) showing how \methodcan outperform LLM-agents that use LLMs to take actions, and (3) showing how our LLM-improvement method outperforms other similar LLM-skill learning methods.
We tested our method on two games that present distinctive challenges. Game of Pure Strategy (GOPS) is a two-player, extensive zero-sum card game (see B for rules) well known and studied for its complexity arising from partial information and simultaneous moves  (Ross, ; Lanctot et al., ).
The Resistance: Avalon is a multi-agent (5+) team-based discussion game (see A for rules) known for its complexity in discussion, deception, deduction, and combining language with action  (Light et al., ).
For Avalon dialogue generation, we specifically benchmark on the Merlin role and Assassin roles, representing the hardest roles on both Good and Evil sides.
Experiments were run with gpt-3.5-turbo-0125, with more ablation studies in Appendix K. Details on how we implemented policies from learned strategies and acquired feedback are described in Section 2.2, and Appendix E, F, and G.

### 3.1 Different LLM Improvement Methods

We demonstrate the effectiveness of our strategy improvement method by benchmarking it against four other skill-improvement methods. Line search (Madaan et al., ) always reflects and improves upon the latest improved strategy. Greedy search (Ma et al., ) selects the best strategy from the last generation of improved strategies to improve upon each improvement cycle. Best first search (Yao et al., ) improves upon the $k$ best strategies generated in any iteration of each improvement cycle. Best first search with thought enhances BFS by prompting the LLM to reflect, think, and propose ideas on how to improve the previous strategy before improving the strategy itself  (Yao et al., ). \methodis our method that uses an additional idea queue $Q$
and an idea generation step to guide the improvement process.
Comparing BFS with thought and \methodhelps demonstrate the value of having a modularized reflection and idea proposition process that is separate from strategy generation, as mentioned in Section 2.3.3. More details can be found in Appendix N.

Our results, presented in Table 1, use the same feedback method (simulation-based population self-play) while varying the improvement methods, with a constant number of new strategies generated across all methods. Figure 3 (right) shows the gameplay scores of these strategies on GOPS. Even when controlling for the number of output tokens generated by the LLM, our method outperforms the others, as demonstrated in Figure 15. We attribute this to (1) the idea queue, which helps test incremental improvements and guide the search process, and (2) our strategy and idea selection policy, which more efficiently explores the strategy space and escapes local maxima (Figure 3 left).

**Table 1: Comparison of different self-improvement methods. The improvement process was run with the same number of strategies generated for each method (40 for GOPS, 24 for Avalon) on the same seed functions, all with GPT3.5. We collect 9 functions from each process and play them against each other (a total of $5\times 9=40$ different agents), reporting the average number of points you win over your opponents for GOPS and the average winrate for Avalon. The median scores ($\pm$ IQR/2) for each method are shown. For the dialogue guide, we show the improvement over the baseline seed function, which has a score $z=-0.875\in[-2,2]$, a rating from opponents which we describe in G.**
| Self-Improvement    Methodology | Line search  (Madaan et al., ; Shinn et al., ) | Greedy search  (Ma et al., ) | Best First Search (BFS) (Yao et al., ) | BFS with thought | \method |
| --- | --- | --- | --- | --- | --- |
| GOPS Value Heuristic | -0.47 $\pm 0.74$ | -0.54 $\pm 0.45$ | 0.092 $\pm 0.67$ | -0.48$\pm 0.375$ | 1.5 $\pm 0.99$ |
| Avalon Value Heuristic | 0.54 $\pm 0.11$ | 0.47 $\pm 0.11$ | 0.50 $\pm 0.085$ | 0.55 $\pm 0.065$ | 0.59 $\pm 0.11$ |
| Merlin Dialogue Guide | $0.37\pm 0.19$ | $0.62\pm 0.13$ | $0.49\pm 0.063$ | $0.37\pm 0.06$ | 0.88 $\pm 0.063$ |
| Assassin Dialogue Guide | $1.83\pm 0.25$ | $1.81\pm 0.063$ | $1.82\pm 0.063$ | $1.89\pm 0.063$ | 1.98 $\pm 0.042$ |

### 3.2 Scaling Inference-Compute can Continually Improve Strategy

Figure: Figure 4: Performance of strategies on GOPS with different MCTS search budgets (nodes). (Left) Scaling curve for initial unimproved LLM-generated value-heuristic. (Right) Scaling curve for improved value-heuristic using \methodafter 20 and 40 iterations (steps) of self-improvement respectively. \methodimproved value heuristics scale better with increased low-level refinement.
Refer to caption: extracted/5921100/graphics/budget_gops_worse.png

We demonstrate that both our high-level strategy improvement and low-level refinement processes scale effectively with increased budgets by showing how different high-level strategies performance with varying MCTS search budgets. A higher search budget allows for more nodes to be looked ahead before taking actions, resulting in a more refined policy. As shown in Figure 4, strategies improved with more iterations using \methodexhibit both higher performance and greater performance gains with increased refinement. Policy refinement also scales exceptionally well.

### 3.3 LLM-improvement vs. Reinforcement Learning (RL) based methods

Figure: Figure 5: Performance of different training methods against the baseline in Avalon and GOPS.
Refer to caption: extracted/5921100/graphics/LLM_RL_Random_avalon.png

We demonstrate the effectiveness of our method compared to traditional RL-based approaches for learning a good policy. Specifically, we show that our method learns a value heuristic function more efficiently than deep RL, as used in AlphaGo, MuZero  (Silver et al., ; Schrittwieser et al., ), and DeepRole  (Serrino et al., ). While AlphaGo uses MCTS  (Kocsis & Szepesvári, ) with a deep value network, DeepRole combines counterfactual regret minimization with a deep value network  (Moravčík et al., ; Zinkevich et al., ). We adapt both algorithms to our setting.

Although deep RL can approximate the true value function with enough data, training, and a large network, we ensure a fair comparison by (1) limiting both RL methods and our approach to the same number of simulated episodes, and (2) capping the number of training steps after each batch of episode trajectory data. While both RL methods and \methoduse the same number of self-play episodes, \methodonly trains on a small subset of transition steps, whereas RL methods train on the entire dataset.
Our results, shown in Table 2 and Figure 5, demonstrate that \methodconsistently outperforms both AlphaGo and DeepRole. More details on our RL implementation and the effects of increased sample size can be found in Appendix L, where we observe performance improvements with additional samples.

**Table 2: Comparison of reinforcement learning vs our method. We run each process 10 times, taking the best strategy generated by each run and playing them against each other for 1024 games. Average win-rates, total number of self-play episodes, and training transition steps across best generated strategies are shown here.**
| Setting | Metric | VS Alpha-go | VS DeepRole |  |  |
| --- | --- | --- | --- | --- | --- |
|  |  | Alpha-go | \method | DeepRole | \method |
| GOPS | Winrate | $-0.39\pm 0.71$ | $0.33\pm 1.21$ | $-0.56\pm 0.57$ | $1.14\pm 0.30$ |
| Self-play eps. | 320 episodes | 320 episodes | 320 episodes | 320 episodes |  |
| Trans. steps | $\sim 3,840$ steps | 100 steps | $\sim 3,840$ steps | 100 steps |  |
| Avalon | Winrate | $0.30\pm 0.11$ | $0.38\pm 0.11$ | $0.33\pm 0.12$ | $0.44\pm 0.08$ |
| Self-play eps. | 160 episodes | 160 episodes | 160 episodes | 160 episodes |  |
| Trans. steps | $\sim 24,000$ steps | $60$ steps | $\sim 24,000$ steps | $60$ steps |  |

### 3.4 Feedback Quality and Reward Signal

We benchmark our feedback method (population based self-play) against (1) an LLM-critic  (Madaan et al., ) and (2) trajectory feedback from a fixed opponent policy, with results in Table 3 showing superior performance in both GOPS action planning and dialogue generation. This shows the effectiveness of our evolutionary population based self-play approach, and that of our strategy abstraction that learns a strategic profile for all players.

**Table 3: Comparison of different methods of collecting feedback. All methods use the same high-level improvement process (\method). For GOPS we collect 24 generated functions from each method and play them against each other. For Avalon we evaluate 9 generated guides. We simulated 32 games for GOPS and 4 rounds of discussion for Avalon to collect gameplay feedback during each improvement step, across 10 and 6 improvement rounds for GOPS and Avalon respectively.**
| Setting/Method | Metric | LLM-critic | Fixed opponent | Population-based Self-play |
| --- | --- | --- | --- | --- |
| GOPS | Performance | $-0.27\pm 1.1$ | $0.089\pm 0.86$ | 0.87 $\pm 1.5$ |
| # of opponents | 0 | 1 | 4 |  |
| Avalon | Performance | $0.37\pm 0.063$ | $0.62\pm 0.13$ | 0.88 $\pm 0.06$ |
| # of opponents | 0 | 1 | 4 |  |

### 3.5 \method vs. LLM Agents

We demonstrate that our method also achieves better performance against other LLM-agents.
ReAct is a popular LLM-agent that prompts the LLM to think before taking an action  (Yao et al., ).
ReCon is a LLM-agent for hidden identity games that prompts the LLM to recursively contemplate on what opponents are thinking and might do before taking actions  (Wang et al., ). We adapt ReCon to our setting by asking the agent to recursively contemplate. Our gameplay results are shown in Table 4. This suggests that through \method, our LLM-agent is able to learn high-level strategies similar in performance to those of ReCon, such as recursive contemplation.

**Table 4: Results of \methodplaying against LLM-based baselines, i.e., ReAct and ReCon. Winrate (%) and assassination accuracy (%) are reported.**
| Metric | VS ReAct | VS ReCon |  |  |
| --- | --- | --- | --- | --- |
| ReAct | \method | ReCon | \method |  |
| Winrate | 47.5 $\pm$ 2.5 | 52.5 $\pm$ 2.5 | 38.9 $\pm$ 5.5 | 61.1 $\pm$ 5.5 |
| #Tokens per round | 56 $\pm$ 14.3 | 164.3 $\pm$ 27.7 | 245.7 $\pm$ 21.2 | 248.2 $\pm$ 24.1 |

## 4 Related Work

LLMs for text agents. Large language models (LLMs) have demonstrated significant emergent capabilities, such as zero-shot prompting and complex reasoning (Bommasani et al., ; Brown et al., ; Raffel et al., ; Wei et al., ; Chowdhery et al., ; Chung et al., ). They also possess extensive world knowledge (Yu et al., ), which has spurred increasing efforts to use LLMs for decision-making in text agents (Wang et al., ). One notable paradigm is ReAct (Yao et al., ), which employs an observation-reasoning-acting loop for agent planning with LLMs. Building on ReAct, Reflexion (Shinn et al., ) incorporates self-reflection to enhance reasoning capabilities. Other works in this domain have utilized feedback (Wang et al., ; Huang et al., ), memory (Park et al., ), and tool use (Schick et al., ; Cai et al., ) to further enhance agent performance. Our proposed method, \method, integrates these components to design an agent capable of systematic analysis and strategic decision-making. Typical prompting techniques for text agents include Chain-of-Thought (Wei et al., ), Tree-of-Thought (Yao et al., ), and Graph-of-Thought (Besta et al., ). While these techniques are effective for high-level reasoning, they are insufficient for complex games that require feedback signals for self-improvement. \methodadopts a bi-level tree search approach, enabling both high-level planning and low-level agent self-play for providing feedback.

Skill learning with LLMs. Recent works have explored the possibly of LLMs learning skills through learning a textual short and long term memory  (Shinn et al., ; Majumder et al., ), or textual insights extracted from the memories  (Zhao et al., ).
Due to the length of trajectories in our game setting and the numerical nature of the data, it is difficult to learn textual memories, so we learn high level strategies instead.
We also explore how to acquire simulational self-play feedback in multiagent settings.
Using LLMs to learn a functional reward model has also been applied to great success on single-agent robotic tasks  (Ma et al., ; Yu et al., ).
We build upon their work by introducing a new improvement method that can help learn a better reward model, and exploring how function learing can be applied to multiagent settings with simulated feedback.

AI in strategy games.
AI has been applied to great success in board games. AlphaGo and MuZero demonstrated the power of combining MCTS, deep learning, and feedback generation using self-play in games such as Go, Chess, and Shogi (Silver et al., ; Schrittwieser et al., ).
Language models can also be trained on human in-game discussion data and integrated with another separately trained action planner to play board games with dialogue  († et al.(2022)(FAIR)†, Bakhtin, Brown, Dinan, Farina, Flaherty, Fried, Goff, Gray, Hu, et al., ).
We build upon the AI for games literature by showing that LLMs can accomplish both * (1) the training of a value heuristic like that in AlphaGo through self-play more efficiently than RL and (2) dialogue generation in discussion games with no human examples*.
These adversarial environments are not just limited to board games. For example, there has been recent interest on creating LLM-agents that can negotiate (Abdelnabi et al., ; Fu et al., ), which our method can also be applied to.

## 5 Conclusion

In conclusion, we have introduced \method, a bi-level framework that facilitates high-level abstract strategy learning with LLMs and a generalizable non-parametric self-improvement mechanism. This approach enables the model to learn and refine skills autonomously. Without relying on task-specific prompts or human-generated policy data, our method demonstrates its ability to learn effective strategies through population-based self-play, guided solely by the rules of the game.

The performance of \methodhighlights the potential of leveraging LLMs for generating high-level strategic abstractions, while using low-level tree search to iteratively refine the policy. This dual approach not only showcases the power of modular guidance—whether through high-level strategy exploration or low-level self-play feedback—but also underlines the value of integrating these processes for accelerated and robust skill acquisition in LLMs.

Furthermore, our results suggest broader implications for the development of LLM-driven decision-making agents across a range of complex domains. By embedding flexible and adaptive learning mechanisms, our framework paves the way for more autonomous systems capable of mastering tasks with minimal human intervention. This opens new avenues for the application of LLMs in areas such as multi-agent systems, reinforcement learning, and general AI, where strategic planning and self-improvement are key.

## References

- Abdelnabi et al. (2023)
Sahar Abdelnabi, Amr Gomaa, Sarath Sivaprasad, Lea Schönherr, and Mario Fritz.
Llm-deliberation: Evaluating llms with interactive multi-agent negotiation games.
*arXiv preprint arXiv:2309.17234*, 2023.
- Besta et al. (2024)
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al.
Graph of thoughts: Solving elaborate problems with large language models.
In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pp.  17682–17690, 2024.
- Bommasani et al. (2021)
Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, Shyamal Buch, Dallas Card, Rodrigo Castellon, Niladri Chatterji, Annie Chen, Kathleen Creel, Jared Quincy Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren Gillespie, Karan Goel, Noah Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, Omar Khattab, Pang Wei Koh, Mark Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair,
Avanika Narayan, Deepak Narayanan, Ben Newman, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, Julian Nyarko, Giray Ogut, Laurel Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Rob Reich, Hongyu Ren, Frieda Rong, Yusuf Roohani, Camilo Ruiz, Jack Ryan, Christopher Ré, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishnan Srinivasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tramèr, Rose E. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kaitlyn Zhou, and Percy Liang.
On the opportunities and risks of foundation models.
*arXiv preprint arXiv: Arxiv-2108.07258*, 2021.
- Brown et al. (2020)
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.
Language models are few-shot learners.
In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), *Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual*, 2020.
URL [https://proceedings.neurips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html](https://proceedings.neurips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html).
- Cai et al. (2023)
Tianle Cai, Xuezhi Wang, Tengyu Ma, Xinyun Chen, and Denny Zhou.
Large language models as tool makers.
*arXiv preprint arXiv:2305.17126*, 2023.
- Chowdhery et al. (2022)
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy Meier-Hellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel.
Palm: Scaling language modeling with pathways.
*arXiv preprint arXiv: Arxiv-2204.02311*, 2022.
- Chung et al. (2022)
Hyung Won Chung, Le Hou, Shayne Longpre, Barret Zoph, Yi Tay, William Fedus, Eric Li, Xuezhi Wang, Mostafa Dehghani, Siddhartha Brahma, Albert Webson, Shixiang Shane Gu, Zhuyun Dai, Mirac Suzgun, Xinyun Chen, Aakanksha Chowdhery, Sharan Narang, Gaurav Mishra, Adams Yu, Vincent Zhao, Yanping Huang, Andrew Dai, Hongkun Yu, Slav Petrov, Ed H. Chi, Jeff Dean, Jacob Devlin, Adam Roberts, Denny Zhou, Quoc V. Le, and Jason Wei.
Scaling instruction-finetuned language models.
*arXiv preprint arXiv: Arxiv-2210.11416*, 2022.
- Deng et al. (2024)
Xiang Deng, Yu Gu, Boyuan Zheng, Shijie Chen, Sam Stevens, Boshi Wang, Huan Sun, and Yu Su.
Mind2web: Towards a generalist agent for the web.
*Advances in Neural Information Processing Systems*, 36, 2024.
- (9)
Meta Fundamental AI Research Diplomacy Team (FAIR)†, Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, et al.
Human-level play in the game of diplomacy by combining language models with strategic reasoning.
*Science*, 378(6624):1067–1074, 2022.
- Fu et al. (2023)
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.
- Grill et al. (2020)
Jean-Bastien Grill, Florent Altché, Yunhao Tang, Thomas Hubert, Michal Valko, Ioannis Antonoglou, and Rémi Munos.
Monte-carlo tree search as regularized policy optimization.
In *International Conference on Machine Learning*, pp.  3769–3778. PMLR, 2020.
- Huang et al. (2022)
Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, Pierre Sermanet, Noah Brown, Tomas Jackson, Linda Luu, Sergey Levine, Karol Hausman, and Brian Ichter.
Inner monologue: Embodied reasoning through planning with language models.
*arXiv preprint arXiv: Arxiv-2207.05608*, 2022.
- Kambhampati (2024)
Subbarao Kambhampati.
Can large language models reason and plan?
*Annals of the New York Academy of Sciences*, 1534(1):15–18, 2024.
- Kambhampati et al. (2024)
Subbarao Kambhampati, Karthik Valmeekam, Lin Guan, Kaya Stechly, Mudit Verma, Siddhant Bhambri, Lucas Saldyt, and Anil Murthy.
Llms can’t plan, but can help planning in llm-modulo frameworks.
*arXiv preprint arXiv:2402.01817*, 2024.
- Kocsis & Szepesvári (2006)
Levente Kocsis and Csaba Szepesvári.
Bandit based monte-carlo planning.
In *European conference on machine learning*, pp.  282–293. Springer, 2006.
- Lanctot et al. (2009)
Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling.
Monte carlo sampling for regret minimization in extensive games.
*Advances in neural information processing systems*, 22, 2009.
- Light et al. (2023)
Jonathan Light, Min Cai, Sheng Shen, and Ziniu Hu.
From text to tactic: Evaluating llms playing the game of avalon.
*arXiv preprint arXiv:2310.05036*, 2023.
- Liu et al. (2023)
Xiao Liu, Hao Yu, Hanchen Zhang, Yifan Xu, Xuanyu Lei, Hanyu Lai, Yu Gu, Hangliang Ding, Kaiwen Men, Kejuan Yang, et al.
Agentbench: Evaluating llms as agents.
*arXiv preprint arXiv:2308.03688*, 2023.
- Ma et al. (2023)
Yecheng Jason Ma, William Liang, Guanzhi Wang, De-An Huang, Osbert Bastani, Dinesh Jayaraman, Yuke Zhu, Linxi Fan, and Anima Anandkumar.
Eureka: Human-level reward design via coding large language models.
*arXiv preprint arXiv:2310.12931*, 2023.
- Madaan et al. (2024)
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al.
Self-refine: Iterative refinement with self-feedback.
*Advances in Neural Information Processing Systems*, 36, 2024.
- Majumder et al. (2023)
Bodhisattwa Prasad Majumder, Bhavana Dalvi Mishra, Peter Jansen, Oyvind Tafjord, Niket Tandon, Li Zhang, Chris Callison-Burch, and Peter Clark.
Clin: A continually learning language agent for rapid task adaptation and generalization.
*arXiv preprint arXiv:2310.10134*, 2023.
- Moravčík et al. (2017)
Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisỳ, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling.
Deepstack: Expert-level artificial intelligence in heads-up no-limit poker.
*Science*, 356(6337):508–513, 2017.
- Nottingham et al. (2024)
Kolby Nottingham, Bodhisattwa Prasad Majumder, Bhavana Dalvi Mishra, Sameer Singh, Peter Clark, and Roy Fox.
Skill set optimization: Reinforcing language model behavior via transferable skills.
*arXiv preprint arXiv:2402.03244*, 2024.
- Park et al. (2023)
Joon Sung Park, Joseph C O’Brien, Carrie J Cai, Meredith Ringel Morris, Percy Liang, and Michael S Bernstein.
Generative agents: Interactive simulacra of human behavior.
*arXiv preprint arXiv:2304.03442*, 2023.
- Perolat et al. (2022)
Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub, Vincent de Boer, Paul Muller, Jerome T Connor, Neil Burch, Thomas Anthony, et al.
Mastering the game of stratego with model-free multiagent reinforcement learning.
*Science*, 378(6623):990–996, 2022.
- Raffel et al. (2020)
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu.
Exploring the limits of transfer learning with a unified text-to-text transformer.
*J. Mach. Learn. Res.*, 21:140:1–140:67, 2020.
URL [http://jmlr.org/papers/v21/20-074.html](http://jmlr.org/papers/v21/20-074.html).
- Ross (1971)
Sheldon M Ross.
Goofspiel—the game of pure strategy.
*Journal of Applied Probability*, 8(3):621–625, 1971.
- Schick et al. (2024)
Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Eric Hambro, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom.
Toolformer: Language models can teach themselves to use tools.
*Advances in Neural Information Processing Systems*, 36, 2024.
- Schrittwieser et al. (2020)
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, et al.
Mastering atari, go, chess and shogi by planning with a learned model.
*Nature*, 588(7839):604–609, 2020.
- Serrino et al. (2019)
Jack Serrino, Max Kleiman-Weiner, David C Parkes, and Josh Tenenbaum.
Finding friend and foe in multi-agent games.
*Advances in Neural Information Processing Systems*, 32, 2019.
- Shinn et al. (2024)
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao.
Reflexion: Language agents with verbal reinforcement learning.
*Advances in Neural Information Processing Systems*, 36, 2024.
- Shridhar et al. (2020)
Mohit Shridhar, Xingdi Yuan, Marc-Alexandre Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht.
Alfworld: Aligning text and embodied environments for interactive learning.
*arXiv preprint arXiv:2010.03768*, 2020.
- Silver et al. (2017)
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al.
Mastering the game of go without human knowledge.
*nature*, 550(7676):354–359, 2017.
- Sutton & Barto (2018)
Richard S Sutton and Andrew G Barto.
*Reinforcement learning: An introduction*.
MIT press, 2018.
- Thorne et al. (2018)
James Thorne, Andreas Vlachos, Christos Christodoulopoulos, and Arpit Mittal.
Fever: a large-scale dataset for fact extraction and verification.
*arXiv preprint arXiv:1803.05355*, 2018.
- Valmeekam et al. (2023)
Karthik Valmeekam, Matthew Marquez, Sarath Sreedharan, and Subbarao Kambhampati.
On the planning abilities of large language models-a critical investigation.
*Advances in Neural Information Processing Systems*, 36:75993–76005, 2023.
- Wang et al. (2023a)
Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar.
Voyager: An open-ended embodied agent with large language models.
*arXiv preprint arXiv:2305.16291*, 2023a.
- Wang et al. (2024)
Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et al.
A survey on large language model based autonomous agents.
*Frontiers of Computer Science*, 18(6):186345, 2024.
- Wang et al. (2022)
Ruoyao Wang, Peter Jansen, Marc-Alexandre Côté, and Prithviraj Ammanabrolu.
Scienceworld: Is your agent smarter than a 5th grader?
*arXiv preprint arXiv:2203.07540*, 2022.
- Wang et al. (2023b)
Shenzhi Wang, Chang Liu, Zilong Zheng, Siyuan Qi, Shuo Chen, Qisen Yang, Andrew Zhao, Chaofei Wang, Shiji Song, and Gao Huang.
Avalon’s game of thoughts: Battle against deception through recursive contemplation.
*arXiv preprint arXiv:2310.01320*, 2023b.
- Wei et al. (2022a)
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, Ed H. Chi, Tatsunori Hashimoto, Oriol Vinyals, Percy Liang, Jeff Dean, and William Fedus.
Emergent abilities of large language models.
*arXiv preprint arXiv: Arxiv-2206.07682*, 2022a.
- Wei et al. (2022b)
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Ed Chi, Quoc Le, and Denny Zhou.
Chain of thought prompting elicits reasoning in large language models.
*arXiv preprint arXiv:2201.11903*, 2022b.
- Wikipedia contributors (2023)
Wikipedia contributors.
Goofspiel — Wikipedia, the free encyclopedia, 2023.
URL [https://en.wikipedia.org/w/index.php?title=Goofspiel&oldid=1174471596](https://en.wikipedia.org/w/index.php?title=Goofspiel&oldid=1174471596).
[Online; accessed 22-May-2024].
- Xi et al. (2023)
Zhiheng Xi, Wenxiang Chen, Xin Guo, Wei He, Yiwen Ding, Boyang Hong, Ming Zhang, Junzhe Wang, Senjie Jin, Enyu Zhou, et al.
The rise and potential of large language model based agents: A survey.
*arXiv preprint arXiv:2309.07864*, 2023.
- Yang et al. (2018)
Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhutdinov, and Christopher D Manning.
Hotpotqa: A dataset for diverse, explainable multi-hop question answering.
*arXiv preprint arXiv:1809.09600*, 2018.
- Yao et al. (2022a)
Shunyu Yao, Howard Chen, John Yang, and Karthik Narasimhan.
Webshop: Towards scalable real-world web interaction with grounded language agents.
*Advances in Neural Information Processing Systems*, 35:20744–20757, 2022a.
- Yao et al. (2022b)
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao.
React: Synergizing reasoning and acting in language models.
*arXiv preprint arXiv:2210.03629*, 2022b.
- Yao et al. (2023)
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao.
React: Synergizing reasoning and acting in language models.
*arXiv preprint arXiv:2210.03629*, 2023.
- Yao et al. (2024)
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan.
Tree of thoughts: Deliberate problem solving with large language models.
*Advances in Neural Information Processing Systems*, 36, 2024.
- Yu et al. (2023a)
Jifan Yu, Xiaozhi Wang, Shangqing Tu, Shulin Cao, Daniel Zhang-Li, Xin Lv, Hao Peng, Zijun Yao, Xiaohan Zhang, Hanming Li, et al.
Kola: Carefully benchmarking world knowledge of large language models.
*arXiv preprint arXiv:2306.09296*, 2023a.
- Yu et al. (2023b)
Wenhao Yu, Nimrod Gileadi, Chuyuan Fu, Sean Kirmani, Kuang-Huei Lee, Montse Gonzalez Arenas, Hao-Tien Lewis Chiang, Tom Erez, Leonard Hasenclever, Jan Humplik, et al.
Language to rewards for robotic skill synthesis.
*arXiv preprint arXiv:2306.08647*, 2023b.
- Zhao et al. (2024)
Andrew Zhao, Daniel Huang, Quentin Xu, Matthieu Lin, Yong-Jin Liu, and Gao Huang.
Expel: Llm agents are experiential learners.
In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pp.  19632–19642, 2024.
- Zhou et al. (2023)
Shuyan Zhou, Frank F Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, et al.
Webarena: A realistic web environment for building autonomous agents.
*arXiv preprint arXiv:2307.13854*, 2023.
- Zinkevich et al. (2007)
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione.
Regret minimization in games with incomplete information.
*Advances in neural information processing systems*, 20, 2007.

## Appendix A Resistance: Avalon Game Description

Figure: Figure 6: The three phases per round of Resistance game. Good players are shown in blue, while Evil players in red. In Selection Phase, the team leader (player 5 in this round) proposes a team (player 1 and 5, himself). In Voting Phase, all players vote publicly whether to approve this team or not. If the strict majority votes yes, the team is approved and moves on to the mission phase. Otherwise, redo the Selection Phase with the next player as leader. If the team goes on the Mission Phase, selected team members (player 1 and 5) anonymously vote to pass or fail the mission. If at least one person (player 1, as he is the evil player) votes fail, the mission fails. Otherwise, it succeeds.
Refer to caption: extracted/5921100/graphics/Avalon-06.png

Figure: Figure 7: Communication Skills required to play Avalon. 1) First, they use logical reasoning to analyze the voting pattern and dialogue of other players and deduce their motives. 2) they must coordinate, communicate, and persuade their teammates to follow a particular strategy. 3) they must also hide their identity and motives through deception.
Refer to caption: extracted/5921100/graphics/Avalon-07.png

We describe the game in more detail here.
There are four phases in the game where players need to make decisions: (1) team selection phase, (2) voting phase, (3) quest phase, and (4) assassination phase. The game alternates between the first three phases until the end condition is reached, at which point we move on to the assassination phase. Each phase also contains discussion where players can challenge others, defend themselves, and negotiate. A flowchart of the game is presented in Figure 8, and an Avalon Rule Prompt is included in Section A.4.

### A.1 Roles

There are four basic roles in Resistance Avalon: Servant of Arthur, Minion of Mordred, Merlin, and Assassin. The Servant is a basic good character who does not know the identity of any of the other players. The Minion is a base evil character who knows who is good and evil but does not know the specific roles of each player. Merlin is a unique good character who knows who is good and evil. The Assassin is a unique evil character who knows who is good and evil, and in addition, has the ability to assassinate a character at the end of the game. If that character is Merlin, the evil team wins.

Good players will always outnumber evil players.
Hence, evil players must pretend to be good in order to be voted in on teams (and thus sabotage missions). Servants will thus need to sniff out the evil players through their actions and dialogue. Merlin is usually the only good player with additional information, so they will need to discreetly guide the Servants in the right direction. Servants also need to protect Merlin, so a common strategy is for Servants to pretend to have hidden information so that evil players will think that they are Merlin. Evil players will be trying to sniff out Merlin at the same time, so deduction skills are required for all roles.

### A.2 Actions for each Phase

Depending on the phase team selection, voting, quest, and assassination, players may conduct different actions. We detail the specific actions that players can take in each of these phases below.

During the team selection phase, only the current *leader* has to make a choice. Leadership passes around the players sequentially in a loop. The action space of team selection for the leader consists of all subsets of the players with size equal to the mission team size. The mission team size is different for each mission and is determined by the total number of players in the game. For example, in a 5-player game, on mission No.4, the mission team size is $3$, so any subset of $\{1,2,3,4,5\}$ with size $3$ would be a valid action. After the team proposal is determined by the leader, we move on to the voting phase with the selected players.

During the voting phase, *every* player in the game needs to simultaneously vote either Approve (1) or Reject (0). Votes are publicly revealed to all players, so players can see what other players voted. If a strict majority votes APPROVE (1), we then move on to the quest phase with the team that was approved. Otherwise, we move back to the selection phase. Note that if four teams have been rejected in a row, and this is the fifth time a team is proposed (for the same mission), we skip the voting and move directly to the quest phase. This prevents the game from dragging on forever.

During the quest phase, *each selected player on the approved team* votes anonymously to either Pass (1) or Fail (0) the mission. The number of votes of Pass vs Fail are then revealed to everybody. If the number of Fails is greater than or equal to the number of Fails required for the mission to fail (usually 1), then this mission is marked as a failure.
Otherwise, this mission is marked as a success. Hence, good players usually have no incentive to fail missions, while evil players will want to have enough failures to pass the failure threshold. If three out of five missions fail, evil wins immediately. Otherwise, if three out of five missions succeed, we move on to the assassination phase.

Figure: Figure 8: Flowchart illustrating the various game states and transition diagram. Round boxes indicate game states (phases) where the player (role highlighted in bracket) has to make decisions
Refer to caption: x1.png

### A.3 Discussion

Group discussion occurs between the quest and selection phases, as well as right before the assassination phase. Players may not communicate during any other time. All conversations are public, and there is no private communication. Typically players may discuss in any format of their choosing as long as only one person is speaking at a time. Some examples of formats include a natural (spontaneous) seminar style (most common, where there is no fixed order of speaking), or sequentially (where players speak in some predefined order). Interruptions and arguments between two players are very common between human players.

Usually, players will spend this time discussing a couple of key topics, including (1) the observations they made, (2) the guessed identities and sides of players, and (3) the plan for the next mission. The team leader will usually spend this time asking for advice on what team to select and gathering support for that team. Persuasion and adhering to the preferences of other players are usually key to getting a team approved. Players can also accuse other players of being evil, though arguments will need to be justified in order to be persuasive.

For example, a player (player 3) could start off by stating their (1) observations of what happened in the previous mission. One Fail was observed, so at least one player on the previous team (consisting of players (1,2,3)) is evil. Player 3 then emphasizes that both Players 1 and 2 voted Approve for the previous mission, which ended up a failure. Moreover, the team was proposed by Player 1 in the first place. Player 3 then moves on to discuss the (2) identities of other players. The player says that, despite the fact that only one Fail was observed, both Players 1 and 2 are evil since they both voted to Approve previously. Player 0 is probably good since they voted to Reject in the previous mission, and Player 3 is also good since they also voted to Reject, even though they were on the mission. Player 3 then says what they think the (3) plan should be. Specifically, Player 3 says that they should reject the current team no matter what since Player 2 is the leader and is evil. The leadership will then pass to Player 3, who will choose the team $(0,3,4)$, which good players should vote to approve since it does not contain any suspected evil players(^1^11At this point, Player $2$ reveals that they are the assassin and assassinates Player $3$, who is indeed Merlin. Player $3$’s intuition and analysis were way too correct to be a Servant).

### A.4 Game Ending and Assassination

In classic Resistance, a good team wins immediately if three missions are successful. In Resistance Avalon, there is an additional assassination phase if three missions are successful.
During the assassination phase, the Assassin player chooses one player to assassinate. If that player is Merlin, then evil wins. Otherwise good wins.

Before they assassinate a player, the Assassin player can and is encouraged to discuss with the other players (mostly their teammates). good players are also welcome to join in on this discussion to mislead the evil players, though it rarely helps. Players can discuss in a format of their choosing, though there is usually a time limit on how long players can discuss before reaching a decision.

## Appendix B Game of Pure Strategy (GOPS) Game Description

Game of Pure Strategy (GOPS) is a card game for two or more players with a standard deck of card, which is commonly used as an example of multi-stage move game in artificial intelligence (Wikipedia contributors ()). In our experiments we play 5 or 6 card GOPS. Specifically, the score cards are $\{1,2,....n\}$ and each player starts with a hand of cards $\{1,2,....n\}$ where $n$ is the number of cards and rounds. The GOPS rules prompt is included in this section below.

## Appendix C Limitations

While our method performs better on average, individual runs can have high variance.
Since the performance of an agent in multi-agent adversarial game settings is highly dependent on opponents’ policies, feedback from these environments tend to be highly noisy, with noise increasing with the number of players.
This is especially true when learning Avalon heuristics, where the performance depends on the policies of 5 other players, teammates and opponents.
We believe that running more game simulations with different opponent policies can help reduce this feedback noise. We also acknowledge the inherent noisiness in LLM generations and how that can impact our results. We tried to reduce this noise by (1) using the same seed functions when benchmarking the different LLM improvement methods and (2) collecting generated strategies from multiple runs.
We also did not test our method on other non-adversarial environments such as question answering and text-based worlds.
However, given the strong performance of our method in adversarial multi-agent settings, we believe that similar performance will be observed in single agent, non-adversarial settings.

## Appendix D Improvement Process Implementation Details

Figure: Figure 9: Overview of our high-level strategy improvement method: The process alternates between two steps—idea generation and strategy improvement.
Refer to caption: extracted/5921100/graphics/neurips-two-thirds-02.png

Figure: Algorithm 1 \methodPseudocode

## Appendix E Avalon Agent Implementation Details

We describe in detail how we implement our model below and as shown in figure 10. Unless otherwise specified, the word ‘action’ will refer to non-dialogue actions. Note that we do not conduct search over raw dialogue space since that is not very computationally feasible. Instead, we search over intended actions and condition our dialogue on that.

Specifically, the language component consists of a dialogue analyzer and a dialogue generator, while the moves component consist of the action planner. Whenever the agent needs to speak, they first analyze what was said so far in the current discussion round using the dialogue analyzer. The dialogue analyzer, with the help of an LLM, updates the internal beliefs of the agent. For example, in Avalon, internal beliefs might include the probability that the agent assigns to each other player of being Evil and of being Merlin. These beliefs are then passed to the action planner, which uses them to figure out the best next move, i.e. the action intent. The action intent is then passed to the dialogue generator, which generates dialogue with the help of an LLM.
When the agent needs to take a move, we run through the same process except that the agent takes the action intent as the move and no dialogue is generated.

Figure: Figure 10: Overview of the LLM-powered agent, including the three main modules that we use to generate dialogue during discussion
Refer to caption: extracted/5921100/graphics/dialogue-action-02.png

### E.1 Dialogue Analyzer (Discriminator)

The dialogue analyzer $f_{ana}$ takes as input $\boldsymbol{I}$ information set (partial information) of the current state for the player, $\boldsymbol{d}_{t}$ the discussion so far this round, and $\boldsymbol{b}$ some prior beliefs about the hidden state of the game, and returns $\widehat{\boldsymbol{b}}$, the updated beliefs, and $\widehat{\boldsymbol{\Pi}}_{t}$, the predicted joint action policy of the all the players (i.e. the action intent) for the next action step $t$. Recall that simultaneous games can be expanded as partial information games, where the simultaneous moves are treated as hidden information. Hence, we are essentially predicting a distribution over the hidden states $\boldsymbol{s}$ given the information set $\boldsymbol{I}$ using the dialogue analyzer.

$$ $\widehat{\boldsymbol{b}},\widehat{\boldsymbol{\Pi}}_{t}=f_{ana}(\boldsymbol{I} ,\boldsymbol{d}_{t},\boldsymbol{b})$ $$

In the context of Avalon, $\boldsymbol{I}$ will contain information such as (1) the dialogue this round so far (2) summary of the dialogue from previous rounds (3) mission track record (4) historical record of actions taken by players in previous rounds, and (5) private information of the player such as who is Good and Evil. $\boldsymbol{b}$ will contain information on (1) the probability of each player being Evil and (2) the probability of each player being Merlin, both conditioned on the private information contained in $\boldsymbol{I}$. While a full treatment of the distribution over the hidden state space $\mathcal{S}$ we require assigning probabilities to each possible combination of Good and Evil players, not just assessing the marginal probability of each player being Good individually, in practice

We implement $f_{ana}$ using an LLM, which is fed $\boldsymbol{I}$, $\boldsymbol{d}$, $\boldsymbol{b}$ (converted to natural language form) as prompts, along with some instruction prompt $\boldsymbol{\phi}_{ana}$ that prompts it to produce $\widehat{\boldsymbol{b}},\widehat{\boldsymbol{\Pi}}_{t}$. Specifically,

$$ $f_{ana}(\boldsymbol{I},\boldsymbol{d}_{t},\boldsymbol{b})=f_{LLM}(\boldsymbol{ \phi}_{dis},\boldsymbol{I},\boldsymbol{d},\boldsymbol{b})$ $$

We show examples of such prompts in Appendix J.

### E.2 Action Planner

Given $\widehat{\boldsymbol{b}}$ the belief prior, $\widehat{\boldsymbol{\Pi}}_{t}$ the predicted joint action policy for all players, and $\boldsymbol{s}$ the representation of the current state, the action generation model $f_{act}$ generates a probability distribution over possible actions $\boldsymbol{\pi}^{i}$ for the main player $i$ that is the best response to $\widehat{\boldsymbol{\Pi}}_{t}$. We do so by using search techniques to look ahead and find the best response.

$$ $\boldsymbol{\pi}^{i}=f_{act}(\widehat{\boldsymbol{b}},\widehat{\boldsymbol{\Pi }}_{t},\boldsymbol{I})$ $$

More specifically, in our search implementation, at the first layer, we first sample across possible hidden states $\boldsymbol{s}\sim\widehat{\boldsymbol{b}}$ according to the belief prior. At the second layer (i.e. the first action stage $t$), we calculate expected $q$-values for each action $a\in\mathcal{A}$ that the main player can take if the other players play actions $\boldsymbol{a}\sim\widehat{\boldsymbol{\Pi}}_{t}$ according to the predicted joint distribution. In subsequent action stages, the search process will assume that other players play according to their policy simulated and induced by the value heuristic that is not dialogue dependent. We then take the best response action $a^{*}_{i}=\mathop{max}(\boldsymbol{\pi}^{i})$ as the intended action. Since this is a partial information game, expected $q$-values are taken across information sets, not states. We describe how our action planner is implemented in more detail in Appendix F.

### E.3 Dialogue Generation

The dialogue generator $f_{gen}$ takes as input $\boldsymbol{I}$ some representation of the current information set and $a^{*}_{i}$, the intended best response action, and outputs dialogue $d$.

$$ $d=f_{gen}(\boldsymbol{I},a^{*}_{i})$ $$

We will implement $f_{gen}$ using an LLM, which is fed $\boldsymbol{I}$ and $a^{*}_{i}$ directly as prompts, along with some instruction prompt $\phi_{gen}$ that prompts it to produce realistic sounding dialogue that helps it achieve its intended action.

For example, perhaps the player wants to approve the next team. Then it should try to generated dialogue that convinces the other players to also approve.

We show examples of such prompts in Appendix J.

## Appendix F Value Heuristic Implementation Details

Figure: Figure 11: Overview of how we utilize the trained value heuristics in MCTS tree search to get a non-dialogue based policy. While we only display the values for a single player in the diagram, note that in practice we infer and update the values for all players at the same time. Next states are sampled using the PUCT formula we described. We sample an initial hidden state based on the internal beliefs of the agent. Metropolis-Hastings is used to sample since it may be difficult to calculate the probability density specified by the internal beliefs. Note that values estimated using MCTS are also passed as feedback to the evaluator.
Refer to caption: extracted/5921100/graphics/neurips_third-04.png

The MCTS search process is depicted in Figure 11, where we simulate a trajectory from the hidden state we are at until we reach some unexpanded state $s$. The probability of transitioning to a state during simulations is computed assuming that each player samples from their optimal actions according to their PUCT (polynomial upper confidence trees) values (and $\phi_{e}$ for the environment actor)  (Schrittwieser et al., ). Since in some environments players may only be able to observe information sets, when computing the PUCT values we average over all expanded states in that information set. Moreover, the initial hidden state can be sampled according to a prior (or empirical prior) over the states in the information set that the player observed.
Then, using our value heuristic, we compute the values of each of the next hidden states. We then backpropogate our new values back up the simulated trajectory, updating the intermediate states. After running a few MCTS simulations (roll-outs) like the one we described, the planner then outputs the action which leads to the highest value next state. We show our information set PUCT formula below, where $N(s,a)$ is the number of times we took action $a$ at state $s$ during MCTS rollouts, $P(s,a)$ is the prior prior probability of selecting action $a$ from state $s$, $C$ is the exploration constant, $Q_{emp}$ is the empirical average of MCTS roll-out outcomes, $\widehat{Q}(s,a)$ is the prior computed by our value heuristic, $\alpha$ controls how much weight be put on the prior (often $\alpha=1$), and $\pi_{B}$ is the distribution across hidden states in the information set given our beliefs $B$, some parametrization of $\pi_{B}$. Since $\pi_{B}$ is often hard to compute, we can simply set $\pi_{B}(s|I)=\frac{\sum_{b}N(s,b)}{\sum_{s^{\prime}\in I}\sum_{b}N(s^{\prime},
b)}$ to be the empirical roll-out distribution, given that we sample initial states $s_{0}\sim\pi_{B}(s_{0}|I)$ according to our beliefs. For example, in Avalon, we can sample the hidden roles according to our beliefs $B$ using Metropolis-Hastings for the initial state $s_{0}$.

$$ $\displaystyle Q(s,a)=\frac{N(s,a)\cdot Q_{\text{emp}}(s,a)+\alpha\cdot\widehat {Q}(s,a)}{N(s,a)+\alpha}$ (1) $\displaystyle\text{PUCT}(I,a)=\sum_{s\in I}\pi_{B}(s|I)\left[Q(s,a)+C\cdot P(s ,a)\cdot\frac{\sqrt{\sum_{b}N(s,b)}}{1+N(s,a)}\right]$ (2) $$

## Appendix G Dialogue Guide Improvement Evaluation Implementation Details

We provide more details on our dialogue improvement evaluation process here and as shown in figure 12. The improvement method (skill coach) remains the same as we described before.

We first generate a synthetic dataset by simulating a game of Avalon with initial dialogue and move policies $\boldsymbol{\phi}$. Given the dialogue guide $\sigma$ we want to evaluate, we then sample ‘scenarios’ from the dataset. A scenario consists of a game state, intended action, and private information in the simulated trajectory. We create an Avalon agent like the one we described in E for each player in the game, initialized with their corresponding private information. The Avalon agent is then asked to generate dialogue using the dialogue guide $\sigma$.

Using this new generated dialogue, we then simulate the next round of dialogue analysis for each Avalon agent. This produces analysis scores based on how likely they think the player is to be Merlin $z_{merlin}$, and how likely they think the player is to be Evil $z_{evil}$, where $z_{merlin},z_{evil}\in[-2,2]$. For evaluating Merlin, we get the average $z_{merlin}$ scores from the Evil players, $\overline{z}_{merlin}$, along with the average $z_{evil}$ scores from the Good players $\overline{z}_{evil}$. We then take the minimum of these two as the feedback score $z=\mathop{min}\{\overline{z}_{evil},\overline{z}_{merlin}\}$. This is because Merlin wants to both minimize the probability of being detected by the Evil players, and also minimize the probability of being identified as Evil by the Good players.

Figure: Figure 12: Overview of our improvement process for learning dialogue generation strategies. This includes how we evaluate the dialogue and how we collect feedback. The skill coach here can be implemented as either our improvement method, \method, or any of the baseline methods we described.
Refer to caption: extracted/5921100/graphics/neurips_third-03.png

The dialogue analyzer (discriminator) is described in more detail in Appendix E and the specific generation and analysis prompts are shown in Appendix J.

## Appendix H Value Heuristic LLM Prompt and Output Examples

### H.1 System Prompts

System prompt are guidelines for LLM to generate outputs align with the intended goals. In our case, the goal is to generate a function that evaluates the value of a state in a game under low cost.

The following example is a detailed prompt telling the LLM how to format the value heuristics specifically in the GOPS game. The format of input and output are clearly defined in the prompt with illustrations, examples and structures.

### H.2 Idea Generation Examples

The idea generation prompt included system prompt, game rules, previous guide and feedback reflections. Following those four components, we construct the format and an example of ideas to guide the generation of LLM.

Below is an instance of Feedback of GOPS game, showing the setup of two players, the intermediate values involved in the computation, and the actual scores.

Recall that feedback reflection refers to feedback for strategy, which is used to generate ideas. For prompting, We specify that game rules, previous guide and feedback examples are generated previously. The following is the prompt for feedback reflections.

Below is the feedback reflections from the LLM.

Also, with the prompts of idea generation, below is the generated new ideas by LLM.

### H.3 Strategy Implementation Examples

During the strategy implementation step, we first select a strategy and an idea from the libraries using the adaptive selection policy. Then, we prompt the LLM to implement the idea on the strategy, generating a new improved strategy.

In this section, we showcase two examples. Each example illustrates strategies before and after enhancements made by the LLM. This comparison highlights the effectiveness of our strategy implementation. The improved parts by LLM are highlighted in yellow.

Below is the prompt for strategy implementation.

#### H.3.1 Example 1

Below is the GOPS Value Heuristics Function before the strategy improvement.

Below is the selected idea to improve the above strategy.

Below is the GOPS Value Heuristics Function after enhancement by LLM.
The improved parts by LLM are highlighted in yellow.

#### H.3.2 Example 2

Below is the Avalon Value Heuristics Function before improvements.

Below is the improvement idea pf Avalon Value Heuristics Function.

The following is Avalon Value Heuristics Function after enhancements, highlighted in yellow.

#### H.3.3 Example 3

Below is the GOPS Value Heuristics Function before the strategy improvement.

Below is the selected idea to improve the above strategy.

Below is the GOPS Value Heuristics Function after enhancement by LLM. The improved parts by LLM are highlighted in yellow.

#### H.3.4 Example 4

Below is the GOPS Value Heuristics Function before the strategy improvement.

Below is the selected idea to improve the above strategy.

Below is the GOPS Value Heuristics Function after enhancement by LLM. The improved parts by LLM are highlighted in yellow.

## Appendix I Dialogue Guide LLM Prompt and Output Examples

This sections shows the system prompts of dialogue guidance on LLM and several examples, including system prompts, idea generation prompts, and strategy implementation examples.

### I.1 System Prompts

Below is the Dialogue guide system prompt.

Dialogue guide signature follows, specifying the structures and contents dialogues regarding role playing the Merlin.

### I.2 Idea Generation Examples

The following is the selected dialouge guide speaking as the Merlin role.

A feedback example is provided for better understanding of dialogue guidance to teach LLM how to role play Merlin.

This is the prompt for feedback reflections.

The following are the feedback reflections generated by LLM.

Below is the Prompt for idea generation regarding this dialogue guides

Generated new improvement ideas are demonstrated below, showing the improvements made by LLM following the prompt for idea generation.

### I.3 Strategy Implementation Examples

Recall the strategy implementation mentioned in the paper before. Here, we implement strategy improvements on dialogue guide. The improved dialogue guide is highlighted.

#### I.3.1 Example 1

Below is the dialogue guide before any improvements happened.

Below is the improvement idea prompted into LLM.

Here, implementation prompty follows to teach LLM how to improve the dialogue guide.

Finally, we have a improved dialogue guide, where the changes are highlighted below comparing to the previous guide.

#### I.3.2 Example 2

Below is the dialogue guide before any improvements happened.

Below is the improvement idea prompted into LLM.

Here, implementation prompt follows to teach LLM how to improve the dialogue guide.

Finally, we have a improved dialogue guide, where the changes are highlighted below comparing to
the previous guide

#### I.3.3 Example 3

Below is the dialogue guide before any improvements happened.

Below is the improvement idea prompted into LLM.

Here, implementation prompt follows to teach LLM how to improve the dialogue guide.

Finally, we have a improved dialogue guide, where the changes are highlighted below comparing to the previous guide

## Appendix J Dialogue Generation and Analysis Example LLM Inputs and Outputs

This sections shows the examples of dialogue generation and analysis, including descriptive prompts, dialogue generation, and dialogue analysis.

### J.1 Descriptive Prompts

Below is the discussion history prompted into LLM for better knowledge of dialogue generation.

State description shows LLM which state it will be for role playing and dialogue generation.

### J.2 Dialogue generation

Below is the prompt for filling out worksheet. Filling out this worksheet assists LLM generated better dialogue aligned with the role, Merlin as in the example.

The worksheet filled out by LLM follows, demonstrating the LLM capability and the effectiveness of prompting.

Below is the prompt for speech generation. Worksheet completion assists LLM to understand the states and role. The following prompt asks LLM to assemble responses to the questionaire filled out above.

Finally we have LLM generated speech after the preparations.

### J.3 Dialogue Analysis

After dialogue generation, we continue have LLM assume the role of Merlin, and dialogue analysis is conducted.

Below is the prompt for dialogue analysis regarding to the role of Merlin. A thought is included to guide LLM analyze.

Generated dialogue analysis follows. The role is Merlin.

Under dialouge analysis, besides focusing on one specific role, we also have LLM target on good and evil in the game, which is broader in terms of role playing. Below is the prompt for dialogue analysis regarding to Good and Evil.

Below is the dialogue analysis generated by LLM on Good and Evil.

## Appendix K Other Ablation Studies

#### K.0.1 Base LLM Model

We show the performance of different base models in Figure 13.

Figure: Figure 13: Game play performance of base LLM models on six card GOPS: GPT3.5 and GPT4.0. We see that the two language models perform similarly with our method.
Refer to caption: extracted/5921100/graphics/gpt_4_35.png

#### K.0.2 Search Budget

How does the effectiveness of the search+LLM agent scale with regards to the search budget? Does having a larger search process help achieve better performance?

**Table 5: Average score difference for MCTS (num_rollout=32) + LLMFunction (Player1, top-3 functions shown in the table) vs. MCTS (num_rollout=32) + RandomRollout (Player2, num_rollout=10); 100 games for each experiment;**
| budget | Best Func. | 2nd Best Func. | 3rd Best Func. |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Player 1 | Player 2 | Player 1 | Player 2 | Player 1 | Player 2 |  |
| 16 | -0.91 | 0.91 | -0.7 | 0.7 | -0.88 | 0.88 |
| 32 | -0.95 | 0.95 | 0.44 | -0.44 | -0.73 | 0.73 |
| 64 | -1.14 | 1.14 | 1.15 | -1.15 | 0.46 | -0.46 |
| 128 | -1.28 | 1.28 | 0.36 | -0.36 | 0.25 | -0.25 |
| 256 | -0.45 | 0.45 | -0.85 | 0.85 | -0.42 | 0.42 |
| inf | -1.5 | 1.5 | -2.26 | 2.26 | -1.03 | 1.03 |

## Appendix L Details on Learning the Value Heuristic via Reinforcement Learning

We employ Monte-Carlo based RL approach (Sutton & Barto ()) to train a value heuristic for both five-player Avalon and five-card GOPS games. To do so, we construct a MSE loss in each episode for training the value function, i.e.,

$$ $\displaystyle\mathop{argmin}_{\theta}\sum_{i}^{\mathcal{N}}\sum_{t=0}^{T}\left (V_{\theta}^{i}(s_{t})-Score^{i}(s_{t})\right)^{2}$ $$

where $\mathcal{N}$ represents the number of actors, $V_{\theta}^{i}(s_{t}),i=1,2,\cdots,\mathcal{N}$ denotes the value function for each actor, and $T$ is the time horizon. Notice that $s_{t}$ and $Score^{i}(s_{t})$ denote the state at time step $t$ and the corresponding cumulative reward for each actor, i.e., $\sum_{t}^{T}R_{i}(s_{t},a_{t})$. It is worth pointing that $Score^{i}(s_{t})$ (the cumulative reward starting from $s_{t}$) is the unbiased estimate of the value function $V_{\theta}^{i}(s_{t})$.

For both Avalon and GOPS games, the value function $V_{\theta}^{i}(s_{t})$ is predicted by a neural network. We then train the value function network by minimizing the aforementioned loss function over episodes. In Avalon, we consider 20 evolutions (epochs) for the training process. At the end of each evolution, 30 batch runs (episodes) are generated and used to train the value function network, i.e., a total of 600 episodes for training. In GOPS, we train by 20 evolutions as well while considering 60 batch runs each (1200 episodes in total). We evaluate the final performance over 10 episodes in both games. The neural network is constructed by a multilayer perceptron (MLP) with 2 hidden layers. We select a hidden layer size of $128*128$ for Avalon and that of $64*64$ for GOPS. Likewise, the chosen learning rates are $5e-4$ and $8e-4$, respectively. The value function is expected to predict the score for each player in the game, e.g., two for GOPS and number of players for Avalon. All experimental hyper-parameters are summarized in Table 6.

Having introduced the set up, one can observe in Figure 14 an increased performance of RL-trained value heuristic in both five-player Avalon and five-card GOPS games. This validates the improvement for training value heuristic via reinforcement learning within limited evolutions.

Figure: (a) Avalon
Refer to caption: extracted/5921100/graphics/avalon_rl_improve.png

**Table 6: Summary of experimental hyper-parameters in RL-training value heuristic**
| Parameters | Avalon | GOPS |
| --- | --- | --- |
| Type of neural network | MLP | MLP |
| Number of hidden layers | 2 | 2 |
| Hidden layer size | 128*128 | 64*64 |
| Learning rate | 5e-4 | 8e-4 |
| Output dimension | # of players | 2 |
| Number of evolutions | 20 | 20 |
| Number of batch runs | 30 | 60 |
| Number of final batch runs | 10 | 10 |

## Appendix M Experimental Compute Resources

All experiments in this work were performed on a workstation with an NVIDIA GeForce RTX 3070 GPU, Intel Core i9-10900 CPU at 2.80 GHz, and a Macbook Pro.

## Appendix N Improvement method baselines

Line search is a straightforward iterative process that continuously builds upon the most recent improved strategy. In each iteration, a strategy is generated and evaluated based on feedback from the environment. The feedback is then used to enhance the strategy via the LLM, and this cycle is repeated—similar to the Reflexion framework (Madaan et al., ). The essence of line search lies in its focus on immediate feedback, where only the latest strategy is considered for improvement, ensuring that progress is always aligned with the most recent understanding of the problem space.

Greedy search takes a more competitive approach by selecting the best-performing strategy from the last generation to serve as the foundation for the next cycle of improvements. During each cycle, the best strategy is used to generate $n$ variations, each an attempt at improvement. These variations are evaluated, and feedback from the environment is gathered to determine the best candidate for the subsequent cycle. This method is inspired by the Eureka framework (Ma et al., ), where LLMs are leveraged to iteratively refine reward functions in a manner akin to evolutionary algorithms, focusing on a winner-takes-all selection mechanism.

Best-first search generalizes the improvement process by considering the top $k$ strategies at each iteration, as opposed to focusing on a single best option. This is reminiscent of beam search but with a flexible branching factor that allows for the generation of multiple strategies from each selected candidate. By expanding multiple promising pathways simultaneously, the search can escape local optima and explore a broader solution space. This approach is related to the Tree of Thought method (Yao et al., ), which similarly employs a branching mechanism to explore various strategies in parallel during self-improvement cycles.

Best-first search with thought enhances best-first search by incorporating a reasoning layer into the improvement process. Before generating new strategies, the LLM is prompted to first refine the underlying “thoughts” or decision-making processes that led to the generation of the top $k$ strategies, including possible improvement ideas, before generating a new strategy. This meta-cognitive step draws from the React framework (Yao et al., ), which emphasizes reasoning and actions during strategy development, adding an introspective element that encourages deeper exploration of strategy refinements.

introduces an additional layer of guidance through the use of an idea queue, $Q$. In this approach, ideas are generated and stored in $Q$, providing a reservoir of potential directions for improvement. The LLM uses these ideas to steer the strategy enhancement process, enabling more structured exploration. By separating idea generation from strategy improvement, \methodfacilitates a more focused and deliberate search, ensuring that each iteration explores both immediate refinements and novel directions.

All methods were run with the same computational budget—i.e., each method was allowed to generate the same number of improved strategies—ensuring a fair comparison across approaches in our experiments.

We display a scaling curve for the various improvement methods in Figure 15.

Figure: Figure 15: Number of output tokens from LLM vs game-play performance of generated value heuristics for 6-card GOPS. Each method was run 20 times at different token budgets, and the best function generated by each method was benchmarked against a baseline opponent policy.
Refer to caption: extracted/5921100/graphics/budget_gops.png

### 2.3 Modular search for high-Level strategy improvement

The framework for our high-level strategy improvement process is shown in Figure 2 with corresponding pseudo-code in 1 and more detailed diagram in Figure 9. Each improvement cycle has two steps: (1) reflection and idea generation, and (2) strategy improvement. In the idea generation step, we prompt the LLM to reflect on simulated self-play feedback from previous strategies and generate improvement ideas, which are added to the idea queue. In the strategy improvement step, we select a strategy from the strategy tree and an idea from the queue, prompting the LLM to refine the strategy. The improved strategy is then evaluated through self-play simulations, with feedback and reward signals guiding future improvements.

Figure: Figure 2: Overview of our high-level strategy improvement method: The process alternates between two steps—idea generation and strategy improvement. For more details see Figure 9.
Refer to caption: extracted/5921100/graphics/neurips_third-14.png

The improvement process maintains a strategy library, starting with seed strategies, along with each strategy’s performance score and raw feedback. It also keeps a queue of improvement ideas, tracking how much each idea improves strategies on average (score). Strategies are connected in a tree structure, showing how they evolved and which improvement ideas were used. The process alternates between two loops: the reflection and idea generation step and the strategy improvement step, running for a fixed number of cycles. An adaptive selection policy, such as UCB or BFS, is used to choose strategies and ideas for improvement.

#### 2.3.1 Idea Generation

A sampled strategy $\sigma$ and its simulated feedback trajectory $\tau_{\sigma}$ are selected from the strategy tree using the adaptive selection policy. The feedback consists of trajectories from previous self-play simulations, including visited states, actions taken, estimated win-rates, final outcomes, and intermediate values. Since these trajectories can be lengthy, we select key states to translate into natural language. The LLM is then prompted to reflect on this feedback and propose new improvement ideas, which are added to the idea queue with a prior score estimating their potential effectiveness.

$$ $\texttt{Idea-queue}\leftarrow\texttt{LLM-idea-inventor}(\text{Sampled strategy , strategy feedback})$ $$

#### 2.3.2 Strategy Improvement

We first sample a strategy and an idea from the libraries using a method that balances exploration and exploitation such as UCB. We then prompt the LLM to implement the idea of the strategy, generating a new improved strategy. We then evaluate the strategy using the evaluator, which conducts self-play simulations with the strategy, and records the simulated trajectory data. During simulations, players conduct an MCTS tree search to estimate the expected win-rate at different states, which provides additional feedback. We add the improved strategy (and its performance) to the strategy tree, and update the improvement score for the idea that was used.

$$ $\texttt{Strategy-library}\leftarrow\texttt{LLM-reviser}(\text{Sampled idea, sampled prior strategy})$ $$

#### 2.3.3 Search Modularization

A key challenge in the improvement process is evaluating whether a new strategy is better than the previous one and understanding why. Simply prompting the LLM to improve based on feedback without a clear idea often leads to changes across all parts of the strategy, making it difficult to pinpoint which changes had an impact. To address this, we use an idea queue to modularize the search process. Instead of improving everything at once, we *incrementally refine the strategy, ceteris paribus*, enabling a more *scientific* approach that avoids confounding factors.

The idea queue also helps track successful improvements, which are likely to be useful in the future. Since strategies are similar and used in the same context, improvements from one strategy can be transferred to another. These improvements, often involving additive adjustments like penalties or extra questions, are generalizable across strategies.
We also prompt for high-level, generalizable ideas.
For example, in a dialogue guide, an idea might be to add a certain question. For value heuristics generation, an idea might be to add a dynamic penalty term based on high-value cards. These general ideas apply to various strategies. Empirically, we found that transferable and additive improvements boost performance, as shown in Table 1.

UCB (upper confidence bound) sampling from the idea library helps us both explore new improvement ideas, and exploit old ones. Our UCB equation is

$$ $UCB(\text{improvement idea})=\overline{z}_{\text{improvement idea}}+c\sqrt{ \frac{\ln(N_{\text{total}})}{N_{\text{improvement idea}}}}$ $$

where $\overline{z}$ is the empirical average improvement score, $N_{\text{total}}$ is the total number of idea implementations, and $N_{\text{improvement idea}}$ is the number of times we have implemented this improvement idea specifically.

To make the improvement process more manageable, we optimize the policy for dialogue generation and moves separately in Avalon. We then integrate the two parts (refer to Appendix E), which together produces an agent fully capable of playing games with discussion.
This type of integration of separate components has seen success in other settings such as Diplomacy † et al.(2022)(FAIR)†, Bakhtin, Brown, Dinan, Farina, Flaherty, Fried, Goff, Gray, Hu, et al. ().

### 2.4 Population based self-play simulation

Recent works focus on using either another LLM for critique-based feedback  (Madaan et al., ; Shinn et al., ), real environment interactions  (Nottingham et al., ), or a combination of both  (Wang et al., ) during the LLM-improvement process.
Our method improves on this by simulating opponents using the learned high-level strategy, enabling higher-quality feedback.
Since our high-level strategies can be refined into a policy for any player, we can easily pit different strategies against each other by refining them into specific policies for different players.
Specifically, we use population based self-play, where we conduct round-robin games among the top ten strategies generated and use the average performance as the strategy score for each strategy.
During round-robin games, strategies are given the same level of low-level refinement to ensure fairness.
This evolutionary approach makes the final improved strategy more robust to different opponent policies, since it will have survived multiple round-robin tournaments.
We demonstrate the effectiveness of this method in section 3.4.

## 3 Experiments

Figure: Figure 3: Left: Example performance of value heuristics strategy tree for GOPS. Points indicate the final evaluation scores and the generation of improved functions, with lines showing the evolutionary path between functions. Our method successfully escapes local maxima and continues exploring the strategy space. These scores reflect final gameplay results against a fixed set of opponents, differing from the intermediate self-play scores used to guide strategy improvements. Right: Comparison of different improvement methods on 6-card GOPS, where 9 functions generated by each method play against one another over 1024 total games.
Refer to caption: extracted/5921100/graphics/improvement.png

We demonstrate the effectiveness of our bi-level framework and improvement method through (1) showing how \methodcan outperform existing RL-based deep learning methods, (2) showing how \methodcan outperform LLM-agents that use LLMs to take actions, and (3) showing how our LLM-improvement method outperforms other similar LLM-skill learning methods.
We tested our method on two games that present distinctive challenges. Game of Pure Strategy (GOPS) is a two-player, extensive zero-sum card game (see B for rules) well known and studied for its complexity arising from partial information and simultaneous moves  (Ross, ; Lanctot et al., ).
The Resistance: Avalon is a multi-agent (5+) team-based discussion game (see A for rules) known for its complexity in discussion, deception, deduction, and combining language with action  (Light et al., ).
For Avalon dialogue generation, we specifically benchmark on the Merlin role and Assassin roles, representing the hardest roles on both Good and Evil sides.
Experiments were run with gpt-3.5-turbo-0125, with more ablation studies in Appendix K. Details on how we implemented policies from learned strategies and acquired feedback are described in Section 2.2, and Appendix E, F, and G.

### 3.1 Different LLM Improvement Methods

We demonstrate the effectiveness of our strategy improvement method by benchmarking it against four other skill-improvement methods. Line search (Madaan et al., ) always reflects and improves upon the latest improved strategy. Greedy search (Ma et al., ) selects the best strategy from the last generation of improved strategies to improve upon each improvement cycle. Best first search (Yao et al., ) improves upon the $k$ best strategies generated in any iteration of each improvement cycle. Best first search with thought enhances BFS by prompting the LLM to reflect, think, and propose ideas on how to improve the previous strategy before improving the strategy itself  (Yao et al., ). \methodis our method that uses an additional idea queue $Q$
and an idea generation step to guide the improvement process.
Comparing BFS with thought and \methodhelps demonstrate the value of having a modularized reflection and idea proposition process that is separate from strategy generation, as mentioned in Section 2.3.3. More details can be found in Appendix N.

Our results, presented in Table 1, use the same feedback method (simulation-based population self-play) while varying the improvement methods, with a constant number of new strategies generated across all methods. Figure 3 (right) shows the gameplay scores of these strategies on GOPS. Even when controlling for the number of output tokens generated by the LLM, our method outperforms the others, as demonstrated in Figure 15. We attribute this to (1) the idea queue, which helps test incremental improvements and guide the search process, and (2) our strategy and idea selection policy, which more efficiently explores the strategy space and escapes local maxima (Figure 3 left).

**Table 1: Comparison of different self-improvement methods. The improvement process was run with the same number of strategies generated for each method (40 for GOPS, 24 for Avalon) on the same seed functions, all with GPT3.5. We collect 9 functions from each process and play them against each other (a total of $5\times 9=40$ different agents), reporting the average number of points you win over your opponents for GOPS and the average winrate for Avalon. The median scores ($\pm$ IQR/2) for each method are shown. For the dialogue guide, we show the improvement over the baseline seed function, which has a score $z=-0.875\in[-2,2]$, a rating from opponents which we describe in G.**
| Self-Improvement    Methodology | Line search  (Madaan et al., ; Shinn et al., ) | Greedy search  (Ma et al., ) | Best First Search (BFS) (Yao et al., ) | BFS with thought | \method |
| --- | --- | --- | --- | --- | --- |
| GOPS Value Heuristic | -0.47 $\pm 0.74$ | -0.54 $\pm 0.45$ | 0.092 $\pm 0.67$ | -0.48$\pm 0.375$ | 1.5 $\pm 0.99$ |
| Avalon Value Heuristic | 0.54 $\pm 0.11$ | 0.47 $\pm 0.11$ | 0.50 $\pm 0.085$ | 0.55 $\pm 0.065$ | 0.59 $\pm 0.11$ |
| Merlin Dialogue Guide | $0.37\pm 0.19$ | $0.62\pm 0.13$ | $0.49\pm 0.063$ | $0.37\pm 0.06$ | 0.88 $\pm 0.063$ |
| Assassin Dialogue Guide | $1.83\pm 0.25$ | $1.81\pm 0.063$ | $1.82\pm 0.063$ | $1.89\pm 0.063$ | 1.98 $\pm 0.042$ |

### 3.2 Scaling Inference-Compute can Continually Improve Strategy

Figure: Figure 4: Performance of strategies on GOPS with different MCTS search budgets (nodes). (Left) Scaling curve for initial unimproved LLM-generated value-heuristic. (Right) Scaling curve for improved value-heuristic using \methodafter 20 and 40 iterations (steps) of self-improvement respectively. \methodimproved value heuristics scale better with increased low-level refinement.
Refer to caption: extracted/5921100/graphics/budget_gops_worse.png

We demonstrate that both our high-level strategy improvement and low-level refinement processes scale effectively with increased budgets by showing how different high-level strategies performance with varying MCTS search budgets. A higher search budget allows for more nodes to be looked ahead before taking actions, resulting in a more refined policy. As shown in Figure 4, strategies improved with more iterations using \methodexhibit both higher performance and greater performance gains with increased refinement. Policy refinement also scales exceptionally well.

### 3.3 LLM-improvement vs. Reinforcement Learning (RL) based methods

Figure: Figure 5: Performance of different training methods against the baseline in Avalon and GOPS.
Refer to caption: extracted/5921100/graphics/LLM_RL_Random_avalon.png

We demonstrate the effectiveness of our method compared to traditional RL-based approaches for learning a good policy. Specifically, we show that our method learns a value heuristic function more efficiently than deep RL, as used in AlphaGo, MuZero  (Silver et al., ; Schrittwieser et al., ), and DeepRole  (Serrino et al., ). While AlphaGo uses MCTS  (Kocsis & Szepesvári, ) with a deep value network, DeepRole combines counterfactual regret minimization with a deep value network  (Moravčík et al., ; Zinkevich et al., ). We adapt both algorithms to our setting.

Although deep RL can approximate the true value function with enough data, training, and a large network, we ensure a fair comparison by (1) limiting both RL methods and our approach to the same number of simulated episodes, and (2) capping the number of training steps after each batch of episode trajectory data. While both RL methods and \methoduse the same number of self-play episodes, \methodonly trains on a small subset of transition steps, whereas RL methods train on the entire dataset.
Our results, shown in Table 2 and Figure 5, demonstrate that \methodconsistently outperforms both AlphaGo and DeepRole. More details on our RL implementation and the effects of increased sample size can be found in Appendix L, where we observe performance improvements with additional samples.

**Table 2: Comparison of reinforcement learning vs our method. We run each process 10 times, taking the best strategy generated by each run and playing them against each other for 1024 games. Average win-rates, total number of self-play episodes, and training transition steps across best generated strategies are shown here.**
| Setting | Metric | VS Alpha-go | VS DeepRole |  |  |
| --- | --- | --- | --- | --- | --- |
|  |  | Alpha-go | \method | DeepRole | \method |
| GOPS | Winrate | $-0.39\pm 0.71$ | $0.33\pm 1.21$ | $-0.56\pm 0.57$ | $1.14\pm 0.30$ |
| Self-play eps. | 320 episodes | 320 episodes | 320 episodes | 320 episodes |  |
| Trans. steps | $\sim 3,840$ steps | 100 steps | $\sim 3,840$ steps | 100 steps |  |
| Avalon | Winrate | $0.30\pm 0.11$ | $0.38\pm 0.11$ | $0.33\pm 0.12$ | $0.44\pm 0.08$ |
| Self-play eps. | 160 episodes | 160 episodes | 160 episodes | 160 episodes |  |
| Trans. steps | $\sim 24,000$ steps | $60$ steps | $\sim 24,000$ steps | $60$ steps |  |

### 3.4 Feedback Quality and Reward Signal

We benchmark our feedback method (population based self-play) against (1) an LLM-critic  (Madaan et al., ) and (2) trajectory feedback from a fixed opponent policy, with results in Table 3 showing superior performance in both GOPS action planning and dialogue generation. This shows the effectiveness of our evolutionary population based self-play approach, and that of our strategy abstraction that learns a strategic profile for all players.

**Table 3: Comparison of different methods of collecting feedback. All methods use the same high-level improvement process (\method). For GOPS we collect 24 generated functions from each method and play them against each other. For Avalon we evaluate 9 generated guides. We simulated 32 games for GOPS and 4 rounds of discussion for Avalon to collect gameplay feedback during each improvement step, across 10 and 6 improvement rounds for GOPS and Avalon respectively.**
| Setting/Method | Metric | LLM-critic | Fixed opponent | Population-based Self-play |
| --- | --- | --- | --- | --- |
| GOPS | Performance | $-0.27\pm 1.1$ | $0.089\pm 0.86$ | 0.87 $\pm 1.5$ |
| # of opponents | 0 | 1 | 4 |  |
| Avalon | Performance | $0.37\pm 0.063$ | $0.62\pm 0.13$ | 0.88 $\pm 0.06$ |
| # of opponents | 0 | 1 | 4 |  |

### 3.5 \method vs. LLM Agents

We demonstrate that our method also achieves better performance against other LLM-agents.
ReAct is a popular LLM-agent that prompts the LLM to think before taking an action  (Yao et al., ).
ReCon is a LLM-agent for hidden identity games that prompts the LLM to recursively contemplate on what opponents are thinking and might do before taking actions  (Wang et al., ). We adapt ReCon to our setting by asking the agent to recursively contemplate. Our gameplay results are shown in Table 4. This suggests that through \method, our LLM-agent is able to learn high-level strategies similar in performance to those of ReCon, such as recursive contemplation.

**Table 4: Results of \methodplaying against LLM-based baselines, i.e., ReAct and ReCon. Winrate (%) and assassination accuracy (%) are reported.**
| Metric | VS ReAct | VS ReCon |  |  |
| --- | --- | --- | --- | --- |
| ReAct | \method | ReCon | \method |  |
| Winrate | 47.5 $\pm$ 2.5 | 52.5 $\pm$ 2.5 | 38.9 $\pm$ 5.5 | 61.1 $\pm$ 5.5 |
| #Tokens per round | 56 $\pm$ 14.3 | 164.3 $\pm$ 27.7 | 245.7 $\pm$ 21.2 | 248.2 $\pm$ 24.1 |

## 4 Related Work

LLMs for text agents. Large language models (LLMs) have demonstrated significant emergent capabilities, such as zero-shot prompting and complex reasoning (Bommasani et al., ; Brown et al., ; Raffel et al., ; Wei et al., ; Chowdhery et al., ; Chung et al., ). They also possess extensive world knowledge (Yu et al., ), which has spurred increasing efforts to use LLMs for decision-making in text agents (Wang et al., ). One notable paradigm is ReAct (Yao et al., ), which employs an observation-reasoning-acting loop for agent planning with LLMs. Building on ReAct, Reflexion (Shinn et al., ) incorporates self-reflection to enhance reasoning capabilities. Other works in this domain have utilized feedback (Wang et al., ; Huang et al., ), memory (Park et al., ), and tool use (Schick et al., ; Cai et al., ) to further enhance agent performance. Our proposed method, \method, integrates these components to design an agent capable of systematic analysis and strategic decision-making. Typical prompting techniques for text agents include Chain-of-Thought (Wei et al., ), Tree-of-Thought (Yao et al., ), and Graph-of-Thought (Besta et al., ). While these techniques are effective for high-level reasoning, they are insufficient for complex games that require feedback signals for self-improvement. \methodadopts a bi-level tree search approach, enabling both high-level planning and low-level agent self-play for providing feedback.

Skill learning with LLMs. Recent works have explored the possibly of LLMs learning skills through learning a textual short and long term memory  (Shinn et al., ; Majumder et al., ), or textual insights extracted from the memories  (Zhao et al., ).
Due to the length of trajectories in our game setting and the numerical nature of the data, it is difficult to learn textual memories, so we learn high level strategies instead.
We also explore how to acquire simulational self-play feedback in multiagent settings.
Using LLMs to learn a functional reward model has also been applied to great success on single-agent robotic tasks  (Ma et al., ; Yu et al., ).
We build upon their work by introducing a new improvement method that can help learn a better reward model, and exploring how function learing can be applied to multiagent settings with simulated feedback.

AI in strategy games.
AI has been applied to great success in board games. AlphaGo and MuZero demonstrated the power of combining MCTS, deep learning, and feedback generation using self-play in games such as Go, Chess, and Shogi (Silver et al., ; Schrittwieser et al., ).
Language models can also be trained on human in-game discussion data and integrated with another separately trained action planner to play board games with dialogue  († et al.(2022)(FAIR)†, Bakhtin, Brown, Dinan, Farina, Flaherty, Fried, Goff, Gray, Hu, et al., ).
We build upon the AI for games literature by showing that LLMs can accomplish both * (1) the training of a value heuristic like that in AlphaGo through self-play more efficiently than RL and (2) dialogue generation in discussion games with no human examples*.
These adversarial environments are not just limited to board games. For example, there has been recent interest on creating LLM-agents that can negotiate (Abdelnabi et al., ; Fu et al., ), which our method can also be applied to.

## 5 Conclusion

In conclusion, we have introduced \method, a bi-level framework that facilitates high-level abstract strategy learning with LLMs and a generalizable non-parametric self-improvement mechanism. This approach enables the model to learn and refine skills autonomously. Without relying on task-specific prompts or human-generated policy data, our method demonstrates its ability to learn effective strategies through population-based self-play, guided solely by the rules of the game.

The performance of \methodhighlights the potential of leveraging LLMs for generating high-level strategic abstractions, while using low-level tree search to iteratively refine the policy. This dual approach not only showcases the power of modular guidance—whether through high-level strategy exploration or low-level self-play feedback—but also underlines the value of integrating these processes for accelerated and robust skill acquisition in LLMs.

Furthermore, our results suggest broader implications for the development of LLM-driven decision-making agents across a range of complex domains. By embedding flexible and adaptive learning mechanisms, our framework paves the way for more autonomous systems capable of mastering tasks with minimal human intervention. This opens new avenues for the application of LLMs in areas such as multi-agent systems, reinforcement learning, and general AI, where strategic planning and self-improvement are key.

## Appendix A Resistance: Avalon Game Description

Figure: Figure 6: The three phases per round of Resistance game. Good players are shown in blue, while Evil players in red. In Selection Phase, the team leader (player 5 in this round) proposes a team (player 1 and 5, himself). In Voting Phase, all players vote publicly whether to approve this team or not. If the strict majority votes yes, the team is approved and moves on to the mission phase. Otherwise, redo the Selection Phase with the next player as leader. If the team goes on the Mission Phase, selected team members (player 1 and 5) anonymously vote to pass or fail the mission. If at least one person (player 1, as he is the evil player) votes fail, the mission fails. Otherwise, it succeeds.
Refer to caption: extracted/5921100/graphics/Avalon-06.png

Figure: Figure 7: Communication Skills required to play Avalon. 1) First, they use logical reasoning to analyze the voting pattern and dialogue of other players and deduce their motives. 2) they must coordinate, communicate, and persuade their teammates to follow a particular strategy. 3) they must also hide their identity and motives through deception.
Refer to caption: extracted/5921100/graphics/Avalon-07.png

We describe the game in more detail here.
There are four phases in the game where players need to make decisions: (1) team selection phase, (2) voting phase, (3) quest phase, and (4) assassination phase. The game alternates between the first three phases until the end condition is reached, at which point we move on to the assassination phase. Each phase also contains discussion where players can challenge others, defend themselves, and negotiate. A flowchart of the game is presented in Figure 8, and an Avalon Rule Prompt is included in Section A.4.

### A.1 Roles

There are four basic roles in Resistance Avalon: Servant of Arthur, Minion of Mordred, Merlin, and Assassin. The Servant is a basic good character who does not know the identity of any of the other players. The Minion is a base evil character who knows who is good and evil but does not know the specific roles of each player. Merlin is a unique good character who knows who is good and evil. The Assassin is a unique evil character who knows who is good and evil, and in addition, has the ability to assassinate a character at the end of the game. If that character is Merlin, the evil team wins.

Good players will always outnumber evil players.
Hence, evil players must pretend to be good in order to be voted in on teams (and thus sabotage missions). Servants will thus need to sniff out the evil players through their actions and dialogue. Merlin is usually the only good player with additional information, so they will need to discreetly guide the Servants in the right direction. Servants also need to protect Merlin, so a common strategy is for Servants to pretend to have hidden information so that evil players will think that they are Merlin. Evil players will be trying to sniff out Merlin at the same time, so deduction skills are required for all roles.

### A.2 Actions for each Phase

Depending on the phase team selection, voting, quest, and assassination, players may conduct different actions. We detail the specific actions that players can take in each of these phases below.

During the team selection phase, only the current *leader* has to make a choice. Leadership passes around the players sequentially in a loop. The action space of team selection for the leader consists of all subsets of the players with size equal to the mission team size. The mission team size is different for each mission and is determined by the total number of players in the game. For example, in a 5-player game, on mission No.4, the mission team size is $3$, so any subset of $\{1,2,3,4,5\}$ with size $3$ would be a valid action. After the team proposal is determined by the leader, we move on to the voting phase with the selected players.

During the voting phase, *every* player in the game needs to simultaneously vote either Approve (1) or Reject (0). Votes are publicly revealed to all players, so players can see what other players voted. If a strict majority votes APPROVE (1), we then move on to the quest phase with the team that was approved. Otherwise, we move back to the selection phase. Note that if four teams have been rejected in a row, and this is the fifth time a team is proposed (for the same mission), we skip the voting and move directly to the quest phase. This prevents the game from dragging on forever.

During the quest phase, *each selected player on the approved team* votes anonymously to either Pass (1) or Fail (0) the mission. The number of votes of Pass vs Fail are then revealed to everybody. If the number of Fails is greater than or equal to the number of Fails required for the mission to fail (usually 1), then this mission is marked as a failure.
Otherwise, this mission is marked as a success. Hence, good players usually have no incentive to fail missions, while evil players will want to have enough failures to pass the failure threshold. If three out of five missions fail, evil wins immediately. Otherwise, if three out of five missions succeed, we move on to the assassination phase.

Figure: Figure 8: Flowchart illustrating the various game states and transition diagram. Round boxes indicate game states (phases) where the player (role highlighted in bracket) has to make decisions
Refer to caption: x1.png

### A.3 Discussion

Group discussion occurs between the quest and selection phases, as well as right before the assassination phase. Players may not communicate during any other time. All conversations are public, and there is no private communication. Typically players may discuss in any format of their choosing as long as only one person is speaking at a time. Some examples of formats include a natural (spontaneous) seminar style (most common, where there is no fixed order of speaking), or sequentially (where players speak in some predefined order). Interruptions and arguments between two players are very common between human players.

Usually, players will spend this time discussing a couple of key topics, including (1) the observations they made, (2) the guessed identities and sides of players, and (3) the plan for the next mission. The team leader will usually spend this time asking for advice on what team to select and gathering support for that team. Persuasion and adhering to the preferences of other players are usually key to getting a team approved. Players can also accuse other players of being evil, though arguments will need to be justified in order to be persuasive.

For example, a player (player 3) could start off by stating their (1) observations of what happened in the previous mission. One Fail was observed, so at least one player on the previous team (consisting of players (1,2,3)) is evil. Player 3 then emphasizes that both Players 1 and 2 voted Approve for the previous mission, which ended up a failure. Moreover, the team was proposed by Player 1 in the first place. Player 3 then moves on to discuss the (2) identities of other players. The player says that, despite the fact that only one Fail was observed, both Players 1 and 2 are evil since they both voted to Approve previously. Player 0 is probably good since they voted to Reject in the previous mission, and Player 3 is also good since they also voted to Reject, even though they were on the mission. Player 3 then says what they think the (3) plan should be. Specifically, Player 3 says that they should reject the current team no matter what since Player 2 is the leader and is evil. The leadership will then pass to Player 3, who will choose the team $(0,3,4)$, which good players should vote to approve since it does not contain any suspected evil players(^1^11At this point, Player $2$ reveals that they are the assassin and assassinates Player $3$, who is indeed Merlin. Player $3$’s intuition and analysis were way too correct to be a Servant).

### A.4 Game Ending and Assassination

In classic Resistance, a good team wins immediately if three missions are successful. In Resistance Avalon, there is an additional assassination phase if three missions are successful.
During the assassination phase, the Assassin player chooses one player to assassinate. If that player is Merlin, then evil wins. Otherwise good wins.

Before they assassinate a player, the Assassin player can and is encouraged to discuss with the other players (mostly their teammates). good players are also welcome to join in on this discussion to mislead the evil players, though it rarely helps. Players can discuss in a format of their choosing, though there is usually a time limit on how long players can discuss before reaching a decision.

## Appendix B Game of Pure Strategy (GOPS) Game Description

Game of Pure Strategy (GOPS) is a card game for two or more players with a standard deck of card, which is commonly used as an example of multi-stage move game in artificial intelligence (Wikipedia contributors ()). In our experiments we play 5 or 6 card GOPS. Specifically, the score cards are $\{1,2,....n\}$ and each player starts with a hand of cards $\{1,2,....n\}$ where $n$ is the number of cards and rounds. The GOPS rules prompt is included in this section below.

## Appendix C Limitations

While our method performs better on average, individual runs can have high variance.
Since the performance of an agent in multi-agent adversarial game settings is highly dependent on opponents’ policies, feedback from these environments tend to be highly noisy, with noise increasing with the number of players.
This is especially true when learning Avalon heuristics, where the performance depends on the policies of 5 other players, teammates and opponents.
We believe that running more game simulations with different opponent policies can help reduce this feedback noise. We also acknowledge the inherent noisiness in LLM generations and how that can impact our results. We tried to reduce this noise by (1) using the same seed functions when benchmarking the different LLM improvement methods and (2) collecting generated strategies from multiple runs.
We also did not test our method on other non-adversarial environments such as question answering and text-based worlds.
However, given the strong performance of our method in adversarial multi-agent settings, we believe that similar performance will be observed in single agent, non-adversarial settings.

## Appendix D Improvement Process Implementation Details

Figure: Figure 9: Overview of our high-level strategy improvement method: The process alternates between two steps—idea generation and strategy improvement.
Refer to caption: extracted/5921100/graphics/neurips-two-thirds-02.png

Figure: Algorithm 1 \methodPseudocode

## Appendix E Avalon Agent Implementation Details

We describe in detail how we implement our model below and as shown in figure 10. Unless otherwise specified, the word ‘action’ will refer to non-dialogue actions. Note that we do not conduct search over raw dialogue space since that is not very computationally feasible. Instead, we search over intended actions and condition our dialogue on that.

Specifically, the language component consists of a dialogue analyzer and a dialogue generator, while the moves component consist of the action planner. Whenever the agent needs to speak, they first analyze what was said so far in the current discussion round using the dialogue analyzer. The dialogue analyzer, with the help of an LLM, updates the internal beliefs of the agent. For example, in Avalon, internal beliefs might include the probability that the agent assigns to each other player of being Evil and of being Merlin. These beliefs are then passed to the action planner, which uses them to figure out the best next move, i.e. the action intent. The action intent is then passed to the dialogue generator, which generates dialogue with the help of an LLM.
When the agent needs to take a move, we run through the same process except that the agent takes the action intent as the move and no dialogue is generated.

Figure: Figure 10: Overview of the LLM-powered agent, including the three main modules that we use to generate dialogue during discussion
Refer to caption: extracted/5921100/graphics/dialogue-action-02.png

### E.1 Dialogue Analyzer (Discriminator)

The dialogue analyzer $f_{ana}$ takes as input $\boldsymbol{I}$ information set (partial information) of the current state for the player, $\boldsymbol{d}_{t}$ the discussion so far this round, and $\boldsymbol{b}$ some prior beliefs about the hidden state of the game, and returns $\widehat{\boldsymbol{b}}$, the updated beliefs, and $\widehat{\boldsymbol{\Pi}}_{t}$, the predicted joint action policy of the all the players (i.e. the action intent) for the next action step $t$. Recall that simultaneous games can be expanded as partial information games, where the simultaneous moves are treated as hidden information. Hence, we are essentially predicting a distribution over the hidden states $\boldsymbol{s}$ given the information set $\boldsymbol{I}$ using the dialogue analyzer.

$$ $\widehat{\boldsymbol{b}},\widehat{\boldsymbol{\Pi}}_{t}=f_{ana}(\boldsymbol{I} ,\boldsymbol{d}_{t},\boldsymbol{b})$ $$

In the context of Avalon, $\boldsymbol{I}$ will contain information such as (1) the dialogue this round so far (2) summary of the dialogue from previous rounds (3) mission track record (4) historical record of actions taken by players in previous rounds, and (5) private information of the player such as who is Good and Evil. $\boldsymbol{b}$ will contain information on (1) the probability of each player being Evil and (2) the probability of each player being Merlin, both conditioned on the private information contained in $\boldsymbol{I}$. While a full treatment of the distribution over the hidden state space $\mathcal{S}$ we require assigning probabilities to each possible combination of Good and Evil players, not just assessing the marginal probability of each player being Good individually, in practice

We implement $f_{ana}$ using an LLM, which is fed $\boldsymbol{I}$, $\boldsymbol{d}$, $\boldsymbol{b}$ (converted to natural language form) as prompts, along with some instruction prompt $\boldsymbol{\phi}_{ana}$ that prompts it to produce $\widehat{\boldsymbol{b}},\widehat{\boldsymbol{\Pi}}_{t}$. Specifically,

$$ $f_{ana}(\boldsymbol{I},\boldsymbol{d}_{t},\boldsymbol{b})=f_{LLM}(\boldsymbol{ \phi}_{dis},\boldsymbol{I},\boldsymbol{d},\boldsymbol{b})$ $$

We show examples of such prompts in Appendix J.

### E.2 Action Planner

Given $\widehat{\boldsymbol{b}}$ the belief prior, $\widehat{\boldsymbol{\Pi}}_{t}$ the predicted joint action policy for all players, and $\boldsymbol{s}$ the representation of the current state, the action generation model $f_{act}$ generates a probability distribution over possible actions $\boldsymbol{\pi}^{i}$ for the main player $i$ that is the best response to $\widehat{\boldsymbol{\Pi}}_{t}$. We do so by using search techniques to look ahead and find the best response.

$$ $\boldsymbol{\pi}^{i}=f_{act}(\widehat{\boldsymbol{b}},\widehat{\boldsymbol{\Pi }}_{t},\boldsymbol{I})$ $$

More specifically, in our search implementation, at the first layer, we first sample across possible hidden states $\boldsymbol{s}\sim\widehat{\boldsymbol{b}}$ according to the belief prior. At the second layer (i.e. the first action stage $t$), we calculate expected $q$-values for each action $a\in\mathcal{A}$ that the main player can take if the other players play actions $\boldsymbol{a}\sim\widehat{\boldsymbol{\Pi}}_{t}$ according to the predicted joint distribution. In subsequent action stages, the search process will assume that other players play according to their policy simulated and induced by the value heuristic that is not dialogue dependent. We then take the best response action $a^{*}_{i}=\mathop{max}(\boldsymbol{\pi}^{i})$ as the intended action. Since this is a partial information game, expected $q$-values are taken across information sets, not states. We describe how our action planner is implemented in more detail in Appendix F.

### E.3 Dialogue Generation

The dialogue generator $f_{gen}$ takes as input $\boldsymbol{I}$ some representation of the current information set and $a^{*}_{i}$, the intended best response action, and outputs dialogue $d$.

$$ $d=f_{gen}(\boldsymbol{I},a^{*}_{i})$ $$

We will implement $f_{gen}$ using an LLM, which is fed $\boldsymbol{I}$ and $a^{*}_{i}$ directly as prompts, along with some instruction prompt $\phi_{gen}$ that prompts it to produce realistic sounding dialogue that helps it achieve its intended action.

For example, perhaps the player wants to approve the next team. Then it should try to generated dialogue that convinces the other players to also approve.

We show examples of such prompts in Appendix J.

## Appendix F Value Heuristic Implementation Details

Figure: Figure 11: Overview of how we utilize the trained value heuristics in MCTS tree search to get a non-dialogue based policy. While we only display the values for a single player in the diagram, note that in practice we infer and update the values for all players at the same time. Next states are sampled using the PUCT formula we described. We sample an initial hidden state based on the internal beliefs of the agent. Metropolis-Hastings is used to sample since it may be difficult to calculate the probability density specified by the internal beliefs. Note that values estimated using MCTS are also passed as feedback to the evaluator.
Refer to caption: extracted/5921100/graphics/neurips_third-04.png

The MCTS search process is depicted in Figure 11, where we simulate a trajectory from the hidden state we are at until we reach some unexpanded state $s$. The probability of transitioning to a state during simulations is computed assuming that each player samples from their optimal actions according to their PUCT (polynomial upper confidence trees) values (and $\phi_{e}$ for the environment actor)  (Schrittwieser et al., ). Since in some environments players may only be able to observe information sets, when computing the PUCT values we average over all expanded states in that information set. Moreover, the initial hidden state can be sampled according to a prior (or empirical prior) over the states in the information set that the player observed.
Then, using our value heuristic, we compute the values of each of the next hidden states. We then backpropogate our new values back up the simulated trajectory, updating the intermediate states. After running a few MCTS simulations (roll-outs) like the one we described, the planner then outputs the action which leads to the highest value next state. We show our information set PUCT formula below, where $N(s,a)$ is the number of times we took action $a$ at state $s$ during MCTS rollouts, $P(s,a)$ is the prior prior probability of selecting action $a$ from state $s$, $C$ is the exploration constant, $Q_{emp}$ is the empirical average of MCTS roll-out outcomes, $\widehat{Q}(s,a)$ is the prior computed by our value heuristic, $\alpha$ controls how much weight be put on the prior (often $\alpha=1$), and $\pi_{B}$ is the distribution across hidden states in the information set given our beliefs $B$, some parametrization of $\pi_{B}$. Since $\pi_{B}$ is often hard to compute, we can simply set $\pi_{B}(s|I)=\frac{\sum_{b}N(s,b)}{\sum_{s^{\prime}\in I}\sum_{b}N(s^{\prime},
b)}$ to be the empirical roll-out distribution, given that we sample initial states $s_{0}\sim\pi_{B}(s_{0}|I)$ according to our beliefs. For example, in Avalon, we can sample the hidden roles according to our beliefs $B$ using Metropolis-Hastings for the initial state $s_{0}$.

$$ $\displaystyle Q(s,a)=\frac{N(s,a)\cdot Q_{\text{emp}}(s,a)+\alpha\cdot\widehat {Q}(s,a)}{N(s,a)+\alpha}$ (1) $\displaystyle\text{PUCT}(I,a)=\sum_{s\in I}\pi_{B}(s|I)\left[Q(s,a)+C\cdot P(s ,a)\cdot\frac{\sqrt{\sum_{b}N(s,b)}}{1+N(s,a)}\right]$ (2) $$

## Appendix G Dialogue Guide Improvement Evaluation Implementation Details

We provide more details on our dialogue improvement evaluation process here and as shown in figure 12. The improvement method (skill coach) remains the same as we described before.

We first generate a synthetic dataset by simulating a game of Avalon with initial dialogue and move policies $\boldsymbol{\phi}$. Given the dialogue guide $\sigma$ we want to evaluate, we then sample ‘scenarios’ from the dataset. A scenario consists of a game state, intended action, and private information in the simulated trajectory. We create an Avalon agent like the one we described in E for each player in the game, initialized with their corresponding private information. The Avalon agent is then asked to generate dialogue using the dialogue guide $\sigma$.

Using this new generated dialogue, we then simulate the next round of dialogue analysis for each Avalon agent. This produces analysis scores based on how likely they think the player is to be Merlin $z_{merlin}$, and how likely they think the player is to be Evil $z_{evil}$, where $z_{merlin},z_{evil}\in[-2,2]$. For evaluating Merlin, we get the average $z_{merlin}$ scores from the Evil players, $\overline{z}_{merlin}$, along with the average $z_{evil}$ scores from the Good players $\overline{z}_{evil}$. We then take the minimum of these two as the feedback score $z=\mathop{min}\{\overline{z}_{evil},\overline{z}_{merlin}\}$. This is because Merlin wants to both minimize the probability of being detected by the Evil players, and also minimize the probability of being identified as Evil by the Good players.

Figure: Figure 12: Overview of our improvement process for learning dialogue generation strategies. This includes how we evaluate the dialogue and how we collect feedback. The skill coach here can be implemented as either our improvement method, \method, or any of the baseline methods we described.
Refer to caption: extracted/5921100/graphics/neurips_third-03.png

The dialogue analyzer (discriminator) is described in more detail in Appendix E and the specific generation and analysis prompts are shown in Appendix J.

## Appendix H Value Heuristic LLM Prompt and Output Examples

### H.1 System Prompts

System prompt are guidelines for LLM to generate outputs align with the intended goals. In our case, the goal is to generate a function that evaluates the value of a state in a game under low cost.

The following example is a detailed prompt telling the LLM how to format the value heuristics specifically in the GOPS game. The format of input and output are clearly defined in the prompt with illustrations, examples and structures.

### H.2 Idea Generation Examples

The idea generation prompt included system prompt, game rules, previous guide and feedback reflections. Following those four components, we construct the format and an example of ideas to guide the generation of LLM.

Below is an instance of Feedback of GOPS game, showing the setup of two players, the intermediate values involved in the computation, and the actual scores.

Recall that feedback reflection refers to feedback for strategy, which is used to generate ideas. For prompting, We specify that game rules, previous guide and feedback examples are generated previously. The following is the prompt for feedback reflections.

Below is the feedback reflections from the LLM.

Also, with the prompts of idea generation, below is the generated new ideas by LLM.

### H.3 Strategy Implementation Examples

During the strategy implementation step, we first select a strategy and an idea from the libraries using the adaptive selection policy. Then, we prompt the LLM to implement the idea on the strategy, generating a new improved strategy.

In this section, we showcase two examples. Each example illustrates strategies before and after enhancements made by the LLM. This comparison highlights the effectiveness of our strategy implementation. The improved parts by LLM are highlighted in yellow.

Below is the prompt for strategy implementation.

#### H.3.1 Example 1

Below is the GOPS Value Heuristics Function before the strategy improvement.

Below is the selected idea to improve the above strategy.

Below is the GOPS Value Heuristics Function after enhancement by LLM.
The improved parts by LLM are highlighted in yellow.

#### H.3.2 Example 2

Below is the Avalon Value Heuristics Function before improvements.

Below is the improvement idea pf Avalon Value Heuristics Function.

The following is Avalon Value Heuristics Function after enhancements, highlighted in yellow.

#### H.3.3 Example 3

Below is the GOPS Value Heuristics Function before the strategy improvement.

Below is the selected idea to improve the above strategy.

Below is the GOPS Value Heuristics Function after enhancement by LLM. The improved parts by LLM are highlighted in yellow.

#### H.3.4 Example 4

Below is the GOPS Value Heuristics Function before the strategy improvement.

Below is the selected idea to improve the above strategy.

Below is the GOPS Value Heuristics Function after enhancement by LLM. The improved parts by LLM are highlighted in yellow.

## Appendix I Dialogue Guide LLM Prompt and Output Examples

This sections shows the system prompts of dialogue guidance on LLM and several examples, including system prompts, idea generation prompts, and strategy implementation examples.

### I.1 System Prompts

Below is the Dialogue guide system prompt.

Dialogue guide signature follows, specifying the structures and contents dialogues regarding role playing the Merlin.

### I.2 Idea Generation Examples

The following is the selected dialouge guide speaking as the Merlin role.

A feedback example is provided for better understanding of dialogue guidance to teach LLM how to role play Merlin.

This is the prompt for feedback reflections.

The following are the feedback reflections generated by LLM.

Below is the Prompt for idea generation regarding this dialogue guides

Generated new improvement ideas are demonstrated below, showing the improvements made by LLM following the prompt for idea generation.

### I.3 Strategy Implementation Examples

Recall the strategy implementation mentioned in the paper before. Here, we implement strategy improvements on dialogue guide. The improved dialogue guide is highlighted.

#### I.3.1 Example 1

Below is the dialogue guide before any improvements happened.

Below is the improvement idea prompted into LLM.

Here, implementation prompty follows to teach LLM how to improve the dialogue guide.

Finally, we have a improved dialogue guide, where the changes are highlighted below comparing to the previous guide.

#### I.3.2 Example 2

Below is the dialogue guide before any improvements happened.

Below is the improvement idea prompted into LLM.

Here, implementation prompt follows to teach LLM how to improve the dialogue guide.

Finally, we have a improved dialogue guide, where the changes are highlighted below comparing to
the previous guide

#### I.3.3 Example 3

Below is the dialogue guide before any improvements happened.

Below is the improvement idea prompted into LLM.

Here, implementation prompt follows to teach LLM how to improve the dialogue guide.

Finally, we have a improved dialogue guide, where the changes are highlighted below comparing to the previous guide

## Appendix J Dialogue Generation and Analysis Example LLM Inputs and Outputs

This sections shows the examples of dialogue generation and analysis, including descriptive prompts, dialogue generation, and dialogue analysis.

### J.1 Descriptive Prompts

Below is the discussion history prompted into LLM for better knowledge of dialogue generation.

State description shows LLM which state it will be for role playing and dialogue generation.

### J.2 Dialogue generation

Below is the prompt for filling out worksheet. Filling out this worksheet assists LLM generated better dialogue aligned with the role, Merlin as in the example.

The worksheet filled out by LLM follows, demonstrating the LLM capability and the effectiveness of prompting.

Below is the prompt for speech generation. Worksheet completion assists LLM to understand the states and role. The following prompt asks LLM to assemble responses to the questionaire filled out above.

Finally we have LLM generated speech after the preparations.

### J.3 Dialogue Analysis

After dialogue generation, we continue have LLM assume the role of Merlin, and dialogue analysis is conducted.

Below is the prompt for dialogue analysis regarding to the role of Merlin. A thought is included to guide LLM analyze.

Generated dialogue analysis follows. The role is Merlin.

Under dialouge analysis, besides focusing on one specific role, we also have LLM target on good and evil in the game, which is broader in terms of role playing. Below is the prompt for dialogue analysis regarding to Good and Evil.

Below is the dialogue analysis generated by LLM on Good and Evil.

## Appendix K Other Ablation Studies

#### K.0.1 Base LLM Model

We show the performance of different base models in Figure 13.

Figure: Figure 13: Game play performance of base LLM models on six card GOPS: GPT3.5 and GPT4.0. We see that the two language models perform similarly with our method.
Refer to caption: extracted/5921100/graphics/gpt_4_35.png

#### K.0.2 Search Budget

How does the effectiveness of the search+LLM agent scale with regards to the search budget? Does having a larger search process help achieve better performance?

**Table 5: Average score difference for MCTS (num_rollout=32) + LLMFunction (Player1, top-3 functions shown in the table) vs. MCTS (num_rollout=32) + RandomRollout (Player2, num_rollout=10); 100 games for each experiment;**
| budget | Best Func. | 2nd Best Func. | 3rd Best Func. |  |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Player 1 | Player 2 | Player 1 | Player 2 | Player 1 | Player 2 |  |
| 16 | -0.91 | 0.91 | -0.7 | 0.7 | -0.88 | 0.88 |
| 32 | -0.95 | 0.95 | 0.44 | -0.44 | -0.73 | 0.73 |
| 64 | -1.14 | 1.14 | 1.15 | -1.15 | 0.46 | -0.46 |
| 128 | -1.28 | 1.28 | 0.36 | -0.36 | 0.25 | -0.25 |
| 256 | -0.45 | 0.45 | -0.85 | 0.85 | -0.42 | 0.42 |
| inf | -1.5 | 1.5 | -2.26 | 2.26 | -1.03 | 1.03 |

## Appendix L Details on Learning the Value Heuristic via Reinforcement Learning

We employ Monte-Carlo based RL approach (Sutton & Barto ()) to train a value heuristic for both five-player Avalon and five-card GOPS games. To do so, we construct a MSE loss in each episode for training the value function, i.e.,

$$ $\displaystyle\mathop{argmin}_{\theta}\sum_{i}^{\mathcal{N}}\sum_{t=0}^{T}\left (V_{\theta}^{i}(s_{t})-Score^{i}(s_{t})\right)^{2}$ $$

where $\mathcal{N}$ represents the number of actors, $V_{\theta}^{i}(s_{t}),i=1,2,\cdots,\mathcal{N}$ denotes the value function for each actor, and $T$ is the time horizon. Notice that $s_{t}$ and $Score^{i}(s_{t})$ denote the state at time step $t$ and the corresponding cumulative reward for each actor, i.e., $\sum_{t}^{T}R_{i}(s_{t},a_{t})$. It is worth pointing that $Score^{i}(s_{t})$ (the cumulative reward starting from $s_{t}$) is the unbiased estimate of the value function $V_{\theta}^{i}(s_{t})$.

For both Avalon and GOPS games, the value function $V_{\theta}^{i}(s_{t})$ is predicted by a neural network. We then train the value function network by minimizing the aforementioned loss function over episodes. In Avalon, we consider 20 evolutions (epochs) for the training process. At the end of each evolution, 30 batch runs (episodes) are generated and used to train the value function network, i.e., a total of 600 episodes for training. In GOPS, we train by 20 evolutions as well while considering 60 batch runs each (1200 episodes in total). We evaluate the final performance over 10 episodes in both games. The neural network is constructed by a multilayer perceptron (MLP) with 2 hidden layers. We select a hidden layer size of $128*128$ for Avalon and that of $64*64$ for GOPS. Likewise, the chosen learning rates are $5e-4$ and $8e-4$, respectively. The value function is expected to predict the score for each player in the game, e.g., two for GOPS and number of players for Avalon. All experimental hyper-parameters are summarized in Table 6.

Having introduced the set up, one can observe in Figure 14 an increased performance of RL-trained value heuristic in both five-player Avalon and five-card GOPS games. This validates the improvement for training value heuristic via reinforcement learning within limited evolutions.

Figure: (a) Avalon
Refer to caption: extracted/5921100/graphics/avalon_rl_improve.png

**Table 6: Summary of experimental hyper-parameters in RL-training value heuristic**
| Parameters | Avalon | GOPS |
| --- | --- | --- |
| Type of neural network | MLP | MLP |
| Number of hidden layers | 2 | 2 |
| Hidden layer size | 128*128 | 64*64 |
| Learning rate | 5e-4 | 8e-4 |
| Output dimension | # of players | 2 |
| Number of evolutions | 20 | 20 |
| Number of batch runs | 30 | 60 |
| Number of final batch runs | 10 | 10 |

## Appendix M Experimental Compute Resources

All experiments in this work were performed on a workstation with an NVIDIA GeForce RTX 3070 GPU, Intel Core i9-10900 CPU at 2.80 GHz, and a Macbook Pro.

## Appendix N Improvement method baselines

Line search is a straightforward iterative process that continuously builds upon the most recent improved strategy. In each iteration, a strategy is generated and evaluated based on feedback from the environment. The feedback is then used to enhance the strategy via the LLM, and this cycle is repeated—similar to the Reflexion framework (Madaan et al., ). The essence of line search lies in its focus on immediate feedback, where only the latest strategy is considered for improvement, ensuring that progress is always aligned with the most recent understanding of the problem space.

Greedy search takes a more competitive approach by selecting the best-performing strategy from the last generation to serve as the foundation for the next cycle of improvements. During each cycle, the best strategy is used to generate $n$ variations, each an attempt at improvement. These variations are evaluated, and feedback from the environment is gathered to determine the best candidate for the subsequent cycle. This method is inspired by the Eureka framework (Ma et al., ), where LLMs are leveraged to iteratively refine reward functions in a manner akin to evolutionary algorithms, focusing on a winner-takes-all selection mechanism.

Best-first search generalizes the improvement process by considering the top $k$ strategies at each iteration, as opposed to focusing on a single best option. This is reminiscent of beam search but with a flexible branching factor that allows for the generation of multiple strategies from each selected candidate. By expanding multiple promising pathways simultaneously, the search can escape local optima and explore a broader solution space. This approach is related to the Tree of Thought method (Yao et al., ), which similarly employs a branching mechanism to explore various strategies in parallel during self-improvement cycles.

Best-first search with thought enhances best-first search by incorporating a reasoning layer into the improvement process. Before generating new strategies, the LLM is prompted to first refine the underlying “thoughts” or decision-making processes that led to the generation of the top $k$ strategies, including possible improvement ideas, before generating a new strategy. This meta-cognitive step draws from the React framework (Yao et al., ), which emphasizes reasoning and actions during strategy development, adding an introspective element that encourages deeper exploration of strategy refinements.

introduces an additional layer of guidance through the use of an idea queue, $Q$. In this approach, ideas are generated and stored in $Q$, providing a reservoir of potential directions for improvement. The LLM uses these ideas to steer the strategy enhancement process, enabling more structured exploration. By separating idea generation from strategy improvement, \methodfacilitates a more focused and deliberate search, ensuring that each iteration explores both immediate refinements and novel directions.

All methods were run with the same computational budget—i.e., each method was allowed to generate the same number of improved strategies—ensuring a fair comparison across approaches in our experiments.

We display a scaling curve for the various improvement methods in Figure 15.

Figure: Figure 15: Number of output tokens from LLM vs game-play performance of generated value heuristics for 6-card GOPS. Each method was run 20 times at different token budgets, and the best function generated by each method was benchmarked against a baseline opponent policy.
Refer to caption: extracted/5921100/graphics/budget_gops.png

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 3
presentation: 3
questions: 1. How does the proposed method compare to other RL-LLM approaches? Both conceptually and experimentally?

2. Is STRATEGIST properly randomizing its actions in the actual play of Avalon?

3. Are there any human evaluation results?
soundness: 2
strengths: 1. The idea of using LLM to generate high-level strategy and use MCTS to get low-level strategy is interesting.

2. The proposed method is evaluated in two game environments, one simple and one complex, which is good.
summary: The paper presents STRATEGIST which combines LLM-generated high-level strategies with Monte Carlo Tree Search (MCTS) for refined action execution. STRATEGIST uses population-based self-play to optimize strategies. The paper presents experimental results in two game environments: GOPS and The Resistance: Avalon. The results indicate that STRATEGIST outperforms traditional RL agents and pure LLM-based methods.
weaknesses: 1. 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. 

2. 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. 

3. 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.

4. 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.

5 (minor). Ambiguity in RL Positioning: The abstract and methodology sections position MCTS as an RL method. However, MCTS is typically classified as a heuristic search within the RL framework and lacks key RL characteristics, such as learning policy updates from experience. So I would suggest the authors carefully choose the wording to avoid confusing the readers.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: - 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).
soundness: 3
strengths: - The paper is well written and well organised.
- The description of different components in STRATEGIST is clear.
- The experimental results are strong and comprehensive.
summary: This paper introduces STRATEGIST, which is a framework to optimize the strategy induced by LLMs through population-based self-play simulations without the need for any training data. The effectiveness of STRATEGIST in learning optimal strategies is demonstrated against strong baselines on Game of Pure Strategy (GOPS) and the Resistance: Avalon.
weaknesses: - 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] ...) .

[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)

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: Please see Weaknesses.
soundness: 3
strengths: 1. Novel approach: the combination of LLMs with a bi-level tree search for strategy improvement is a novel method for enhancing performance in complex multi-agent games. Addressing both high-level strategic planning and low-level execution allows for improvements of agent capabilities.
2. Good empirical evaluation: The authors conduct various ablation studies and additional experiments comparing their method with established baselines like DeepRole and ReCon, providing a broader context for their contributions.
summary: The paper presents Strategist, a novel framework that leverages Large Language Models (LLMs) for strategic skill acquisition in multi-agent games through a bi-level tree search and self-improvement mechanism. The approach aims to enhance both high-level strategy formulation and low-level execution by utilizing self-play simulations and LLM-based reflections. The framework is evaluated on two games, Game of Pure Strategy (GOPS) and Resistance: Avalon, demonstrating improved performance over baseline methods.
weaknesses: 1. 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.
2. 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.
3. Statistical significance and result variability: the reported variances are very large and show significant overlap in many results like Table 1, 2, 3, etc., which implies that the proposed methods might not be delivering substantial enhancements in these test environments. For example, in Table 2, the result of Alpha-go is $-0.39\pm0.71$, and the result of Strategist is $0.33\pm1.21$. The variance is too large to determine whether the new method offers improvements over existing baselines.
4. Suggestions on some related works: the experiments on mainly conducted on the social deduction game named Avalon. A closely related game is Werewolf and there are some recent works like [1,2,3] on building LLM AI agents for these games and could be added to the related work section.

[1] Yuzhuang Xu, et al. "Exploring large language models for communication games: An empirical study on werewolf." arXiv preprint arXiv:2309.04658 (2023).

[2] Zelai Xu, et al. "Language agents with reinforcement learning for strategic play in the werewolf game." arXiv preprint arXiv:2310.18940 (2023).

[3] Bailis, Suma, Jane Friedhoff, and Feiyang Chen. "Werewolf arena: A case study in llm evaluation via social deduction." arXiv preprint arXiv:2407.13943 (2024).

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
questions: - What happens when the LLM generates syntactically correct but semantically inconsistent or illogical strategies? How does the framework detect and handle such cases? 
- How does the method prevent the idea queue from becoming dominated by similar or redundant improvement suggestions? 
- What happens when there are multiple valid interpretations of a strategy? How is the most appropriate one selected? 
- Are the proposed method verified to learn general strategies instead of overfitting to specific feedback examples?
- Could the method combine successful elements from different strategies into new hybrid approaches?
soundness: 3
strengths: - Integration of LLMs with MCTS in a bi-level framework that leverages their complementary strengths.
- Clear empirical validation through rigorous experiments.
- The paper is well written and easy to follow
summary: The paper presents STRATEGIST, a framework that combines LLMs with MCTS for learning optimal strategies in competitive multi-agent games. The approach uses LLMs to generate and iteratively improve high-level strategies, which are then refined into executable policies using MCTS. The framework is evaluated on two games: GOPS and Avalon, showing superior performance compared to traditional RL methods and other LLM-based approaches.
weaknesses: See the questions below.

---

confidence: 2
contribution: 3
initial_rating: 5
presentation: 2
questions: Please refer to Weaknesses. Especially,
- Could you report the standard error of the median in addition to the IQR for all results in Table 1? Could you improve the clarity of Figure 4, perhaps by separating the data into multiple plots or using a different visualization method.
- Could you discuss potential limitations or biases introduced by using textual strategies only for dialogue actions? Have you considered any alternative methods to unify the approach of both types of actions, and if so, why they were not pursued?
- Could you clarify what metric is being reported in the 'Winrate' column for GOPS in Table 2, as negative values are unexpected for winrates? If this is an error, please provide the correct values.
soundness: 2
strengths: - The idea to learn skills (strategies) not only for (1) text strategy guide, but also for (2) a value heuristic is inspiring. Utilizing LLMs for generating and improving value functions in code modality seems to be an innovative practice that utilizes their ability to reason and to write code. Moreover, the value functions generated could be used to search for good actions for non-speech phases of the game. To use these generated functions rather than to use LLMs could be cost-efficient and time-efficient.
- Improvement is shown. Moreover, performance scales with improvement of inference budget.
- Extensive experiments and details are provided to show the improvement of value functions and text strategies.
summary: This paper proposes a new complicated method named Strategist for using LLMs to generate strategies and ideas for multi-agent games.

In summary, there are two levels.

- Low-level self-play tree-search provides value for learning and updating skills.

- High-level skill learning module improves skills, both for text-based strategies (in text modality) and for value heuristic functions (in code modality).
weaknesses: - 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\pm error(median)$, 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.

- From section 2 it seems that the value functions are mainly for non-dialogue actions, and the text-based strategies are mainly for dialogue actions, and the action planner based on MCTS tree search described in Appendix F seems to be searching on the values generated by heuristic value functions. According to Appendix G it seems that the authors do not conduct similar search process on dialogue actions, and speeches are mainly provided through a rather traditional prompt-based approach. Of-course this does make sense given that speech is more related to text and is harder to assign scores, but these different approaches for non-dialogue and dialogue actions give a sense of fragmentation.

- There are typos. For example, in table 2 for GOPS the averaged 'winrate' of AlphaGo and DeepRole is negative (I assume it is a typo here: do the authors mean Heuristic Value or other scores?); in table 4 there are only results for winrate but no assassination rate is reported (though mentioned in table caption).

Meta-review: The paper explores Avalon as a benchmark for planning agents. The reviewers were overall positive, aside from XeVt who did not respond despite the authors addressing many concerns. While I do believe the authors were a little over aggressive (sometimes less is more :D), it is still definitely the case that some concerns were resolved and the score could have increased. In particular, it is great to see that the work now contains a human evaluation. I would encourage the authors to keep the website live for some time before the camera ready to increase the scope of this evaluation if possible.

Decision: Accept (Poster)