Learning to Discuss Strategically: A Case Study on One Night Ultimate Werewolf

Summary

The authors take a specific natural language game (One Night Ultimate Werewolf) and study the performance of RL-trained LLM agents with respect to the mathematically derived (by the authors) Nash equilibrium solutions.

Strengths

[1] The paper chooses ONUW as a game that has the Nash equilibrium solution to be used as an oracle/reference. The paper then applies learning to improve the 0-shot answers/behavior of LLMs. The learning is performed with offline RL over the collected game episodes. [2] Even though the paper laser-focuses on ONUW, its methodology and results can be a valuable stepping stone to solving real-life problems. [3] As negotiations are an integral part of the society, its automation and improvement of effectiveness is a valuable direction of research. This paper makes a small but definite step in the direction of automated LLM-powered negotiations. [4] The authors do a great job of rigorous and comprehensive research of ONUW optimal strategies for players by proving theorems for several specific cases. [5] The formalized way to assess the performance of the learned policies with the help of NashConv (distance to equilibria) is very valuable and insightful. [6] In 6.3 and 6.4 the authors show that the policy learned with ChatGPT4 can be transferred to Gemini thus demonstrating the generalization across backend LLMs. [7] As described in E.2 the use of text embeddings to encode the state is intriguing. [8] The broader impact is well discussed.

Weaknesses

[1] Per se the entire paper is bound to the ONUW game and its rules. The ability of the bundle of proposed algorithms and proofs to transfer to different games or game-like environments like financial markets is not demonstrated. [2] I have not found any examples of the discussions between the LLM players in the manuscript. Further, the code is not provided by the authors. Thus there is no way to see the actual discussions between the LLM players and assess the value and quality of the generated discussion. [3] Artificial prior knowledge is inserted into the solution that constraints the model to choose between 6 options: Honest/Deceptive and Evidence/Accusation/Defense. The proposed model is seemingly limited by these options and does not allow learning or discovery of alternative discussion strategies. [4] It would be good to have a random choice baseline and compare the proposed method to its performance. [5] The paper studies a game with one round of negotiations that has limited practical use in the light of the fact that negotiations normally are conducted in several rounds.

Questions

[1] What was the reasoning behind choosing offline RL over online RL? [2] How is the classification into Honest/Deceptive and Evidence/Accusation/Defense performed: manually or by an 0-shot LLM? [3] In “An ε-Nash equilibrium is found under the 74 limitation of both human-side and werewolf-side strategies [28] ” maybe villager-side? [4] As per Table 3 state dim is 1536 which seems quite high for ONUW. What is the reasoning behind selection of this specific number? Is there any graph of a sweep across the state dimension as a hyperparameter. [5] In E.4 the USD cost per game is discussed. What is the total cost of the experiments described in the paper?

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

The limitations are well discussed or clear in principle.

Summary

This paper delves into the strategic aspects of discussion in the context of a population social deduction game, "One Night Ultimate Werewolf" (ONUW) game. By analyzing Perfect Bayesian Equilibria in scenarios with and without discussion, the authors highlights the pivotal role of discussion tactics in influencing players' beliefs and utilities. They propose a novel framework that employs reinforcement learning to instruct an LLM agent, enabling it to decide and execute strategic discussion policies. The authors empirically show that their framework can recognize and approximate the equilibira, and achieve strong performance across diverse ONUW settings.

Strengths

1. The paper introduces a new complex communication game, ONUW, and provides a clear explanation of the problem formulation. The ONUW game offers interesting role deduction challenges and seems it can be a benchmark for evaluating the deduction ability of LLM agents. 2. The authors present thoroughly theoretical analyses on a specific setting of the ONUW game, which prove the significance of discussion on influencing other players' belief and provide a solid foundation for their following proposed method. 3. The idea of integrating RL policy into LLM agents to improve their strategic ability in communication games is innovative. It has the potential to be applied in future work related to strategic LLM agents in various situations. And the empirical results shows the efficacy of this method.

Weaknesses

