Learning to Deceive in Multi-Agent Hidden Role Games

Deception is prevalent in human social settings. However, studies into the effect of deception on reinforcement learning algorithms have been limited to simplistic settings, restricting their applicability to complex real-world problems. This paper addresses this by introducing a new mixed competitive-cooperative multi-agent reinforcement learning (MARL) environment inspired by popular role-based deception games such as Werewolf, Avalon, and Among Us. The environment's unique challenge lies in the necessity to cooperate with other agents despite not knowing if they are friend or foe. Furthermore, we introduce a model of deception, which we call Bayesian belief manipulation (BBM) and demonstrate its effectiveness at deceiving other agents in this environment while also increasing the deceiving agent's performance.


Introduction
Human tendency to trust in the honesty of others is essential to effective cooperation and coordination [25]. At the same time, trust opens up the risk of being exploited by a deceptive party. Deception is prevalent in many real-life settings, especially in those that are adversarial in nature. Examples include cyber-security attacks [1], warfare [8], games such as poker [5], and even every-day economic interactions [16]. Outside of simplistic signaling games (e.g. [23,7]), use, and defence against, deceptive strategies has received relatively little research attention.
The popularity of social deception games, such as Werewolf, Avalon, and Among Us, reveals both a human fascination with deception, and the challenges that it creates. These games require players to cooperate with their unknown teammates to achieve their goals, all while trying to hide their identities. Therefore, social deception games could provide an interesting setting for research into deception. To explore deception beyond simple signalling games, we introduce a new hidden role mixed competitive-cooperative multi-agent reinforcement learning (MARL) environment Rescue the General (RTG). Our environment features three teams: red and blue, who have conflicting goals, and a neutral green team. To perform well, agents must learn subtle trade-offs between acting according to their team's objectives and revealing too much information about their roles.
To this end, we trained two sets of agents to play RTG, one in which the agent pursues the rewards of the game as per normal, and another where the agents are provided an intrinsic reward [31] to incentivise deceptive actions. We compare the behaviour of the two groups and analyse the their performance when pitted against each other. 1 The main contributions of this work are: We designed RTG with the following objectives: the game should be fast to simulate but complex to solve; game observations should be both human and machine-readable; code for the environment should be open source and easy to modify; the game should be mixed competitive/cooperative (i.e., not zero-sum); hidden roles should be a core game mechanic; 4 and good strategies should require non-trivial (temporally extended) deception.

Teams and Objectives
The game consists of three teams: red, green, and blue. The blue team knows the location of a general and must perform a rescue by dragging them to the edge of the map, but requires multiple soldiers to do so. Green are 'lumberjacks' who receive points for harvesting wood from the trees scattered around the map, and whose interests are orthogonal to the other teams. The red team does not know the general's location and must find and kill the general. Similar to the StarCraft Multi-Agent Challenge [30], each soldier is controlled independently, and has a limited vision (a range of six tiles for red, and five for green and blue). The complication is that no soldier knows any other's identity', including their own team members. Communication is limited to the soldiers' actions, namely movement by one tile north, south, east or west and the ability to shoot in one of the four cardinal directions. All soldiers have an ID colour allowing soldiers to track previous behaviour.
Player teams are randomised at the beginning of each game. Their locations are randomily initialised such that they are near to each other, but always more than 2-tiles away from the general.

Observational Space
Egocentric observations are provided to each agent in RGB format, as shown in Figure 1. Status indicator lights give the agent information on their x-location, y-location, health, turns until they can shoot, turns until a game timeout, and team colour. A marker indicating the direction of the general is also given to blue players. Rewards depend on the scenario and are detailed in Section 3.4. Figure 1: The global observation (left) and an agent's local observation (right). Soldiers are painted with their unique ID color on the outside, and their team color on the inside. Local observations omit the team color for all non-red players. Each map tile is 3x3 and encoded in RGB colour.

Scenarios
The RTG environment provides six scenarios of differing levels of challenge. These scenarios are given in Table 1. Additional custom scenarios can also be created through configuration options (for details see Appendix A).
In the primary scenario, Rescue, the blue team must rescue a general without allowing a lone red player to find and shoot the general. The Wolf scenario features a single red player who must kill all three green players before being discovered. R2G2 demonstrates orthogonal objectives, with two green players harvesting trees while two red players attempt to find and kill the general. Red2, Green2 and Blue2 are simple test environments where each team can learn their objective unobstructed.

