Learning Strategic Language Agents in the Werewolf Game with Iterative Latent Space Policy Optimization

Thank you for your appreciation of our work and constructive suggestions. We hope the following response can address your concerns.

The paper would benefit from a more detailed mathematical formulation of both the problem and its solution. Also, adding some algorithm boxes might be better for understanding. But these are not severe weaknesses.

We agree with the reviewer and will add more detailed formulations in our revised manuscript. More specifically, some of the core definitions to be added are as follows.

1. Abstracted game: we define the abstracted game as an extensive-form game with tuple $<N, H, P, f_c, (I_i)_{i\in N}, u>$ where $N$ is the set of players, $H$ is the set of history, $P$ is the player function, $f_c$ is the probability measure for the chance node, $I_i$ is the information partition for player $i$, and $u$ is the utility function.
2. Strategy: a (mixed) strategy $\sigma_i$ for player i is the probability measure over actions for all $I\in I_i$.
3. Best response (BR): a BR to $\sigma_{-i}$ is $BR(\sigma_{-i})=\arg\max_{\sigma_i}u(\sigma_i, \sigma_{-i})$.
4. Nash equilibrium (NE): NE is a strategy profile where everyone plays a best response to others' strategies.
5. Counterfactual value: $v(I)$ is the expected payoff of player $i$ when reaching $I$, weighted by the probability that $i$ would reached $I$ if tried to do so. Formally, $v^{\sigma}(I)=\sum_{z\in Z_I}\pi^{\sigma}_{-i}(z[I])\pi^{\sigma}(z[I]\rightarrow z)u_i(z)$. Definition of $v^{\sigma}(I, a)$ is the same except it assumes action $a$ is always played at infoset $I$.
6. Counterfactual regret: $R_T(I, a)=\sum_{t=1}^T(v^{\sigma^t}(I, a) - v^{\sigma^t}(I))$.

We will also add algorithm boxes for CFR and our proposed method LSPO in our revised manuscript according to the reviewer's suggestion.

Can the author explain why prompting the LLM to generate N strategically distinct discussion candidates and randomly choose one to execute in the game that encourages diversity?

This is because the LLM tends to exhibit intrinsic bias in the action generation. Therefore, generating a single action will result in limited diversity and underexploration of the game.

The issue of intrinsic bias is discussed in detail by [1] with a simple Rock-Paper-Scissors (RPS) example. They use GPT-4 to play 100 independent RPS games and find that GPT-4 chooses Rock in 67 games, Paper in 27 games, and Scissors in only 6 games. This result shows that the LLM has a clear bias towards choosing Rock.

To solve this problem, a single method is to let the LLM generate multiple different actions. For example, in RPS, instead of a single action (which is probably Rock), we can prompt the LLM to generate 3 different actions (which include Rock, Paper, and Scissors), and then randomly choose an action. This would mitigate the intrinsic bias of LLM's action and encourage diversity and exploration in the game.

[1] Xu, Zelai, et al. "Language Agents with Reinforcement Learning for Strategic Play in the Werewolf Game." ICML, 2024.

---

We would like to express our appreciation for your feedback and hope our answers have addressed your concerns. We would be very grateful if you could consider raising the rating of our work based on our responses.

Thank you for your constructive comments and questions! We hope the following response can address your concerns.

Generalization to games other than Werewolf.

We perform experiments on two additional games to show the general applicability and effectiveness of our method. Due to the word limit, please see the results and discussion in our rebuttal to reviewer sE2V's first concern.

Applying CFR to an ever-evolving action space is questionable.

We would like to clarify that although we expand the abstracted game between iterations, in each iteration, CFR is applied to the game with a fixed action space.

Applying CFR to latent space in language games is less established.

We agree with the reviewer that there are few prior works that apply CFR to free-form language games. Our work takes an initial attempt to convert natural language into latent strategies and apply CFR to solve free-form language games. The intuition is that the strategic intent behind natural language is relatively concentrated, and can be regarded as a latent "action" in the abstract game and suitable for CFR. Our experiment results show that our method works for language games.

Assumption of a fixed set of latent strategies can limit the flexibility.

We agree that our method can be further improved by dynamically maintaining different latent strategy spaces at different states. In practice, we find it simple yet effective to use a fixed and large k, which already outperforms SOTA agents in our experiments. We will include a discussion in our revised manuscript.

Limited scalability of latent space construction.

