Training Language Models for Social Deduction with Multi-Agent Reinforcement Learning

Motivation

• Partially observable multi-agent settings require agents to parse others’ messages and share useful information to achieve shared goals.Social deduction games make this communication requirement explicit because agents must collectively infer hidden environmental information.Source: §1 · p. 1

Setting

• Among Us grounds social deduction discussions in embodied observations, requiring crewmates to complete tasks, identify imposters, and vote during adversarial discussion phases.A reported corpse initiates free-form chat followed by voting, making communication directly relevant to game success.Source: §1 · pp. 1–2

Problem

• Sparse game-win rewards provide little guidance about message helpfulness, while large human communication datasets are often unavailable.The paper therefore seeks effective and convincing communication without task-specific human data.Source: §1 · p. 2

Approach

• The method rewards messages according to how they change other crewmates’ beliefs while training agents to predict the imposter after each message.This jointly targets speaking and listening using the agents’ goal of identifying the imposter as a dense signal.Source: §1 · p. 2

Results

• 2× higher success rates than standard RL and over 3× higher success rates than base models over four times larger demonstrate the value of the discussion augmentation.The reported strategy also produces emergent human-like behaviors, including accusing suspects and providing evidence.Source: §1 · pp. 2–3

Emergent Communication

• Social deduction is harder than referential games because agents do not know the ground-truth answer and must collectively infer it while alternating between speaker and listener roles.This removes the clear division between an informed speaker and an uninformed listener found in many emergent-communication tasks.Source: §2 · p. 3

Language Models Agents

• Prior embodied-agent work demonstrates language models’ abilities for planning, social simulation, memory, and multi-agent coordination, but does not provide a specific training mechanism for this task.These capabilities motivate using language models as starting policies in challenging environments.Source: §2 · p. 3

Reinforcement Learning with Foundation Models

• Cicero produces natural dialogue in Diplomacy but requires many human demonstrations and prevents reinforcement learning from directly controlling generated messages.The present framework is designed to avoid both limitations.Source: §2 · p. 3
• Other work uses language models as reward signals for separate coordination policies, whereas this paper trains the language model itself.The distinction is whether the foundation model supplies rewards to another policy or is directly optimized.Source: §2 · p. 3
• Self-improvement methods such as RLHF and self-generated rewards motivate this work, but its reward remains grounded by imposter prediction rather than relying on pretrained models to critique their own generations.This grounding is presented as enabling smaller models and correction of logical errors over time.Source: §2 · p. 3

POMG Formulation

• A social-deduction POMG augments the standard game tuple with possible answers Q and a correct answer q that agents must identify through interaction.Voting for the correct imposter corresponds to taking the correct answer action q.Source: §3 · p. 3
• Each player follows a policy from its own action-observation history, which includes environmental observations, embodied actions, and prior discussions.The history is partial because each player experiences only its own sequence.Source: §3 · p. 3

Language Models

• Causal language models predict each next token conditioned on all preceding tokens in the sequence.This next-token formulation supplies the policy mechanism used for observations and actions.Source: §3 · pp. 3–4
• The environment encodes each observation as a token sequence and each action as one token, allowing language models to sample legal actions from the current history.This unified token representation supports both natural-language generation and constrained embodied actions.Source: §3 · p. 4

Foundation Model

• RWKV is selected as the foundation model because recurrent processing gives constant per-token trajectory cost and supports unbounded-context training with truncated backpropagation.This matters for Among Us trajectories that can reach tens of thousands of tokens per player.Source: §3 · p. 4

Role Assignment

• Crewmates receive tasks in a grid environment, while the single imposter can kill crewmates; roles are asymmetric because imposters know one another’s identities but crewmates do not.The game is configured with one imposter and n−1 crewmates.Source: §4 · p. 4

Gameplay Phase

• During gameplay, agents move or wait, crewmates perform temporarily unobservable tasks, imposters kill co-located crewmates subject to cooldown, and reporting a corpse starts discussion.These mechanics provide the embodied observations that later ground discussion.Source: §4 · p. 4

Gameplay Loop

• At each timestep, the environment sends observations to all agents and collects tokenized actions constrained to the valid action subset.The gameplay loop connects simultaneous observation delivery with legal action selection.Source: Figure 2 · p. 4, §4 · p. 4

Discussion Phase