Reward Structure
The rewards are structured such that a victory for red or blue always results in a score of ten, and are outlined in Table 2. R b refers to the total reward for the blue team this game, and is used to make sure blue always receives a maximum of ten points for a win. Green is also able to score ten points if they harvest all the trees on the map, but unlike red and blue, they will not terminate the game by achieving their objective. Due to the complexity of rescuing the general (two players must work together to move the general tile-by-tile) we provide small rewards to blue for completing partial objectives.

Bayesian Belief Manipulation Model
Our deception model is based on belief manipulation [10]. Each agent keeps track of what it believes other agents believe that an action would imply about their role. We refer to this as 'inverse' prediction. That is, predicting what others would predict about ourselves. Using these inverse predictions and an assumption of Bayesian belief updates, a reward is generated to incentivise agents to take actions that would mislead other agents about their true role. We call this Bayesian belief manipulation (BBM).

Theory of Mind
In order to deceive another player, we need to model our belief about their belief of how our actions would be interpreted. Take, for example, the situation in Figure 2. If red believes that blue knows that red can see the general, this action will be considered a very 'red' move. However, if red believes that blue is unaware of the general, this action can, perhaps, be taken without revealing red's role. Thus, agents must model, not only the beliefs about others but also others' beliefs about themselves.

Assumptions
In our model the deceiving agents operate under the following assumptions: 1. All non-deceiving agents are Bayesian in their approach to updating belief about roles. 5 2. The policy of each role is known by all players. 6 Figure 2: Should red believe they are giving away their role by shooting east? This depends on whether red knows that blue knows that red is shooting the general (depicted with a cross). Blue's limited vision is shaded, and both soldier's roles are visualised for context. If blue knows that red knows where the general is, blue will interpret this as a very 'red' move.
3. Agents are limited to second-order theory of mind.
The second assumption amounts to knowing the type of the policy, that is, knowing the set of potential policies, but not knowing which one the agent is acting out. Because the set of policies could, in theory, be very large, this assumption is not as limiting as it sounds. The third assumption follows the findings of [9], who conclude that while agents with first-order and second-order theory of mind (ToM) outperform opponents with shallower ToM, deeper levels of recursion show limited benefit.

Notation
We use the following notation: • A i refers to the i th agent, and A z i refers to the event that the i th agent has role z. • h t i is A i 's history of local observations up to and including timestep t. Where t is omitted it can be assumed to be the current timestep.
• Z is the set of all roles, and π z the policy of role z.
We also write P i to mean the probability that the A i assigns to an event, and P i,j to be A i 's estimation of the the probability that A j would assign to an event. For example P 1,2 (A r 1 ) is A 1 's estimate of how much A 2 believes that A 1 is on the red team.

The Model
Given the assumptions in Section 4.2, we consider how a Bayesian agent j would update their belief about agent i's role given that they observed A i taking action a in context h i . We denote A i 's true role with * .
Because A j does not know h i , they must estimate it as h j,i . A i in turn does not know what h j,i is and so must estimate this too as h i,j,i . Therefore A i can estimate A j 's new belief about their role, if they were to take action a as Given that the probability of taking an action given history and role is, by definition, the known policies for each role, A i can estimate the Bayes factor with which A j would update their belief about A i 's true role as As we wish to encourage deceptive agents to minimise this belief, we must reward agents for actions that generate ρ < 1 and disincentivise actions that would generate ρ > 1. Therefore, we provide agents with a − log(ρ) reward bonus, which fulfils this criterion, and whose interpretation is an estimate of the negative log of the Bayes factor in a Bayesian update for the other agent.
Implementing this bonus requires each agent i to model both h i,j,i for each other player j, as well as model P i,j (A z i ) for each z ∈ Z. The predicted history for each agent must then be run through each known policy to produce action distributions estimations for each role.

Direct Policy Prediction
The requirement that each agent must model all other other agents' complete histories can be removed by predicting the current policies for each agent directly. This avoids predicting irrelevant details about the other agents' observations, is more computationally efficient, and relaxes assumption (2) about needing to know the policies ahead of time. 7 We do this by modelling This direct policy prediction method amounts to each agent predicting what agent thinks it would do in its current circumstance, if it was each of the known roles.