We have added experiments on two more games. We would also like to argue that 7-player Werewolf is already a game with complex and dynamic interactions. The game involves 7 players, which is much harder than 2-player games, has both cooperation and competition, and has no restriction on natural language communication. We believe it serves as a challenging free-form language game.

Dependence on predefined clustering (ablation on k).

We perform an ablation study in a simpler 4-player Werewolf game with $k=1, 2, 3$. Due to the word limit, please see the results and discussion in our rebuttal to reviewer gyxq's Q2.

Limited baseline comparisons.

We compare our method with fine-tuned agents without strategic optimization. Given a state $x$, we collect a pair of language actions $(y_1, y_2)$ and use gpt-3.5 to generate the preference. Then we use DPO to fine-tune the LLM with the same hyperparameters and compare against our method with 1 iteration. The table below shows that our method with strategic optimization achieves better results.

Lack of game dialogue analysis.

Due to the word limit, please see the analysis in the rebuttal supplementary.

The construction of latent space and DPO requires an extremely large number of game rounds.

We would like to clarify that the two mentioned processes usually require a few hundred games, which is not an extremely large number with batched inference. More game simulations and strategic optimization in performed in the abstracted game, which does not involve the LLM.

Q1: Example of preference data with different regret value.

A typical example is when Seer has identified Player X as a Werewolf. Two different language actions are:

1. Reveal: I'm the Seer and I saw Player X is a Werewolf, ...
2. Conceal: I do not have information ...

Our method learns a much lower regret value for reveal than conceal, making our agent more inclined to reveal their information. This aligns with the intuition that Seer should share information and guide the Villagers.

Q2: Text embedding.

We would like to clarify that the text embedding does not distinguish the strategic intent in the language. It simply encodes the language "I support player X" to a vector and lets the CFR make strategic decisions.

Q3: Examples for sophisticated patterns.

Due to the word limit, please see the analysis in the rebuttal supplementary.

Q4: Additional iterations.

We provide two more iterations and the results in the table below show that the performance converges. Due to the word limit, please see the results and discussion in our rebuttal to reviewer gyxq's Q1.

---

We greatly appreciate your thorough review of our work and hope our answers effectively address your concerns. We would be very grateful if you could consider raising the rating based on the responses.

Thank you for your constructive comments and questions! We hope the following response can address your concerns.

Q1: Convergence behavior of the iterative LSPO process. (Also mentioned in Weakness 3)

Theoretically, suppose the free-form language action has a finite vocabulary size $N_v$ and a finite maximum length $L$, then the language action space $N_v^L$ is also finite. Then with at most $N_v^L$ iterations, our method will cover the full language action space and the abstracted game becomes the original full game. And the LSPO process will converge in a finite number of iterations.

Empirically, we observe that the iteration for convergence is much less than the theoretical upper bound. We perform two more iterations in the 7-player Werewolf game, and the results in the table below show that the performance converges.

The early convergence compared to the theoretical upper bound is because the number of latent strategies in free-form language games is much smaller than the whole language space. For example, in the Werewolf game, the latent strategies for Werewolves can be roughly divided into pretending to be the Seer, pretending to be the Doctor, and pretending to be a Villager. More iterations lead to more fine-grained latent strategies, but the semantic meaning remains similar. Therefore, our method empirically converges with a few iterations.

Q2: Sensitivity and robustness analysis. (Also mentioned in Weakness 2)

To perform sensitivity analysis on our method, we consider a simpler 4-player Werewolf game (1 Werewolf vs 1 Seer + 2 Villagers).

We first perform experiments on the number of initial clusters $k=1, 2, 3$. The results in the table below show that the number of clusters can influence the performance in the early iterations, but does not influence the final performance.

We also perform ablations on the DPO hyperparameter $\beta=0.05, 0.1, 0.2$. The result in the table below shows that our method is robust to fine-tuning hyperparameters.

Q3: Application to other games. (Also mentioned in Weakness 1)

We perform experiments on two additional games to show the general applicability and effectiveness of our method. The two new games are Rock-Paper-Scissors-Spock-Lizard and Undercover (Who is Spy). Our method achieves the best performance in these two games. Due to the word limit of rebuttal, please see the detailed discussion in our rebuttal to reviewer sE2V's first concern.

Rock-Paper-Scissors-Spock-Lizard

Undercover

Q4: Computation requirement and trade-offs for scalability.

Our method is trained on an 8xA800 GPU server with a 64-core CPU. The main computation bottleneck is fine-tuning the LLM (llama 3 8B) with DPO. Some trade-offs can be introduced to reduce the computation with some loss of performance.

