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

Authors: jingwu  tang
gokul  swamy
fei  fang
zhiwei steven wu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 15:07:29

Abstract: We study a multi-agent imitation learning (MAIL) problem where we take the perspective of a learner attempting to *coordinate* a group of agents based on demonstrations of an expert doing so. Most prior work in MAIL essentially reduces the problem to matching the behavior of the expert *within* the support of the demonstrations. While doing so is sufficient to drive the *value gap* between the learner and the expert to zero under the assumption that agents are non-strategic, it does not guarantee robustness to deviations by strategic agents. Intuitively, this is because strategic deviations can depend on a counterfactual quantity: the coordinator's recommendations outside of the state distribution their recommendations induce. In response, we initiate the study of an alternative objective for MAIL in Markov Games we term the *regret gap* that explicitly accounts for potential deviations by agents in the group. We first perform an in-depth exploration of the relationship between the value and regret gaps. First, we show that while the value gap can be efficiently minimized via a direct extension of single-agent IL algorithms, even *value equivalence* can lead to an arbitrarily large regret gap. This implies that achieving regret equivalence is harder than achieving value equivalence in MAIL. We then provide a pair of efficient reductions to no-regret online convex optimization that are capable of minimizing the regret gap *(a)* under a coverage assumption on the expert (MALICE) or *(b)* with access to a queryable expert (BLADES).

Main paper: 
 introduction: 
 We consider the problem of a mediator learning to coordinate a group of strategic agents via recommendations of actions to take without knowledge of their underlying utility functions (e.g. routing a group of drivers through a road network). Given the difficulty of manually specifying the quality of a recommendation in such situations, it is natural to provide the mediator with data of desired coordination behavior, turning our problem into one of multi-agent imitation learning (MAIL, [27, 6, 19, 26, 11] ). In our work, we explore the nuances of a fundamental MAIL question:What is the right objective for the learner in a multi-agent imitation learning problem?We can begin to answer this question by exploring the following scenario: consider developing a routing application to provide personalized route recommendations (σ) to a group of users with joint policy π (e.g. the routing policy that underlies the recommendations provided in Google Maps [3] ). As usual in imitation learning (IL), we assume we are given access to demonstrations from an expert σ E (e.g. a past iteration of the application). We can imagine two kinds of users of our application (i.e. agents): non-strategic users who blindly follow the recommendations of our routing application and strategic users who will deviate from our recommendations if they have the incentive to do so under their (unknown) personal utility function (e.g. we recommend a long route to a busy driver). We use J i (π σ ) below to denote the value of the mediator's learned policy σ under the ith agent's utility.Case 1: No Strategic Agents. In the idealized situation where all agents in the population are perfectly obedient, we can essentially treat a MAIL problem as a single-agent IL (SAIL) problem over joint policies. It is therefore natural to use a direct extension of the well-studied value gap criterion from the SAIL literature [1, 28, 21, 24, 22, 23, 25, 16] to the multi-agent setting:max i∈[m] J i (π σ E ) -J i (π σ ).Intuitively, driving the value gap to 0 (i.e. achieving value equivalence in the terminology of [10] ) implies that along as long as all agents blindly follow our recommendations, we have learned a policy that performs at least as well as that of the expert from the perspective of any agent in the population. In our running routing application example, this means that if no driver deviates from the previous behavior, all drivers will be at least as happy as they were with the prior iteration of the application.Case 2: Strategic Agents. Of course for any MAIL problem where agents actually have agency, we need to account for the fact that agents may deviate from our recommendations if it appears beneficial to do so from their subjective perspective. Let us denote the class of deviations (i.e. policy modifications) for agent i as Φ i . Then, we can define the regret induced by the mediator's policy asR Φ (σ) := max i∈[m] max ϕi∈Φi (J i (π σ,ϕi ) -J i (π σ )),where ϕ i is a strategic deviation of agent i and π σ,ϕi is the joint agent policy induced by all agents other than i following σ's recommendations. Intuitively, regret captures the maximum incentive any agent in the population has to deviate from the mediator's recommendations. We can then compare this metric between the expert and learner policies to arrive at the notion of a regret gap [27] :R Φ (σ) -R Φ (σ E ).Driving the regret gap to zero (i.e. achieving regret equivalence) implies that even if agents are free to deviate, our learned policy is at least as good as the expert's from the perspective of an arbitrary agent in the population. In our preceding example, this means that despite the fact that they are not forced to follow our application's recommendations, all agents would have no more incentive to take an alternate route than they did under the previous iteration of the application.A simple decomposition allows us to show that a small value gap does not in general imply a small regret gap. Consider the performance difference between the learner's policy under all obedient (J i (π σ )) and a deviating ith agent (J i (π σ,ϕi )). We can decompose this quantity into the following: J i (π σ,ϕi ) -J i (π σ ) = (J i (π σ,ϕi ) -J i (π σ E ,ϕi )) (I: value gap under ϕi) + (J i (π σ E ,ϕi )) -J i (π σ E ))(II: expert regret under ϕi)+ (J i (π σ E ) -J i (π σ )) (III: SAIL value gap), where we use π σ E ,ϕi to denote agent joint behavior under expert recommendations and deviation ϕ i . Term III is the standard single-agent value gap (i.e. the performance difference under the assumption that no agents deviate). Term II is the expert's regret under deviation ϕ i (i.e. a quantity we cannot control). Thus, the difference between the regret gap and value gap objectives can be boiled down to Term I: J i (π σ,ϕi ) -J i (π σ E ,ϕi ). Observe that because of the state distribution shift induced by deviation ϕ i , minimizing Term III doesn't give us any guarantees with respect to Term 1. This underlies our key insight: regret is hard in MAIL as it requires knowing what the expert would have done in response to an arbitrary agent deviation. More explicitly, our contributions are three-fold:3. We provide a pair of efficient algorithms to minimize the regret gap under certain assumptions. While regret equivalence is hard to achieve in general as it depends on counter-factual expert recommendations, we derive a pair of efficient reductions for minimizing the regret gap that operate under different assumptions: MALICE (which operates under a coverage assumption) and BLADES (which requires access to a queryable expert). We prove that both algorithms can provide O(H) bounds on the regret gap, where H is the horizon, matching the strongest known results for the value gap in single-agent IL. See Table 1 for a summary of our regret gap bounds.Upper Bound (Matching) Lower Bound J-BC β-Coverage O 1 β ϵuH , Theorem 5.1 Ω 1 β ϵuH , Theorem 5.2 J-IRL β-Coverage O 1 β ϵuH , Theorem 5. 
