Select to Perfect: Imitating desired behavior from large multi-agent data

Weaknesses

For the results, it is necessary to provide some reference for a better understanding of the performance, e.g., reporting the results using the ground truth identification, or the results using the shapely value or other credit assignment methods.

Thank you for this remark. We would first like to clarify that, for the human datasets, a ground-truth identification does not exist, as no ground-truth cluster assignments are given for the human participants in this dataset. For the simulated datasets, we can observe in Figure 4 that the EV estimation error is very low if 30% of groups are observed, hence the estimated EVs are very close to ground-truth EVs. The results for EV2BC in Table 3 assume that 30% of groups are observed and hence very closely match the performance using ground-truth identification of agents. We will add the exact results for ground-truth identification, but for now focused on the additional Starcraft experiments.

Unfortunately, it is impossible to compute a Shapley Value baseline in the given scenarios, as Shapley Values cannot be computed for fixed-size games. However, if Shapley Values could be computed (in the absence of group size constraints), then the ordering of agents by Exchange Values is identical to the ordering of agents by Shapley Values (see section 4.1 "Relationship between Shapley Value and Exchange Value" for details). Hence, in the absence of group size constraints, using Shapley Values to guide imitation learning will result in identical results as when using Exchange Values. We have also empirically verified this in the Tragedy of Commons environment. We are unaware of other credit-assignment methods that apply to our problem setting but will include a comparison if pointed to such works.

The paper uses a limited number of environments and datasets to evaluate the proposed method and does not consider more complex or realistic scenarios that involve heterogeneous agents, partial observability, communication, or coordination, e.g., applying the exchange value in proactive multi-camera cooperation[1] or SMAC[2].

We now conducted additional experiments in the Starcraft multi-agent environment, which is a widely used multi-agent coordination benchmark [C, D], which is partially observable, involves long-term planning, requires strong coordination, and where agents are heterogeneous. We find that also here, our method outperforms the baselines by a substantial margin, underlining the applicability of our method to diverse settings. Please consider the general response for details.

Questions

How do you deal with the uncertainty or variability in the EV estimates, especially when the data is incomplete or anonymized? How robust is your method to noise or outliers in the data?

We address the case of noisy or incomplete (individually anonymized) observations by combining both EV-Clustering and behavior clustering. This allows us to achieve good performance even on individually anonymized, noisy, real-world data, as demonstrated by the experiments on the human dataset in the Overcooked environments (see results for $D^{human}$ in Table 1). 

How do you justify the choice of the DVF for each domain? How do you ensure that the DVF is aligned with the desired behavior and does not have any unintended consequences or biases?

We would like to point out that in the discussion of AI Alignment, a distinction between normative and technical alignment is often made [A]. Our work addresses solely the technical aspect of alignment, and it does not try to answer the question of which norms AI systems should align with. Specifically, we do not try to answer the question of what the correct Desired Value function (DVF) for a given problem is. The DVFs that we chose for the different environments are simply inspired by previous literature. A possible option for setting DVFs is to crowdsource rankings of collective outcomes from human annotators [B]. 

Citations:
[A] “Artificial Intelligence, Values and Alignment”, Gabriel, Minds and Machines, 2020
[B] "Human-centred mechanism design with Democratic AI", Koster et al., Nature human behaviour, 2022

Dear reviewer,

we kindly wanted to ask if we were able to address your concerns. If so, we would like to ask if you would be willing to increase your score, given the positive results in Starcraft.

Best wishes, The authors

Weaknesses

The proposed method assumes that the collective value function can be expressed as a sum of individual contributions. The authors should comment more on the class of problems that this is applicable to.

We would like to point out that this assumption does not apply to Exchange Values or EV2BC, but is merely made to arrive at a theoretical motivation for EV-Clustering.

The inessential game assumption is commonly made when estimating Shapley Values [A], as it makes theoretical analysis tractable. It represents the simplest non-trivial class of cooperative games, and hence a natural first step. Future work could investigate defining the game as a weighted graph (possibly with self-loops), where the value of a group is the total weight of its internal edges (inessential games correspond to graphs where only self-loops have non-zero weight). We now added this clarification to the main paper.

Even when the inessential game assumption is not made, the objective of EV-Clustring, i.e. maximizing the variance in EVs across all agents, is nonetheless well motivated, as this objective results in maximally distinct EVs, while a random partition into clusters would have very low variance (and hence agents would have very similar EVs). 

