Multi-Agent Imitation Learning: Value is Easy, Regret is Hard

Summary

The paper studies the problem of an mediator coordinating the actions of a collection of agents by learning from the demonstrations of an expert. Unlike previous work the paper considers strategic deviations of the agents given the recommended actions instead of just matching the experts recommendations. It is shown the minimizing the standard performance measure (value gap) can lead to high regret in this setting. Finally, two algorithms are shown to minimize the regret under some assumptions.

Strengths

1-The paper makes a nice extension of prior work. It is reasonable to expect the agents to deviate to maximize their utility instead of just following the recommended actions. 2-I am not familiar with this area and the related work, but the paper has a nice logical flow. It starts by showing the difference between the performance measure of value and regret. Then it gives two algorithms to minimize the regret.

Weaknesses

1-The paper's presentation can be improved. So many theorems are followed by [proof] in blue which looks very sloppy. 2-It seems that the motivation of the paper has some similarities with incentivized exploration where the principle recommends an action but the agent is not forced to follow it, but I did not see it mentioned in the related work. Perhaps, there is even an extension of this work that connects to incentivized exploration.

Questions

1-In lines (123-124) it says "Critically, no agent observes the recommendations the mediator provides to another agent", but in the definition of regret between lines 50 and 51 we have the agent maximizing utility based on $\pi_{\sigma,\phi_i}$ which is the "joint agent policy induced by all agents other than i following σ’s recommendations". I don't understand how agent $i$ can find the strategy to maximize utility if he does not know the recommended actions and therefore $\pi_{\sigma,\phi_i}$ ? 2-Please see the points above under Weaknesses.

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

I think the limitations were properly addressed.

Summary

In this work, the authors 1.initiate the study of an alternative objective for multi-agent imitation learning termed the regret gap; 2. investigate the relationship between regret gap and the value gap; 3. provided 2 provably efficient algorithms to minimize the regret gap under coverage assumption on the expert or access to a queryable expert respectively.

Strengths

This work proposes to study a new alternative objective for multi-agent imitation learning, which is one step closer to downstream applications like routing a group of drivers. The paper contains both upper and lower bounds for regret gap optimization, along with detailed proofs. The presentation is generally clear, and the appendix is well-organized.

Weaknesses

Some assumptions are not explicitly made clear, such as the realizable expert, which can be relatively strong in practice. Also, in line 123, the requirement that no agent observes the recommendations the mediator provides to another agent sounds restrictive. Additionally, in line 146, it is required that identity mapping is in the class. It would be beneficial to have an extensive summary of assumptions in the appendix. Proposed algorithms seems like straight forward applications of existing algorithms, it would be nice to list the challenges when applying existing results. No experimentation or code is included with the work, making it difficult to examine whether the proposed algorithms are efficient in practice.

Questions