• Discussion cycles through each player twice in random order for natural-language messages, then each player votes and the plurality-elected player is ejected.If the imposter is not ejected, the game returns to gameplay and crewmates continue tasks.Source: §4 · p. 4
• The environment queries each crewmate’s immediate vote before and between discussion messages, without changing the game state, for use by the training algorithm.Voting actions are also the social-deduction answer space, with the correct imposter corresponding to q.Source: §4 · p. 4

Reward Structure

• Crewmates win when tasks are completed or the imposter is ejected for +1, while imposters win when their number reaches or exceeds the number of crewmates, giving crewmates −1.This defines the team zero-sum reward structure.Source: §4 · p. 4

5 TRAINING LLM CREWMATES IN AMONG US

• Zero-shot RWKV crewmates frequently vote incorrectly, motivating training procedures that improve decision-making and discussion.The base policy is a pretrained RWKV model used directly as the agent policy.Source: §5 · pp. 4–5

5.1 Reinforcement Learning in Among Us

• Standard reinforcement learning optimizes sparse game and task rewards, but provides little direct feedback about message effectiveness or correct imposter identification.A soft KL constraint also regularizes trained models toward the base language model to preserve natural-language discussions.Source: §5.1 · p. 5

5.2 Enhancing Communication of Crewmates

• The combined listening-and-speaking objective trains crewmates to optimize actions while improving their ability to interpret and produce useful discussions.The paper identifies these listening and speaking loss terms as contributions that enhance discussion use.Source: §5.2 · pp. 5–6
• Listening training uses environment ground truth at belief-querying timesteps so agents learn to infer the imposter from observations and prior messages without human demonstrations.The listening loss is incorporated into an RL policy or used alone in a purely listening policy.Source: §5.2 · p. 5
• Speaking training rewards messages according to changes in living crewmates’ beliefs about the true imposter, approximating each message’s effect on correct prediction.The objective is to encourage messages that help other crewmates vote out the true imposter.Source: §5.2 · p. 6

5.3 Training for Dynamic Settings

• Iterated self-play trains crewmates and imposters against earlier adversary policies, while frozen partners, randomized layouts, and task counts target robustness and generalization.Training uses four crewmates and one imposter, with evaluation extending to different numbers of crewmates; world modeling helps preserve recurrent features and separate discussion from action outputs.Source: §5.3 · p. 6

6.1 Cooperative Training

• In the base environment, both 1.5B and 7B base models win less than 20% of the time, while training with RL significantly boosts performance and outperforms the 7B model.Source: §6.1 · pp. 6–7
• 2×: the full model achieves twice the win rate of the RL-only baseline in the base environment.Combining RL with listening produces large gains, while denser speaking rewards provide further improvement but only a relatively small additional difference.Source: §6.1 · p. 7
• Win rates generally persist across environment configurations, declining with more tasks and increasing with more crewmates, while unseen configuration changes follow expected trends.Environment shape has little effect, smaller environments are generally easier, and additional crewmates can recover from incorrect votes.Source: §6.1 · p. 7, Figure 4 · p. 7
• The trained agents develop human-like discussion behaviors, including naming suspects, making accusations, and sharing observations as evidence, though they sometimes fabricate convincing evidence.Naming an agent makes other agents more likely to vote against them, and the messages can reflect observations such as leaving a room where a body was found.Source: §6.1 · p. 7

6.2 Robustness to Imposters

• Crewmate scores converge to 0.51–0.56 after a few self-play iterations against adversarially trained imposters.The large lower-bound jump from iterations 0 to 1 and the lack of a significant performance drop indicate robustness to adaptive opponents.Source: §6.2 · p. 7, Figure 5 · p. 8
• Imposters counter-accuse and mimic crewmate discussion patterns, sometimes deceiving crewmates who support unwitnessed claims.The paper attributes similar behavior in base-model imposters to language models’ in-context learning capabilities.Source: §6.2 · p. 8

6.3 Failure Modes

• Training can produce degenerate silence, stationary behavior, or action-token discussions unless the algorithms constrain language and agent adaptation.The authors freeze one crewmate to prevent shared strategies and use a world-modeling loss to preserve natural-language behavior.Source: §6.3 · p. 8

