Symmetric Machine Theory of Mind
Authors: Melanie Sclar
Graham Neubig
Yonatan Bisk
Venue: ICLR 2022 Submitted (2022)

Abstract: Theory of mind (ToM), the ability to understand others' thoughts and desires, is a cornerstone of human intelligence. Because of this, a number of previous works have attempted to measure the ability of machines to develop a theory of mind, with one agent attempting to understand anothers' internal "mental state''. However, ToM agents are often tested as passive observers or in tasks with specific predefined roles, such as speaker-listener scenarios. In this work, we propose to model machine theory of mind in a more flexible and symmetric scenario; a multi-agent environment SymmToM where all agents can speak, listen, see other agents, and move freely through a grid world. An effective strategy to solve SymmToM requires developing theory of mind to maximize each agent's rewards. We show that multi-agent deep-reinforcement learning models that model the mental states of other agents achieve significant performance improvements over agents with no such ToM model. At the same time, our best agents fail to achieve performance comparable to agents with access to the gold-standard mental state of other agents, demonstrating that the modeling of theory of mind in multi-agent scenarios is very much an open challenge.


Under review as a conference paper at ICLR 2022
SYMMETRIC MACHINE THEORY OF MIND
Anonymous authors
Paper under double-blind review
ABSTRACT
Theory of mind (ToM), the ability to understand others' thoughts and desires, is cornerstone of human intelligence. Because of this, number of previous works have attempted to measure the ability of machines to develop a theory of mind, with agent attempting understand anothers' internal "mental state". However, ToM agents are often tested as passive observers or in tasks with specific predefined roles, such as speaker-listener scenarios. In this work, we propose model machine theory of mind in a more flexible and symmetric scenario; multi- agent environment SymmToM where all agents can speak, listen, see other agents. and move freely through a grid world. An effective strategy to solve SymmToM requires developing theory of mind to maximize each agent's 's rewards. We show that multi-agen deep reinforcement learning models that model the mental states other agents achieve significant performance improvements over agents with no such ToM model. At the same time, our best agents fail to achieve performance comparable to agents with access to the gold -tandst mental state of other agents, demonstrating that the modeling of theory of mind in multi-agen multi-agent scenarios is very much an open challenge.
INTRODUCTION
Human communication is shaped by the desire to efficiently cooperate and achieve communicative goals (Tomasello, 2009). Children learn from a young age that the others they interact with have independent mental states, and therefore communicating is necessary to obtain information from or shape the intentions of those they interact with. Remembering and reasoning over others' mental states ensures efficient communication by avoiding having to repeat information, and in cases where cooperation is involved contributes to achieving a common goal with minimal effort.
Because of this, there is growing interest in developing agents that exhibit this kind of behavior, referred to as Theory of Mind (ToM) by developmental psychologists (Premack & Woodruff 1978) Previous work on agents imbued with some capability of ToM has focused mainly on two types of tasks. The former are tasks where the agent is a passive observer of a scene that has to predict the future by reasoning over others' mental states. These tasks may involve natural language (Nematzadeh et al.) 2018) or be purely spatial (Gandhi et al. 2021 Rabinowitz et al. 2018 Baker jet 2011). The latter are tasks where the ToM agent has a specific role, such as "the speaker" in speaker-listener scenarios (Zhu et al. 202T).
In contrast, human cooperation and communication very often multi-party, and rarely assumes that people have pre-fixed roles. Moreover, human interlocutors are seldom passive observers of a scene but instead proactively interact with their environment. Since previous domains limited us research questions where most parties involved did not have active role, we developed more flexible environment where we can now study what happens when all participants must act both speaker and listener. In this paper, we present Symm'ToM, a fully symmetric multi-agent environment where all agents can see, hear, speak, and move, and are active players of a simple information-gatheriin game. To solve Symm'ToM, agents need to exhibit different levels of ToM, as well as efficiently communicate through a simple channel with a fixed set of symbols.
In the present work we focus solely on reasoning over mental states. Other aspects of ToM include understanding preferences, goals, and desires of others. Multi-agent scenarios for inferring agent's 's goals have been studied (Ullman et al. 2009), and passive-observer henchmarks (Gandhi et al. [222]] Shhu et al. [02T] Netanyahu* al. 2021 have heen proposed for evaluating understanding of agent's goals and preferences.

---

