Social Interactions as Recursive MDPs
Authors: Ravi Tejwani
Yen-Ling Kuo
Tianmin Shu
Boris Katz
Andrei Barbu
Venue: CoRL2021 Poster (2021)

Abstract: While machines and robots must interact with humans, providing them with social skills has been a largely overlooked topic. This is mostly a consequence of the fact that tasks such as navigation, command following, and even game playing are well-defined, while social reasoning still mostly remains a pre-theoretic problem. We demonstrate how social interactions can be effectively incorporated into MDPs by reasoning recursively about the goals of other agents. In essence, our method extends the reward function to include a combination of physical goals (something agents want to accomplish in the configuration space, a traditional MDP) and social goals (something agents want to accomplish relative to the goals of other agents). Our Social MDPs allow specifying reward functions in terms of the estimated reward functions of other agents, modeling interactions such as helping or hindering another agent (by maximizing or minimizing the other agent's reward) while balancing this with the actual physical goals of each agent. Our formulation allows for an arbitrary function of another agent's estimated reward structure and physical goals, enabling more complex behaviors such as politely hindering another agent or aggressively helping them. Extending Social MDPs in the same manner as I-POMDPs extension would enable interactions such as convincing another agent that something is true. To what extent the Social MDPs presented here and their potential Social POMDPs variant account for all possible social interactions is unknown, but having a precise mathematical model to guide questions about social interactions has both practical value (we demonstrate how to make zero-shot social inferences and one could imagine chatbots and robots guided by Social MDPs) and theoretical value by bringing the tools of MDP that have so successfully organized research around navigation to hopefully shed light on what social interactions really are given their extreme importance to human well-being and human civilization.

Social Interactions as Recursive MDPs
Ravi Tejwani", Yen-Ling Kuo", Tianmin Shu, Boris Katz, Andrei Barbu
MIT CSAIL & CBMM (tejwanir, ylkuo, tshu, boris, abarbu | @ @mit.edu
Abstract: While machines and robots must interact with humans, providing them with social skills has been a largely overlooked topic. This is mostly consequence of the fact that tasks such as navigation, command following, and even game playing are well-defined, while social reasoning still mostly remains pre-theoretic problem. We demonstrate how social interactions can be effectively incorporated into MDPs (Markov decision processes) by reasoning recursively about the goals of other agents. In essence, our method extends the reward function to include combination of physical goals (something agents want accomplish in the configuration space, a traditional MDP) and social goals (something agents want accomplish relative to the goals of other agents). Our Social MDPs allow specifying reward functions in terms of the estimated reward functions of other agents, modeling interactions such helping hindering another agent (by maximizing or minimizing the other agent's ' reward) while balancing this with the actual physical goals of each agent. Our formulation allows for an arbitrary function of another agent's 's estimated reward structure and physical goals, enabling more complex behaviors such as politely hindering another agent or aggressively helping them. Extending Social MDPs in the same manner as I-POMDPs (Interactive- partially observed Markov decision processes) extension would enable interactions such as convincing another agent that something is true. To what extent the Social MDPs presented here and their potential Social POMDPs variant account for all possible social interactions is unknown, but having a precise mathematical model to guide questions about social interactions has both practical value (we demonstrate how to make zero-shot social inferences and one could imagine chatbots and robots guided by Social MDPs) and theoretical value by bringing the tools of MDP that have successfully organized research around navigation to shed light on what social interactions really are given their extreme importance to human well-being and human civilization.
Introduction
Progress on modeling social interactions and giving machines social goals, such as being particularly nice to a user, is significantly hampered by the lack of theoretical models which characterize what social interactions are. While microsociology has uncovered common structures in social interactions [1] a computational model is still elusive. Until not too long ago, this was also the state of robot navigation and sensing which was revolutionized by extending MDPs [2] POMDPs [3]. Defining the problem clearly allowed us as a field to understand what we can model and how to do so. Until we take this same step for social interactions, they will remain on shaky ground despite their importance to virtually every interaction humans engage in.
We introduce an extension of MDPs, which we term Social MDPs. In the process, we make several assumptions. First, that agents have both physical goals (c.g., bring the red key home) and social goals (e.g.. prevent John from getting his yellow key), and that their overall reward structure is an arbitrary combination of the two, potentially accompanied by other terms. Physical goals are precisely what MDPs can already express, a function of points in a configuration space. Social goals are a function of the estimate of the reward structure of another agent. For example, reward that hinders another agent is a negative function of the estimated reward of that agent. Complicating matters is the fact that social rewards like beliefs can be recursive: an agent may want to help another agent help them. To model this, Social MDPs are recursive up to a bounded depth, much like interactive POMDPs (4), I-POMMPs. Unlike I-POMDPS, Social MDPs are not recursive in terms of agent's beliefs about the
'quua contribution.
5th Conference on Robot Learning (CoRI. 2021), London, UK.

---

Algorithm The algorithm to compute so- cial policy v/g for agent at level and time t. We use the estimated social policy v v at previous time step update the estimated physical and social goal as described Sec- tion 3.3.1. At O, we assume P(g) and P(X)L are from uniform distributions. This algorithm is called at all recursion steps 3 to estimate social policy for the other agent j E J. The estimated goals and poli- cies are used to compute the rewards and Q values for selecting the actions.
Solve vf using:
Level 2
X1e (ground truth)
2 c1.2 03
(estimate agent
Level
Solve $2" using:
R2 X21
97 X112 (estimate agent 1)
Require: 1,8", a'> Xijs
Snivve 01 using:
Level
if = 0 then
91
solve MDP for agent i
An example of recursively solving Social MDP for the yellow robot at level 2 in a two-agent interaction scenario. We denote the yellow robot as agent and the red robot as agent At level 2, the yellow robot estimates the red robot's goals (hoth physical 02 and social ) and social policy by assuming the red robot is running a level Social MDP. Solving the social policy 2.2 of the red robot at level requires the red robot estimate the yellow robot's ' goals and policy by assuming the yellow robot is running a level 0 Social MDP, i.c., a regular MDP, so we can drop estimation X12 here. All these estimates are in agent belief space and are updated at every time step.
Figure 1:
else
for all Xjs : "93
do
compute
P(G 167
P 1 (111-1)
3 Jo end for
(s a's sill
OssKye" ,9 ,3
compute (5", at, xi)
compute Qi(s', aJ 9:)
.i + argmax,, Q
end if
state of the world. Instead, Social MDPs are recursive in terms of the rewards of the agents. This makes Social MDPs and I-POMDPs orthogonal and complementary. Social MDPs are specifically formulated not interfere with the standard extension from MDPs to POMDPs, making it possible to include partial observability. While we do not develop a joint Social I-POMDP here, this is a reasonable extension which would cover far more of the space of social interactions, although one that is computationally challenging.
Our contributions are: (I) formulating Social MDPs where an agent's reward function is an arbitrary function of the recursive estimate of another agent's reward and a physical goal, (2) implementation where that function is a linear transformation. which captures many notions of helping and hindering, (3) demonstrating that the model performs zero-shot social reasoning in agreement with human subjects experiment, and (4) examples of the practical utility of recursive social reasoning, In an anonymized online appendix² we fully enumerate all possible scenarios predicted by our model given an environment simple enough to allow doing so, demonstrating that it captures a diverse set of social behaviors. We also provide videos of the behavior of our model in all these scenarios.
2 Related Work
Modeling other agents In order interact with other agents effectively, an agent must be able to reason about the goals, preferences, and beliefs of other agents [5]. Theory-based models for social goal attribution [6, 7, 8, 9, 10], Bayesian inverse planning infer an agent's 's goal given the observations of their behaviors [1 1, 12], and learning the reward functions of other agents [13] have been explored. Prior research also tried to recognize social interactions such as waving and hugging in videos where people are involved in group activities [14, 15, 16). These methods generally involve two separate stages [17]: social perception stage and coordination or collaboration stage where agents interact. In contrast, Social MDPs constantly reevaluate the goals of other agents enabling them to adapt to changes in the plans of other agents. Social MDPs also allow for enumerating social situations by formally defining the space of what social interactions are, opening the doors to more theoretical approach to social interactions. Game theory [18, 19] considers altruistic and spiteful behavior through linear combinations of payoffs, similarly to what we consider here although such
"See https://sociallmmd ind.gittubb.

---

models are limited to level reasoning and to scenarios where the goals are known prior rather than estimated on the fly as they are in Social MDPs and in practical robotic applications.
Simulating social interactions Heider and Simmel [20] simulated agent trajectories to study social perceptions through a set of animations involving the movements of geometrical figures. Simulating agent behaviors in physics engines had been explored to collect datasets in fully observable [21, 22] and partially observable environments [23, 17]. The collected datasets are used to study social perception or build machine learning models that can recognize agents' goals. These frameworks assume that each agent has either a physical goal or social goal. Here we consider a more general scenario where agents have both a physical goal and social goal and the overall behavior is blend of the two. This is more practical setting as when one decides to help another agent one does not abandon every other concern and physical care. Our formulation allows for an arbitrary function of another agent's reward recognizing for complex social interactions. We explore only subset of the full power of Social MDPs here by considering only linear functions.
Learning to interact with other agents Interactive POMDPs [24, 25, 26] (I-POMDPs) are exten- sions of POMDPs that recursively model the beliefs of other agents. Social MDP and I-POMDPs are orthogonal. Social MDPs allow agents reason recursively about other agents' reward functions while I-POMDPs allow agents to reason recursively about other agent's 's beliefs about the state of the world. The two could in principle be combined, but while Social MDPs require solving modest number of additional nested MDPs, I-POMDPs require significantly nested inference, and when the two are combined the problem quickly becomes intractable. Xie al. [27] propose different type of approach that does not require nested inference: learning a -iw-eiinniionll representation of another agent's 's strategy. This approach allows an agent avoid another agent or to manipulate another agent into some mutually-beneficio behavior. Social MDPs, on the other hand, allow building the strategy of another agent directly into the reward function of an agent, enabling behaviors such as helping or hindering regardless of what the other agent is trying to achieve. Moreover, Social MDPs are zero-shot, while this prior approach not. From the point of view of generalization and sample-effcient robotics, a zero-shot approach is preferable; in addition, it opens new doors for more theoretical understanding of social interactions. We could combine Social MDPs with this prior work to build in latent representations of strategies into reward functions [28, 29] creating more efficient approximations of Social MDPs.
3 Social MDPs
Social MDPs are recursive MDPs (Markov decision process) with nested estimates of other agent's goals. They are inspired by hierarchical models of games [30] and nested MDP that reason about the beliefs of other agents [31, 32, 33]. Fig. shows an example of recursively estimating the other agent's goals and policy in two-agent scenario. Like other nested models, c.g I-POMDPs, Social MDPs have the notion of a level. A level 0 Social MDP is simply an MDP: agents reason about the map state. A level 1 Social MDP enables each agent to reason about the physical goals of other agents (those other agents are treated like level O agents). A level 2 Social MDP enables each agent to reason about the level 1 social goals of other agents. To perform this nested inference, agents must have access to another agents' physical and social goals. These goals are estimated by solving Social MDPs recursively every level.
A level 0 agent can take physical actions, but cannot reason socially. A level I agent can take actions relative to another agent's physical goals; such actions include helping, hindering, stealing, etc. A level 2 agent can take actions relative to another agent's 'ss social and physical goals; such actions include avoiding an attempt to be hindered, recognizing that help is needed, joining in to help together. Levels deeper than 2 continue to describe meaningful interactions although we do not consider them here. It is unclear what level of recursion is required before agents exceed the social reasoning capacities of humans.
3.1 Assumptions
As we are in an MDP setting, all physical states are fully observable to all agents. Note however that the goals are not available to other agents. In other words, agents can observe one another at any distance and regardless of any obstacles but they cannot know what another agent wants (either physically or socially) by reading that agent's 's mind. Agents must infer the physical and social goals, if any, of other agents from their actions. Agents reason completely independently of one another.
3

---

In this paper, we consider only pairwise Social MDPs; indeed, all our experiments involve settings where only two agents are present. N-way Social MDPs that consider social interactions between multiple agents at the same time are extensions of pairwise MDP and scale linearly at every level. Computationally however, n n-way Social MDPs, as with any such model, scale exponentially in n.
As with many multiagent MDP settings, the experiments performed here assume that agents are optimal planners. This is not an inherent limitation of Social MDPs, but relaxing this assumption makes estimating the other agents' goals and rewards far more difficult.
3.2 Formal definition of Social MDPs
A Social MDP for agent i with respect to all agents J consists of an arity (here we formulate the pairwise case) and a maximum level, I, and is defined as:
M
xw.. R1,
(1)
where S is set of states in the environment where s E S; A, is the set joint moves of all agents in J. a, is an action for agent i; T' is the probability distribution of going from state s E S to next state s' E S given actions of all agents in J: (s' s, a.): XiJ agent i's social goal toward every other agent in J. For convenience, XiJ is shorthand for U JEJ
Xiji 9: is agent i's physical
goal: R is the I-th level reward function for agent i based on its estimate of other agents' rewards; and y is discount factor, y E (0, 1).
Reward Each agent has its own physical goal, e.g., going landmark, well social goal, e.g..
helping or hindering other agents. What enables Social MDPs to go beyond regular MDPs is the recursive nature of the reward function which can be written in terms of the estimated rewards of other agents. The immediate reward of an agent at level is computed as follows:
(J,.,))) = (s, ai Di)+ + Σ
Xsy(R) (s, a,, Xis.
and "1' c(a;)
(2)
JEJ
where r(.) is the static reward given the agent's 's own physical goal 9r. Fy (.) is the estimated reward for agent j from agent i's point of view assuming agent j is level I agent, c(-) is the cost for taking an action. For negative levels, the reward is defined to be zero.
Xij is the social goal, it transforms the reward of another agent into goal that is part of the reward of the target agent i. In this paper, we instantiate the model with a linear transformation, so Xij is simply reweighting of the estimated reward of the other agent. If it is negative value, the target agent will attempt to minimize the reward of another agent, i.e. hindering. A positive value corresponds to helping. Social goals can be eliminated entirely by setting this weight to zero
In order to estimate another agent's 's reward function, one needs to estimate that agent's physical and V social goals. We use Xjj and " to denote the estimated social and physical goals. The superscript i, i indicates agent at level is making the estimations.
We describe how to estimate the social and physical goals in Section 3.3.1.
3.3 Planning for Social MDPs
Analogous to MDPs, the Q function of Social MDPs is the sum of immediate reward and the expected value in the future.
(' XJ,,,9)) R(s, az XiJ, + Σ T(s,a,,,)VVle (u,,)
(3)
e'ES
Since agent is interacting with other agents j E J, it needs to estimate what actions other agents are likely to take in order compute its state-action value. Social MDPs take the expectation over the estimated goals and actions of agent to compute (s''s, ( Xi).
vo (ooo))))))))))) = max <EEA; F 253 at 1Q (oxe)
(4)
max <EE:;
Σ Σ
of
JEM of C. 336
cotinate plo
coimats socid pel (B4
cxtiut extal palay (B4 7
(Ec. 61

---

When solving agent i's MDP at level I, the estimated social and physical goals are further used to update the other agent j's social policy to the actions agent j may take. We denote the estimated social policy for agent j at reasoning level (-1 as 0);51 S A, x Xxj X - [0, 1]. Algorithm I summarizes the steps to compute the state-action values and select optimal actions for any level I at time step 1. We first update the probability of the estimated goals of other agents using the observed state and the estimated policy from the previous time step. The updated probability of goals are used to update the policy of other agents and compute the reward and Q function of the target agent. The recursion happens at estimating the social policies of other agent lower level.
rid
3.3.1 Updating social and physical goals of other agents
agent's estimate of another agent's social and physical goals at time step and level I can be updated based on the actions performed by the agents. At time step & = 0, we use uniform distributions for social and physical goals.
The social goal, estimated at time step t. is updated after actions taken by all agents at the previous time step. This update is similar to the belief update in the POMDP framework but based on the estimated social policy of the other agent j:
PGG |s"=",a] "a x P(X
Σ P(a) 2
18
.95 - x T( 's')
(5)
The physical goal gj of agent j is estimated by as follows, similar Shu al. [21] but marginalized over the estimated social goal as the agent is estimating the social goal at the same time.
P(s
P(s2:t-1 the
Xji x) P(T)" P(X
(6)
3.3.2 Estimating social policies of other agents
The (-level social policy T.d of the agent j is predicted by i using the Q-function at level 1-1:
Jy (s, aJ, vid x = Softmax(Q) (s, aJ,
This is a softmax policy where we use a temperature parameter to control how much the agent follows the greedy actions. As shown in Eq. 4, in order use agent j's Q function at level 1-1, requires to compute agent i's Q function at level 1-2, and so on. This involves solving Social MDPs recursively levels 0, 0,
3.4 Time complexity
The time complexity of solving Social MDP at level 0 is the same as that of solving MDP. At level 1, an MDP must be solved for every agent independently in order to compute the likely physical goals of every other agent. Assume that the number of models considered for each pair of agents at each level is bounded by a number M (based on the number of social and physical goals to consider). Solving Social MDP level I requires solving O(M(A 1)2() MDPs, where A is the number of agents. Social MDPs form tree with branching factor A - 1 as every agent must compute the pairwise social goal of every other agent until level 0 where the tree bottoms out. There are many potential speedups that can alleviate this runtime to allow for efficient inference even in the face of many agents. For example, a distance horizon could be used where far away agents could simply be considered non- non-interacting. Similar to Netanyahu et al. [23], it is also possible to speed up the algorithm by amortized inference over goals and relations by training neural net to recognize goals and relations as initial guesses and refine them through probabilistic inference.
4 Results
We apply the Social MDP framework to a multi-agent grid world inspired by previous studies on social perceptions [12, 6, 34]. The 10 10 world consists two agents, a yellow robot and red robot, two physical landmarks, flower and tree, and two objects, yellow watering can and red watering can. The yellow agent has a low cost for moving the yellow watering can, while has a high cost for moving the red watering can. Robots can have a physical goal of moving the watering can to target
5

---

Level
Level 2
(a) Scenario 28: Red wants to help yellow yeleww 2)
Lovel 1
Level
(b) Scenario 30: Red wants to hinder yellow (Xrol-yellow
Two examples of zero-shot social interactions.. The Social MDP gives the robots the ability to understand and predict relationships, thereby making far more efficient actions. The yellow robot wants to water the tree. Moving the yellow watering is easy for the yellow robot, while moving the red is hard for the yellow robot. The yellow robot performs inference understand what the red robot doing. With level Social MDP, the yellow robot assumes that the red robot has a physical goal, but not social goal. With level Social MDP, the yellow robot assumes that the red robot has both physical and social goal, then recursively estimates the social goal of the red robot (which is in turn modeled as level Social MDP).
Figure 2:
(a) At level the yellow robot follows the red one around. does not understand that the red robot trying help. The red robot correctly executes social goal helping the yellow robot by moving its watering can toward the tree. At level 2. the yellow robot recognizes that red is helping. then estimates where its future trajectory will take it, and efficiently goes to the intercept point accepting red's help.
(b) At level yellow does infer that red wants hinder it. As such, attempts to move the yellow and repeatedly fails, entering local minima where the yellow is the one casiest move without realizing that the red robot will forever prevent this. At level 2, the yellow robot recognizes that the red robot attempting to hinder it, gives up on the yellow can, and makes a globally-optimal move of using the garder-to-move red can instead.
plant. Robots can have a social goal of helping or hindering to different degrees. In the grid world, agents can move in four directions (left, right, up. down) or choose not to move.
98 different experiment scenarios are systematically created in this grid world. Each scenario has agents having either the same physical goal or different physical goals and one of 7 different scaling factors on each of their social goals (-2, -1, -0.5, 0, O.5, 1, 2) (2 * * 7 = 98 scenarios). indicates that the social goal is weighted much more than the physical goal, and agent wants to maximize the other agent's 's goal. Similarly for -2, except that an agent wants to minimize another agent's goal. At 1, agents weigh their social goals equally with their own physical goals. At 0.5, they put twice as much weight on their physical goals as their social goals. These agents are less likely to help, particularly if helping will cost more time or energy than carrying out the physical goal. Finally, either agent can have the factor set to zero; these agents only have physical goal and social goal. The fact that we can enumerate all possible social interactions, as predicted by our model, in given scenario is an important feature missing from alternative representations. All 98 experiment scenarios correspond to reasonable interactions between agents. The degree to which this is true in more complex environments and the degree to which systematically unfolding the model in
'Interactions for the experimental scenarios can be viewed at https://sociaa http://soocaalll.....a..o mdp. .ip..ii thub. scenarios

---

(left) Weight of social goals
(right) Weight physical goals
Figure 3: Twelve human subjects, and our model, the Social MDP, watched and scored 196 videos at different snapshots. These videos consist of 98 scenarios where robots reason at either level or level 2 (presented to the users in randomized order). The straight black line represents the best lincar fit to the data, and the light blue band around the line shows the uncertainty in the lincar fit. The light blue band represents a 95% confidence interval. (left) Models and humans were asked predict how social the agents interaction (was it positive or negative). Non-social seltings have a weight of O. while adversarial settings have a social weight of -2, overwhelming the physical goal of any agent. Humans and machines predict similar social goals both in terms of value and magnitude. (right) Models and humans were asked to predict weight factor on the physical goal, how much does this agent care about its physical goal. At O, the physical goal is ignored. At 1, is weighted equally with social goal also set at 1. Human and model scores are again highly correlated. Our model able to effectively generate trajectories that humans recognize as being social interactions. is also able to predict the type of social interaction that humans helieve occurred.
and the valence of the
Social MDP (ours)
Inverse Planning Cue-based
Social Goal Physical Goal
0.83
0.76
0.19
0.74
0.64
0.06
Table I: The cocfficient of correlation with 95% confidence interval between human and machine judgements for all the 98 experiment scenarios (each scenario has agents having either the same or different physical goals along with one of 7 scaling factors on each of their social goals (-2,-1, -0.5, 0, 0.5. 1, 2)). Refer to Appendix for detailed results for each scenario. We provide two baselines and our own approach. The cue-based model is described in Shu et al. [21]. The inverse planning model is described in Ullman et al. [12]. Social MDPs produce better alignment with ground truth than other models and do not require training like the cue-based model.
more complex environments always results in what humans would describe as social interactions is an important topic for future work.
Each agent's 's reward for reaching its physical goal is based on that agent's geodesic distance from the goal after taking an action [12]. This physical reward function is parameterized by p and 8 that determines the scale and shape of the reward: (8 a, (i) = max (p (1 - distance(s, 0, (0)) O). We set the cost, C, of an action a. to 1 for grid moves and 0.1 staying in place while p and were set to 1. 1.25 and 5, respectively. The discount factor, 7, was set to 0.99.
Two of the scenarios selected for our experiment are shown in Fig. 2. We used the Social MDP to select actions for the yellow agent which has a physical goal, watering the flower tree, while interacting with the red agent. The red agent had a physical goal, watering the tree, and a varying social goal. At every time step, the yellow agent estimates the physical and social goal of the red agent, depending on the Social MDP level. At deeper levels, the agents behave more optimally and more socially.
To quantitatively establish the quality of the social inferences made by the Social MDPs, we compare human judgements of 12 subjects against those of two baseline models: inverse planning [12] and a recent cue-based model [21]. Refer to Table 2 and Table 3 in the appendix for detailed results for each scenario. Humans and models had to estimate the physical and social goals of agents in these environments when the agents were acting both as level one agents (unaware that the other agents are also social) and as level two agents (who could account for the fact that the other agents are social). In Fig. 3 we show the raw judgements of humans and of our models, along with best linear fit. The performance of models against human judgements, was measured through correlation coefficient at 95% confidence level, for social goal estimation (r=0.s 0.89 for the Social MDP vs. r= 0.81 for the Inverse Planning model vs. r= 0.23 for the Cue-based model) and physical goal estimation = 0.78 for the Social MDP vs. r 0.72 for the Inverse Planning model vs. 0.08 for the Cue-based model).
7

---

Scenario 1
Scenario 15
Scenaria
Scenario
Scenario 30
SOccal cone netr seteration Phyytia Coal sec Ohoed 23
(level
Step
Figure 4: deep dive into how humans and each model interpret the five experiment scenarios (refer Appendix for results all experiment scenarios) both levels cach time step (in red Human scores, blue our Social MDP scores, in green Inverse planning [12]. in purple the cuc-based model [21], and in dotted the ground truth). The goal of each model is to interpret how one agent perceives another. (lop) At level one. agent has belief over the physical goal of another agent. Humans and models predict what this belief is other agent heading toward tree the flower). Note that all models perform rather well and follow human judgements. (bottom) At level two, an agent has a belicf over the physical and social goals of another agent. Humans and models predict what the belief' of the agents about the social goals of other agents. In other words, what degree does this agent think that the other agent hindering helping them. Here model fits human data much better because of its recursive nature. At deeper levels, our model capahle of capturing social interactions and social inferences that other models cannot. Other models are confused, and so predict that there is very weak or non-existent social goal in most cases while our model follows human judgements.
(the degree to which the agent believes
Our model performs considerably better than other models. This is even more evident in the deep dive shown in Fig. 4. For level one agents, agents that are social but that assume that other agents are not social, all models agreed with human judgements. Yet, for level two agents, agents that are social and can assume that other agents are also social, our models are far better aligned with human judgements. Prior work could capture a far smaller space of social interactions than the Social MDPs craft here.
Conclusion
Social MDPs are first step toward theory of social interactions that fits within the established frameworks we have in robotics. They can perform zero-shot social recognition and planning for diverse situations. The fact that MDPs can be extended in natural way that is also computationally tractable to account for many social interactions by nesting inference and allowing models to take arbitrary functions of the estimated rewards of other agents has not been noted before. Our experiments clearly show that Social MDPs are superior to prior models and account for more social interactions.
In this work, we have only begun to explore what Social MDPs can represent. The environment we consider is very simple, yet, the same time, more than enough differentiate Social MDPs from other models. So far, we have unrolled Social MDPs only two levels; what exists at deeper levels is still unclear. likely that humans do not perform deeply-nested recursive reasoning carry out social interactions, although, what the cutoff is, and if Social MDPs are close enough to human's 's mental model to allow for measuring that cutoff is unknown.
We would like see in the future that any MDP-based system be augmented be social by a straightforward extension with Social MDPs. Much like virtually any approach can be easily augmented to partially-observed environments using POMDPs. Social MDPs and POMDPs compatible, exploring their combinations and the implications of partial observability for social interactions remains future work.

---

Acknowledgments
This work was supported by the Center for Brains, Minds and Machines, NSF STC award 1231216. the MIT CSAIL Systems that Learn Initiative, the CBMMM-Seemens Graduate Fellowship, the MIT- IBM Watson AI Lab, the DARPA Artificial Social Intelligence for Successful Teams (ASIST) program, the United States Air Force Research Laboratory and United States Air Force Artificial Intelligence Accelerator under Cooperative Agreement Number FA8750-19-2-1000 and Award Number N00014- 20-1-2643. The views and conclusions contained in this document are those of the authors and should not be interpreted representing the official policies, either expressed or implied, of the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. We would like thank the members of InfoLab, particularly Bennett Stankovits and Dylan Sleeper, for helping in data collection and environment setup.
and the Office
of Naval Research under Award Number N00014-20-1-40
References
[1] J. Scheff. Microsociology: Discourse, emotion, and social structure. University of Chicago Press, 1990.
[2] R. Bellman. A markovian decision process. Journal of mathematics and mechanics, 6(5): 679-684, 1957.
[3] K. J. Aström. Optimal control of markov processes with incomplete state information. Journal of Mathematical Analysis and Applications, 10(1):174-205, 1965.
[4] P. J. Gmytrasiewiez and P. Doshi. Interactive pomdps: Properties and preliminary results. In International Conference on Autonomous Agents: Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-, volume 3, pages 1374-1375, 2004.
[5] S. V. Albrecht and P. Stone. Autonomous agents modelling other agents: A comprehensive survey and open problems. Artificial Intelligence, 258:66-95, 2018.
[6] C. L. Baker, N. D. Goodman, and J. B. Tenenbaum. Theory- social goal inference. In Proceedings of the thirtitth annual conference of the cognitive science society, pages 1447-1452. Cognitive Science Society, 2008
[7] C. L. Baker and J. B. Tenenbaum. Modeling human plan recognition using bayesian theory of mind. Plan, activity, and intent recognition: Theory and practice, 7:177-204, 2014.
[8] J. Kiley Hamlin, T. Ullman, J. Tenenbaum, N. Goodman, and C. Baker. The mentalistic basis of core social cognition: Experiments in preverbal infants and computational model. Developmental science, 16(2):209-226, 2013.
[9] M. Kleiman- Kleiman-Weiner, M. K. Ho, J. L. Austerweil, M. L. Littman, and B. Tenenbaum. Coordi- nate to cooperate compete: abstract goals and joint intentions in social interaction. In CogSci, 2016.
[10] N. Rabinowitz, F. Perbet, F. Song. C. Zhang, S. A. Eslami, and M. Botvinick. Machine theory of mind. In International conference on machine learning, pages 4218 4227. PMLR, 2018.
[11] C. L. Baker, R. Saxe, and J. B. Tenenbaum. Action understanding as inverse planning. Cognition, 113(3):329-344 2009.
[12] T. D. Ullman, C. L. Baker, O. Macindoe, O. Evans, N. D. Goodman, and J. Tenenbaum. Help or hinder: Bayesian models of social goal inference. Technical report, MASSACHUSETTS INST OF TECH CAMBRIDGE DEPT OF BRAIN AND COGNITIVE SCIENCES, 2009.
[13] D. Madfield-Menell S. J. Russell, P. Abbeel, and A. Dragan. Cooperative inverse reinforcement learning, Advances in neural information processing systems, 29:3909-3917, 2016.
[14] A. Patron-Perez, M. Marszalek, I. Reid, and A. Zisserman. Structured learning of human interactions tv shows. IEFE Transactions on Puttern Analysis and Machine Intelligence, 34
(12):2441-2453, 2012.

---

[15] M. J. Marin-Jimened A. Zisserman, M. Eichner, and V. Ferrari. Detecting people looking at each other in videos. International Journal of Computer Vision, 106(3):282 2014.
[16] M. S. Ryoo and J. K. Aggarwal. Spatio-temporal relationship match: Video structure comparison for recognition of complex human activities. In 2009 IEEE 12th international conference on computer vision, pages 1593-1600. IEEE, 2009.
[17] X. Puig, T. Shu, S. Li, Z. Wang, B. Tenenbaum, S. Fidler, and A. Torralba. Watch-and-hed and-help: A challenge for social perception and human-ai collaboration. In The International Conference on Learning Representations, 2021.
[18) D. K. Levine. Modeling altruism and spitefulness in experiments. Review of economic dynamics, 133):593-62, 1998.
[19] Z. Feng, C. Tan, J. Zhang, and Q. Zeng. Bargaining game with altruistic and spiteful preferences. Group Decision and Negotiation, 30(2):277-300 2021.
[20] F. Heider and M. Simmel. An experimental study of apparent behavior. The American journal of psychology, 57(2):243-255) 1944.
[21] T. Shu, M. Kryven, T. D. Ullman, and J. B. Tenenbaum. Adventures in flatland: Perceiving social interactions under physical dynamics. 42d proceedings of the annual meeting of the cognitive science society, 2020.
[22] M. Kryven, T. Ullman. B. Cowan, and J. Tenenbaum. Plans or outcomes: How do we attribute intelligence to others? In PsyArXiv, 2021.
[23] A. Netanyahu, Shu, B. Katz, A. Barbu, and J. B. Tenenbaum. Phase: syssically-grunnde abstract social events for machine social perception. In The AAAI Conference on Artificial Intelligence, 2020.
[24] P. Doshi and P. J. Gmytrasiewicz. Monte carlo sampling methods for approximating interactive pomdps. Journal of Artificial Intelligence Research, 34:297-337, 2009.
[25] P. Doshi and D. Perez. Generalized point based value iteration for interactive pomdps. In AAAI, pages 63-68, 2008
[26] B. Ng, K. Boakye, C. Meyers, and A. Wang. Bayes-adaptive interactive pomdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, 2012.
[27] A. Xie, D. P. Losey, R. Tolsma, C. Finn, and D. Sadigh. Learning latent representations to influence multi-agent interaction. In Conference on Robot Learning (CoRL., 2020.
[28) M. Igl, L. Zintgraf, T. A. Le, F. Wood, and S. Whiteson. Deep variational reinforcement learning for POMDPs. In J. Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 2117-2126. PMLR, 10-15 Jul 2018.
[29] A. X. Lee, A. Nagabandi, P. Abbeel, and S. Levine. Stochastic latent actor-critic: Deep reinforcement learning with latent variable model. In Neural Information Processing Systems (NeurIPS), 2020.
[30] C. F. Camerer, T.-H. Ho, and J.-K. Chong. A cognitive hierarchy model of games. The Quarterly Journal of Economics, 119(3)861-889, 2004.
[31] I. Shpitser, R. J. Evans, T. S. Richardson, and J. M. Robins. Introduction to nested markov models. Behaviormetrika, (1(::33,,, 2014.
[32] W. Yoshida, J. Dolan, and K. J. Friston. Game theory of mind. PLOS Comput Biol, 4(12):
e1 e1000254, 2008
[33] N. Hoang and K. H. Low. Interactive pomdp lite: Towards practical planning to predict and exploit intentions for interacting with self-interested agents. In Twenty-Third International Joint Conference on Artificial Intelligence, 2013.
[34] C. Baker, R. Saxe, and J. Tenenbaum. Bayesian theory of mind: Modeling joint belief-desire attribution. In Proceedings of the annual meeting of the cognitive science society, volume 33, 2011.
10


Reviews:
[{"review_id": "lA5NOl7ph1w", "reviewer": "Reviewer_BjXW", "summary": "This work introduces recursive social MDPs, which are able to reason about other agents physical and social goals at different levels of recursion. These social MDPs enable agents to behave more socially…for example, if another agent wants to help them, they can accept help rather than trying to do their own physical task alone. These recursive social MDPs are tested on five potential social scenarios in a gridworld, and the social MDPs predictions are shown to correlate with human predictions of social/physical goal behavior.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The proposed Social MDPs are a very interesting idea, and the stated motivation for them is strong. The proposed framework is also quite general, which lends itself well to future extensions of this work to multiple agents, and potentially POMDPs. The paper shows a good amount of thought put towards future extensions of Social MDPs.\n\nHowever, it is unclear to me how the five chosen scenarios were picked for testing, and as far as I can tell there were no scenarios tested where both agents were trying to help each other. Without additional reasoning for why Scenarios 1, 15, 22, 28, and 30 were the ones chosen, it’s unclear how convincing the results are for the overall performance of Social MDPs. However, there is good performance shown on the selected five scenarios.\n\nOverall, this is a very interesting paper, and the motivation for Social MDPs is convincing.", "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": "I am recommending a weak reject, because it’s unclear why the specific scenarios were picked for testing while others were excluded. However, the Social MDPs are quite interesting and well presented, and the motivation was convincing.\n\nUpdated post-rebuttal: the authors added significant experiments during the rebuttal period, including all scenarios during testing. I now recommend accepting this paper, and have changed the technical quality to Very Good. I have not seen the full written addition to the paper as the authors were not able to add the full experiments to the pdf yet, so I am somewhat torn between a weak accept and a strong accept, but I'm updating my review to a strong accept contingent on these results being added to the paper.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Very Good:  Well organized and clear.", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning.", "reviewer_expertise": "Very good: Comprehensive knowledge of the area"}, "extra_text": {"issues": "Issues to address in the author response/revision period:\n-\tWhy were Scenarios 1, 15, 22, 28, and 30 chosen? Are other scenarios expected to perform as well as these five? \n-\tHow would a scenario with two helpful agents (say two agents with social goals set to 2) play out? \n-\tSome of the equations (for example, Equation 3), might be easier to understand with a written description alongside the mathematical equation.\n-\tHow do the agents take joint moves in this gridworld? Does agent 1 move, and then agent 2, or do they move simultaneously? \n-\tThe Social MDPs are tested on a task that is a fairly simple level 0 MDP. How would the time/learning complexity extend to more complex MDPs, and is it still feasible for 0 shot learning?\n-\tTiny note, but I think ~R_j^(j-1) in equation 2 is supposed to read ~R_j^(l-1), is that right?\n"}}, {"review_id": "XKVWO0K4jx", "reviewer": "Reviewer_jXz2", "summary": "This paper presents a novel methodology to include social goals in a decision-making problem (where physical goals are already considered). In this way, the problem is very well defined: how to incorporate social interactions into MDPs? The authors propose to consider recursive goals (social and physical) of all agents of the environment. In doing so, the authors (probably) opened a new research line in the Robotics community: Social Markov Decision Processes (Social MDPs).\n", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths\nIndeed, the novelty of this work is its strength. There are few related works, so the authors may open here a new research line in Robotics. In addition, the problem has paramount importance for topics such as Human-Robot Interaction and Robot Learning. \n\n* Weaknesses\nHowever, the authors define \"Social Interactions\" in a very superficial way (helping/hindering), which should be comprehensively exploited. Other weaknesses that can be pointed out are: \n     - mathematical formulations poorly justified/explained\n     - results visually unclear but that are very important to understand the evidences/hypotheses presented in the document\n\nSee also \"Issues\"", "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": "Although the article is well written and the idea is very interesting, there are some missing links found throughout the document. The document needs some clarifications and discussions (maybe proofs, if that's the case) in the mathematical formulations. There is space for an Appendix for more explanations or additional material.\n", "technical_quality": "Fair: Significant additional evidence required to support the claims.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "2: Unsure, difficult to assess.", "reviewer_expertise": "Good: General knowledge of the area"}, "extra_text": {"issues": "Abstract\nThe authors consider hindering and helping as social interactions, while one can state that these are more collaborative/uncooperative interactions. Could you define social interactions? For instance, in the experiments you show results with two robots. Do two robots comprise a social group? Perhaps, reasoning about other's intention may be considered as a social behavior, but it is an instance of social behaviors. \n\nIn the Abstract you should define the abbreviations: MDP - Markov decision process, and POMDP- Partially observable Markov decision process. The first time MDP is defined is in Sec. 3, line 103.\n\nSection 1. Introduction\nYou could define better (crisper) physical and social goals by including practical examples. \n\nThe authors consider social and physical goals at the same level of abstraction. However, one may figure cases where social goals drive physical goals. In these cases, social goals trigger physical goals. We can even consider, in those specific situations, that the physical goals are drives to satiate the social goals. Throughout the author's description, one can see that both concepts are disentangled, which is not (always) true - e.g. An agent wants to go towards a human to greet him (social goal); so, the agent needs to go to a certain location (physical goal) in order to greet the human. Hence, the physical goal stems from a social goal. How do you see that these cases affect your formulation? For instance, should the physical goal depend on the social goal? If so, how?\n\nSection 2. Related Work, Simulating social interactions\nRewrite lines 82-83 (word repetition - \"allow\").\n\nSection 3. Social MDPs\nLine 43: \"Unlike I-POMDPs, Social MDPs are not recursive in terms of agent's beliefs (...)\". Line 104: \"Social MDPs are (...) and nested MDPs that reason about the beliefs of other agents\". Please be coherent or clarify better. \n\nRegarding the notion of levels, in which extent levels deeper than 2 vary from the considered ones?\n\nSection 3.1 Assumptions\nIRL should be defined and discussed. There was no previous context when \"IRL\" was mentioned.\n\nSection 3.2 Formal definition of Social MDPs\nWhy the physical goal is not part of the definition? Or seen from a different perspective why the social goal is part of the definition? Being coherent here is important.\n\nReward\nIn the formula, the expresion R_j^{j-1,i}  is not clear, do you mean R_j^{l-1,i}? It is the estimated reward for agent from 's point of view and following the methodology's formulation, j's are all considered with one level below the target's one.\n\nSections 3.3. ,3.4, and 3.5\nMathematical choices and formulas should be explained, discussed or referenced.\n\n4. Results\nThe results are extremely important and show how fruitful was the presented work. All images and plots must be bigger, otherwise one cannot see the real impact of your approach (the videos are also very good, but try to increase the size of the images, perhaps the inclusion of an Appendix is a great solution). In the caption of figure 1. (b) there is a mistake: the red robot wants to hinder the yellow, not to help it. Again, one can envisage social behaviors included in this system, but for now it is not clear that two robots helping/hindering each other is the representation of a social interaction.\n\nFinally, you reference Figure 3, but it is a Table. Please revise it.\n\nSection References\nReferences 12, 19, and 30 do not contain the respective conference or journal, Please include this information."}}, {"review_id": "MYavogE8PW", "reviewer": "Reviewer_N7Wd", "summary": "In response to the near complete rewrite of the methods section, and the addition of some sorely lacking figures, I have upgraded my clarity score from poor to good. After arguments with the authors, I have become convinced that in principle at least a human level of heuristic based pruning for larger numbers of agents and levels is possible in principle, although I still think there isn't a clear direction on what this heuristic might be. Due to the novelty and strong potential impact of the paper, I am upgrading my recommendation from weak accept to strong accept. The original review is left unchanged below.\n\n===\n\nWhen an has social desires i.e. desires about the success or failure of other agents, a recursive problem comes into being where each agent must estimate other agent's reward in order to estimate their own reward, which in turn requires a recursive estimation of all other agent's rewards. Traditional MDPs cannot model such agents. This paper introduces a recursive social MDP where rewards are computed at different social levels. The 0th social level excludes social rewards entirely. In the first social level, each agent is rewarded according to their 0th level, and considering the 0th level rewards of all other agents according to their social reward function. On the second level, each agent is rewarded according to the other agent's first level rewards, and so on and so forth. This paper claims to have methods for computing these social rewards, social value functions, and social policies at different levels by estimating the physical and social goals of each other agent. The paper evaluates their method by comparing its estimates of the social relationships between agents (helping or hindering) to humans estimates of the same, and finds a significantly higher correlation between these estimates and the estimate of two baseline methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper addresses a significant problem in using RL for human robot interactions.\n\nThe method solves a significant technical challenge.\n\nWeaknesses:\n\nThe methods section of this paper is exceptionally unclear. I took at least 3 hours to understand just the method, in the process generating several figures that should have been in the main paper. The notation in the paper is used inconsistently, further exacerbating this problem.\n\nAlthough the social MDP framework allows for arbitrary recursive levels and numbers of agents, only two agents and two levels are tested experimentally.\n\nThe method is extremely computationally expensive. $O((A-1)^2\\ell)$ MDPs need to be solved, where $A$ is the number of agents and $\\ell$ is the depth of the social recursion. This is impractical for all but the smallest number of agents, which is likely why the experiments are limited. The paper suggests some spatial pruning of the dependency might be possible to alleviate this, but there are many environments where our actions can affect agents spatially far away, and so it is not obvious that further speedups are possible.", "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": "I recommend accepting this paper contingent on a significant rewrite of the methods section, which was exceptionally unclear. This paper addresses the important problem of modelling agents who value the wellbeing of others. The method, while poorly explained, is correct to the best of my knowledge, and is a natural complete description of the problem. Social reasoning is computationally expensive and difficult for humans, and so it is not surprising that it would also be so mathematically.\n\nI could be convinced to reject the paper if another reviewer found an unresolvable mathematical error in the method, which is reasonably likely, as I am not confident in my understanding of the method. I would also be convinced to reject if another reviewer had a strong argument that experiments with more agents or more social depth were unlikely to be as successful.", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning.", "reviewer_expertise": "Fair: Some knowledge of the area"}, "extra_text": {"issues": "I have several significant confusions about how the method works. Many of these confusions could be resolved by the inclusion of an explicit algorithm figure for computing the actions of an agent within a social MDP and a diagram indicating how estimates of $R,Q,\\tilde{\\psi},\\tilde{\\chi},$ and $\\tilde{g}$ at different levels depend on each other. It would also help a lot if each of the expressions could include a derivation, even if they are only a few lines.\n\nAfter much deliberation, I now believe I understand the algorithm up to l=2 for 2 agents. I will now produce that algorithm here so that any misconceptions can be cleared up. I am deeply uncertain of many aspects of this description, especially when certain things are priors vs belief vectors at the previous level. I would like to reiterate that this was written very unclearly and in order to accept I would need a significant rewrite of the methods section.\n\nCompute $P(\\tilde{g}_2^{1,0})$ for many values of $g$, and then determine the working $\\tilde{g}_2^{1,0}$ by sampling one, or using the MLE or mean or something.\n\n=> In order to do so, estimate $\\tilde{R}\\_2^{0,1}$ under the assumed $g$ (which doesn't rely on $\\chi$ at the 0th level), then use that to compute $Q_{2}^0$, and use that to compute $\\tilde{\\pi}_2^1$, the non-social policy. The non social policy can then be used to determine $P(s^{1:T} | g_2)$, and the other terms are priors at this level. This whole procedure is essentially IRL in a non-social MDP.\n\nUnder this working $g$, compute $R \\rightarrow Q \\rightarrow \\pi$ as before. $\\tilde{\\psi}_2^{1,1} = \\tilde{\\pi}_2^1$.\n\nUsing an identical procedure, estimate $\\tilde{R}_1^{2,0}$.\n\nCompute $P(\\tilde{g} _2^{1,1})$ using prior belief vector $P(\\tilde{g}_2^{1,0})$ and $\\tilde{\\psi}_2^{1,1}$ to compute $P(s^{1:T} | g_2)$. Equation 3 does not include a level on the likelihood of $g$, so I'm assuming you pick the $\\psi$ at the current level and use the $\\chi$ implicitly used by $\\psi$, so you use the $\\chi$ of the prior level. This means that estimating $\\tilde{g}_2^{1,0}$ still doesn't rely on any $\\chi$ information, and so $P(\\chi)$ drops away at this level as well.\n\nEstimate $\\tilde{\\chi}_2^{1,1}$ using $\\tilde{\\psi}_2^{1,1}$ for $P(a_j^{t-1}|...)$. I assume at $t=0$ instead of recursing you use an improper prior of $1$.\n\nThen we estimate $\\tilde{R}_2^{1,1}$ using the estimated $\\tilde{g}_2^{1,1}$ to determine the non-social term, $\\tilde{\\chi}_2^{1,1}$ as the social weight, and the earlier $\\tilde{R}_1^{2,0}$ estimate of our own level 0 reward.\n\nFinally, we can compute our own $R^2_1$ level 2 reward using our ground truth $g_1$, our ground truth $\\chi_{12}$, and the estimated level 1 reward of agent 2 $\\tilde{R}_2^{1,1}$. From there we can estimate our own $Q^2_1$ function, and from there our own social policy $\\phi_1^2$.\n\nI will now describe other issues with the paper.\n\nYou define $\\mathcal{A} = \\mathcal{A}\\_i \\times \\mathcal{A}\\_J$. Does the set J include the $i$-th agent or not? If it does, does $\\mathcal{A}$ include agent $i$'s actions twice? This ambiguity is present everywhere $J$ is used, and it is used both ways e.g. in equation 4, the sum is over $j \\in J, j \\neq i$ which implies $i \\in J$, but line 140 states \"$\\chi_{iJ}$ is agent $i$'s social goal towards every other agent in J.\" which suggests $i \\notin J$.\n\nWith 2 agents, when agent 1 is trying to compute their first action, they need to maximize $Q_1^l(s, a_1, a_2, \\chi_{12}) = R_1(s, a_1, a_2, \\chi_{12}) + ...$, which requires knowing what $a_2$ is going to be. Agent 2 has the same problem. How is this resolved? Do the two agents take turns, and know the other agent's last action? Is there some protocol where a Pareto optimum is found?\n\nYou claim the time complexity is $O((A-1)^2 \\ell)$, but you also need to solve an MDP for each value of $g$ you test at the 0th layer, which is not included in the stated complexity.\n\nIn figures 2 and 3, are the given visual bounds and +- terms a confidence interval (if so, at what confidence). If not, what do they indicate?\n\nLine 70 \"Moreover, MDPs tend to be more efficient...\" What are the alternative formulations? Is this a claim you are making in this paper, or do you believe this is common knowledge? If the latter, please find a citation.\n\nThere are several notational or grammatical errors, some of which create ambiguity or affect clarity. I called out one earlier with the lack of a level on $P(g|s)$. Here are some more:\n\nLine 91: \"[24] propose\" -> nit, please list the author before the citation. The sentence should still be valid if all the citations are removed.\n\nEquation 2: $R_j^{j-1}$ -> $R_j^{l-1}\n\nLine 197: \"must compute pairwise social goal\" -> nit \"must compute the pairwise social goals\"\n\nFigure 1b caption \"that red wants to help it\" -> \"that red agent wants to harm it\".\n\nLine 208: \"four connected\" -> omit, just include the latter description. Four connection is under specified."}}]

Author rebuttal:

Meta-review: ### Final Meta-Review

The authors have thoughtfully and proactively engaged with the concerns raised by reviewers and have made significant improvements to the paper, including substantially clearer technical exposition and a rich set of new simulation results to more rigorously evaluate the proposed framework.

Ultimately, the final manuscript has earned strong reviewer support and will no doubt be a welcome contribution to CoRL. I am pleased to recommend the paper for acceptance.

### Original Meta-Review

The reviewers agree that the paper addresses a significant and well-motivated problem and proposes a substantially novel approach to tackle it. On the other hand, they also raise concerns regarding clarity of exposition and adequacy of the experimental evaluation.

All three reviewers have stressed the lack of clarity in the Results section, as well as inconsistencies or typos in the mathematical notation. This section would need to be significantly revised by the authors prior to eventual publication of the paper. Reviewers have also suggested the use of examples and visual illustrations to improve the paper's readability.

Reviewer N7Wd brings up the challenging scalability of the proposed formulation with the number of agents and levels considered and notes that only two agents and two levels (the bare minimum) are shown. Reviewer BjXW notes the lack of justification regarding the five scenarios chosen, as well as the apparent absence of a mutually helpful scenario.

Finally, I strongly encourage the authors to clearly establish the connection between their proposed formulation and dynamic (Markov) games, especially game-theoretic formulations that model "altruism" and "spite" as part of players' payoffs.
Decision: Accept (Poster)