• The technique enables language models to communicate effectively and extract information from discussion messages without task-specific human data.Source: §7 · p. 8
• Crewmates remain coordinated against adversarially trained imposters, who attempt to sabotage discussions but do not break coordination.Source: §7 · p. 8
• Scene prediction is task-dependent because the approach manually relies on a connection between discussion and predicting the imposter’s identity.Source: §7 · p. 8
• Crewmates may make convincing rather than truthful statements, motivating truthfulness optimization as future work outside the sandboxed game.Source: §7 · p. 8

Gameplay Phase

• Crewmates navigate a W×H grid, wait or move between rooms, perform tasks, and report nearby corpses, while imposters can wait, move, or kill players after a cooldown.Imposters can appear to perform tasks by waiting, and actions are mapped to unique tokens for language-model generation.Source: A ENVIRONMENT DESIGN · p. 11
• Agents receive natural-language observations describing time, room, nearby players, movement, and role-specific information, while legal actions are represented as discrete tokens.Crewmates additionally observe uncompleted tasks in their room, whereas imposters observe their elimination cooldown.Source: A ENVIRONMENT DESIGN · p. 11

Discussion Phase

• Reporting a corpse starts a discussion in which living players speak in randomized order, share free-form messages of up to 20 tokens, and then vote or abstain.The discussion returns to gameplay unless all imposters are ejected; ties or abstention produce no ejection.Source: A ENVIRONMENT DESIGN · p. 11
• Before discussion and between messages, the environment records living crewmates’ imposter beliefs from their voting probabilities for training without affecting gameplay.Source: A ENVIRONMENT DESIGN · p. 11

Reward Structure

• Crewmates receive +1 when tasks are completed or all imposters are ejected, whereas imposters win with crewmate reward −1 when imposters are at least as numerous as crewmates.Source: A ENVIRONMENT DESIGN · p. 11

• Accuracy exhibits diminishing returns at 1.5 billion parameters, motivating that model size for ablation experiments.Source: B BASE MODEL RESULTS · p. 12
• Table 1 reports scaling performance using accuracy, PPLWorld, and PPLLAM for the RWKV base model.PPLWorld measures perplexity for predicting environment observation tokens, while PPLLAM is Lambada evaluation perplexity.Source: Table 1 · p. 12, B BASE MODEL RESULTS · p. 12

• Discussion samples include direct accusations and evidence-based claims that lead crewmates to identify and eject an imposter.In one sample, Player Blue is voted out after multiple players express suspicion, and crewmates win.Source: C SAMPLE GENERATIONS · pp. 12–13
• Imposters can counter-accuse crewmates and persuade others to eject an innocent player, producing an imposter victory.Source: C SAMPLE GENERATIONS · p. 12
• False information can coexist with correct imposter identification and a crewmate victory.Source: C SAMPLE GENERATIONS · p. 13
• Counter-accusations do not always succeed: in one sample, the accused imposter is voted out despite attempting to redirect suspicion.Source: C SAMPLE GENERATIONS · p. 13
• Some discussions end without an ejection when votes are split among players.Source: C SAMPLE GENERATIONS · p. 13

• The paper aims to enable multi-agent communication between language-model agents in novel settings without human demonstration data.Source: D BROADER IMPACTS · p. 13
• Natural-language communication could support smoother coordination between humans and AI in heterogeneous teams.Source: D BROADER IMPACTS · p. 13
• The authors caution that unsupported statements by both roles create risks for deployment beyond Among Us.Source: D BROADER IMPACTS · p. 13

E HYPERPARAMETERS AND COMPUTE

• The experiments use AdamWScheduleFree without a separate scheduler, with λL values of 3.0 and 0.1 for the two listed policy variants.Source: E HYPERPARAMETERS AND COMPUTE · pp. 13–14
• RL trajectories are collected from 30 environments and processed in parallel in groups of 6 trajectories during optimization.Source: E HYPERPARAMETERS AND COMPUTE · p. 14
• All models can be trained within 48 hours on individual A40 GPUs with 48 GB of VRAM.Source: E HYPERPARAMETERS AND COMPUTE · p. 14

F ASSETS AND LICENSES

• The implementation borrows CleanRL’s PPO code, released under the MIT license.Source: F ASSETS AND LICENSES · p. 14
• The work uses Among Us intellectual property with permission for non-commercial and educational use but is not officially licensed by Innersloth.Source: F ASSETS AND LICENSES · p. 14
• Paper art assets were created with Processing, Matplotlib, and Keynote, while the paper and code use CC-BY-4.0 and GNU GPL v3.0 licenses.Source: F ASSETS AND LICENSES · p. 14