related work: 
 Single-Agent Imitation Learning. Much of the theory of imitation learning focuses on the singleagent setting [14] . Offline approaches like behavioral cloning (BC, [15] ) reduce the problem of imitation to mere supervised learning. Ignoring the covariate shift in state distributions between the expert and learner policies can cause compounding errors [17, 21] and associated poor performance.In response, interactive IL approaches like inverse reinforcement learning (IRL, [1, 28] ) allow the learner to observe the consequences of their actions during the training procedure, preventing compounding errors [21] . However, such approaches can be rather sample-inefficient due to the need to repeatedly solve a hard RL problem [25, 16] . Alternative approaches include interactively querying the expert to get action labels on the learner's induced state distribution (DAgger, [17] ) or, assuming full coverage of the demonstrations, using importance weighting to correct for the covariate shift (ALICE, [20] ). Our BLADES and MALICE algorithms can be seen as the regret gap analog of the value gap-centric DAgger and ALICE algorithms, operating under the same assumptions.Multi-Agent Imitation Learning. The concept of the regret gap was first introduced in the exceptional work of Waugh et al. [27] , though their exploration was limited to Normal Form Games (NFGs), in contrast to the more general Markov Games (MGs) we focus on. Fu et al. [7] briefly consider the regret gap in Markov Games (MGs) but do not explore its properties nor provide algorithms for efficient minimization. Most empirical MAIL work [19, 12, 4, 26, 11] is value gap-based, while we take a step back and ask what the right objective is for MAIL in the first place.Inverse Game Theory. Another line of work focuses on inverse game theory in Markov Games [13, 8] , where the goal is to recover a set of utility functions that rationalize the observed agent behavior, rather than learning to coordinate from demonstrations. A detailed comparison between the goals of our work at that of inverse game theory provided in Appendix F. 
preliminaries: 
 We begin with the notation we will use in our paper. Throughout, we use ∆(X) denote the space of probability distribution over a set X . We will use ℓ to denote the loss function each algorithm optimizes, which should be thought of as a convex upper bound on the total variation distance TV.We use ℓ TV when the loss function is exactly the TV distance.Markov Games. We use M G(H, S, A, T , {r i } m i=1 , ρ 0 ) to denote a Markov Game (MG) between m agents. Here, H is the horizon, S is the state space, and A = A 1 × ... × A m is the joint action space for all agents. We use T : S × A → ∆(S) to denote the transition function. Furthermore, the reward (utility) function for agent i ∈ [m] is denoted by r i : S × A → [-1, 1]. Lastly, we use ρ 0 to denote the initial state distribution from which the initial state s 0 ∼ ρ 0 is sampled.Learning to Coordinate. Rather than considering the problem of learning individual agent policies in the MG, we take the perspective of a mediator who is giving recommendations to each agent to help them coordinate their behavior (e.g. a smartphone mapping application providing directions to a set of users). At each time step, the mediator gives each agent i a private action recommendation a i to take at the current state s. Critically, no agent observes the recommendations the mediator provides to another agent. We can represent the mediator as a Markovian joint policy σ ∈ Σ, where σ : S → ∆(A). We use σ(⃗ a|s) to denote the probability of recommending joint action ⃗ a in state s. We use π : S → ∆(A) to denote the joint policy that agents play in response to the mediator's policy. When agents exactly follow the mediator's recommendations, we denote their joint policy as π σ .A trajectory ξ ∼ π = {s h , ⃗ a h } h=1,...,H refers to a sequence of state-action pairs generated by starting from s 0 ∼ ρ 0 and repeatedly sampling joint action ⃗ a h and next states s h+1 from π and T for H - 1Q π i,h (s, ⃗ a) = E ξ∼π [ H t=h r i (s t , ⃗ a t )|s h = s, ⃗ a h = ⃗ a].We define advantage of an agent i to be the difference between its Q-value on a selected action and the V-value on the state, i.e.EQUATIONs). We also define the performance of a policy π from the perspective of agent i asJ i (π) = E s0∼ρ0 [E ξ∼π [ H t=1 r i (s t , ⃗ a t )|s = s 0 ]].Observe that performance is the inner product between the occupancy measure and the agent's reward function, i.e. J i (π) = H s,⃗ a ρ π (s, ⃗ a)r i (s, ⃗ a). Correlated Equilibria. We now introduce the notion of a correlated equilibrium (CE, Aumann [2] ). First, we define a strategy deviation ϕ i for the i-th agent as a map ϕ i : S × A i → A i . Intuitively, a strategy deviation captures how the agent responds to the current state of the world and the recommendation of the mediator -they can either obey (in which case ϕ i (s, a) = a) or defect (in which case ϕ i (s, a) ̸ = a). Let Φ i be the set of deviations for agent i, which is a subset of all possible deviations. We use Φ := {Φ i } m i=1 to denote deviations for all agents. We assume that for all i, the identity mapping ϕ i (s, a) ≡ a is in Φ i . We use π σ,ϕi to denote (ϕ i • π σ,i ) ⊙ π σ,-i : the joint agent policy induced by mediator policy σ being over-ridden by deviation ϕ i . We can now define a CE. Definition 3.1 (Regret and CE in General-Sum MGs). Let σ ∈ Σ be the mediator's policy in a Markov Game, and Φ i , i ∈ [m] be the deviation classes for each agent. Then, 1. We define the regret of a mediator policy σ to beEQUATION2. We say a mediator with policy σ induces an ϵ-approximate Correlated Equilibrium (CE) ifEQUATIONIntuitively, regret captures the maximum utility any agent can gain by defecting from the mediator's recommendation. A CE is an induced joint policy where no agent has a large incentive to deviate. 