Under review as a conference paper at ICLR 2022
remember Yellow only knowing #4, Yellow must have shared #4. Blue may have shared either #1 or #2.
will share info #4
will share
Yellow and Blue know exactly the same info do, although could hear them. will move to talk to Red.
Red does not know Yellow already learned and misjudged situation.
Figure I:
In SymmToM, agents aim to gain all the information available (depicted as diamonds, black for known information, white for unknown). Since hearing is limited neighbor cells, they must guess what happened beyond this range. Agents can see the whole grid, but even then, mistakes in inferences may happen (as did this example to the red agent).
SymmToM is partially observable setting for all agents: even when agents have full vision, hearing may be limited. This also differentiates Symm from prior work, as modeling may require probabilistic theory of mind. In other words, agents need to only remember and infer other agents' knowledge based on what they saw, but also estimate the probability that certain events happened. This estimation may be performed by assuming other agents' optimal behavior and processing the partial information available. Despite its simplicity, Symm ToM fulfills the properties required for symmetric ToM to arise, which will be discussed the following section.
We find that SymmToM cannot be completely solved neither by using well-known multi-agent deep reinforcement learning (RL) models, nor by tailoring those models to our task. We show that even maintaining the simple rules of the environment, modifying its parameters results in much more difficult challenges, even for models where we artificially introduce perfect information. We discuss examples where different levels of theory of mind are required to solve the task, and possible metries.
THEORY-OF-MIND AGENTS
A belief Theory-of-Mind agent can be defined modification of the standard multi-agent RL paradigm, where the agents' policies are conditioned on their beliefs about others. Formally, we define reinforcement learning problem M tuple of state space S, action space A, state transition probability function T x A R, and reward function (S, A, T, R). In this setting, agent learns a (possibly probabilistic) policy π S + A that maps from states to actions, with the goal maximizing reward.
x A + R, i.. M
In multi-agent RL setting each agent can potentially have its state space, action space, transition probabilities, and reward function, so we can define an instance of M; = AS T, R,) for each agent i. For convenience, entire world in which all agents are interacting. Importantly, in this setting each agent will have its own view of the entirety of the world, described by a conditional observation function wy that maps from the state of the entire environment to only the information observable by agent
can also define joint state space S = U, S; that describes the
Ω
As elaborated above, ToM is the ability to know (and act upon) the knowledge that an agent has. Agents with no ToM will follow policy that depends only on their current (potentially partial or noisy) observation of their environment: TT wi(s))). Agents with zeroth order ToM can reason over their own knowledge. These agents will be stateful, (T(- wi (s:),, (b(5)) where h: is i's hidden state. Hidden states are always accessible to their owner, i.e. has access to h
Agents with capabilities of reasoning over other agents' mental states will need to estimate h,5) for j * í. We will denote the estimation that does of j's mental state in time as h (1.))
T.( ([()))))) 10 (6.1) h (1,8-1) (0.0-1),,((0000 (0,441) ((()))
2

---

Under review as a conference paper at ICLR 2022
How do estimate R4 (,(62) As function of i's (the predicting agent) previous hidden state (-1, i's observation in 1, and i's prediction of the hidden states of every agent in the previous turn:
((++1) = f(h (x - 1), A, ( - 1 ((1 ((()))) h
i's prediction of other agents' observation in t 1--110 is also crucial, but not explicitly mentioned since it can be computed using wi (s:-1)). For the initial turn, A( may be initialized differently depending on the problem: if initial knowledge is public, (/-3) is trivial; if not, ((-5) may be estimated.
(6-5)
3 SYMMETRIC THEORY-OF-MIN
We define symmetric theory of mind environments as settings where theory of mind is required to perform task successfully, and all agents have the same abilities. There least four defining characteristics of symmetric ToM to arise:
Symmetric action space. In symmetric ToM all agents required to have the same action space (in contrast to, for example, ToM tasks in speaker-listnner settings). Concretely, A. = A, * 0 Vi,
Imperfect information. In perfect information scenarios all knowledge is public, making impossible to have agents with different mental states. In ToM tasks in general, there could be subset of agents with perfect information: one example would a passive observer that needs to predict future behavior. In symmetric ToM, since all agents have the same abilities and roles, all agents must have imperfect information. More precisely, wi must not be the identity for any agent
Observation of others. Agents must have at least partial information of another agent to estimate its mental state. In contrast to passive-observer settings, symmetric ToM every agent must be able to partially observe all others. More precisely, W, must observe least partial information about st (the subset of & that refers to agent j), although we do not require st (f) * 01 in every single turn. Moreover, if communication is allowed, it is desirable to partially observe infer interactions between two or more agents to develop second order ToM (i.e. predicting what an agent thinks about what another agent is thinking) higher.
Information--eeking behavior. It should be relevant for successfully performing the task to gather much information possible, and this ceeemmttionngathrrinn should involve some level of reasoning over other agent's 's knowledge. This is true for first-order ToM tasks in general, and could be formalized x² * π for any zeroth-orde ToM policy TT(- ws:s),, (.)).. Furthermore, it would be desirable to design task with perpetual information seeking behavior, since it would ensure that all agents have an incentive play efficiently even in long episodes. If one wants design task with perpetual informationnseeeiine and finite knowledge, information must be forgotten eventually. A forgetting mechanism could be implemented as explicit loss of knowledge under specific conditions, or make remembrances less reliable or noisy. Moreover, this introduces the concept of information staleness. Since information is not cumulative and the environment is only partially observable, agents will need to estimate whether what they knew to be true still holds in the present.
4 THE SYMMTOM ENVIRONMENT
SymmToM is an enviromment where a agents are placed in a w X w grid world, and attempt to maximize their reward by gathering all the information available in the environment. There e available information pieces, that each agent may or may not know initially. Information pieces known at the start of an episode are referred as first-hand information. Each turn, agents may move through the grid to one of its four neighboring cells, and may speak exactly one of their currently known information pieces. More precisely, the action space of agent j defined as follows:
A₁ = (left, right, up, down, no movement) x (l....,ec
When an agent utters an information piece, it is heard by every agent in its hearing range (an x grid centered in each agent, with h 2wo 1). The agents who heard the utterance will be able
3

---

Under review as a conference paper at ICLR 2022
Figure 2: Example of three consecutive turns in episode. There are three agents in 5 x 5 grid, each with a hearing range (shaded the same color the agent), Fully-colored cells depict recharge bases. Information is represented by diamonds: black, gray, and white diamonds represent an information piece known first-hand, second-hare and not known, respectively. Black circles show the information piece currently being said by each agent.
to share this newly-learned information with others in following turns. We refer to this as second- hand information, since it is learned -as opposed to first-hand information, given at the start of each episode. The state space is comprised of the position of the agents and their current knowledge:
= [((ps ki), for i {I....,a}) where ps (l.....w} x (1,...,w) w), and k {0, 1)
Each agent aims to maximize their individual reward R, via information seeking and sharing. Rewards are earned by hearing new piece of information, giving someone else new piece of information, or correctly using recharge bases. Recharge bases are special cells where agents can reset their knowledge in exchange for large reward (e.g. (n- 1)c times the reward for listening to or sharing new information). Each agent has its own stationary recharge base during an episode. trigger base, an agent must step into its designated base having acquired all the available pieces of information, causing the agent to lose all the second-hand information it learned. Recharge bases guarantce that there is always reward to seek this environment. Concretely, {(p,, k4), for i {I....,a) } and a; (ater a; aquumm), we can define the reward as the addition of the reward for hearing new information, giving new information, and using the recharge base:
(s, = =1 -Pyllo S h and Ki = 0} + Σ
fllp: -Pilloo I h and kj 0}
+ (n-1) {p base; and ky = (1, 1, .,....113 1}}
A non-ToM agent can have only limited success in this environment. Without reasoning about its own knowledge (i.e. without zeroth order ToM), it does not know when to use a recharge base. Moreover, without knowledge about other agent's knowledge (i.e. without first order ToM) it is not possibly to know which agents possess the information pieces it is lacking. Even if it accidentally hears information, to maximize its reward. Higher order ToM is also often needed in SymmToM, as we will discuss further in Section 7.3
non-firstorrder ToM agent cannot efficiently decide what to utter in response
Even though we only discussed a collaborative task for Symm ToM, it can easily be extended for competitive tasks. Moreover, all models are also designed to work under competitive settings. SymmToM satisfies the desiderata we laid out in the previous section, as we will detail below:
Symmetric action space. As defined in Eq. I Ai A, for all j. Only a subset may be available at time since agents cannot step outside the grid, speak piece they have not heard, or move if they would collide with another agent in the same cell, but they all share the same action space.
Imperfect information. Messages sent by agents outside of the hearing range will not be heard. For example, in Fig. (2 green sends a message but not heard by anyone, since outside of red's and blue's Slues range. Hearing ranges are guaranteed not to cover the whole grid, since h < 2w 1.
Observation others. Agents have perfect vision of the grid, even they cannot hear what was said outside of their hearing range. Hence, agent may see that two agents in range of each
4

---

Under review as a conference paper at ICLR 2022
other, and thus probably interacted, but not hear what communicated. An example of this can be seen in Fig. 24, where green observes blue and red interacting without hearing what was uttered.
The uncertainty in the observation also differentiates SymmToM from prior work: to solve the task perfectly, an agent needs to assess the probability that other agents outside its hearing range shared specific piece of information knowledge of what each agent knows (first order ToM), the perceived knowledge of each of the agents in the interaction (second order ToM), as well higher order ToM.
avoid repetition. This estimation may be performed using the
Information-seekingg behavior Rewards are explicitly given for hearing and sharing novel information, guaranteeing iioommtiion-eekinng is crucial in SymmToM. Recharge bases ensure that the optimal solution is not for all agents accumulate in the same spot and quickly share all the information available; and that the information tracking required is more complex than accumulating past events. Conceptually, with recharge bases we introduce an explicit and observable forgetting mechanism. As discussed in Section [ this allows for perpetual information seeking and requires information staleness estimation. An example of successful recharge base use is shown Fig. 2b.
5 BASELINE LEARNING ALGORITHMS AND OTHER BOUNDS
To learn a policy for acting in the multi-agent SymmToM environment, it is good strategy to use a multi-agent reinforcement learning algorithm. We use MADDPG (Lowe et al.) 2017), a well- known multi-agent actor-critic framework with centralized planning and decentralized execution, to counter the non-stationarity nature of multi-agent settings. In MADDPG, each actor policy receives its observation space as input, and outputs the probability of taking each action.
Notably, actors in MADDPG have no mechanism for remembering past turns. This is a critical issue in SymmToM, as agents cannot remember which pieces they currently know, which ones they shared and to whom, and other witnessed interactions. To mitigate this, it is necessary to add recurrence mechanism to carry over information from past turns. One option would be to modify the agent policy using recurrent network like an LSTM, as RMADDPG (Wang al. 2020) does.
Perfect Information, Heuristic and Lower Bound Models Performance is difficult interpret without simpler baselines. As a lower bound model we use the original MADDPG, that since it does have recurrence embedded, should perform worse or equal any of the modifications described above. We also include an oracle model (MADDPG-Onan since it receives the current knowledge K for all agents in its observation space. The performance of MADDPG-Oran may not always be achieved, as there could be unobserved communication with multiple situations happening with equal probability. Moreover, as the number of agents and size of the grid increases, current reinforcement learning models may not be able to find an optimal spatial exploration policy; they may also not be capable of inferring the optimal piece of information to communicate in larger settings. In these cases, MADDPG Oracle may not perform optimally, also include a baseline with hcuristic agents to compare performance.
that does not require theory of mind
Heuristic agents will always move to the center of the board and communicate round-robin all the information pieces they know until they have all the available knowledge. Then, they will move efficiently their recharge base and come back to the center of the grid, where the process restarts. We must mention that this heuristic is not necessarily the perfect policy, but it will serve as baseline note settings where current MARL models fail even with perfect information. Qualitatively, smaller settings have shown to approximately follow a policy like the heuristic just described.
DIRECT MODELING OF SYMMETRIC THEORY OF MIND
In contrast to RMADDPG (Wang et al., 2020 we specifically design algorithms for our environment to maximize performance. Intuitively, our model computes matrix, K E 1]exe that reflects the information pieces known by each agent from the perspective of the agent being modeled: Kiş reflects if the agent being modeled believes that agent knows i. К is updated every turn and used as input of the following turn of the agent, obtaining the desired recurrent behavior. K is also concatenated to the usual observation space, to be processed by two-layer ReLU MLP and
5

---

Under review as a conference paper at ICLR 2022
obtain the probability distributions for speech and movement, in the original MADDPG. There are several ways to approximate K. It is important to note that each agent can only partially observe communication, and therefore it is impossible to perfectly compute K deterministically.
The current knowledge is comprised of first-hand information (the initial knowledge of every agent, F. publicty available) and second-hand information. Second-hand information may have been heard this turn (S, whose computation will be discussed below) or in previous turns (captured in the K received from the previous turn, noted (((-1)). Additionally, knowledge may be forgotten when an agent steps on base having all the information pieces. To express this, precompute vector B E (0. } that reflects whether each agent is currently on its base; and a vector E E {0. 1) that determines if agent is entitled to their recharge hase: Fg =1 E, K,,=o for all j E (1, ( a). We are then able to compute as follows:
K. (Fij or S 1 or Kij (t-1) 1) and not (Bij and Egg)
(2)
F, ((-1)), and B are given as input, but we have not yet discussed the computation of the second- hand information S. 5 often cannot be deterministically computed, since our setting partially observable. We will identify three behaviors and then compute S as the sum of the three:
S 5 + 5(1) + 5(2)
For simplicity, we will assume from now on that we are modeling agent k. 5( will symbolize the implications of the information spoken by agent k: if agent & speaks a piece of information, they thus know that every agent in its hearing range must have heard it (first order ToM). 5t' will symbolize the implications of information heard by k: this includes updating k's known information (zeroth order ToM) and the information of every agent that is also in hearing range of the speaker heard by k. S will symbolize the estimation of information pieces communicated between agents that are out of k's hearing range. Since we assume perfect vision, & will be able to see if two agents are in range of each other, but not hear what they communicate (if they do at all).
s!o] and ş(1] can be deterministically computed. To do so, it is key to note that every actor knows the set of actions A {0, 1]cxa performed by each agent last turn, given that those actions were performed in their hearing range. Moreover, each agent knows which agents are in its range, as they all have perfect vision. We precompute H E {0, 1] laa to denote if two given agents are in range.
Then, S = if and only if information piece i was said by k. and agents h and j are in hearing range of each other. More formally,
$!. As Hkj
1/ = 1 if and only if agent ls (the actor are modeling) heard some agent l speaking information piece i, and agent j is also in range of agent f. Note that agent is does not need to be in hearing range of agent j. More precisely,
s Are HEg Hej, for any agent l
S the interactions between agents not in hearing range of the agent we are modeling- can be estimated in different ways. A conservative approach would be not estimate interactions we do which we will call another approach would be to assume that every interaction we do not witness results in sharing a piece of information that will maximize the rewards in that immediate turn. We will call this last approach MADDPG- HLDDDPGGGreedyBan GreedyEncounterr (MADDPG-GE) MADDPG-CE GE assumes agents play optimally, but does not necessarily know all the known information and that could lead wrong prediction. This is particularly true during training, as agents may not behave optimally. The computation of S(3] for MADDPG-GE is as follows.
witness (S
(MADDPG-CE) and
First, we predict the information piece Uş that agent l uttered. MADDPG-GE predicts Up will be the piece that the least number of agents in range know, as it will maximize immediate reward:
U = arg min Σ (Ka and H3²) E [1....c]
With this prediction, agent j will know information i at least one agent in its range said it:
s if exists + ks such that Up j and H5e and f else

---

Under review as a conference paper at ICLR 2022
(MADDPG-EE) MADDPG-CO CE and MADDPG-GE two paths to information sharing estimation, but in none of them do we estimate the probability of an agent knowing specific piece of information. In MADDPG-EttinateEncnm EstinatteEncounter (MADDPG-ER) known information of other agents not binary, i.e. Ki E [0. 1]. This added flexibility can avoid making predictions of shared information based upon unreliable information.
MADDPG-EE estimates the probability that an agent j uttered each piece of information (U3 E RR) by providing the current information of all agents in its range an MLP:
U = softmax (K1g..... Kej, Sogg{KKn [Kie.... Ket for all & where H)t)), with f an MLP
Then, the probability of having heard a specific piece of information will be the complement of not having heard it, which in turn means that none of the agents in range said it. More formally,
s = II
U-
t,Hy==1
Since MADDPG-EE requires functions to be differentiable, we use differential approximation of Eq. 2 A pseudocode of MADDPG-EE's implementation can be found in Section A.4 MADDPG- EE solely focuses first order ToM, and we leave to future work modeling with second order ToM. The structure of the model would be similar but with an order of magnitude more parameters.
EXPERIMENTS
7.1 EXPERIMENTAL SETTINGS
In this section, compare the different algorithms explained in the previous section. The observation space will be constituted of processed version the last turn in the episode, to keep the input size controlled. More precisely, the observation space is composed of: the position of all agents, all recharge bases, the current direction each agent is moving towards to and what they communicated in the last turn, the presence of a wall in each of the immediate surroundings, and every agents' first-hand information. First-hand information is publicly available in our experiments to moderate the difficulty of the setup, but this constraint could also be removed. This simple setting is still partially observable, since the agents cannot hear interactions outside of their hearing range.
We use the reward as our main evaluation metric. This metric indirectly evaluates ToM capabilities, since potomnation-seeking is at the core of SymmToM. We train through 60000 episodes, and with random seeds to account for high variances in the rewards obtained. Our policies are parametrized by two-layer ReL.U MIP with 64 units per layer, in the original MADDPG (Lowe et al. 2017). MADDPG-EE's function f is also a two-layer ReLU MLP with 64 units per layer.
We test two board sizes (w 6, and quantities of information pieces (c a, c = 2a e 3a). The length of each episode set to 5w. More detail about design decisions can be found in Section A.5
12), two numbers of agents (a = 3 and a = 4), and three
7.2 MAIN RESULTS
As we can observe in Table [ there is significant difference in performance between MADDPG- Oracle and MADDPG (MADDPG-Oracle) is 123% better on average): this confirms that developing ToM and recurrence is vital to perform successfully in SymmToM. an upper bound: when a, the heuristic performs better (101% on average). This shows that even with perfect information, it can be difficult to learn the optimal policy using MADDPG. Moreover, models with a recurrence mechanism perform significantly better than MADDPG (61 better on average), also showing that remembering past information gives a notable ad advantage. As expected, having recurrent models tailored to our problem resulted in better performance than a general LSTM recurrence (RMADDPG). The performance of the best of the tailored models (MADDPG- CE, MADDPG-GE MADDPG-ER was 42% better on average than plain RMADDPG. LSTM was able to surpass the best of the tailored models only for = 3, 12, 3a.
HADDPG-Orache is often not
Increasing c generally decreases global rewards for learned agents (on average, rewards for c = 2a are 75.54% of those for a, and rewards for 3a are 75.66% of those for a).

---

Under review as a conference paper at ICLR 2022
Table 1: Average rewards per agent in trained models evaluated during 1000 episodes. 7 runs are averaged for each, using the best checkpoint: this compensates for collapses in performance seen in Fig. [] and Fig. [ Values shown are individual rewards normalize by the number of agents. Bold lettering represents the best result of learned imperfect-information model for each setting. Standard deviations are detailed A.5
agents (a.
grid width (w)
12
12
info pieces (c)
a
2a
3a
0
2a
3a
a
2a
3a
a
2a
3a
Heuristic
38
54
58
37
57
72
58
89
101
MADDPG-Oracle
42
49
39
54
38
41
71
45
30
57
33
29
MADDPG
39
18
16
35
32
11
34
23
13
18
14
14
+RNN (RMADDPG)
37
19
19
44
27
19
29
20
16
32
17
16
CConservative (CE)
36
26
33
46
43
14
40
30
25
27
27
16
+Greedy (GE)
34
25
33
47
68
15
35
30
25
35
29
17
+Estimated (EE)
13
39
26
25
19
This suggests that probabilistic decisions are harder to learn, or impossible to successfully navigate when several events are equally likely. MADDPG-EE, did not show improvements over the other learned agents, and in some cases decreased its performance more heavily than other learned agents 3a). MADDPG-EE uses an MLP in its definition flexibility but also implies a more complex function to learn. We leave to future work to explore other probabilistic agents, but the significant difference in performance between all of the learned models and the highest performing ones (MADDPG-Oracl and the heuristic) shows there is ample space for improvement in this task, and hence proves SymmToM to be a simple yet unsolved benchmark.
(e.g. w 6,
5(2,, which gives more
Increasing results in a 10% reduction of performance on average for learned models. Nonetheless, the heuristic improved its rewards by an average of 46%, given the larger opportunities for rewards when including an additional listener. Overall, this implies that increasing also makes the setup significantly more difficult. Finally, increasing w did not have a conclusive result: for a = consistently decreased performance in 177, but for 61% % for a and e = 2a respectively.
improvement of 16% and
In sum, modifying e and provides easy way of making setting more difficult without introducing additional rules.
7.3 DISCUSSION
In the past section we analyzed results using the metric of episode rewards. Although the rewards in SymmToM are designed to correlate with information seeking and knowledge state of the agent themselves and others, they do not show explicitly if agents are exhibiting theory mind. To do so more directly, develop categories of possible analyses: scenarios specifically designed to test theory of mind, and post-hoe analyses of episodes.
A classic example of scenario specifically designed test ToM behavior is the Sally-Anne task /Wimmer & Perner] 1983). This false belief task, originally designed for children, aims to test if passive observer can answer questions about the beliefs of another person, in situations where that belief may not match reality. If we were to use it for machine ToM, we could repeat the experiment and ask an agent predict the position of an object varying the underlying conditions. This test is feasible because there is only one agent with freedom of action, which ensures that desired conditions are met every time. Testing becomes unfeasible when giving multiple agents freedom of action, as constraints planned in test design may be broken by collective drift from the strategy thought by the designer. Testing becomes easier we allow for controlling agents but one, as shown in Fig. 3 Other tests besides the ones shown may be designed. In particular, in Fig. 3d we show an example of probabilistic ToM where two communicative events are equally likely, but one could modify this scenario to have different probabilities and test the expected value of the turns until red successfully shares an information piece. One could also design retroactive deduction tests: for example, in Fig. 3d if red communicates and receives reward, it deduce that green had
8

---

Under review as a conference paper at ICLR 2022
(a) 0th order ToM test.
(d) ToM test.
Probabilistic
(b) 1 and 2nd order ToM test.
(c) 2nd order ToM test.
Figure: 3: Axample of tests for zeroth, first, second order, and probabilistic ToM. We test red agents, immobilize gray agents, and control blue and green agents' movements. In Fig. Baj red will go to the top right if it remembers to have heard the first piece, and to the left otherwise. In Fig. 33b] red will move the right if and only if it assumes that the two agents on the left played optimally (red cannot hear what they communicated), In Fig. 3c blue is controlled to ensure it will search the agent on the bottom left (its optimal play, five moves). Red's optimal move to meet blue, and hence must only move to the bottom left, even if the agent currently there will not provide any reward. In Fig. 3d red will interact with green not knowing what it communicated with blue in the previous turn. It should be able to communicate the missing piece with an expected value of 1.5 turns.
received that information from blue. there had been another agent (let's say, yellow agent) in range of blue when it spoke to green, the red agent could also update its knowledge about yellow. Results for the tests proposed in FigureßJare detailed in Appendix A.
Post-hoe analysis also has its challenges in multi-agent settings, Thanks to our reward shaping, using recharge bases is always the optimal move when an agent has all the information available: agent will have reward of (n 1)e for using the base, whereas it can only gain up to n 1 per turn if decides not to use it. Even in this case, small delays using the base may occur, for example the agent can gather additional rewards on its path the base. More generally, having multiple agents makes specific behaviors attributable to any of the several events happening once, or combination of them.
in the most direct cases.
Even though it may be difficult to establish causality when observing single episodes, we developed metries that comparatively show which models are using specific features of the environment better than others. Examples of metrics are unsuccessful recharge base usage count; number of times an agent shares an information piece everyone in range already knows when having better alternatives; number of times agent moves away from every agent when not having all the information pieces available; among others. See Appendix A.2 for detailed description and results. Reward also be understood post-hoc metrie with more indirect intepretation.
Post-hoc analyses single episodes can also be blurred by emergent communication. Because agents were trained together, they may develop special meaning assignment to particular physical movements or messages. Even though qualitatively this does not seem to be the case for the models presented in the paper, tests should also account for future developments. This also implies that one should not overinterpret small differences in the metrics described the paragraph above.
8 CONCLUSIONS AND FUTURE WORK
We defined a framework to analyze machine theory of mind multi-agent symmetric setting, more realistic setup than the tasks currently used in the community. Based on the four properties needed for symmetric theory the problem, and we showed we can easily increase difficulty by growing the number of agents or communication pieces. Our main goal in this work was not to solve symmetric theory of mind, but rather to give starting point to explore more complex models in this area. We showed that with this minimal set of rules, SymmToM proves algorithmically difficult for current multi-agent deep reinforcement learning models, even when tailoring them to specific task. We leave to
mind to arise, we provided simplified setup on which to test

---

Under review as a conference paper at ICLR 2022
future work to develop models that handle second-order theory of mind and beyond, and models that periodically reevaluate past turns to make new deductions with information gained a posteriori (i.e.. models that pass retroactive deduction tests). Another interesting direction would be to replace the information pieces with constrained natural language: communication sharing in our task is binary, whereas in language there is flexibility communicate different subsets of knowledge base using single sentence. We will make our codebase public upon publication, that also includes additional observation space restrictions increase difficulty.
ETHICS AND REPRODUCIBILITY STATEMENT
Theory of mind research its core deals with understanding the mental states of other individuals. In the present work we focused on collaborative machine theory of mind, which entails interactions only between artificial agents, and only in scenarios where every party involved has the same incentive structure. This design decision is intentional. Other approaches to theory of mind research could include scenarios with human-agent interaction, which could potentially lead to agents learning to model human players' mental states. This is not concerning per se, but in scenarios where players do not have the same incentive structure, it could lead to agents learning to deceive other players (potentially human players). The state of the art in machine theory of mind is still far away from these capabilities, but we believe that experiment design choices should always take this matter into account.
Regarding reproducibility, we will make all code public upon acceptance, including the environment and the models' code. The exact set of parameters used for training will also be shared. Multi-age reinforcement learning models do have high variance, so models should be run several times to see similar confidence intervals as the ones shown in Fig. and Fig.
REFERENCES
Chris Baker, Rebecca Saxe, and Joshua Tenenbaum. Bayesian theory of mind: Modeling joint belief-desire attribution. In Proceedings of the annual meeting of the cognitive science society, volume 33, 2011.
Kanishk Gandhi, Gala Stojnic, Brenden M. Lake, and Moira R. Dillon. Baby intuitions benchmark (bib): Discerning the goals, preferences, and actions of others. CoRR, abs/2102. 1938, 2021.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, Pieter Abbeel, and Igor Mordatch. Multi-agent actor- critic for mixed cooperative-compeliivee environments. pp. 6382-6393, 2017.
Aida Nematzadeh, Kaylee Burns, Erin Grant, Alison Gopnik, and Tom Griffiths. Evaluating theory of mind in question answering. pp. 2392-2400, October-November 2018. doi: 10.18653/v1/ 218-1261. URL htR.sttps:/ http://///claatttologgooooo
org/ 1261
Aviv Netanyahu*, Tianmin Shu*, Boris Katz, Andrei Barbu, and Joshua B. Tenenbaum. Phase: Physically-groundee abstract social events for machine social perception. 35th AAAI Conference on Artificial Intelligence (AAAI), 2021.
tshu 1o/PHASE/
David Premack and Guy Woodruff. Does the chimpanzee have theory of mind? Behavioral and brain sciences, 144):515-55 526, 1978.
Neil Rabinowitz, Frank Perbet, Francis Song, Chiyuan Zhang, SM Ali Eslami, and Matthew Botvinick. Machine theory of mind. In International conference on machine learning, pp. 4218- 4227. PMLR, 2018
Tianmin Shu, Abhishek Bhandwaldar, Chuang Gan, Kevin A. Smith, Shari Liu, Dan Gutfreund, Elizabeth S. Spelke, Joshua B. Tenenbaum, and Tomer Ullman. Agent: benchmark for core psychological reasoning. In ICML, pp. 9614-9625. 2021.
Michael Tomasello. Constructing language. Harvard university press, 2009.
10

---

Under review as a conference paper at ICLR 2022
Tomer Ullman, Chris Baker, Owen Macindoe, Owain Evans, Noah Goodman, and Joshua Tenenbaum. Help or hinder: Bayesian models of social goal inference. In Y. Bengio, D. Schuurmans, J. Lafferty, C. Williams, and A. Culotta (eds.), Advances in Neural Information Processing Systems, volume 22. Curran Associates, Inc., 2009.
Rose E Wang, Michael Everett, and Jonathan How. R-maddpg for partially observable environments and limited communication. arXiv preprint crXIv:2002.06684, 2020.
Heinz Wimmer and Josef Perner. Beliefs about beliefs: Representation and constraining function of wrong beliefs in young children's understanding of deception. Cognition, 13(1):103-128, 1983.
Hao Zhu, Graham Neubig, and Yonatan Bisk. Few-shot language coordination by modeling theory of mind. In International Conference on Machine Learning, pp. 12901-12911. PMLR, 2021.

---

Under review as a conference paper at ICLR 2022
(a) Oth order ToM test, 6. Minimum turns to succeed: 3.
(b) 1st & 2nd order test, 6 Minimum turns succeed: 2.
(c) Probabilistic ToM test, w = 12 Minimum turns to succeed: 1.5.
(d) Oth order ToM test, 12 Minimum turns succeed: 9.
(e) 1st & 2nd order test, w = 12 Minimum turns succeed: 8.
(f) 2nd order ToM test,
12.
Figure 4: Depictions of rescaled tests from Figure 3 designed to match some of the parameter combinations already experimented on.
A APPENDIX
A.1 AD-HOC THEORY OF MIND TESTS
We test on the four examples shown in Figure adapting the examples to one of the grid sizes we already experimented
For the tests described in Figure 3a and Figure 3b test two different grid sizes: w 6 and w = 12. For the tests described in Figure [e and Figure [3d] we only test 12 and w 6 respectively. Image depictions of the exact test configurations can be seen in Figure 4
We measure three metrics: average success rate, average failure rale, and ratio of average lurns to succeed vs. optimun (RATSO). Note that Average Success Rate and Average Failure Rate do not necessarily sum since these two metrics only include trials where the agent reached any of the two proposed outcomes. If, for example, the agent never moved from the starting point, the trial would be counted positively towards Avg. Success Rate Avg. Failure Rate. In addition, ratio of average turns to succeed vs. optimum (RATSO) is the ratio between the average turns it took to succeed successful trials, and the optimum number turns to succeed a specific trial.
4ed the trial ends when the red agent reaches the hearing range of one the two possible target agents. The test depicted in Figure 4i pass/fail test: if red moves suboptimally at any point before meeting blue, the trial is declared failed. This makes it particularly difficult test to pass at random. Because the nature of this second order ToM test, we only report the average success rate. Finally, for the probabilistic ToM test want measure how fast can red communicate all the information it has to green. The optimal number turns is 1.5 (as discribed in Figure 3 and because of the nature of this test will only report RATSO.
For the tests in Figure 4a 4b
4d
All results can be found Table 2 higher reward models (MADDPG-CE and MADDPG-GE are the best models), suggesting that the
As expected, a larger average success rate correlates with
12

---

Under review as a conference paper at ICLR 2022
Fig.
Fig. 3a
ToM test
(2nd
(Oth order)
order)
grid width (w)
6
12
12
SR
FR
1-SR-FR
RATSO
FR
I-SR-FR
RATSO
SR
MADDPG
17%
75%
3.66
44%
3.75
33%
RMADDPG
18%
59%
24%
5.30
1%
3%
96%
5.39
32%
MADDPG-CE
32%
49%
19%
4.94
10%
1%
89%
5.00
24%
MADDPG-GE
32%
40%
28%
4.97
10%
12%
78%
4.99
32%
MADDPG-EE
16%
54%
29%
5.26
0%
25%
75%
4.39
33%
Fig. 3b
Fig. 3d (probabilistic)
ToM test
(Ist and 2nd order)
grid width (tr
SR
FR
I-SR-FR
RATSO
SR
FR
1-SR-FR
RATSO
RATSO
MADDPG
9%
79%
12%
3.37
0%
62%
38%
5,49
6.40
RMADDPG 18%
74%
8%
3.70
2%
61%
37%
4.49
5,02
MADDPG-CE 16%
74%
10%
3.67
2%
67%
31%
4.71
7.12
MADDPG-GE 27%
72%
1%
3.36
2%
66%
32%
4.62
6.33
MADDPG-EE 14%
81%
5%
3.94
0%
85%
15%
3.52
6.40
Table Results for tests depicted Fig. 4 evaluated during 1000 episodes for each of different random seeds. SR means average success rate, FR means average failure rate, and RATSO is the ratio of average turns to succeed vs. the optimum turns to succeed. 1-SR-FR depicts the ratio of episodes where agent did not reach any grid cell to terminated the test (either successfully or unsuccessfully) before the trial reached the maximum number of turns allowed (5w). A horizontal line means metric could not be computed.
reward is valuable overall metric. The low average success rates across all tests show there is significant room improve in this benchmark. Success rate drops sharply when increasing the grid size, suggesting larger grids impose more difficult training settings. In this analysis, we used models that were trained specifically for each parameter combination.
Results for Oracle were omitted since some tests assumed no knowledge about communication (e.g. even though agents in Figure 4b do not communicate during the test, the test was designed to test the red agent assumed them to be).
As we emphasized in the main text, many more tests can proposed. The code base we will release allows for casily adding new tests to the suite.
13

---

Under review as a conference paper at ICLR 2022
A.2 POST-HOC ANALYSES
We developed several post hoc metrics to analyze specific aspects of our models.
Unsuccessful recharge base usage rate: Average times per episode an agent steps on its recharge base without having all the information available (i.e. wrong usage of recharge base). Note that an agent may step on its base just because it is on the shortest path to another cell. Therefore, a perfect theory of mind agent will likely not have zero on this score; but generally, lower is better. See results in Table
Wrong communication piece selection count: Average times per episode an agent attempted say an information they currently do not possess. these cases, no communication happens. Lower is better. See results in Table
Useless communication piece selection count: Average times per episode an agent communicated an information piece that everyone in its hearing range already knew, when having piece of information that at least one agent in its range did not know. Lower is better. See results in Table
Useless movement: Average times per episode agent moves away from every agent that does not have the exact same information it has, given that the agent does not currently possess all the information available. This means that the agent is moving away from any possible valuable interaction. Lower is better. See results in Table
All metries are normalized by number of agents (i.c., they show the score for a single agent). This allows for better comparison between 3 and 4 settings.
RMADDPG had the worst scores for unsuccessful recharge base use rate and useless communication piece selection count. RMADDPG scored 43% more than Oracle for unsuccessful base usage average, and 63% more than Oracle on average for usage of a useless communication piece. The best tailored models (MADDPG-CE and MADDPG-GE) performed similarly to Oracle on average for these two metrics. In contrast, MADDPG-CE and MADDPG-GE performed significantly worse than Oracle for the wrong communication piece selection count (48% and 56% more than Oracle on average). This suggests that all models may be making wrong decisions, but RMADDPG is biased towards communicating redundant information whereas MADDPG-CE and MADDPG-EE tend towards not communicating at all (the true effect of trying to communicate something they are allowed). Further analysis needed to truly understand if these apparently wrong behaviors were done in turns where the agent had all the information available to make better move, or if this their default when they believe they have nothing of value to communicate. priori RMADDPG bias seems more principled, but it still showed worse performance overall.
No learned model performed particularly better in the useless movement metric (average differences in performance were less than 10%), suggesting that they perform pointless movements in similar frequencies. It is important not to overinterpret small differences in these metrics. For example, useless movement may be signal of emergent communication. Furthermore, agent may communicate something suboptimal for its immediate reward but this move may not affect its expected reward for the trial.
agents (a)
grid width (w)
6
12
6
12
info pieces (c)
2a
3a
2a
30
2u
3a
2a
3a
MADDPG-Oracle
3.6
3.1
4.4
4.9
3.7
3.1
2.8
4.4
1.3
2.4
3.1
1.0
MMADPG
4.8
3.5
2.9
6.7
6.3
0.4
6.6
3.5
0.8
6.5
2.7
0.6
RMADDPG
5.9
5.0
3.2
9.9
6.3
4.7
5.4
4.8
0.8
7.3
2.6
0.5
MADDPG-CE
5.7
3.3
4.3
2.8
0.4
3.4
1.1
4.3
1.7
0.5
MADDPG-GE
4.1
5.5
3.7
4.9
5.0
0.3
4.3
3.3
1.0
3.7
2.3
0.6
MADDPG-EE 4.8
4.1
2.4
6.2
6.4
0.3
6.6
3.0
0.7
7.0
3.5
0.4
Table 3: Results for unsuccesstul recharge base usage rate, normalized by agent. Bold lettering represents the best result of a learned imperfecttinformatonn model for each setting (lower is better).
14

---

Under review as a conference paper at ICLR 2022
agents (a)
grid width (w)
6
12
info pieces (c)
2a
3a
2a
30
2a
3a
2a
3a
MADDPG-Oracle
3.2
3.0
3.5
10.7
10.2
5.2
2.7
5.1
2.0
7.5
6.4
3.4
MADDPG
4.7
0.4
0.3
11.8
4.8
1.3
5.7
0.3
1.3
10.3
0.8
2.0
RMADDPG
3.2
1.7
1.0
9.7
5.9
3.4
3.3
2.0
1.0
10.3
5.5
5.0
MADDPG-CE
6.2
3.8
3.5
11.4
5.3
3.8
7.0
4.2
3.7
15.5
4.7
10.9
MADDPG-GE
6.3
3.3
11.3
6.6
3.9
4.2
14.2
7.8
MADDPG-EE
4.5
0.4
0.2
9.5
4.1
0.4
5.1
0.1
0.8
9.1
1.5
2.9
Table 4: Results for wrong communication piece selection count, normalized by agent. Bold lettering represents the best result of a learned imperfect-infooratiion model for each setting (lower better).
agents (a.)
4
grid width (w)
12
info pieces (c)
a
2a
3a
a
2a
3a
2a
30
a
2a
3a
MADDPG-Oracle
8.4
13.2
14.7
20.6
26.2
19.0
10.6
17.3
12.2
24.0
17.3
12.6
MADDPG
8.4
13.1
20.4
18.2
30.5
43.2
14.6
16.9
24.3
25.1
38.6
49.8
RMADDPG
8.1
16.4
18.6
18.3
33.4
38.4
14.3
19.7
24.4
29.0
38.1
50.0
MADDPG-CE 11.8
9.5
9.8
20.7
13.3
8.6
17.4
13.2
14.8
27.2
12.1
28.4
MADDPG-GE 12.4
9.3
10.4
19.8
12.7
9.6
16.7
11.7
16.8
24.7
17.4
27.5
MADDPG-EE 7.8
12.8
20.3
16.1
35.0
41.3
14.4
23.2
36.5
49.6
Table 5: Results for useless communication piece selection count, normalized by agent. Bold lettering represents the best result of a learned imperfect-infoomation model for each setting (lower better).
agents (a)
grid width (w)
12
6
12
info pieces (c)
a
2a
30
2u
a
3a
MADDPG-Oracle
2.4
1.3
1.9
4.1
3.6
2.6
1.8
MADDPG
2.1
2.2
1.4
5.0
3.9
3.1
2.1
1.2
0.7
4.4
3.4
1.4
RMADDPG
2.8
1.6
3.8
3.7
1.9
1.5
0.4
4.1
1.2
MADDPG-CE
2.3
2.4
1.7
5.4
2.3
3.4
1.9
0.8
1.0
4.2
1.0
3.8
MADDPG-CS
3.0
2.1
1.7
4.5
1.8
3.1
1.9
0.6
0.8
4.2
2.0
3.6
MADDPG-EE
2.4
2.2
1.7
4.2
5.0
3.4
2.2
1.3
0.5
4.6
3.5
1.9
Table 6: Results for useless movement count, normalized by agent. Bold lettering represents the best result of learned imperfect-informatioo model for each setting (lower better).
15

---

Under review as a conference paper at ICLR 2022
A.3 TRAINING CURVES FOR THREE RANDOM SEEDS COMBINED
(a) a = 3, C 0, W 6
(b) a = 4, = 0, W
310
300
(C) 3, C 2a, w
(d) a = 4, c 2a, 6
30
300
310
350
(e) = 3, = 3z, w
(l) a = 4, c. 3a, W 6
MADDPG-EE MADDPG-GE
Heuristic MADDPG-CE
RMADDPG
MMADPG MADDPG-Oracle
Figure 5: Average episode rewards throughout training for 60000 episodes for all combinations of
a E (3, 4}, w = 6, and c E {u, 3.).
16

---

Under review as a conference paper at ICLR 2022
(a) a = 3,c w 12
(b) a = 1, a, w = 12
400
281
16
20
304
(c) 3, C 2a, 12
(d) 4, 2a. 12
10
10:
(e) 3, c 3u, 12
(f) = 4, = 33, 12
MADDPG-EE - MADDPG-GE - Heuristic
MADDPG-CE
RMADDPG - MMADPG MADDPG-Oracle
Figure 6: Average episode rewards throughout training for 60000 episodes for all combinations of E (3, 4), w = 12, and E {a, 3..
17

---

Under review as a conference paper at ICLR 2022
A.4 PSEUDOCODE MADDPG-EE
Algorithm Actor implementation of MADDPG-BE, approximating K to make differentiable.
Input: observation, A E 10,1), agent_idx E a F E (0,1]exa K E {0, B E {0, 1)". E [0,1) 1
Make agents not in their own hearing range, to avoid talking to themselves from the previous turn. This would be problematic when using recharge bases.
H laxa
Compute sto), all the heard information spoken by agent_idx:
şlol copy A ugent idx] @ copy H Hagent.idis idx,:)
times
Compute 5(1), all heard information by agent_idx, spoken by all agents:
||ll (A @ copy H [agent idx,:))
C
Compute stz,, an estimation of information pieces communicated between agents that were out of agent_idx's hearing range:
U, = softmax( (K Kej, (Kie,..,, Kee for all l where Hyeh)), with fi an MLP
s! ij
III, 1 Ue for all i fo....,c 1] and {0, (O....,
$ = 5tol + 5(4 + St2
E. 1 sum (//((():))=== E {0, for all -0...., 1}
K step(F 100 + K copy [Bo E))
return softmar ([(0maa(((((obbevvatia) K()), where f2 is an MLP
A.5 EXPERIMENT DESIGN DECISIONS AND CONSIDERATIONS ABOUT RESULT PRESENTATION
All our experiments are with 1: only the immediate neighbors of an agent will hear what they communicate.
We tested with and and not larger numbers of agents, the training time increases quadratically with also, the intrinsic difficulty of larger setup evvnn with perfect information- would possibly degrade performance to the point of making it impossible to compare models.
Running experiments with the same number of turns for every setting would imply that agents can move less combinations with larger values of w, hence the need of making proportional the size of the grid. Since the duration of the experiment is directly proportional to the length of the episodes, we settled on a small multiplier. 5w allows agents to move to each edge the grid and back to the center. A similar decision is required when choosing c: having constant number of information pieces when increasing the number of agents would make the problem easier, as each agent would have fewer options of first-hand information pieces.
We decided to evaluate rumning additional episodes over the best checkpoints of each model because there was high variance for some runs, and drops in performance after achieving the highest rewards. Those results are the base of the discussion and can be seen in Table T Still, we share the training curves so that the reader observe these behaviors in Fig. 5 and Fig. 6
We used the same hyperparameters as the ones used MADDPG, except with a reduced learning rate and (Ir 0.001 and 0.005). We used the same parameters for all experiments.
18

---

Table 7: Standard deviations of the average episode reward averaged by seed shown in Table Under review as a conference paper at ICLR 2022
agents (a)
grid width (w)
6
12
12
info pieces (c)
2a
3a
2a
30
2a
3a
2a
3z
MADDPG-Oracle
20
16
13
53
35
55
1.5
20
14
41
25
21
MADDPG
5
7
2
34
41
24
12
2
17
4
RMADDPG
15
8
24
10
MADDPG-CE
15
11
15
32
86
20
12
15
29
35
MADDPG-GE
16
9
12
56
70
43
16
13
26
51
8
MADDPG-EE 11
8
6
25
32
35
11
3
59
12
4
19


Reviews:
[{"review_id": "quwmUYuhZ8g", "reviewer": "Reviewer_t9A3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\nThe topic covered in the paper is extremely timely: ToM, and MARL in general (specifically centralized training with decentralized execution (CTDE) MARL such as MADDPG), are topics receiving a great deal of interest, with many workshops and conference publications related to this work.\n\nThe paper makes a compelling case for SymmToM with both the motivating discussion and the results. The definitions of \"Theory-of-Mind Agents\" and \"Symmetric Theory-of-Mind environments,\" while perhaps having some debatable components (e.g. is it important that each agent _always_ get some information about every other agent, as seems to be implied?), are reasonable and in my mind cover many interesting cases. The definition of SymmToM follows cleanly from this. It is a very simple environment that seems to contain minimal aspects critical for it to count as a Symmetric Theory-of-Mind environment. Finally, the results make a compelling case that this is a useful benchmark. In particular, by tuning the number of agents and info pieces, we easily reach a regime in which Heuristic substantially dominates several reasonable baselines. \n\nThese baselines are extremely hand-crafted for the environment, which would detract if the point of the paper were to demonstrate their utility. But that is not the point: the point is that (1) there is a substantial delta between these and Heuristic, and (2) that they are so hand-crafted that I cannot think of a way in which more generic baselines with more sophisticated methods could reasonably be expected to do better. This means that there is demonstrably considerable room to improve.\n\nThe paper is well-written and easy to read, with useful figures.\n\nWeaknesses:\n\nIt is important to think critically about whether SymmToM provides a robust test for ToM. Intuitively, several things are challenging about this environment: the need to estimate the belief/knowledge states of others, coordination (generating mutually beneficial behaviors between agents -- as Heuristic does in a very nontrivial way), and long-range planning (collecting all these info pieces before going to the recharge bases.\n\nWith regard to the need to estimate the belief/knowledge states of others, one critique is that this is a drastically simplified parametrization of belief/knowledge. That is, belief/knowledge is not about embodied/spacial/actionable knowledge about the environment, but rather it is abstracted away into discrete info pieces and thus lacks real-world nuance (e.g. one might try to estimate the location of something and know roughly where it is, and roughly where others think it is, but not have an exact sense of either; or one might be attempting to estimate others' goals). It is thus a bit unclear just how much this is capturing in our intuitive, psychological notion of theory of mind.\n\nCoordination is a massive challenge in CTDE MARL. In a sense, the Heuristic baseline largely solves a coordination problem: with this sort of simple behavior, ToM estimation and long-term planning is seems relatively easy. What might be difficult is not necessarily ToM estimation but rather simply achieving this level of coordination between agents. Failing massive amounts of coordination, planning in this environment seems to be very challenging as well, easily being difficult for long-range planning algorithms simply because of the number of subgoals one needs to achieve in order to get the recharge reward.\n\nA few things (not necessarily in the scope of this paper) could help clarify this.\n\n(1) Perhaps easiest, a direct analysis of the baselines' capacity to estimate K, as well as a ceiling for K estimation, would be useful. If it turns out that the models are already estimating K well, then this is perhaps more a benchmark for other challenges, not ToM.\n(2) It would be helpful to see what humans do on this task. One would be to see how often humans, playing together for a while, converge to simple, effective cooperative behaviors such as Heuristic.\n(3) The other would be to see how well a human does when the other agents are not particularly coordinated. One possibility is that the amount of things needed to be kept track of in the higher a, c environments simply make for not particularly human-doable tasks.", "summary_of_the_paper": "This paper introduces SymmToM, an environment aimed at benchmarking agents' Theory of Mind (ToM) capabilities. In motivating the construction of this environment, it outlines criteria.\n\n- It first defines ToM agents in terms of knowledge/prediction of each agent's own hidden state,\n\n- It then defines \"Symmetric Theory of Mind\" environments as having certain properties: symmetric action space, imperfect information, observation of others, and information-seeking behavior (really, the task-relevance of it). This is motivated by attempts to move away from more traditional ToM situations, e.g. where one agent is a passive observer or agents have one of several different designated roles.\n\nWith this, it defines the environment, a simple grid environment with several modifiable parameters.\n\nIt then defines several reasonable baselines: an oracle (that knows info states of all agents but must learn what to do with this via MADDPG -- so, not necessarily an upper bound), an heuristic (consisting of a simple coordinated strategy between agents that is also not an upper bound, but represents decent coordinative behavior), and several hand-crafted agents that explicitly track knowledge estimates (these have a great deal of domain-specific architecture).\n\nIt then tests each of these baselines on several versions of the environment (varying the aforementioned parameters). In all but the simplest versions, the heuristic method dwarfs the performance of everything else (including the oracle), thereby demonstrating room to improve.", "summary_of_the_review": "In sum, the paper puts forth a compelling benchmark: one that is simple and well-motivated but appears to demonstrate a considerable delta between an heuristic \"upper bound\" (not necessarily actually the upper bound) and reasonable baselines. I feel that these merits outweigh the critique that this might not be isolating critical aspects of ToM capacity in people. As such, I think it would be worthwhile to get this to the broader community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "ZHRoz1SXOWd", "reviewer": "Reviewer_cEGn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThe paper introduces the concept of theory of mind well and does a good job at motivating the papers direction.\n\nThe proposed environment is well motivate dwith respect to the target of theory of mind. Although, I do think it's important to make sure to qualify the term theory of mind a bit more - as the original concept in psychology does include additional knowledge such as beliefs, desires, intentions and emotions. Most of which are not captured in this paper at all. I'd also really suggest to stay away from misleading terms like \"awareness\". E.g. I have trouble with the definition or model non-ToM. Theory of mind is about other agents not oneself. It's also not true that the agent is not \"aware\". It's just that he doesn't have the knowledge in the first place.\n\nMulti-agent settings typically suffer strongly from varied outcomes. It would be important to have more random seeds and also report measures of dispersion of run outcomes. Otherwise, I am not sure these results actually hold true in rigorous statistical testing.\n\nThe discussion of potential tests for ToM in 7.3 is interesting. It's not clear though why you don't just apply some of these, in order, to get good statistical data about the performance of trained agents besides accumulated reward. \n\nWhy did you choose MADDPG and RMADDPG?", "summary_of_the_paper": "The paper proposes a multi-agent environment to develop and test theory of mind capabilities for agents. The environment is one where all agents speak, listen to and move around. Agents share information and the goal for each agent is to get all the information and then release. The paper suggests some architecture that avchieve some improvement over agents without theory of mind capabilties. Ultimately though, the task is unsolved and posed as a research question\n", "summary_of_the_review": "The paper presents an interesting new challenge that could give rise to a number of new research ideas. The challenge is well motivated from the literature\n\nAuthors explore the new task with existing methods with some obvious expansions.\n\nThe proposed baselines should be explored more and specific tests outside of reward should be part of actualy analysis\n\nPRO\n* paper is written well\n* the challenge is well described  \n* paper presents some sensible baselines\n\nCONS\n* no technical contribution\n* potentially shaky results (not clear if these results are significant)\n* evaluation relies on reward only. other evaluations are discussed but not really explored in detail\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VeyDIduxKCC", "reviewer": "Reviewer_VGt1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The problem of imbuing systems with a theory of mind is an interesting one and one that is getting attention in multiple areas in AI. Many works argue for not only modeling the beliefs and knowledge of other agents but also argue that in many scenarios where the agent is interacting with humans, it would need to explicitly take into account what the human expects from the agents (the authors could check works done in explanation in deterministic planning setting for some related work [1]). While the general direction is interesting, I don’t think the paper is ready for publication as the current paper doesn’t make a convincing argument for the novelty or significance of the current results.\n\nUnfortunately, the current version of the paper doesn’t contain a related work section. This is a particularly glaring omission for a paper that is looking at as widely studied a problem as modeling of other agents for multi-agent decision-making settings. Apart from works that frame such modeling of other agents as building theories of mind, which generally happens when there is a human in the setting or if the work is inspired by the psychological phenomena, many (if not most) multi-agent planning itself allows some such form of modeling (even ignoring all the various game-theoretic formulations). Not to mention, there is a pretty mature and well-investigated sub-area of reasoning and planning called epistemic reasoning that has looked at the problem of modeling beliefs and knowledge of other agents for a long time (authors can check [2] for a useful starting point).\n\nA related work section helps the reader compare the contributions of a specific paper against all the previous works that have been done in related areas. For example, in the paper, there was no discussion on how the current problem being proposed compares to multi-agent planning frameworks like DEC-POMDPs [3] or I-POMDPS [4]. Particularly since one of the baselines used in the paper is specifically a solution method for DEC-POMDPs. To the best of my understanding, the specific scenario discussed in the paper seems to be a special case of a DEC-MDP if you allow the facts that the agent collects to be modeled as part of the state. If that is not the case, then the paper should explain why it is not so.\n\nThis brings me to the specific problem being studied in the paper. Why is this problem of particular interest? Does it correspond to any particular practical problems? The methods introduced here leverage specifics of the problem and as such, the usefulness of methods are also limited by the utility of the setting. Additionally, the paper doesn’t provide any complexity analysis of this particular problem type or an optimal solution. It was also not clear to me why forgetting information is particularly important for information-seeking behavior. If a given agent has partial observability, the task is the infinite horizon and its utility depends on the other agent’s state and actions, you could always create a setting where the optimal strategy for the agent involves seeking out the information about other agents' state.\n\nAlso, the beginning of the paper makes some connections to human-agent interaction, if this is one of the problems the authors are interested in, then they are generally incompatible with any centralized planning mechanisms. Since in most cases you can’t plan for the human. It might make more sense for the authors to base their framework on decentralized planning frameworks like I-POMDPs or some game-theoretic formulation.\n\n[1] Sreedharan, Sarath, Tathagata Chakraborti, and Subbarao Kambhampati. \"Foundations of explanations as model reconciliation.\" Artificial Intelligence 301 (2021): 103558.\n\n[2] Fagin, Ronald, et al. Reasoning about knowledge. MIT press, 2003.\n\n[3] Oliehoek, Frans A., and Christopher Amato. A concise introduction to decentralized POMDPs. Springer, 2016.\n\n[4] Gmytrasiewicz, Piotr J., and Prashant Doshi. \"A framework for sequential planning in multi-agent settings.\" Journal of Artificial Intelligence Research 24 (2005): 49-79.", "summary_of_the_paper": "The paper focuses on establishing the framework of symmetric TOM. Paper identifies such decision-making settings as being characterized by four different properties, namely, symmetric action space, imperfect information, observation of others, and information-seeking behavior. The paper then introduces a sample task that instantiates the symmetric TOM setting and then formulates some solution approaches for the setting that builds on an earlier multi-agent actor-critic framework, with an unmodified version being the baseline. The proposed method, particularly the GreedyEncounter variant, seems to perform better than some of the other baselines, but not as well as the heuristic version.", "summary_of_the_review": "As of right now I won't argue for accepting this paper, as the paper doesn’t make a convincing argument for the novelty or significance of the current results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "P9tFgi63Qfx", "reviewer": "Reviewer_n7Fh", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work considers a broader range of tasks by removing a pre-defined role of the agent. From the symmetric setting, every agent can play all roles without being biased towards a specific role.\n\nEven though the paper has merit, the reviewer has the following concerns. \n1)  The paper adopts the partially observable Markov decision process. But in section 7.1, the observation space is defined by a set that consists of the position of **all** agents, **all** recharge bases, **every** agent’s first-hand information, etc. It does not seem to be a “partial” observable setting. In addition, the assumption that the agent has full vision seems not realistic in a large grid world. How can every agent know the initial knowledge of the other agents? \n\n2) Recharge bases seem to be important in the proposed environment. However, the process that happened in the recharge bases is not fully explained. Why all the information gathered are removed? It would be better the information pieces are removed depending on the importance, or time.\n\n3) The paper must include an exact definition of reward. The reward function is not provided in the paper. \n\n4) The experimental results in Table 1 were written with only 3 runs, which is a very insufficient number of trials to explain the claim. In addition, it is not a good method to judge the performance of a specific algorithm through the average of the results performed under different experimental conditions.\n\n5) The values in Table 1 do not have enough explanations. Does it represent a ‘per agent’ reward?\n\n6) The paper should be reorganized. For example, Fig. 2 does not have specific captions(a/b/c), so it is hard to follow. In addition, Fig. 3 has 4 images with different sizes and #1(line 3 in the caption) is not explained.\n\n7) No parameter tuning and hyperparameter setting methods for experiments", "summary_of_the_paper": "This paper suggests a fully symmetric multi-agent environment based on the Theory of Mind, SymmToM. In the SymmTom, agents can remember its information, infer behaviors of other agents, and estimate the probability of others. Interactions between agents are modeled by a partially observable Markov decision process. Each agent decides an action(move, speak) upon its state which consists of partial observations. The authors admit that the proposed SymmTom cannot be completely solved. They adopt MADDPG for performance evaluations.", "summary_of_the_review": "The multi-agent reinforcement learning with the Theory of Mind is an interesting topic to be discussed. The proposed SymmTom aims at the researchers in the Theory of Mind and MARL field. But overall problem setups and experimental results are not described enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OjlZn6IpPmD", "reviewer": "Reviewer_sDZt", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "=====Strengths=====\n\n1. Testing RL agents or any kinds of machine agents' ToM ability is an important and yet understudied problem. When we evaluate the success of multi-agent policies, it is important to test the true social intelligence that comes with the policies. Naturally, that includes ToM reasoning. So this is certainly a welcomed contribution in the area of multi-agent RL in my opinion.\n\n2. The explicit modeling of agents' knowledge is an interesting extension to MADDPG. It makes sense to use domain knowledge in some cases to improve the RL training if there is a discussion on the limit or possible improvement.\n\n3. The two kinds of tests proposed in the discussion are very interesting and are to some extent the most important aspect of this study -- evaluating and analyzing the true ToM ability of agents trained in SymmToM that goes beyond reporting a single reward value.\n\n=====Weaknesses=====\n\n1. The literature is insufficient. There has been a rich history of computational modeling of ToM (e.g., [1,2,3,4]). There have also been multiagent communication and cooperation tasks / environments proposed before (e.g., the particle environment proposed in the MADDPG work, and [5,6]). There should be a more thorough discussion and comparison.\n\n2. It is also unclear to me why it is necessary to have a symmetric setting. This setting is emphasized in the title and in the main text, but I have not seen the motivation for it.\n\n3.  I do not see a systematic and quantitative evaluation of the two kinds of tests proposed in the discussion section. Am I missing something here? Is it more of a proposal than a completed evaluation?\n\n4. There should be a discussion on how general and scalable the explicit modeling of knowledge is as an extension to MADDPG or similar multi-agent RL approaches.\n\nReferences:\n\n[1]  T. D. Ullman, C. L. Baker, O. Macindoe, O. Evans, N. D. Goodman and J. B. Tenenbaum (2010), Help or hinder: Bayesian models of social goal inference. In NeurIPS.\n\n[2]  Netanyahu, A., Shu, T., Katz, B., Barbu, A., & Tenenbaum, J. B. (2021). PHASE: PHysically-grounded Abstract Social Events for Machine Social Perception. In AAAI.\n\n[3] Zhu, H., Neubig, G., & Bisk, Y. (2021). Few-shot language coordination by modeling theory of mind. In ICML.\n\n[4] Shu, T., Bhandwaldar, A., Gan, C., Smith, K. A., Liu, S., Gutfreund, D., ... & Ullman, T. D. (2021). AGENT: A Benchmark for Core Psychological Reasoning. In ICML.\n\n[5] Das, A., Gervet, T., Romoff, J., Batra, D., Parikh, D., Rabbat, M., & Pineau, J. (2019). Tarmac: Targeted multi-agent communication. In ICML.\n\n[6] Jain, U., Weihs, L., Kolve, E., Rastegari, M., Lazebnik, S., Farhadi, A., ... & Kembhavi, A. (2019). Two body problem: Collaborative visual task completion. In CVPR.\n", "summary_of_the_paper": "This paper presents a multi-agent environment and task, termed SymmToM, for analyzing machine theory of mind emerged from multi-agent RL training. In SymmToM, agents can see and act in a 2D grid world as well as share information about the world state through communication. Crucially, all agents have the same physical characteristics, hence, \"symmetric.\" In this task, agents gain rewards by hearing or sharing novel knowledge of the 2D grid world, so that the optimal policy would be cooperatively seeking and sharing information among the agents. The proposed approach extends MADDPG to explicitly model the knowledge of each agent and how it would be affected by the shared information. The experimental results show that this extension improves over the generic RNN based extension to MADDPG (i.e., RMADDPG), but is still not performing as well as the simple heuristics-based baseline.", "summary_of_the_review": "I think this paper has a lot of potentials but is incomplete in its current form due to 1) a lack of interactive review, 2) insufficient evaluation (missing systematic evaluation of the proposed tests), and 3) a lack of discussion of how scalable and generalizable SymmToM and the approach are. Please see specific concerns in my main review.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a theory of mind benchmark. 

This paper certainly improved during the discussion period. However, the paper is still incomplete. The authors are working related work (paper was not updated in this regard). The experiments still need significant work. The original submission used only 3 runs (very, very low). Although the authors bumped up the # of runs, the learning curves in the appendix feature very large and overlapping error bars, and the main table of results presented in the paper contains no measures of certainty---those a reported in a separate table in the appendix making comparison tedious. The paper has a fairly informal approach to dealing with hyper-parameters that should be discussed and improved. The reviewers pointed out (in their reviews and dialog with the authors) several ways the experiments should be extended. 

The contribution of the benchmark is evaluated primarily via experiments; much work needs to be done before acceptance.
Decision: Reject