1. By integrating RL policy into the reasoning process, the authors aim to improve the discussion ability of LLM agents, which provides a new angle for constructing LLM agents. However, applying RL policy to select discussion tactic seems analogous to selecting action candidates in related work [1]. 2. Since the RL policy is trained on game logs generated by LLM agents, it is possible that players in the training dataset appear again during testing, resulting in less convincing results. 3. Typos： 1. In line 115, 126, player i's information state should be $h^i \in \mathcal{H}^i$. 2. The symbol $q$ is used twice as the probability that Werewolves vote for Player 3 (line 194), and as the discussion policy in Equation 6. 3. In line 224-225, it seems that $\theta^i$ refers to player i's derived belief on all players' types, while $\theta$ refers to the groundtruth. These two symbols should be further distinguished. > [1] Zelai Xu, et al. "Language agents with reinforcement learning for strategic play in the werewolf game".

Questions

1. It is a little confusing why the dimension of Player 2's belief $b^2$ is 6 while the dimension of Player 1's belief $b^1$ is 3 in the formal Theorem D.2. 2. Can the authors give a detailed explanation of why the NashConv values of GPT-4-based agents are higher than Gemini-based agents?

Rating

8

Confidence

4

Soundness

3

Presentation

3

Contribution

4

Limitations

The authors have stated the limitations about their work in Section 7.

Summary

The authors investigate the social game ‘One Night Ultimate Werewolf’ (ONUW) as a testbed for their framework on RL-instruct-tuning an agent to select optimal discussion tactics. They prove the existence of a Perfect Bayesian Equilibria in the game ‘Werewolf’ when the game consists of a single round and show the effectiveness of their approach in a three-player setting as well as a five-player setting to prove generality.

Strengths

The authors introduce a novel RL-instructed LLM-based agent framework specifically tailored for strategic discussions in ONUW focused on identifying the best discussion tactics in communication scenarios as well as providing an environment for further testing. In addition, the authors further provide a theoretical analysis of the ONUW game, formulating it as a Multi-Phase Extensive-Form Bayesian Game and establishing the existence of Perfect Bayesian Equilibria in different scenarios

Weaknesses

The primary weakness of the paper is noted by the authors, where the discretization of the space of discussion tactics results in what could be an oversimplification of the dynamics that would typically occur in such a game. For example, what could occur in a typical werewolf game is that the werewolf makes no effort to defend themselves, implying the other villagers are bullying them in an attempt to garner false sympathy. The authors also acknowledge another weakness in that identifying and discretizing the space of discussion tactics in a game is a manual and time-consuming process. While the experiments in the paper imply generalization to X number of players, this generalization is still limited to the ONUW game. A final weakness is that the results are somewhat limited by the experiments only being performed with LLMs rather than including human players as well. However, the reviewer acknowledges the additional time and monetary costs performing such experiments would occur.

Questions

How did the authors determine the specific categories for discussion tactics, and have they considered any automated methods for discovering these categories? Did the authors consider including any human participants in their trials? If not, why? How do the authors imagine the role-switching dynamics of ONUW impacted their results? What might change were the roles fixed?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors touch on some limitations of their work, however it is unclear whether the topics addressed in the questions (the impact of human participants, the word required to pre-define the decision tactics) were not included due to being outside the scope of the work, or not relevant given some metric or detail the reviewer may have missed.

Summary

The paper presents an innovative framework for enhancing the discussion capabilities of language agents in the game "One Night Ultimate Werewolf" (ONUW) using reinforcement learning (RL). The authors propose a multi-phase extensive-form Bayesian game formulation for ONUW, analyze perfect Bayesian equilibria in both discussion and non-discussion scenarios, and develop an RL-trained discussion policy. Experimental results demonstrate the effectiveness and generalizability of the framework across various game settings.

Strengths