1. Parameter-efficient fine-tuning: use techniques like LoRA (Low-Rank Adaptation) to update a small subset of parameters rather than the entire model and cut down the memory and computation usage.
2. Mixed precision training: use lower precision like fp16/bf16 to reduce memory consumption and accelerate training.

Although these techniques can be used to further improve the scalability of our method, we would like to emphasize that the primary focus of our method is to address the intrinsic bias and action coverage issue of LLM agents in strategic games.

---

We genuinely value your dedication to reviewing our paper and believe our detailed responses have addressed your concerns. We would really appreciate it if you could consider raising the rating of our work based on our responses.

Thank you for your constructive comments and questions! We hope the following response can address your concerns.

Claims And Evidence: Evaluation on the Werewolf game alone is not sufficient.

To show the general applicability and effectiveness of our method, we perform additional experiments on the following two games.

(1) Rock-Paper-Scissors-Spock-Lizard: this is a five-weapon variant of the classic Rock-Paper-Scissors game. Although it is not a free-form language game, we use it as a simple proof-of-concept game that highlights the motivations of our method: intrinsic bias in actions and inadequate action coverage of LLM-based agents.

The Nash equilibrium (NE) in this game is to choose each action with an equal probability of 1/5. We use exploitability to evaluate the performance of different agents. A lower exploitability means the strategy is better (closer to NE).

Analysis:

1. ReAct fails because of the intrinsic bias issue. The LLM has higher probabilities to choose Rock, Paper, and Scissors, and much lower probabilities to choose Spock and Lizard, probably due to the bias inherited from pretraining data.
2. SLA fails because of the inadequate action coverage. SLA first uses LLM to propose $N$ actions and then uses RL to learn the optimal policy. A typical value is $N$=3 and results in a subgame without the other 2 actions. An NE in this subgame is not the NE of the original game.
3. Our method LSPO addresses these two issues by iteratively expanding the action space and using CFR to solve the NE. As the LSPO covers the full action space with 3 iterations, it learns the NE of the game.

(2) Undercover (Who is Spy): this is a 5-player free-form language game introduced in LLMArena [1]. The players are divided into 2 groups: 1 undercover and 4 non-undercover. The two groups receive a pair of similar but distinct words (like apple and pear) and describe their words to find the undercover or hide.

We consider 2 settings of this game: one lasts for 1 round, the other lasts for 2 rounds. We use the undercover's win rate against gpt-3.5-turbo in 100 games to evaluate the performance of different agents.

As shown in the table, our method achieves the highest win rates in both settings. This is because the LSPO agent learns the action of deception, i.e., realizes itself is an undercover and follows the descriptions of other agents. This helps the LSPO agent to blend in with the non-undercovers and achieves a higher win rate.

[1] Chen, Junzhe, et al. "LLMArena: Assessing Capabilities of Large Language Models in Dynamic Multi-Agent Environments." ACL (1). 2024.

Method And Evaluation Criteria: Using win rate alone is not sufficient, it would be more interesting to see human-like or even novel strategies.

We would like to clarify that, besides win rates, we also use visualization with discussion of latent policies for qualitative evaluation (Sec. 4.1) and prediction accuracy for quantitative evaluation (Sec. 4.2) in our manuscript.

As discussed in Sec. 4.1, as training proceeds, our method discovers emergent human-like behaviors. For the Werewolves, our method learns to pretend to be the Seer and provide fabricated investigations to sow confusion. For the Seer, our method learns a coordination voting strategy that asks all players to vote for a strongly suspected Werewolf. Due to the word limit of rebuttal, please see more detailed game log in the rebuttal supplementary.

In addition, the prediction accuracy result in Table 1 also shows that our agent is not winning with "unreasonable strategies". Instead, it successfully predicts the hidden roles of other players and wins by strong strategic play.

Questions For Authors: When playing games with humans, humans can make misleading actions or claims. Since humans can use any random language to break LLM-based players, how would you tackle this issue?

Since our method does not restrict the agents' actions to the latent strategies, the LLM agents can also use any random language to exploit their opponents like humans. To make them more robust, we train our agents using self-play with CFR, which has a theoretical regret bound. We also provide some examples in the rebuttal supplementary to show that our agents stay robust to deliberate exploitation from humans.

---

We genuinely value your dedication to reviewing our paper. We have carefully addressed each of your concerns, and we sincerely hope our efforts merit a raise in your rating.