Deception Bonus
Deceptive agents are given a bonus to their rewards based on their estimate of ρ in equation 3. Similar to [20], we filter out all but a 10% random sample of non-visible agents as their contribution adds a lot of noise. 8 We also exclude dead players from receiving or giving deception bonuses. The ρ estimates for all remaining players are summed and added as an intrinsic reward as where r t i is the reward at timestep t for player i, and α i is the magnitude of the deception bonus reward for A i . Therefore, agents are incentivised to take actions that would mislead other agents about their true role. This formulation has several advantages. First, agents are not incentivised to deceive players who already know their role, as in this case the Bayesian update would be very small. Second, agents are not incentivised to pretend to be another role when they can get away with it. If no other player is around, or if they believe that this action could not be interpreted negatively (as in Figure 2), they will not be penalised. It is important to note, that in a complete information game all agents agree on all histories, and this situation would not occur.

Training and Evaluation
To evaluate the effect of BBM as an intrinsic motivation, we trained two groups of agents on the Rescue scenario. Each group consisted of four agents, trained with different random seeds. Agents in all groups trained with deception modules; however, the first group had α = 0 for all agents, while the second group set α = 0.5 9 for red team players, and α = 0 for all other players. We trained the agents under the centralised learning, decentralised execution paradigm [13] detailed further in Section 5.2 7 Each player's current policy is needed as targets during training, so effectively this limitation is still in place. However, it is now a training detail rather than inherent to the model, and could potentially be removed by inferring policy from observed actions. 8 The argument that they did not observe the action and could therefore not update their belief is not valid here, as they could potentially see the consequences of the action in the future (a dead body for example). Our model does not handle this case and is left for future work. 9 α = 0.5 was chosen as initial tests showed this gave agents roughly one quarter of their reward from BBM. We kept the deception bonus reward small so as not to cause agents to loose sight of their primary objective, which was to win the game. Here π r , π g , π b are the current policy estimations for each player if they were red, green and blue. V ext and V int are the value estimations for the extrinsic and intrinsic returns respectively. s t i is the local observation at timestep t for the ith player, and n is the number of players in the game. The output from the deception module is to generate deception bonus' only, and is not required once training is complete.

Agent Architecture
Our BBM agent is composed of two distinct modules: the policy module and the deception module (see figure 3). The policy module was trained using local observations only, while the deception module (discarded after training) required target information from other agents.
Both modules feature the same encoder architecture, which is loosely based on DQN [28], but modified to use 3x3 kernels to the match the 3x3 tile size and lower resolution of the RTG environment. To address partial observability a recurrent layer, in the form of Long Short Term Memory (LSTM) [14], was added to the encoder, with residual connections from the convolution embedding to the output (see Appendix B for more detail on the encoder architecture.).

Training Details
The policy module takes an agent's local observation as input, encodes it via the encoder, and then outputs a policy and extrinsic/intrinsic value estimations for each of the three roles. During training, gradients are only backpropagated through the output head matching the role of the given agent. 10 The policy module was trained using Proximal Policy Optimisation (PPO) [32] by running 4 epochs over batches of size 3,072 segments, each containing 16 sequential observations, using back propagation through time.
We also experimented with using separate models for each policy, but found little difference in the results, at the cost of longer training times (as did [2]). A global value estimate based on the observations of all players was also considered, but we did not find significant differences in the estimates and so opted for local value estimation instead.
To make sure at least some games were winnable for each side we modified the game rules during training so that in half of the games, a player from a randomly selected team was eliminated before the game started. We found failing to do this sometimes caused one team to dominate the other, prohibiting progress.
The policy and deception modules were trained simultaneously on the same data. They share an identical encoder structure but used separate weights. Because of this, the deception module can be removed once training has finished, allowing for decentralized execution. The policy module produces the policy and value estimate based on local observations only. The deception module outputs predictions for player roles and player actions, as well as their inverse predictions (that is, what it predicts that other agents are predicting about itself). See Figure 3 for details.
We trained each of the eight runs for 300-million interactions (which equates to 50-million game steps) over 5-days on four RTX2080 TIs using PyTorch 1.7.1 [29]. Checkpoints every 10-million interactions were saved, allowing for evaluation of the agents' performance at various points during training. Hyperparameters for the model, given in Table 3, were selected by running a grid search on the Red2 scenario. For more details refer to Appendix C.