1. The theoretical analysis of the game, including the formulation as a Bayesian game and the derivation of equilibria, is thorough and well-executed. The experimental design is robust, utilizing state-of-the-art LLMs and a novel RL training methodology. 2. The paper is well-structured and clearly written. The authors provide detailed explanations of the game mechanics, the theoretical framework, and the RL training process, which make the complex content accessible to readers.

Weaknesses

1. Comparison with Related Work: While the paper provides an innovative approach to using RL and LLMs in the Werewolf game, there is a need for a more detailed comparison with closely related works, particularly those combining LLMs with reinforcement learning strategies. For instance: Xu et al. (2023) [1] also explore strategic play in the Werewolf game using language agents trained with reinforcement learning. A comparative analysis highlighting what differentiates the current approach from Xu et al.'s methodology would clarify the novelty and the specific advancements made. Wu et al. (2024) [2] utilize offline RL and a dataset-driven approach to enhance reasoning in LLMs within the same game context. Discussing how the methodologies differ, especially in terms of model training, dataset utilization, and resultant agent behavior, would strengthen the current work's positioning within the field. 2. Lack of Human Evaluation: The experimental section primarily focuses on win rates to demonstrate the effectiveness of the proposed framework. However, Werewolf (ONUW) involves complex human interactions and strategic discussions that might not be fully captured by win rates alone. The game's social and psychological aspects, such as bluffing and persuasion, are crucial: It would be beneficial to include human evaluations to assess the quality of the AI's gameplay and its ability to mimic human-like strategic discussions. This could involve subjective assessments from experienced human players regarding the AI's ability to integrate seamlessly into human gameplay, its strategic depth, and its communication effectiveness. LLM+RL：[1] Zelai Xu, Chao Yu, Fei Fang, Yu Wang, and Yi Wu. Language agents with reinforcement learning for strategic play in the werewolf game. arXiv preprint arXiv:2310.18940, 2023. LLM+offline RL, dataset: [2] S Wu, L Zhu, T Yang, S Xu, Q Fu, Y Wei, H Fu, Enhance reasoning for large language models in the game werewolf. arXiv preprint arXiv:2402.02330, 2024 3. Dataset Size and Composition: Detailed information on the size and composition of the dataset used for offline RL is necessary. Understanding the diversity and representativeness of the game logs in the dataset would help in assessing the potential generalizability and robustness of the trained models. This includes the number of game sessions, variety of player strategies, and the range of game outcomes included.

Questions

1. Detailed Comparison with [1] and [2]: Can the authors provide a more detailed comparison of their work with the approaches in [1] Zelai Xu et al., 2023, and [2] S Wu et al., 2024? Specifically, how does the integration of RL and LLMs in your framework differ from these studies in terms of model architecture, training processes, and performance metrics? 2. Human-Like Gameplay Evaluation: Given the social and psychological complexities of the ONUW game, how do the authors plan to evaluate the AI's performance in terms of human-like behavior and strategic discussion quality? Are there plans to incorporate human player evaluations, and if so, what methodologies would be used to assess the AI's gameplay against human strategies and interactions? 3. The authors note "we additionally contribute a dataset featuring players employing various discussion tactics in the ONUW game. ". Where is the dataset, can the authors opensouce the dataset? 4. Clarification on Offline RL Implementation: The paper mentions the use of offline RL due to the slow interaction with LLMs, but it lacks specific details on how the LLM embeddings are handled within the offline RL framework. Are the state embeddings used by the discussion policy generated by running LLMs on the offline dataset prior to training? If so, how is the freshness and relevance of these embeddings ensured over iterations of RL training?

Rating

4

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The authors should consider expanding the discussion on the limitations related to the discretization of discussion tactics and the potential over-reliance on specific datasets. Suggestions for future work could include exploring methods for dynamic tactic generation or adjustment based on real-time gameplay feedback, which could help in developing more adaptable and robust AI agents for complex communication games. Additionally, addressing the computational demands and proposing more resource-efficient models could make the technology more accessible for broader applications.

Response to the rebuttal

Thank you for your response. As a side note, it is interesting to see ReAct performing worse than random for GPT4. I am keeping my score.