Experiments evaluate the proposed method on a limited set of environments and tasks, and it is unclear how well the method would generalize to other domains and tasks. The authors motivated with a mixed driving dataset, and it would be useful to see how this method applies to driving benchmarks.

To underline the scalability of our method we now added experiments in the Starcraft multi-agent environment (SMAC, [A]), which we picked as it is probably the most widely adopted benchmark in the multi-agent community [C, D] and has various predefined scenarios and benchmarks (unlike multi-agent driving). It is partially observable, involves long-term planning, requires strong coordination, and is heterogeneous (as also described by Reviewer floZ). We find that also here, our method outperforms the baselines by a substantial margin, underlining the applicability of our method to diverse settings. Please consider the general response for details.

Questions

Is EV a good measure if there exist complex/bipolar dynamics between agent behaviors? e.g. two agents work well if they are both in the team but horribly if only one present?

Our work makes the assumption that agents behave relatively consistently across trajectories. If some agents A and B perform well when a third agent C is not present, but perform badly when agent C is present (all other things being equal), then this requires splitting the behavior data of agents A and B into two subagents each, which represent agent A and B in the presence and absence of agent C. We highlight this as an interesting direction for future work in our conclusion.

Ethics Concern

This paper itself does not comment on potential ethical issues. The notion of exchange value can potentially be applied to evaluate human performance/value to a team/company, which should require extra caution. The idea of evaluating value of an individual's contribution based on how much it differs by swaping them out with a random person can be concerning if applied to human performance.

Shapley Values and Exchange Values estimate the alignment of an individual with a group value function (which must be prescribed separately), and as such can be misused if they are included in a larger system that is used to judge those individuals in any way. Discrimination of individuals based on protected attributes is generally unlawful, and care must be taken to avoid any discrimination by automated means. In our work, we demonstrated a novel positive use of these methods by using them to train aligned (beneficial) agents, that do not imitate negative behaviors in a dataset. We expect that the benefits of addressing the problem of unsafe behavior by AI agents outweigh the downsides of misuse of Shapley Values and Exchange Values, which are covered by existing laws. We further clarified this in the Conclusion.

Citations:
[A] "A unified approach to interpreting model predictions", Lundberg et al, NerurIPS, 2017

Weaknesses:

How scalable would this method be to let's say a dataset of multi-agent driving scenes? It seems to me like scalability is an issue here, specifically due to clustering. 

To underline the scalability of our method we now added experiments in the Starcraft multi-agent environment (SMAC, [A]), which we picked as it is probably the most widely adopted benchmark in the multi-agent community [C, D] and has various predefined scenarios and benchmarks (unlike multi-agent driving). It is partially observable, involves long-term planning, requires strong coordination, and is heterogeneous (as also described by Reviewer floZ). We find that also here, our method outperforms the baselines by a substantial margin, underlining the applicability of our method to diverse settings. Please consider the general response for details.

this brings me to an important point, the weaknesses of the proposed approach should be addressed.

We would like to point the reviewer to the conclusion, which already addressed three main limitations of our work. We have now added that we see the application of our method to even larger multi-agent environments, such as driving, as a relevant direction for future research.

I'm still left confused by the differences between behavior clustering and EV-clustering. I understand the differences in the approaches, but the ablation study seems to point to behavioral clustering being more stable in low-data regiments. I see that the ablation study says to look at section 5.1 to show why behavioral clustering is not sufficient by itself, but I do not see the supporting results.

Thank you for this remark; we now discuss this matter in more detail in Section 5.1 in the main paper. We first recall that behavior clustering only considers low-level behavior data (actions taken by individual agents), while EV-clustering only considers collective outcomes (DVF scores assigned to collective trajectories). In general, EV-clustering should be preferred to behavior clustering, for the following reason. Consider a case where two agents contribute equally to the DVF, in which case both agents should be assigned equal EVs, but both agents do show very different low-level behavior. When applying EV-Clustering, both agents would be assigned to the same cluster and would hence correctly be assigned the same EV. However, when applying behavior clustering, both agents would be assigned to different clusters, which would potentially result in erroneously assigning different EVs to each agent (and would likely result in higher-variance EV estimates overall). EV-clustering may have high variance if only very few collective outcomes are observed for some agents, in which case we can combine it with behavior clustering. 

Questions:

I'm a little confused about some experimental details. Specifically, the number of agents in the datasets, and the exact composition of the dataset is unclear. Can you clarify the composition of the  $D^{adv}$ Are there really two different types of agents, but $n=100$ agents?