on the relationship between the value gap and the regret gap: 
 As sketched above, we consider two potential objectives for the learner in MAIL: Definition 4.1 (Value Gap). We define the value gap between the expert's policy σ E and the learner's policy σ ∈ Σ as maxEQUATIONDefinition 4.2 (Regret Gap). We define the regret gap between the expert's policy σ E and the learner's policy σ ∈ Σ asEQUATION)Figure 1 : Under expressive enough reward function and deviation classes, regret equivalence implies value equivalence but not vice versa, making the regret gap a "stronger" objective than the value gap.We say that the learner's policy satisfies value / regret equivalence when the value / regret gap is 0. We now explore the relationship between the value and regret gap in MAIL, 1 summarized in Figure 1 . We use J i (π σ , f ) and R Φ (σ, f ) to denote the value/regret of policy σ under the reward function f .First, we show that if the reward function class and deviation class are both complete, then regret equivalence implies value equivalence. We say that the reward function class is complete when F = {S × A → [-1, 1]} (i.e.(R Φ (σ, f )-R Φ (σ E , f )) = 0), then value equivalence is also satisfied: sup f ∈F max i∈[m] (J i (π σ E , f ) -J i (π σ , f )) = 0. [Proof]Next, we prove that large classes are needed for this implication to hold true. Theorem 4.2 (Incomplete Classes). There exists an MG, an expert policy σ E , and a trained policy σ such that even though the regret equivalence is satisfied under the true reward function r, i.e.R Φ (σ, r) -R Φ (σ E , r) = 0, the value gap max i∈[m] (J i (π σ E , r) -J i (π σ , r)) ̸ = 0. [Proof]Together, these results tell us that with an expressive enough class of reward functions / deviations, regret equivalence is stronger than value equivalence. We now turn our attention to the converse.We now show a surprising result: value equivalence does not directly imply a low regret gap! In the worst case, value equivalence fails to provide any meaningful guarantees on the regret gap. This reveals a critical distinction between SAIL and MAIL not fully addressed in the prior work. Theorem 4.3. There exists a Markov Game, an expert policy σ E , and a learner policy σ, such that even occupancy measure of π σ exactly matches π σ E , i.e. ∀(s, ⃗ a), ρ πσ (s, ⃗ a) = ρ πσ E (s, ⃗ a) (i.e. we have value equivalence under all rewards), the regret gapR Φ (σ) -R Φ (σ E ) ≥ Ω(H). [Proof]We leave the details of the proof for this theorem in Appendix E.3. As visualized in Figure 2 , both the expert and learner policies only visit the states in the lower path s 2 , s 4 , ..., s 2H-2 . The trained policy perfectly matches the occupancy measure of the expert by taking identical actions in visited states s 2 , s 4 , ..., s 2H-2 . However, expert demonstrations lack coverage of state s 1 as it is unreachable by executing π E . This omission becomes critical when agent 1 deviates from the original policy, making s 1 unreachable with high probability. Consequently, the trained policy may perform poorly in s 1 , in stark contrast to the expert playing a CE under the true reward function. This example highlights the key difference between value equivalence and regret equivalence: the former only depends on states actually visited by the policy, while the latter depends on the counterfactual recommendations the learner would make at unvisited states in response to an agent deviations. Remark 4.1. As shown in Theorem 4.3, even if the learner has access to infinite samples on the equilibrium path from expert demonstrations, it is possible that the learner remains unaware of the expert's behavior in states unvisited by the expert (but reachable by the deviated agents joint policy). Thus, from an information theoretic perspective, it is impossible for the learner to minimize the regret gap without knowing how the expert would behave on those states. This demonstrates the fundamental difficulty of minimizing the regret gap, and thus, regret is 'hard' in MAIL. We therefore need a fundamentally new paradigm of MAIL algorithm to minimize the regret gap. Observe that s 1 is un-visited when all agents obediently follow σ E but is with probability1 under deviation ϕ 1 (ϕ 1 (s 0 , a 1 ) = ϕ 1 (s 1 , a 1 ) = a 2 ). This means that unless we know what the expert σ E would have recommended counter-factually in s 1 , we cannot minimize the regret gap.Given the deep connections between regret and correlated equilibrium discussed above, it is perhaps intuitive that if the expert σ E is playing a CE, a low regret gap means the learner is as well.Theorem 4.4 (Regret Gap Implies CE). If the expert policy σ E induces a δ 1 -approximate CE, and the learner policyσ satisfies R Φ (σ) -R Φ (σ E ) ≤ δ 2 , then σ induces a δ 1 + δ 2 -approximate CE. [Proof]Then, by combining our preceding result with Theorem 4.3, it follows that a low value gap does not imply that the learner is playing a CE.Corollary 4.5. There exists a Markov Game, an expert policy σ E , and a learner policy σ, such that σ E induces a δ 1 -approximate CE, andσ satisfies max i∈[m] (J i (π σ E ) -J i (π σ )) = δ 2 , σ induces a Ω(H)-approximate CE.Together, these results imply that if we are interested in inducing a CE amongst the agents in the population, the regret gap is a more suitable objective.Although we have shown that the value gap is a 'weaker' objective in some sense, in many real-world scenarios, the agents may be non-strategic. In these scenarios, minimizing value gap can be a reasonable learning objective. As we will demonstrate here, the natural multi-agent generalization of single-agent IL algorithms can efficiently minimize the value gap-hence, value is 'easy' in MAIL.Behavior Cloning (BC) and Inverse Reinforcement Learning (IRL) are two single-agent IL algorithms aimed at minimizing the value gap. By running these algorithms over joint policies, we can apply BC and IRL to the multi-agent setting, which we call Joint Behavior Cloning (J-BC) and Joint Inverse Reinforcement Learning (J-IRL). Doing so results in the same value gap bounds as in the single-agent setting. More details on of J-BC and J-IRL can be found in Appendix B.Theorem 4.6 (J-BC Value Gap Upper Bound). If J-BC returns a policy σ that satisfiesE s∼d πσ E [ℓ(σ E (s), σ(s))] ≤ ϵ, then the value gap max i∈[m] (J i (π σ E ) -J i (π σ )) ≤ O(ϵH 2 ). [Proof]Theorem 4.7 (J-IRL Value Gap Upper Bound). If J-IRL outputs a policy σ with moment-matching errorsup f ∈F E πσ E H h=1 f (s h , ⃗ a h ) -E πσ H h=1 f (s h , ⃗ a h ) ≤ ϵH, then the value gap max i∈[m] (J i (π σ E ) -J i (π σ )) ≤ O(ϵH). [Proof]As argued by Swamy et al. [21] , satisfying the conditions for either of the above theorems can be achieved oracle-efficiently via a reduction to no-regret online learning. We now turn our attention to sufficient conditions for there to exist efficient algorithms for minimizing the regret gap. 