Q1: The notion of regret gap seems confusing to me. Is it related to the regret in online learning? Could you please explain the reasoning behind this naming? Q2: I assume realizability (i.e., the expert policy being contained in the learner's policy class) is required for your theorems to hold. Is that true? Q3: It would be helpful if the authors could state the challenges encountered when obtaining new theoretical results based on previous works. Q4: It would be helpful if there is an experimental plan to verify the algorithms, such as in simulated driver routing games. Minor suggestions: Is there a typo in line 147 that begins with "identity mapping ..."? Should that sentence end with "Φi"?

Rating

5

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

Same as weakness. Realizability is a limitation. As stated in limitations, this work focus on tabular MGs, while the computation and sample/query complexity is linear over the cardinality of the deviation class.

Summary

This paper addresses the challenge of a mediator coordinating a group of strategic agents by recommending actions. Unlike previous work that focuses on non-strategic users who follow recommendations blindly, this study explores strategic users who may deviate based on their personal utility functions. The authors find that the traditional approach of minimizing the value gap is insufficient for handling deviations by strategic agents, as it fails to account for recommendations outside the induced state distribution. To address this, the paper introduces the concept of the regret gap in multi-agent imitation learning (MAIL) within Markov Games, which explicitly considers potential deviations by agents. The authors demonstrate that under the assumption of complete reward and deviation function classes, achieving regret equivalence ensures value equivalence. However, value equivalence does not guarantee a small regret gap. To minimize the regret gap, the paper presents two efficient algorithms: MALICE, which operates under coverage assumptions, and BLADES, which requires access to a queryable expert. These contributions offer a novel perspective and tools for improving robustness in multi-agent coordination scenarios involving strategic agents.

Strengths

1. **Practical Relevance**: The paper addresses a significant real-world problem in multi-agent imitation learning, applicable in scenarios such as routing a group of drivers through a road network. 2. **Comprehensive Literature Review**: The literature review is thorough, contrasting the prevalent value gap-based approaches in empirical MAIL work with the novel focus on regret gap-based methods. 3. **Strong Motivation**: The paper is well-motivated, extending the existing framework to include strategic users and demonstrating the limitations of previous methods, thereby justifying the need for their proposed approach. 4. **Clarity and Readability**: The paper is well-written and easy to follow, making complex concepts accessible to the reader. 5. **Discussion of Assumptions and Limitations**: The authors provide a clear discussion of the assumptions and limitations of their work, adding depth to their analysis.

Weaknesses

1. **Algorithmic Novelty**: The proposed algorithms, MALICE and BLADES, may lack novelty. MALICE modifies behavior cloning with an importance sampling term, relying on the expert visiting every state with positive probability. BLADES involves querying the expert for action recommendations based on possible deviations. These approaches are not entirely new. 2. **Lack of Empirical Evaluation**: The algorithms have not been empirically evaluated, even in tabular Markov games. Their actual performance remains unknown, and the requirement to enumerate all user deviations may be impractical for real-world applications.

Questions

1. What is the core difference between Algorithm 1 and Algorithm 2? They both enumerate all possible user deviations. Then Algorithm 1 requires a full demonstration coverage assumption to ensure that the importance weights are finite, and Algorithm 2 requests the expert to provide recommendations under all possible user deviations. These two requirements seem to be similar. Could the authors provide more discussions about their core differences? 2. How strict is the Assumption 5.1 (u-recoverability)? This assumption states that all single-agent deviations only incur bounded advantage fluctuations, which seems to be too strict. 3. Is Figure 1 a good example? The Markov game in Figure 1 assumes that the expert only visits the states in the lower path, which contradicts Assumption 5.2 ($\beta$-coverage), I understand that Figure 1 is used to show why "regret is hard", but it is still confusing.

Rating

6

Confidence

3

Soundness

3

Presentation

4

Contribution

2

Limitations

The authors have adequately addressed the limitations of the proposed algorithms.

Summary

The paper studies the problem of multi-agent imitation learning (MAIL), with a focus on the differences and relationships between the value gap objective and the regret gap objective. The set-up consists of a multi-agent Markov game, where a central mediator attempts to coordinate the behaviors of the agents. Two potential objectives are compared: (1) Value gap objective: the coordinator tries to minimize the maximum deficiency among the agents in the overall value under the (joint) learning policy compared to the expert policy; (2) Regret gap objective: the coordinator minimizes instead the excess regret with respect to the expert policy, with regret defined as the maximum utility gain among the agents by deviating from the recommendation. The authors show that, under certain completeness assumptions of both the reward and the deviation classes, regret equivalence implies value equivalence; In contrast, value equivalence in general does not imply regret equivalence. These are in sharp contrast to the single-agent imitation learning setting, where the two notions become equivalent. While regret equivalence is hard in general, the authors provide two algorithms, MALICE and BLADES, under different assumptions on recoverability, policy coverage, and/or query-ability of expert. Both algorithms provide a linear (in horizon) bound on the regret gap, which matches the single agent case.

Strengths

[Originality and significance] The paper brings novel insights on MAIL in the sense that it characterizes how MAIL differs from SAIL in the regret perspective. Both the value-regret relationship results and the algorithms demonstrate the hardness in the multi-agent case due to lack of access to expert recommendations in counter-factual settings. In addition to the hardness results, the authors also provide algorithms that can be potentially useful to tackle the regret gap problem; this is valuable despite the still limited conditions. [Quality and clarity] The paper is generally well written and easy for me to follow. The results and their proofs seem correct.

Weaknesses

The main limitations of this paper lie in the significance of the results, both from the theoretical and the practical front. This is by no means to diminish the value of the results. What concerns me is two folds: (1) The main claims on the hardness of value gap and regret gap see mostly standard. The hardness due to inability to observe certain information in the multi-agent setting seems generally intuitive and unsurprising, and I think prior works (e.g., [1]) have to some extent demonstrated similar insights in related (albeit different) settings. The contribution seems more marginal in this respect. (I do perceive the contribution on the algorithmic side, though, as more substantial.) (2) On the practical side, I am not sure how the proposed methodology shall be applied to solving real world problems. Despite the theoretical nature of this paper, additional discussion on this can help make the paper more approachable to a larger audience. [1] Zhao, G., Zhu, B., Jiao, J., & Jordan, M. Online learning in Stackelberg games with an omniscient follower. International Conference on Machine Learning 2023.

Questions

- Line 172: I am not sure why Theorem 4.2 “proves that the completeness of the classes is *necessary*”. I suspect the word “necessary” is not in its mathematical meaning, since the theorem seems to only show that some condition on the classes is necessary. - Line 179: Why is this the italicized statement “surprising”? I in fact find it quite expected, especially given the discussion in Line 176-177 on the regret equivalence as a stronger notion. This really makes me think that I’m missing on some key intuition regarding why one could hope for the direct implication. - I would like to see more discussion on how restrictive the assumptions (in particular, the recoverability Assumption 5.1) actually are, e.g., when one could expect them to hold. This would help better bridge the gap between the theoretical results and the practice. Minor comments: - Line 146: I find this notation a bit unstandard $\Psi := \{\Psi_i\}_{I=1}^m$ (as a sequence of sets). Maybe the product is more appropriate? - I think $r$ and $f$ are used interchangeably when denoting the reward function. Nothing wrong, but I suppose they could be made consistent. - Line 183: Typo “even” => “even if”

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Addressed in Section 6 and Appendix A. The paper is of a theoretical nature.