Yes, the $D^{adv}$ dataset contains 100 agents but only two different types of agents (some behaving optimally, some behaving adversarially.) In contrast, the $D^{\lambda}$ dataset contains 100 different agents, where $\lambda$ is sampled from a uniform distribution for each agent. We chose to also have 100 agents in $D^{adv}$, to make it equal in size to $D^{\lambda}$.

In my opinion, the paper would be better organized by moving more results from the appendix into the main paper. One simple way of improvement is to move Figure 3 to the appendix and add the ablation study on EV-clustering vs. Behavior clustering.

Thank you for this suggestion. We moved Figure 3 to the Appendix. As we also have to accommodate the additional Starcraft experiments in the main paper, we were unable to move Figure 6 to the main paper, but we now discuss the findings from the ablation study, as well as the pros and cons of both clustering methods, in more detail in Section 5.1.

Citations:
[A] "The Starcraft multi-agent challenge.”, Samvelyan et al., AAMAS, 2019
[B] “Grandmaster level in StarCraft II using multi-agent reinforcement learning”, Vinayls et al., Nature, 2019

Dear reviewer, please let us know if we were able to address your concerns. In light of the positive additional experiments in Starcraft, we would also like to ask you to consider raising your score.

Could authors further explain the definition of the "cluster-centroid agents $C \subseteq K$" in line 223?

C represents a group of cluster-centroid agents, with $C \subseteq K$, and where K is the set of all clusters (or set of all cluster-centroid agents). Generally, a cluster-centroid agent can be thought of as a meta-agent that represents the aggregate of all agents assigned to a given cluster, which is done by grouping the observations for all agents assigned to the same cluster into one cluster-centroid agent (a meta-agent). We can then compute outcomes for groups of cluster-centroid agents C, just like we can compute outcomes for groups of individual agents. Assuming adequate cluster assignments, this grouping of observations allows for a significant reduction in the variance in the EV estimates.

Weaknesses

Limited Environments: Only two environments are studied, while there are many environments that can further highlight the real-world value of the proposed method, e.g. public traffic.

To underline the scalability of our method we now added experiments in the Starcraft multi-agent environment (SMAC, [A]), which we picked as it is probably the most widely adopted benchmark in the multi-agent community [C, D] and has various predefined scenarios and benchmarks (unlike multi-agent driving). SMAC involves long-term planning, requires strong coordination, and is heterogeneous (as also described by Reviewer floZ). We find that also here, our method outperforms the baselines by a substantial margin, underlining the applicability of our method to diverse settings. Please consider the general response for details.

Lack of more theoretical analysis of the properties of EV Shapley Values are known to have good properties, e.g. symmetry, dummy (zero value for null players), additivity, etc, which make it interpretable, appealing, and useful. It would be interesting to see an analysis of Exchange Values with respect to these properties.

Thank you for this remark. The Shapley Value satisfies four main axioms: Dummy, Efficiency, Symmetry, and Linearity. We have now further clarified the relationship between Shapley Values and Exchange Values in the main paper, and added further clarifications about the different axioms. In Appendix A.1 we provide the following proofs:

• for the relationship between Shapley Values and Exchange Values
• that the Exchange Value satisfies the symmetry and linearity axioms
• that the Exchange Value satisfies appropriately modified versions of the dummy and efficiency axioms.

Lack of interpretation of EV: More detailed analysis can be added to the main text with respect to how different EV values can be connected to various behavior patterns. In particular, I think the $\lambda$  values in both "Tragedy of Commons" and "Overcooked" can be linked to the estimated EVs to validate the method.

Thank you for this remark. Such plots are given in the appendix (due to lack of space), and we now improved their descriptions and referencing in the main paper. Figure 6 shows a plot of the relation of $\lambda$ and EV in the Overcooked environments, and Figure 8 shows the relation between EVs and different strategies in Tragedy of Commons. The strong correlation in Figure 6, as well as the visibly correct ordering of agents in Figure 8, provide insights into the relation between EVs and different strategies. This verifies that EVs are adequate estimators for individual contributions in both environments. 

Lack of baseline: I understand that this is the first work tackling this specific problem setup, but I'm interested to see whether Shapley values could be similarly useful for guiding imitation learning in multi-agent datasets when the group size constraint is absent (which should be possible in many cases, e.g. the Tragedy of the Commons).