efficient algorithms for minimizing the regret gap: 
 In our following analysis, we will make a recoverability assumption: that a single-step agents deviation could at most cost the expert a fixed constant. Assumption 5.1 (u-recoverability). We say that an MG is u-recoverable if the expert advantage function is bounded for all deviations, i.e. ∀s, ⃗ a, h, i, ϕ i , Aπ σ E ,ϕ i i,h (s, ⃗ a) ≤ u.Intuitively, a small value of u means that we're not in a problem where a single agent can deviate and a joint mistake happens that even the expert couldn't recover from for the rest of the episode.In the worst case, u is O(H). However, 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 driver chooses not to follow its recommendation, rather than u increasing as H increases.This assumption can be thought of natural multi-agent generalization of the standard recoverability assumption in SAIL [18, 21, 20] which is necessary and sufficient to avoid compounding errors while maintaining computational efficiency. While we define recoverability with respect to the actual reward function for implicitly, one can instead easily define it with respect to the worst-case reward function in a class (sup f ∈F ) -moment recoverability -as in [21] to avoid the need to know the ground truth set of agent reward functions r to bound u.In Section 4.2, we proved that for general MGs, J-BC and J-IRL don't give any guarantees on the regret gap. Fundamentally, without the ability to observe how the expert would have responded in the counter-factual state induced by a deviation, the learner cannot ensure that they match the expert's regret. We now explore two different sets of assumptions that give us this ability.In this section, we introduce a coverage assumption on the expert's state distribution d πσ E (s) which states that the expert visits every state with a positive probability. We will show that this assumption is sufficient to give a regret gap guarantee. The state coverage assumption is a common theoretical assumption in the analysis of learning in MDPs/MGs [5] and has been explored in SAIL [20] . Assumption 5.2 (β-coverage). There exists a constant β > 0 such that for the expert's policy σ E , it holds that d πσ E (s) ≥ β for all s.Intuitively, this assumption implies that in the infinite sample limit, there are no states where we are unsure what the expert would recommend. As discussed in Remark 4.1, without the ability to interactively query the expert, a coverage assumption is necessary because we cannot minimize the regret gap without knowing the expert mediator's actions in counter-factual states.We first show that under Assumption 5.2, J-BC and J-IRL get a (relatively weak) regret gap guarantee.We begin by analyzing joint behavioral cloning (J-BC). Theorem 5.1 (J-BC Regret Gap Upper Bound). Under Assumption 5.1 and Assumption 5.2, if the J-BC algorithm returns a policy σ that satisfiesE s∼d πσ E [ℓ(σ E (s), σ(s))] ≤ ϵ, then R Φ (σ) -R Φ (σ E ) ≤ O 1 β ϵuH .[Proof]We leave the proof in Appendix E.7. It is worth to note that although the dependency of H is linear under our recoverability assumption, we still need to pay for the term 1 β in our regret gap bound. In general, this term can grow exponentially with the horizon, making this guarantee relatively weak. We can show its tightness by slightly modifying the example in Theorem 4.3 to satisfy the assumptions. Theorem 5.2 (J-BC Regret Gap Lower Bound). There exists a Markov Game, an expert policy σ E , and learner policy σ such that σ E satisfies Assumption 5.1 and Assumption 5.2, σ achieves BC errorE s∼d πσ E [ℓ TV (σ E (s), σ(s))] ≤ ϵ, and R Φ (σ) -R Φ (σ E ) = Ω 1 β ϵuH .[Proof]We now prove analogous results for joint inverse reinforcement learning (J-IRL). Theorem 5.3 (J-IRL Regret Gap Upper Bound). Under Assumption 5.2 and Assumption 5.1 and with a complete reward function class F, if J-IRL returns a policy σ with moment-matching errorsup f ∈F E πσ E H h=1 f (s h , ⃗ a h ) H -E πσ H h=1 f (s h , ⃗ a h ) H ≤ ϵ, then R Φ (σ) -R Φ (σ E ) ≤ O 1 β ϵuH . [Proof]There are two interesting features of this theorem. The first is that we needed to assume that the reward function class is complete -otherwise, a small value gap can still translate to a large regret gap. The second is that the upper-bound for J-IRL matches that for J-BC, which is in stark contrast to the single-agent setting, where IRL enjoys linear-in-H guarantees with respect to the value gap [21] .We now show this is not an artifact of our analysis by providing a matching lower bound. Corollary 5.4 (J-IRL Regret Gap Lower Bound). There exists a Markov Game, an expert policy σ E , and a policy σ such that σ E satisfies Assumption 5.1 and Assumption 5.2, the trained policy σ gets moment-matching errorsup f ∈F E πσ E H h=1 f (s h , ⃗ a h ) H -E πσ H h=1 f (s h , ⃗ a h ) H ≤ ϵ, and R Φ (σ) -R Φ (σ E ) = Ω 1 β ϵuH . [Proof]This result implies another fundamental distinction between SAIL and MAIL: in contrast to the value gap, interactive training alone is not sufficient to effectively minimize the regret gap.Observe that the upper bounds for both J-BC and J-IRL include a dependence on the inverse of the coverage coefficient 1 β , which can be rather large for problems with long horizons or large action spaces. We now present an efficient algorithm that is able to avoid this dependence by extending the ALICE algorithm [20] to the multi-agent setting. ALICE is an interactive algorithm that, at each round, uses importance sampling to re-weight the behavior cloning (BC) loss based on the density ratio between the current learner policy and that of the expert. Accordingly, ALICE requires a full demonstration coverage assumption to ensure that these importance weights are finite. ALICE uses a no-regret algorithm to learn a policy that minimizes reweighed on-policy error, which guarantees a linear-in-H bound on the value gap under a recoverability assumption [20] .In Algorithm 1, we describe Multi-agent ALICE (MALICE), where adapt ALICE to the multi-agent setting (i.e. minimizing the regret gap). Specifically, we modify the ALICE loss function to include a maximum over all deviations. This gives usEQUATIONSinceE s∼d π E d π σ,ϕ i (s) d πσ E (s) ℓ(σ E (s), σ(s)) is a convex loss function, and the maximum of convex functions is still a convex function, we know that ℓ MALICE (σ, D E , σ) is a valid convex loss function with scales in [0, 1]. As a result, we can run an (arbitrary) no-regret online convex optimization (OCO) algorithm to efficiently optimize it, giving us an efficient reduction from regret gap minimization to no-regret online convex optimization under demonstration coverage.We now provide regret gap guarantees on the policy returned by MALICE. R Φ (σ) -R Φ (σ E ) ≤ O(ϵuH). [Proof]As promised, observe that adapting the importance sampling technique of Spencer et al. [20] to the multi-agent setting allows us to efficiently minimize the regret gap while avoiding an upper bound that depends on the coverage coefficient of the expert demonstrations.We now show that the bound in Theorem 5.5 is tight by constructing a matching lower bound. Theorem 5.6 (MALICE Regret Gap Lower Bound). There exists a Markov Game, an expert policy σ E that satisfies Assumption 5.1, and a trained policy σ that gets error ℓ TV,MALICE (σ, D E , σ) ≤ ϵ, andR Φ (σ) -R Φ (σ E ) = Ω (ϵuH) .We now turn our attention to an alternate assumption and the corresponding regret gap algorithm.For many problems, full coverage of expert demonstrations is not a reasonable assumption. Thus, we explore another natural assumption that allows us to observe expert recommendations at counterfactual states: access to a queryable expert. In their classic DAgger algorithm, Ross et al. [18] showed that access to a queryable expert allows one to eliminate the covariate shift that results from the difference between expert and learner induced state distributions. When we transition to the multi-agent setting, we can again use access to a queryable expert to handle yet another source of covariate shift: potential strategic deviations by agents in the population that push the learner outside of the support of the expert. We refer to our multi-agent extension of DAgger as BLADES.In each iteration of BLADES, we request the expert to provide recommendations under all possible agent deviations, before training on the aggregated data. More formally, we minimize the following sequence of loss functions:EQUATIONSimilar to MALICE, we know that the loss ℓ BLADES is also a valid convex loss function, and thus we can use a no-regret algorithm to efficiently minimize it. This gives us an efficient reduction from regret gap minimization to no-regret online convex optimization with access to a queryable expert.We now derive and upper and lower bounds on the regret gap of a policy returned by BLADES. Theorem 5.7 (BLADES Regret Gap Upper Bound). Under Assumption 5.1, if a policy σ satisfiesℓ BLADES (σ, σ) ≤ ϵ , then R Φ (σ) -R Φ (σ E ) ≤ O(ϵuH). [Proof]Algorithm 2 BLADES (Bend Learner, Aggregate Datasets of Expert Suggestions) 1: Input: Expert demonstrations D E . 2: Initialize learner σ (1) = arg min σ E s∼D E ℓ(σ E (s), σ(s)). Construct loss function ℓ (n) (σ) = ℓ BLADES (σ, σ (n) ).// Run arbitrary no-regret OCO algorithm on sequence of losses, e.g. FT(R)L: 12: σ (n+1) ← arg min σ∈Σ n j=1 ℓ (n) (σ). 13: end for 14: Return Best of σ (1:N ) on validation data.There exists a Markov Game, an expert policy σ E , and a trained policy σ such that σ E satisfies Assumption 5.1, σ achieves error ℓ TV,BLADES (σ, σ) ≤ ϵ, andR Φ (σ) -R Φ (σ E ) = Ω (ϵuH) . [Proof]In short, under either a demonstration coverage assumption or with access to a queryable expert, we are able to efficiently minimize the regret gap on a recoverable MAIL problem.As the algorithms we proposed are theoretical, we do not foresee any direct societal concerns resulting from this work. However, these theoretical algorithms can serve as a foundation for developing practical algorithms or provide guidance for designing practical algorithms in MAIL, which could be applied to real world problems in the future.Behavioral Cloning (BC, Pomerleau [15] ) treats the problem of imitation learning as supervised learning and performs maximum likelihood estimation with expert states as inputs and expert actions as labels. Unfortunately, as first analyzed by Ross and Bagnell [17] , the covariate shift between the training (expert states) and test (learner states) distributions can lead to compounding errors -i.e. a value gap that increases quadratically as a function of the horizon H. We note that this is not an artifact of the particular objective used in BC -as argued by Swamy et al. [21] , the same can be said for any offline imitation learning algorithm. J-BC extends BC to a multi-agent setting by learning a map from the state space S to the joint action space A. By adapting the analysis of Ross and Bagnell [17] and Swamy et al. [21] to the multi-agent setting, we establish a similar compounding error result for multi-agent behavior cloning in Theorem 4.6. There exists an example of MDP/MG that matches this bound, which shows that the bound is tight [21] .A popular family of online techniques for imitation learning is inverse reinforcement learning (IRL). Intuitively, IRL can be thought of as being similar to a GAN [9] but in the space of trajectories: the generator is the learner's policy coupled with a world model to actually give us trajectories, while the discriminator is trained between expert and learner trajectories and is used as a reward function for policy updates. More formally, IRL can be viewed as a two-player zero-sum game between a reward player and a policy player [21] . In each round, the reward player picks a reward function from F that maximizes the value gap between σ E and σ, while the policy player uses a reinforcement learning algorithm to learn a new policy in Σ that maximizes the performance under this reward function.Intuitively, as the learner can see policy rollouts during training procedure, they cannot be "surprised" by where their policy ends up at test time, removing the covariate shift issue that lies at the heart of compounding errors. More formally, Swamy et al. [21] proved that value gap for single-agent IRL algorithm is O(ϵH). We now generalize this result to the multi-agent setting. Accordingly, our policy class Σ becomes one of joint policies. We use a reward function class F that is identical for all agents (i.e. we assume the the game is common payoff). Then, by following the proof in Swamy et al. [21] , we prove a O(ϵH) value gap bound for multi-agent IRL algorithm in Theorem 4.7.Algorithm 3 J-IRL 1: Input: expert demonstration D E , Policy class Σ, Reward class F 2: Set σ (1) ∈ Σ 3: for n = 1 to N do 4: f (n) ← arg max J(π σ E , f ) -J(Unif(π σ (1:n) ), f ) + R(f )// Treat it as a single-agent RL problem over joint action space under reward function f (n) 5:σ (n+1) ← MaxEntRL(r = f (n) ) 6: end for 7: Return best σ (n) on validationWe introduce a lemma which will be very useful in the analysis under the recoverability assumption. It is used in the analysis in the single-agent DAgger [18] and ALICE [20] , and we will also use it in the analysis for MAIL. It shows that if the policy achieves small on-policy error, then, with recoverability assumption, the value gap is linear over H. Lemma C.1. [Ross et al. [18] ] For agent joint policy π 1 and π 2 , if the advantage of π 1 is bounded under the true reward function ∀i, h, s, ⃗ a, |A π1 i,h (s, ⃗ a)| ≤ u, and π 2 get on-policy errorE s∼d π 2 [ℓ(π 1 (s), π 2 (s))] ≤ ϵ, then |J i (π 1 ) -J i (π 2 )| ≤ ϵuH, ∀i ∈ [m].Proof. Via the performance difference lemma, ∀i ∈ [m], we haveEQUATIONFor our analysis of MALICE and BLADES, we will let π 1 be any deviated expert policy π σ E ,ϕi and π 2 be the deviated trained policy π σ,ϕi under the same deviation.For single-agent IL we prove that the regret gap and the value gap are equivalent. Theorem D.1 (Equivalence in Single-Agent IL). For single-agent MDP, regret gap and value gap are equivalent to each otherJ(π σ E ) -J(π σ ) = R Φ (σ) -R Φ (σ E )Proof. For single-agent MDP, we ignore the index i in the following proof. A strategy deviation in single-agent MDP is equivalent to taking another policy, because there are no other agents affecting the dynamics of the agent. We haveR Φ (σ) = max ϕ∈Φ (J(π σ,ϕ ) -J(π σ )) = J(π * ) -J(π σ )where π * is the optimal policy under the true reward function. Similarly, we haveR Φ (σ E ) = J(π * ) -J(π σ E ) Therefore, R Φ (σ) -R Φ (σ E ) = (J(π * ) -J(π σ )) -(J(π * ) -J(π σ E )) = J(π σ E ) -J(π σ )In single-agent MDPs, the dynamics are fixed because no other agents affect the agent's dynamics, and therefore, the regret gap is equivalent to the value gap. Proof. We prove the lemma by showing that the occupancy measures of π σ and π σ E exactly match, i.e. ρ πσ (s, ⃗ a) = ρ πσ E (s, ⃗ a) for every (s, ⃗ a). Consider a cooperative reward functionf s ′ ,⃗ a ′ = -1(s = s ′ , ⃗ a = ⃗ a ′ ).Under f s,⃗ a , we have J(π σ ) = -Hρ πσ (s, ⃗ a), J(π σ E ) = -Hρ πσ E (s, ⃗ a). The maximum value performance the expert/learner can get after deviation is 0 because the reward function is non-positive. (0 can be achieved by simply not taking ⃗ a on s).Therefore R Φ (σ) = 0 -(-Hρ πσ (s, ⃗ a)) = Hρ πσ (s, ⃗ a), R Φ (σ E ) = 0 -(-Hρ πσ E (s, ⃗ a)) = Hρ πσ E (s, ⃗ a).Since R Φ (σ) -R Φ (σ E ) = 0, we know that ρ πσ (s, ⃗ a) = ρ πσ E (s, ⃗ a). This implies that the occupancy measures of two policies exactly match. As a result,sup f ∈F max i∈[m] (J i (π σ E , f ) -J i (π σ , f )) = 0 E.2 Proof of Theorem 4.2Proof. We can construct an example in normal form games, in which there are mulitple CEs with different pay-offs. We can let the σ E plays CE 1 and σ plays CE 2. Therefore, although the regret gapR Φ (σ) -R Φ (σ E ) = 0, the value gap max i∈[m] (J i (π σ E ) -J i (π σ )) ̸ = 0.The NFG in Figure 5 is an example, where (a 1 , a 1 ) and (a 2 , a 2 ) are two CEs with different values.Proof. We prove the theorem by constructing such a Markov Game and policies that can get Ω(H) regret gap. For simplicity, we construct a two-player cooperative game where the reward is identical for all agents. Agents can not visit the same state at different time steps. These allow us to omit the index i in the reward function in the proof. The notation a i a j is used to represent the action pair (a i , a j ).The transition dynamics are illustrated in Figure 2 , and the rewards are action free. The reward function r(s 3 ) = r(s 5 ) = ... = r(s 2H-3 ) = 1, with all other states yielding a reward of 0. Each agent has an action space A i = {a 1 , a 2 , a 3 }.The expert policy σ E satisfies σ E (a 1 a 1 |s 0 ) = 1.σ E (a 3 a 3 |s 1 ) = 1. Action on all other states don't matter because the transition and the reward would be the same. The trained policy σ satisfies σ(a 1 a 1 |s 0 ) = 1, σ(a 1 a 1 |s 1 ) = 1, and plays the same as the expert in all other states.It is not hard to verify that σ E plays a CE under this reward function, which meansR Φ (σ E ) = 0The worst deviation for σ is to deviate action of agent 1 from playing a 1 to a 2 on both s 0 and s 1 . We getEQUATION) Thus, we know that σ induces a δ 1 + δ 2 -approximate CE.Proof. For any i, we can view multi-agent problem as a single agent MDP over the joint action space under reward function r i . Following the proof in Ross and Bagnell [17] , Swamy et al. [21] , we can proveJ i (π σ E ) -J i (π σ ) ≤ O(ϵH 2 ). Therefore, max i∈[m] (J i (π σ E ) -J i (π σ )) ≤ O(ϵH 2 ).Proof. For any i,J i (π σ E ) -J i (π σ ) ≤ sup f ∈F E ξ∼πσ E H h=1 f (s h , ⃗ a h ) -E ξ∼πσ H h=1 f (s h , ⃗ a h ) ≤ ϵH Therefore, max i∈[m] (J i (π σ E ) -J i (π σ )) ≤ O(ϵH).Proof. With Assumption 5.2, we know thatE s∼d πσ [ℓ(σ E (s), σ(s))] ≤ 1 β E s∼d πσ E [ℓ(σ E (s), σ(s))] ≤ ϵ β By Lemma C.1, we get J i (π σ E ) -J i (π σ ) ≤ O 1 β ϵuHFor any deviation ϕ i , Taking the maximum over i, ϕ i , we getEQUATIONR Φ (σ) -R Φ (σ E ) ≤ O 1 β ϵuH E.8 Proof of Theorem 5.2Proof. We prove the theorem by constructing such a Markov Game policies that can get Ω( 1 β ϵuH) regret gap. We consider the two-player cooperative game similar to the example in Theorem 4.3. What we need to do is to slightly modify the MG and the policy to satisfy Assumption 5.1 and Assumption 5.2. The rewards are action free. Let u ′ = ⌊u⌋, the reward function r(s 3 ) = r(s 5 ) = ... = r(s 2u ′ -3 ) = 1, with all other states yielding a reward of 0. The transition of the MG is shown in Figure 3 . We know that the value is between [0, u ′ ] for any policy, which means Assumption 5.1 is satisfied.Let σ E be the policy that σ E (a 1 a1 |s 0 ) = 1 -2β, σ E (a 2 a 1 |s 0 ) = 2β, σ E (a 2 a 1 |s1) = 1 2 , σ E (a 3 a 3 |s 1 ) = 12 . Action at all other states doesn't matter because the transition and the reward would be the same. σ E satisfies Assumption 5.2.Let trained policy σ be the policy that σ(a 1 a1 |s 0 ) = 1 -2β, σ(a 2 a 1 |s 0 ) = 2β, σ(a 2 a 1 |s1) = 1 2 , σ(a 1 a 1 |s1) = ϵH 2β , σ(a 3 a 3 |s 1 ) = 1 2 -ϵH 2β .σ and σ E only differs at s 1 . Behavior cloning error of σ satisfiesE s∼d πσ E [ℓ TV (σ E (s), σ(s))] ≤ 2β • ϵH 2β • 1 H = ϵIt is not hard to verify, the worst deviation for π σ E is to deviate action of agent 1 at s 0 from playing a 1 to a 2 , and thusR Φ (σ E ) = 1 2 (1 -2β)(u ′ -2)The worst deviation of π σ is to deviate action of agent 1 from playing a 1 to a 2 at s 0 and s 1 .R Φ (σ) = 1 2 (1 -2β)(u ′ -2) + ϵH 2β (u ′ -2) Therefore, the regret gap R Φ (σ) -R Φ (σ E ) = ϵH 2β (u ′ -2) = Ω( 1 β ϵuH).E.9 Proof of Theorem 5.3Proof. We prove it by showing that under complete reward function class F, low IRL error will imply low BC error, and then apply Theorem 5.1.EQUATIONTherefore, we have s,⃗ a |ρ πσ E (s, ⃗ a) -ρ πσ (s, ⃗ a)| ≤ ϵ.s,⃗ a Proof. Consider the same example in proof of Theorem 5.2 with parameter ϵ ′ . In the example, the only difference between the occupancy measures of two policies are ρ(s, ⃗ a) at state s 1 . Therefore,|ρ πσ E (s, ⃗ a) -ρ πσ (s, ⃗ a)| = s,⃗ a |d πσ E (s)σ E (⃗ a|s) -d πσ (s)σ(⃗ a|s)| = s,⃗ a |d πσ E (s)σ E (⃗ a|s) -d πσ E (s)σ(⃗ a|s) + d πσ E (s)σ(⃗ a|s) -d πσ (s)σ(⃗ a|s)| ≥ s,⃗ a (|d πσ E (s)σ E (⃗ a|s) -d πσ E (s)σ(⃗ a|s)| -|d πσ E (s)σ(⃗ a|s) -d πσ (s)σ(⃗ a|s)|) =E s∼d πσ E [TV(σ E (s), σ(s))] - s |d πσ E (s) -d πσ (s)| =E s∼d πσ E [TV(σ E (s), σ(s))] -EQUATIONLetϵ ′ = 1 2 ϵ. Then the regret gap R Φ (σ) -R Φ (σ E ) = ϵH 4β (u ′ -2) = Ω( 1 β ϵuH).E.11 Proof of Theorem 5.5Proof. From the definition of ℓ MALICE , we knowEQUATIONFrom Lemma C.1, we know that for all i, ϕ i , we haveJ i (π σ,ϕi ) -J i (π σ E ,ϕi ) ≤ O(ϵuH) And J i (π σ E ) -J i (π σ ) ≤ O(ϵuH)Therefore, we getEQUATIONTaking the maximum over i, ϕ i , we getR Φ (σ) -R Φ (σ E ) ≤ O (uϵH)E.12 Proof of Theorem 5.6Proof. We prove the theorem by constructing such a Markov Game policies that MALICE can get Ω(ϵuH) regret gap. We consider a single-agent MDP shown in Figure 4 . The rewards are action free. Let u ′ = ⌊u⌋, the reward function r(s 1 ) = r(s 3 ) = ... = r(s 2u ′ -3 ) = 1, with all other states yielding a reward of 0. The transition of the MDP is shown in Figure 4 . We know that the value is between [0, u ′ ] for any policy, and thus Assumption 5.1 is satisfied.Let σ E be the policy that σ E (a 1 |s 0 ) = 1 -β, σ E (a 2 |s 0 ) = β. Action at all other states doesn't matter because the transition and the reward would be the same. It is easy to verify that σ E satisfies Assumption 5.2.Let trained policy σ be the policy that σ(a 1 |s 0 ) = 1 -β -Hϵ, σ(a 2 |s 0 ) = β + Hϵ. σ and σ E only differ at s 0 . Now we verify that ℓ TV,MALICE (σ, D E , σ) ≤ ϵ.Since σ and σ E only differ at state s 0 , and d π σ,ϕ i (s 0 ) = 1 for any i, ϕ i , we have thatE s∼d πσ E d π σ,ϕ i d πσ E TV(σ E (s), σ(s)) = E s∼d π σ,ϕ i [TV(σ E (s), σ(s))] ≤ 1 H • Hϵ = ϵ Therefore, ℓ TV,MALICE (σ, D E , σ) = max i∈[m] max ϕi E s∼d πσ E d π σ,ϕ i d πσ E TV(σ E (s), σ(s)) ≤ ϵIt is not hard to verify, the worst deviation for π E is to deviate action on s 0 from playing a 2 to a 1 , and thusR Φ (π E , r) = β(u ′ -1)the worst deviation for π E is also to deviate action on s 0 from playing a 2 to a 1 .R Φ (π, r) = (β + ϵH)(u ′ -1)Therefore, the regret gap R Φ (π) -R Φ (π E ) = ϵ(u ′ -1)H = Ω(ϵuH). Proof. From the definition of ℓ BLADES , we knowEQUATIONFrom Lemma C.1, we know that for all i, ϕ i , we haveJ i (π σ,ϕi ) -J i (π σ E ,ϕi ) ≤ O(ϵuH) And J i (π σ E ) -J i (π σ ) ≤ O(ϵuH)Therefore, we getEQUATION) Taking the maximum over i, ϕ i , we getR Φ (σ) -R Φ (σ E ) ≤ O (ϵuH)E.14 Proof of Theorem 5.8Proof. Let MDP, expert policy σ E and the trained policy σ be the same example in the proof of Theorem 5.6.Since σ and σ E only differ at state s 0 , and d π σ,ϕ i (s 0 ) = 1 for any i, ϕ i , we haveE s∼d π σ,ϕ i [TV(σ E (s), σ(s))] ≤ 1 H • Hϵ = ϵTherefore, the trained policy π satisfiesℓ TV,BLADES (σ, σ) = max i∈[m] max ϕi E s∼d π σ,ϕ i [TV(σ E (s), σ(s))] ≤ ϵ The regret gap R Φ (σ) -R Φ (σ E ) = ϵ(u ′ -1)H = Ω(ϵuH).F Comparison with Goktas et al. [8] Recent work Goktas et al. [8] worked on similar problem as ours. We will highlight some of the difference between two works.First, the learning goals are different. They focus on a problem of inverse game theory, where the goal is to recover a reward function to rationalize the expert's behavior, i.e. the expert policy plays Justification: This is a theory paper. We do not include experiments for the algorithms.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: We conform to the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: We discuss broader impacts in Appendix A.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper is a theory paper and does not pose such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This is a theory paper and it does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.We initiate the study of the regret gap for MAIL in Markov Games. Unlike the value gap -the standard objective in single-agent IL -the regret gap captures the fact that agents in the population may choose to deviate from the mediator's recommendations. The shift from value to regret gap captures what is fundamentally different about the SAIL and the MAIL problems.We investigate the relationship between regret gap and the value gap. We show that under the assumption of complete reward and deviation function classes, regret equivalence implies value equivalence. However, we also prove that value equivalence provides essentially no guarantees on the regret gap, establishing a fundamental limitation of applying SAIL algorithms to MAIL problems.We prove in Appendix D that the value and regret gaps are equivalent in single-agent IL.ConclusionOur work focuses on the core question of what fundamentally distinguishes multi-agent IL problems from single-agent ones. In short, our answer is that on problems with strategic agents that are not mere puppets, we need to deal with another source of distribution shift: deviations by agents in the population. This new source of distribution shift cannot be efficiently controlled with environment interaction (i.e. inverse RL). Instead, we need to be able to estimate how the expert would act in counter-factual states. Based on this core insight, we derive two reductions that are able to minimize the regret gap under a coverage or queryable expert assumption. We leave the development and implementation of practical approximations of our idealized algorithms to future work. 
 
 Appendix:  


Decision: This paper considers the problem of imitation learning in multi-agent settings, and provides basic theoretical foundations, including:
1) They compare two potential objectives, the value gap and regret gap, and show that while regret equivalence implies value equivalence, value equivalence does not imply regret equivalence in general.
2) While regret equivalence can be harder to achieve in general, they new provide algorithms that achieve this under additional assumptions (either coverage or access to a queryable expert).

Reviewers found the problem this paper studies to be well-motivated and important, and generally felt that the paper makes a reasonable first attempt at providing basic foundations for multi-agent IL. They also found the paper to be clear and well-written, with a nice and relatively complete story. The main limitation highlighted by the reviewers was limited technical depth/surprise factor in the main results. I believe this is OK, given that the theoretical formulation is itself novel and important, but for the final revision I recommend better highlighting the technical challenges to the extent that this is possible.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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”
limitations: limitations: Addressed in Section 6 and Appendix A. The paper is of a theoretical nature.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: The authors have adequately addressed the limitations of the proposed algorithms.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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"?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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.
limitations: limitations: I think the limitations were properly addressed.

Comments: comment: Thank you for your clarification. I increase the score to 6.