Venue: CoRL 2021 Conference

Reviews:

final_score: rating: Strong Accept: I recommend accepting the paper and will argue for my recommendation even if other reviewers hold a different opinion.
review_content: 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.

===

When 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.
strengths_and_weaknesses: Strengths:

The paper addresses a significant problem in using RL for human robot interactions.

The method solves a significant technical challenge.

Weaknesses:

The 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.

Although the social MDP framework allows for arbitrary recursive levels and numbers of agents, only two agents and two levels are tested experimentally.

The 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.
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.

I 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.
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.

After 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.

Compute $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.

=> 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.

Under this working $g$, compute $R \rightarrow Q \rightarrow \pi$ as before. $\tilde{\psi}_2^{1,1} = \tilde{\pi}_2^1$.

Using an identical procedure, estimate $\tilde{R}_1^{2,0}$.

Compute $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.

Estimate $\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$.

Then 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.

Finally, 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$.

I will now describe other issues with the paper.

You 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$.

With 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?

You 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.

In 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?

Line 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.

There 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:

Line 91: "[24] propose" -> nit, please list the author before the citation. The sentence should still be valid if all the citations are removed.

Equation 2: $R_j^{j-1}$ -> $R_j^{l-1}

Line 197: "must compute pairwise social goal" -> nit "must compute the pairwise social goals"

Figure 1b caption "that red wants to help it" -> "that red agent wants to harm it".

Line 208: "four connected" -> omit, just include the latter description. Four connection is under specified.
review_title: null

final_score: rating: Strong Accept: I recommend accepting the paper and will argue for my recommendation even if other reviewers hold a different opinion.
review_content: 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.
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.

However, 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.

Overall, this is a very interesting paper, and the motivation for Social MDPs is convincing.
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.

Updated 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.
issues: Issues to address in the author response/revision period:
-	Why were Scenarios 1, 15, 22, 28, and 30 chosen? Are other scenarios expected to perform as well as these five? 
-	How would a scenario with two helpful agents (say two agents with social goals set to 2) play out? 
-	Some of the equations (for example, Equation 3), might be easier to understand with a written description alongside the mathematical equation.
-	How do the agents take joint moves in this gridworld? Does agent 1 move, and then agent 2, or do they move simultaneously? 
-	The 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?
-	Tiny note, but I think ~R_j^(j-1) in equation 2 is supposed to read ~R_j^(l-1), is that right?
review_title: null

final_score: rating: Weak Accept: I recommend accepting the paper, but will not argue for my recommendation if the majority of other reviewers have a different opinion.
review_content: 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).

strengths_and_weaknesses: * Strengths
Indeed, 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. 

* Weaknesses
However, 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: 
     - mathematical formulations poorly justified/explained
     - results visually unclear but that are very important to understand the evidences/hypotheses presented in the document

See also "Issues"
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.

issues: Abstract
The 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. 

In 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.

Section 1. Introduction
You could define better (crisper) physical and social goals by including practical examples. 

The 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?

Section 2. Related Work, Simulating social interactions
Rewrite lines 82-83 (word repetition - "allow").

Section 3. Social MDPs
Line 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. 

Regarding the notion of levels, in which extent levels deeper than 2 vary from the considered ones?

Section 3.1 Assumptions
IRL should be defined and discussed. There was no previous context when "IRL" was mentioned.

Section 3.2 Formal definition of Social MDPs
Why 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.

Reward
In 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.

Sections 3.3. ,3.4, and 3.5
Mathematical choices and formulas should be explained, discussed or referenced.

4. Results
The 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.

Finally, you reference Figure 3, but it is a Table. Please revise it.

Section References
References 12, 19, and 30 do not contain the respective conference or journal, Please include this information.
review_title: null

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)