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

Thank you for taking the time to review our submission! Please find our replies to your questions/comments below.

Response to W1: We designed the [proof] link after each theory statement to add a hyperlink to the proof in the appendix. This allows readers to easily navigate from the theorem statements to the corresponding proofs and back from the proofs to the theorems. We will follow the reviewer’s suggestion and make it clear in the final version by adding “detailed proof can be found in Sec X in Appendix” along with the hyperlink.

Response to W2: We agree that incentivized exploration is similar to our problem in that agents can choose to deviate from the recommendations. However, the goal of MAIL in this paper is to learn a mediator policy from an expert mediator to coordinate the agents. In contrast, the goal of incentivized exploration is to provide recommendations to agents to incentivize exploration rather than exploitation, where there is no access to an expert mediator.

Answer to Q1: The goal of minimizing the regret gap in this paper is to learn a mediator who coordinates the agents, ensuring that the agents have no incentive to deviate from the recommendations. This means that we focus on learning the mediator's policy, not the agents' best response policy. By minimizing the regret gap, we ensure that the maximum additional gain agents can achieve with any possible deviation is similar to the additional gain they would get by deviating from the expert mediator. Regarding the agents, they can maximize their utility by treating other agents as part of the environment, and set the state as $(s,a)$, where $a$ is the recommendation from the mediator, and use a reinforcement learning algorithm to learn a mapping from $S\times A\rightarrow A$.

Thank you for taking the time to review our submission! Please find our replies to your questions/comments below.

Regarding the assumptions:

1. The theorems in this paper do not require realizability to hold. However, if we want to further analyze the computational complexity of the algorithm (which would be an additional theorem not stated in the paper), realizability can simplify the analysis, as discussed in single-agent imitation learning (see Appendix B.3 of [21]).

2. In game theory literature, it is common for agents to observe only the recommendations provided to themselves in the study of (coarse) correlated equilibrium. This scenario is also typical in practice. For example, a route planning application provides recommendations to many drivers, but each driver only receives their own recommendation. It is reasonable that they cannot see whether the app advises other drivers to turn left or go straight.

3. Identity mapping lies in the class is not an assumption, in the sense that it simply means that the agent can choose to fully follow the recommendation of the mediator.

Regarding the novelty of the algorithms: Our proposed algorithms are indeed built on the previous approaches taken by algorithms like DAgger and ALICE (as the names suggest). However, we have to develop a non-trivial extension of these algorithms for minimizing the regret gap. While the natural extensions of DAgger and ALICE are able to minimize the value gap in MAIL, they fail to minimize the regret gap. To minimize the regret gap, it is necessary to visit the counterfactual states visited by the deviated policy, and this aspect of exploration is our novel contribution.

Regarding the experiments: We choose to focus on theory because we believe there are substantial basic theoretical questions that remain unanswered. Our primary contribution is to advance the theoretical understanding of the objective formulation for MAIL and its implications for algorithm design, which, to the best of our knowledge, have not been addressed by prior works.

Answer to Q1: We adopt this naming from [27], where 'regret' is defined in normal form games (NFG), the standard matrix game in the game theory literature, which can be viewed as an one step ($H=1$) markov game with only a single state. The term 'regret' does not directly relate to the concept of regret in online learning. This naming aims to capture the agent's 'regret' for not deviating from the mediator's recommendations.

Answer to Q2: As mentioned earlier, the theorems in this paper do not require realizability to hold. However, if we want to further analyze the computational complexity of the algorithm (which would be an additional theorem not stated in the paper), realizability can simplify the analysis, as discussed in single-agent imitation learning (see Appendix B.3 of [21]).

Answer to Q3: Thank you for your interest in the challenges we encountered during this project. The biggest challenge is that we found out without certain assumptions, all natural extensions of the single-agent IL algorithms (e.g. DAgger, IRL algorithms, BC) can only minimize the value gap, but fail to provide any guarantees for minimizing the regret gap. That means we cannot get any theoretical results for any of those algorithms and have to adopt new assumptions and develop new algorithms to minimize the regret gap.

Answer to Q4: As mentioned earlier, we choose to focus on theory because we believe there are substantial basic theoretical questions that remain unanswered. Our primary contribution is to advance the theoretical understanding of the objective formulation for MAIL and its implications for algorithm design, which, to the best of our knowledge, have not been addressed by prior works. As for the algorithms, we believe the theoretical results provide insights into designing a practical MAIL algorithm. The key takeaway is that simply extending a single-agent IL algorithm straightforwardly is insufficient to minimize the regret gap (as all previous empirical works have done, to the best of our knowledge). In the multi-agent setting, additional efforts are needed to minimize the regret gap. This includes interactively querying the expert on counterfactual states or applying importance weighting to the expert demonstrations based on the state distribution induced by the deviated policies.

For Minor Suggestions: Thank you for pointing that out. We will fix this typo.

Thank you for taking the time to review our submission! Please find our replies to your questions/comments below.

Response to W1: Our proposed algorithms are indeed built on the previous approaches taken by algorithms like DAgger and ALICE (as the names suggest). However, we have to develop a non-trivial extension of these algorithms for minimizing the regret gap. While the natural extensions of DAgger and ALICE are able to minimize the value gap in MAIL, they fail to minimize the regret gap. To minimize the regret gap, it is necessary to visit the counterfactual states visited by the deviated policy, as shown in lines 5-7 of both Algorithm 1 and Algorithm 2, and this aspect of exploration is our novel contribution.