Thank you for this remark; we now further clarified this in the main paper. As described and shown in Section 4.1, if Shapley Values can be computed (in the absence of group size constraints), then the ordering of agents by Exchange Values is identical to the ordering of agents by Shapley Values. Hence, in the absence of group size constraints, using Shapley Values to guide imitation learning will result in identical results as using Exchange Values. We also empirically verified this in the Tragedy of Commons environment.

Writing: Although I in general enjoyed reading the paper, I still find many sentences throughout the article a bit repetitive and convoluted.

We appreciate this feedback. We have made several improvements, also following other reviewers' suggestions, and welcome any further suggestions.

Questions

What does the m in line 220 denote? Is it a fixed value or can it take multiple possible values (since $m \in M$). Why must $k \geq m$? Should k change when m takes a different value?

We apologize for the misunderstanding. This is a typo that we have now fixed. It now reads $k \leq n$, where n is the number of agents and k is the number of clusters.

You pointed out that we were able to address most of your questions by providing the proofs asked for and running the additional experiments in Starcraft. We kindly wanted to ask whether you would be willing to increase your score?

Thank you for the response. The added StarCraft experiments is encouraging, and the enriched theoretical analysis is valuable. I would have raised my rating to 7, but since 7 is not a choice, I keep my rating of 6.

I must point out that there still exist minor errors in the manuscript. To name a few,

1. The "Table 3" in line 367 is referring to "Figure 3", which is actually a table
2. The caption of Figure 6 describes that "The brighter, the higher an agent’s contribution to a given value function", but there does not seem to be any brightness variation in the plot.

Also, please provide more explanation on the various settings in the StarCraft task.

Questions

Given that the quantification of what is considered desirable behavior is central to the proposed framework, can the authors provide additional insights into how the Desired Value Function (DVF) is defined and quantified across different environments and datasets?

We would like to point out that in the discussion of AI Alignment, a distinction between normative and technical alignment is often made [A]. Our work addresses solely the technical aspect of alignment, and it does not try to answer the question of which norms AI systems should align with. Specifically, we do not try to answer the question of what the correct Desired Value Function (DVF) for a given problem is. The example DVFs that we chose for the different environments are simply inspired by previous works and intuition. A possible option for setting DVFs is to crowdsource rankings of outcomes from human annotators [E]. 

The paper assumes consistent behavior from individual agents across multiple trajectories. Could the authors discuss the potential implications of this assumption in environments where agent behavior is more dynamic and context-dependent?

Our method can be extended to situations where agents’ behavior differs across multiple trajectories by splitting up the data of an individual agent into different sub-agents and treating each sub-agent as its own agent. This extension of our work does not require additional methodological contributions, and we see it as an interesting direction for future work, as also outlined in our conclusion.

The paper suggests the potential for utilizing data on undesired behavior more effectively. Could the authors elaborate on possible approaches for leveraging this type of data to enhance the imitation learning process?

Generally, data on undesired behavior could be used to disincentivize the policy from imitating undesired behavior or to gain further understanding of the environment dynamics. While some work exists in this field [B], this constitutes a highly interesting direction for future work.

How does the framework adapt to different environments, and what are the limitations when applying the proposed EV-Clustering and EV2BC methods to datasets that significantly differ from the ones used in the experiments?

We are not entirely sure we understand this question correctly, and kindly ask for potential clarification. Our framework applies to environments that can be modeled as multi-agent MDPs, and where a function is given that assigns values to collective outcomes. To further showcase the applicability of our approach, we have now conducted additional experiments in the Starcraft multi-agent environment (SMAC, [C]). SMAC is a widely used multi-agent coordination benchmark [C, D], which is partially observable, involves long-term planning, requires strong coordination, and is heterogeneous (as also described by Reviewer floZ). We find that also here, our method outperforms the baselines by a substantial margin, underlining the applicability of our method to diverse settings. Please consider the general response for details.

Citations:
[A] “Artificial Intelligence, Values and Alignment”, Gabriel, Minds and Machines, 2020
[B] “Model-based Offline Imitation Learning with Non-expert Data”, Park et al., arXiv, 2022
[C] "The Starcraft multi-agent challenge.”, Samvelyan et al., AAMAS 2019
[D] “Grandmaster level in StarCraft II using multi-agent reinforcement learning”, Vinayls et al., Nature 2019
[E] "Human-centred mechanism design with Democratic AI", Koster et al., Nature human behavior 2022

Dear reviewer, please let us know if we were able to address your concerns. Best wishes, the authors.