Losses
Action predictions were trained by minimising the Kullback-Leibler (KL) [22] divergence between the predicted distribution and ground-truth targets taken from the agents during rollout generation. We trained the inverse action predictions in the same way, using the other agents' predictions during rollout generation as targets.
We trained the role predictions by minimising the negative likelihood loss, using players' true roles as targets. We trained inverse role predictions by minimising the KL divergence between the agent's prediction of other agents belief about its role, and their actual prediction about the agent's role.

Intrinsic Rewards
Raw deception bonuses were calculated, clipped to the range (-20,20) and logged for each agent. Bonuses were then zeroed for all non-red players, normalised such that the intrinsic returns had unit variance, multiplied by φ(t) where φ(t) = min(1.0, t/10 × 10 6 ) and t is the timestep (in terms of interactions) during training then scaled by α i . This creates a warm-up period where agents can learn the game with without an auxiliary objective. Similar to [6] our model outputs intrinsic and extrinsic value estimations separately, then combines them when calculating advantages.

Evaluation
Evaluating agents within a multi-agent scenario poses some unique challenges. Unlike games where agents compete against a static environment such as Atari, self-play means that as the agent gets stronger, so does its opponent. Thus, an agent's skill progress might not be visible from plots of the scores alone.
To address this we evaluated each run by playing 16 games, every ten-epochs, 11 against opponents from each of the eight runs (128 games in total). The green team was played using the same agent as the adversary. Performance across the four runs was averaged.
We also recorded raw deception bonuses, taken before normalisation or scaling, for all players, even those who did not receive them. This allowed for monitoring of deceptive behaviour on non-deceptively incentivised players. Accuracy of role predictions was taken from data generated during training.

Effect of Deception on Agents' Behaviour
In this section we present the effect of deception on the agents in terms of their ability to predict roles and their performance in the game, and discuss the tendency towards honest behaviour when no deception incentive is provided.

Role Prediction
Identifying other agents' role is a difficult task for blue players in the Rescue scenario. At the end of training, blue assigns an average probability to players' true role of 0.617 ± 0.08(95% CI) when trained against deceptive adversaries, as compared to 0.707 ± 0.07(95% CI) when trained against non-deceptive adversaries (see Figure 4). 12 Red's role predictions were very high at 0.995 ± 0.001(95% CI), which is expected as they are able to see the roles of all visible players. A blue player who knows their role, and assigns remaining probability based on naive population counts would on average score 0.659. Therefore, the deceptive agents red caused the blue team to predict roles more poorly than if they had no in-game observations at all. Figure 4: Probability assigned to true role the blue team. Values shown are the log-averages taken during training and represent the average probability a blue player assigned to each player's true role. As seen by the decrease in role prediction accuracy, the blue team struggles to identify players' roles when faced with deceptively motivated adversaries. The black line indicates a naive, count-based, estimation of player roles.

Performance of Deceptive Agents
Despite the effectiveness on role deception, BBM has only a minor impact on the agents' score in our experiment. As seen in Figure 5 (a), red players trained with deception see an increase in performance at the end of training from −8.71 ± 0.040(95% CI) without deception to −7.21 ± 0.58(95% CI) with deception. This result, while statistically significant, is only seen at the end of training, and does not represent a large difference in performance. It does, however, suggest further experimentation into the effect of a larger deception bonus. When facing deceptive agents blue is slower to learn a winning strategy, but eventually converges to the same outcome (see Figure 5 (b)).

Deceptive Tendencies in Unincentivised Agents
We look now at agents' behaviour when not given explicit deception incentives. Blue learns to act honestly when faced with either deceptive or honestly adversaries. This is expected in the Rescue scenario as blue must identify teammates in order to coordinate with them. An unexpected result is that green, who initially acts honestly, learns an increasingly deceptive strategy, despite no explicit incentive to do so. We suspect that as red develops a strategy that involves pretending to be green, green must respond by pretending not to be green to survive blue's hostility.
The red players, when incentivised to do so, learn to obtain a high degree of deception bonus (see Figure 6 (a)). When no explicit incentive is provided red players do not naturally learn a deceptive strategy. This suggests that either deception is of less value for the red team in the Rescue scenario than expected, or that a deceptive, but effective, strategy is difficult to learn for red.