Response to W2: We choose to focus on theory because we believe there are substantial basic theoretical questions that remain unanswered. Our primary contribution is to advance the theoretical understanding of the objective formulation for MAIL and its implications for algorithm design, which, to the best of our knowledge, have not been addressed by prior works. As for the algorithms, we believe the theoretical results provide insights into designing a practical MAIL algorithm. The key takeaway is that simply extending a single-agent IL algorithm straightforwardly is insufficient to minimize the regret gap (as all previous empirical works have done, to the best of our knowledge). In the multi-agent setting, additional efforts are needed to minimize the regret gap. This includes interactively querying the expert on counterfactual states or applying importance weighting to the expert demonstrations based on the state distribution induced by the deviated policies.

Answer to Q1: Although the theoretical proofs of BLADES and MALICE are similar, they represent two distinct paradigms of IL algorithms. To run BLADES, you will need to have access to a queryable expert (similar to DAgger), whereas to run MALICE, with a coverage assumption, you only need to use importance weighting on expert demonstrations without requiring additional interaction with the expert.

Answer to Q2: As stated in line 224, a small value of $u$ indicates that we are not in a scenario where a one-time joint mistake occurs, and a single agent deviates, and even the (deviated) expert couldn’t recover for the rest of the episode. The recoverability assumption is common in single-agent imitation learning (SAIL), as seen in DAgger [18] and ALICE [20], and ours can be viewed as a natural extension to the multi-agent setting. We believe that in many cases $u$ is small. For instance, in the route planning example, at some point many cars may miss their turns/intersections/exits, but this can be recovered within a constant time, even when a single agent chooses not to follow its recommendation, rather than $u$ increasing as $H$ increases.

Answer to Q3: Figure 1 illustrates the dynamics, while Assumption 5.2 is about the expert policy. For further details, you could check the proof of Theorem 5.2 in Appendix E.7. The example in the proof satisfies $\beta$-coverage, and the dynamics is the same as it is in Figure 1.

Thank you for taking the time to review our submission! Please find our replies to your questions/comments below.

Regarding the significance of theoretical results: We thank the reviewer for bringing up paper [1]. [1] shows that in the repeated Stackelberg game, not being able to observe the follower's response will result in higher regret. At a very high level, one can say that the hardness in MAIL in this paper comes from the inability of observing the expert’s recommendations at counterfactual states if any agent deviates. However, we would like to emphasize that the fundamental reasons are very different from [1]: the hardness of minimizing the regret gap in MAIL mainly comes from the counterfactual states, that is, the state distribution shift brought by deviations. This only becomes a problem when (1) there are multiple agents instead of a single agent, and (2) the game is a Markov Game with multiple states and a long horizon. (For normal form games where $|S|=H=1$, [27] can efficiently minimize the regret gap.) In [1] that the reviewer refers to, the setting is a repeated Stackelberg game, which does not have similar issues. Additionally, the setting is different in that we aim to learn a mediator policy given the expert mediator, while that paper aims to achieve regret minimization for players in a cooperative game. Furthermore, in MAIL, we are the first to point out such hardness related to the regret gap, which has been ignored by the MAIL community for a long time. For these reasons, we argue that the theoretical contribution of this paper is substantial and the significance is not impacted by the results in [1]. We are open to exploring the connection if the reviewer can elaborate further.

Regarding practical implications: We choose to focus on theory because we believe there are substantial basic theoretical questions that remain unanswered. Our primary contribution is to advance the theoretical understanding of the objective formulation for MAIL and its implications for algorithm design, which, to the best of our knowledge, have not been addressed by prior works. As for the algorithms, we believe the theoretical results provide insights into designing a practical MAIL algorithm. The key takeaway is that simply extending a single-agent IL algorithm straightforwardly is insufficient to minimize the regret gap (as all previous empirical works have done, to the best of our knowledge). In the multi-agent setting, additional efforts are needed to minimize the regret gap. This includes interactively querying the expert on counterfactual states or applying importance weighting to the expert demonstrations based on the state distribution induced by the deviated policies.

Answer to Q1: Thank you for pointing that out. The word "necessary" is used in its natural language sense and not in its mathematical meaning. We will fix that to avoid confusion.

Answer to Q2: We use the word "surprising" to highlight our findings:

1. Regret gap and value gap are the same in the single-agent setting (see Appendix D), but value equivalence does not imply regret equivalence in the multi-agent setting.
2. Not only does value equivalence not directly imply regret equivalence, but it also cannot provide any guarantees for the regret gap, which can be arbitrarily large.

Answer to Q3: As stated in line 224, a small value of $u$ indicates that we are not in a scenario where a one-time joint mistake occurs, and a single agent deviates, and even the (deviated) expert couldn’t recover for the rest of the episode. The recoverability assumption is common in single-agent imitation learning (SAIL), as seen in DAgger [18] and ALICE [20], and ours can be viewed as a natural extension to the multi-agent setting. We believe that in many cases $u$ is small. For instance, in the route planning example, at some point many cars may miss their turns/intersections/exits, but this can be recovered within a constant time, even when a single agent chooses not to follow its recommendation, rather than $u$ increasing as $H$ increases.

Regarding Minor Comments:

[1] In the standard game theory notion, a correlated equilibrium (CE) considers the deviation of a single agent and thus does not require defining deviations as a product of individual deviations. Therefore, we use the current notation to avoid confusion.

[2] We inherit this notation from the single-agent IL literature, where they usually let $r$ denote the true reward function, and $f$ denotes any possible reward function in the reward function class.

[3]Thank you for pointing this out. We will fix this typo.