Conclusions and Future Work
Our work presents a new, open-source environment, RTG for development and testing of deception in a complex hidden role game, as well as a novel a model of deception that makes use of second-degree ToM to manipulate other agents belief about it's own role. Our empirical results show BBM to be very effective at manipulating other agents belief about their role while at the same time improving their performance in the game. We also found that deceptive behaviour, when not incentivised, is not learned naturally by the competitive red or blue teams in the Rescue scenario, but surprisingly is learned by the neutral green team.
These results suggest several questions for future research into the effect of deception in a MARL setting. Can the relatively modest performance improvement in performance be extended by increasing the magnitude of the deception bonus, or would this cause agents to act deceptively at the cost of their primary objective? What would the impact of an honesty bonus be on the blue team in the Rescue scenario, would this encourage better cooperation? How would incorporating social aspects, namely explicit communication, impact deceptive behaviour? And how could our model, which assumes only one deceptive team, be extended to account for two or more deceptive teams.

A Scenario Configuration Options
We designed Rescue the General (RTG) to be highly customisable through configuration options. We used only a subset of the configuration settings in the supplied scenarios, with the full set outlined in Table 6. We also designed a voting system where players could initiate votes to remove players. However, we found that agents never developed an effective strategy for this system, and so did not use it.

B Encoder Architecture
In our model, both the policy module and deception module share the same encoder architecture, but with separate parameters. The encoder design is a modification of the network often used in Deep Q-Networks (DQN), but with smaller 3x3 kernels to match our game's tile-size. The encoder takes a single local observation scaled to [0..1], s t , as input, as well as the LSTM cell states (h t−1 , c t−1 ) from the previous timestep. The input is fed through the convolutional layers, flattened and projected into n dimensions, where n are the number LSTM units, then fed through the LSTM layer. See Figure 7 for details. We found that adding a residual connections skipping the LSTM layer improved training performance, and did not negatively affect the agents' ability to remember past events. 13 The policy module used 512 LSTM units, whereas the deception module used 1024.  Figure 7: Encoder Architecture. Input s t is fed into a convolutional neural network, a linear layer, and finally, an LSTM layer.

C Hyperparameter Search
We performed a hyperparameter search for the policy module using a randomized grid-search. Our search used 128 runs over ten epochs on the Red2 scenario. 14 We used the average score taken from the last 100 episodes during training, where score := R × 0.99 t 13 We verified this by observing that red players were able to retain information about the roles of previously seen players 14 We did not use the Rescue scenario as it is more difficult to evaluate performance, and runs would require significantly more training time.
with R being the red teams score at the end of the episode and t being the episode length. Discounting score in this way prefers hyperparameter settings that can more quickly find and kill the general and distinguishes between runs that consistently score the optimal ten points.
The out features setting controls the number of units in the final linear layer. When residual mode was active out features were set to the same value as LSTM units. The off mode disabled the LSTM layer, on passed through the LSTM layer as per normal, concatenate concatenated the LSTM output with the linear layer, and residual added residual connections.
Hyperparameter values were selected during the search by sampling uniformly-random from the values in Table 4. We then plotted each hyperparameter by selecting the best five runs for each value setting and graphing their min, mean and max. The purpose of our hyperparameter search was not to find optimal settings but to find reliable settings that would allow us to assess the difference between deceptively incentivised agents, and the control agents. Therefore, in cases where hyperparameters had similar performance, we preferred values used in prior work and those with better computational efficiency.
A separate hyperparameter search was used to find hyperparameters for the deception module, using 64 runs over 25 epochs on R2G2 with hidden roles. This search was performed using an older version of the algorithm where agents predicted other agents observations rather than action distributions and used the negative log of the mean-squared prediction error as the score. We found these settings to work well on the updated algorithm and did not modify them. Details are given in Table 5.
We enabled window slicing (max window size) on the deception module. During deception module training, shorter windows were extracted from the longer rollout segments. This allowed the deception module to use a shorter backpropagation-through time length than the policy module, which we found to be effective. We also found that the deception module benefited from much smaller mini-batch sizes (256) than the policy module (2048). Due to differences in scale between the role prediction loss and the action/observation prediction loss, we multiplied action/observation prediction losses by loss scale.