Multi-Agent Imitation Learning: Value is Easy, Regret is Hard
Authors: Jingwu Tang
Gokul Swamy
Fei Fang
Steven Wu
Venue: NeurIPS 2024 poster (2024)
Keywords: imitation learning
multi-agent reinforcement learning
Primary area: reinforcement_learning

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

Multi-Agent Imitation Learning: Value is Easy, Regret is Hard
Jingwu Tang Carnegie Mellon University j jingwutangOcmu edu
Gokul Swamy Carnegie Mellon University
gswamyOcmu.
Fei Fang
Zhiwei Steven Wu
Carnegie Mellon University feif feifangecmu. edu
Carnegie Mellon University zstevenvu@cmu.cm edu
Abstract
We study multi-agent imitation learning (MAIL) problem where take the perspective of a learner attempting to coordinate a group of agents based on demon- strations 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 demonstra- tions. 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 because strategic deviations can depend on counterfactual quantity: the coordinator's '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 regrel 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 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 pair of efficient reductions to no-regret online convex optimiza- tion that capable of minimizing the regret gap (a) under coverage assumption on the expert (MALICE) or (b) with access to a queryable expert (BLADES).
Introduction
We consider the problem of mediator learning to coordinate 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 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 provide personalized route recommendations (a) to 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), assume are given access demonstrations from an expert og (e.g. past iteration of the application). We can imagine two kinds of users of our application (i.e.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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 do so under their (unknown) personal utility function (e.g. we recommend a long route to busy driver). We use Ji(Ta) below to denote the value of the mediator's learned policy under the ith agent's '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 single-agent IL (SAIL) problem over joint policies. It is therefore natural to use 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 J(( (Ta) <e[m)
Intuitively, driving the value gap to 0 (i.e. achieving value equivalence in the terminology of [10] implics that along as long as all agents blindly follow our recommendations, we have learned a policy that performs least 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 happy 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 D, Then, we can define the regret induced by the mediator's 's policy as
(a) = max max (Ji(Fo,o.) J. (TT)))
sE[m] 6.E
where o; is strategic deviation of agent i and To, is the joint agent policy induced by all agents other than i following a '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+(o)= R&(OE).
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 '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 '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)(T))) and a deviating ith agent (Ji(To, )). We can decompose this quantity into the following:
J((To,o)) - J((TT) = (Ji(To,o.) - (To)))))) + (Ji(FoR.)))) - J.( + (Ji(Fom) - (T+))
(I: value gap under dc)
(II: expert regret under dz)
(III: SATI. value gap)
where we use Tag.o, to denote agent joint behavior under expert recommendations and deviation Φb-- 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 's regret under deviation Φ; (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. (TT,,..) - )..T) 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:
1. We initiate the study of the regret gap for MAIL in Markoy 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 's recommendations. The shift from value to regret gap captures what is fundamentally different about the SAIL and the MAIL problems.
2. 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.

---

3. We provide pair of efficient algorithms to minimize the regref gap under certain assump- tions. While regret equivalence is hard 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 coverage assumption) and BLADES (which requires access to queryable expert). We prove that both algorithms can provide ((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 for summary of our regret gap bounds.
Assumption
Upper Bound
(Matching) Lower Bound
J-BC
3-Coverage
youH
Theorem 5.1
p cuH
Theorem 5.2
J-IRL
3-Coverage
0
jeuH Theorem 5.3 Ω jeuH
Corollary 5.4
MALICE (ours)
8-Coverage
0 (EuH). Theorem 5.5 $2 (euH). Theorem 5.6
BLADES (ours)
Queryable Expert
(euH), Theorem 5.7 52 (euH). Theorem 5.8
Table 1: A summary of our results: upper and lower bounds on the regret gap (i.e.
(R) (R.
RR (ax))
of various approaches to multi-agent II., Here, 33 is the coverage constant in Assumption 5.2, u the
recoverability constant in Assumption 5.1, H is the horizon.
2
Related Work
Single-Agent Imitation Learning, Much of the theory of imitation learning focuses on the single- agent 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 II. approaches like inverse reinforcement learning (IRI., [1, 28]) allow the learner to observe the consequences of their actions during the training procedure, preventing 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 the regret gap analog of the value gap-centric DAgger and ALICE algorithms, operating under the same assumptions.
compounding errors [21]. However, such approaches
Multi-Agent Imitation Learning. The concept of the regret gap was first introduced in the excep- tional work of Waugh 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 for MAIL in the first place.
Inverse Game Theory. Another line of work focuses on inverse game theory in Markov Games [13, 81, where the goal is 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.
3 Preliminaries
We begin with the notation we will use in paper. Throughout, use A(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 convex upper bound on the total variation distance TV. We use εT when the loss function is exactly the TV distance.
Markov Games, We use MG S, ( Po) to denote a Markov Game (MG) between m agents. Here, is the horizon,
the state space, and A = Ai X ... x Am is the joint action space for all agents. We use T: SS* x A + (SS) to denote the transition function. Furthermore, the reward (utility) function for agent E [m] denoted by r; S x A -> [-1, 1). Lastly, we use Po to denote the initial state distribution from which the initial state so Po sampled.
3

---

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. 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, to take at the current state 8. Critically, no agent observes the recommendations the mediator provides to another agent. We can represent the mediator as a Markovian joint policy a E >, where S - A(A). We use a (āā s) to denote the probability of recommending joint action á in state We use т: S - (AA) to denote the joint policy that agents play in response to the mediator's 's policy, When agents exactly follow the mediator's 's's recommendations,
denote their joint policy as To-
trajectory& { ~ π {sh. ān M==...... refers sequence of state-action pairs generated by starting from So Po and repeatedly sampling joint action āj and next states S4+1 from x and 'T for H time steps. Let df, denote the state visitation distribution at timestep following и and let d = 1 Σi= dz be the average state distribution. Let PK (8h, T.) denote the occupancy measure- if
ie.. probability of reaching state and then taking action ā time step By definition, we know
that Vn, E..a (s ā) = Let p² (s, a) / Ex= P% (s, a) be the average occupancy measure.
We VI,5 denote the expected cumulative reward of agent under this policy from time step h. i.e. Vihh (8) E r (s, a,) 1s, s]. We define Q-value function of agent i as Q7, (s, a)) az a]. We define advantage of an agent i to be the difference between its Q-value on selected action and the V-value on the state, i.e. A,,, a) = Q7 (s. a)
Be E == (st, Ts)
(s).
(s). We also define the performance of a policy æ from the perspective of agent as (
Eea Ee E'= re (s),,,))) soll. Observe that performance is the inner product between the occupancy measure and the agent's 's reward function, i.c. ((( = -., p² ()): a).
Correlated Equilibria. We now introduce the notion of a correlated equilibrium (CE, Aumann [2]). First, define strategy deviation o; for the i-th agent 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 (1 a) a) defect (in which case (8, a) * a). Let 4; be the set of deviations for agent i, which is a subset of all possible deviations. We use +- == { ym
map o; S x A, - A;-
denote deviations for all agents. We assume that for all the identity mapping (5, a) = a is in +;. We use Ta to denote (Ø,, o To.s ④ To,-i ;: the joint agent policy induced by mediator policy a being over-ridden by deviation Φ.. We can now define a CE.
Definition 3.1 (Regret and CE in General-Sum MGs). Let E E, be the mediator's policy in Markov Game, and 4., E [m] be the deviation classes for each agent. Then,
1. We define the regret of a mediator policy to be
Ro(o) := max max (J. - J((To)), sE(m] 0.E0.
2. We say mediator with policy induces an 6-approximate Correlated Equilibrium (CF) if
R₂ SC..
Intuitively, 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 large incentive to deviate.
4 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 's policy dg and the learner's ss policy a E Σ as
max (J.(a)) - (.)
(3)
VE ml
Definition 4.2 (Regret Gap). We define the regret gap between the expert's 's policy oF and the
learner's 's policy E E as
Ra(o) - ( = max max (J.( (((T)) #E|m 0.E0,
max max (Ju(Tog - Ju (Too))) (4)
Re [m) DN

---

Complete Reward Deviation Classes
Regret Equivalence
Value Equivalence
Figure I: 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 O. We now explore the relationship between the value and regret gap in MAIL, summarized in Figure 1. We use (T. f) and R (c,, f) to denote the value/regret of policy under the reward function f.
4.1 Regret Equivalence Complete Reward / Deviation Class
Value Equivalence
First, we show that 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 = A + [-1, 1]} (i.e. all convex combinations of state-action indicators), and that the deviation class is complete if for every agent i, 4; = (S x Ai - A:} (i.e. all possible deviations). Theorem 4.1 (Complete Classes). the reward function class F and deviation class & are complete and regret equivalence is satisfied (i.e. sup oupfer(Ru(0 f) R4 f)) 0), then value equivalence is also satisfied: sup max (m)) (Ji(Tog f) (1 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, expert policy dg, and trained policy a such that even though the regret equivalence satisfied under the true reward function т, i.e. Ra (a, (a r) 0, the value gap max4e(m) (Tag Ji(mo, 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 attention to the converse.
4.2 Value Equivalence + Regret Equivalence
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, expert policy og, and learner policy such that even occupancy measure of Tu exuctly matches Tag i.e. v(s, p=* = - (s, a) (i.e. we have value equivalence under all rewards), the regret gap R4(a) R*(0E) 2 9(H). [Proof]
We leave the details 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 82, 54, 8 2. The trained policy perfectly matches the occupancy measure of the expert by taking identical actions visited states $2 $1, ... $2H 22 However, expert demonstrations lack coverage of state $1 as it is unreachable by executing Tg. This omission becomes critical when agent 1 deviates from the original policy, making 81 unreachable with high probability. Consequently, the trained policy may perform poorly in $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 states actually visited by the policy, while the latter depends on the counterfactual recommendations the learner would make at unvisited states response to 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 's behavior in states unvisited by the expert (but reachable by the deviated agents joint policy). Thus, from an information theoretic perspective, it impossible for the learner to minimize the regret gup without knowing how the expert would behave on those states. This demonstrates the fundamental difficully of minimizing the regret gup, and thus, regret is haadd' MAHL We therefore need a Jundamentally new parudigm of MAIL algorithm to minimize the regret gap.
We prove in Appendix D that the value and regret gaps equivalent in single-agent IL.
5

---

83
85
82
0g
else
else
all
all
82
84
86
8211
Figure Illustration of an Markov Game that captures why "regret is hard". Here, dg (aja1 =. Observe that 81 is un-visited when all agents obediently follow d but is with probability under deviation Φ (80, a1) = Φ1 (#1, 01) ) = a2). This means that unless we know what the expert dg would have recommended counter-factually in 81, cannot minimize the regret gap.
4.3 Low Regret Gap CE, Low Value Gap
++>
CE
Given the deep connections between regret and correlated equilibrium discussed above, it is perhaps intuitive that the expert dæ playing CE, low regret gap means the learner is as well.
Theorem 4.4 (Regret Gap Implies CE). If the expert policy o induces a 8y dy-approximate CE, and the learner policy a satisfies (a) (a & 82, then a induces a 8n + 62-approximate CE [Proof]
Then, by combining preceding result with Theorem 4.3, it follows that low value gap does not imply that the learner is playing a CE.
Corollary 4.5. There exists a Markov Game, an expert policy ag, and a learner policy a, such that og induces a 81 -pppproxieatee CE, and satisfies maxqe ml (Ji(Tog) JI(Ta)) 82 o induces ((H)) apprrxxmate CE.
Together, these results imply that if we are interested in inducing a CE amongst the agents in the population, the regret gap is more suitable objective.
4.4 Efficient Algorithms for Minimizing the Value Gap
Although we have shown that the value gap is 'weaker' objective in some sense, in many real-world scenarios, the agents may be non-strategic. In these scenarios, minimizing value gap can be reasonable learning objective. As we will demonstrate here, the natural multi-agent generalization of single-agent 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 rumning 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 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 policy a that satisfies E Exsd" [ (s))) S then the value gap (J - S O(eH²). [Proof]
Theorem 4.7 (J-IRL Value Gap Upper Bound). If J-IRL outputs policy a with moment-matching error
H f(s an)
sup En
E((sh, an) Aum
Ex,
I eH,
JEF
Lhml
then the value gap max (Ji(FaE) J((TT)) S O(eH). [Proof]
As argued by Swamy et al. [21], satisfying the conditions for either of the above theorems can be achieved oracle-effiiinnly via 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 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... Vs, a. h i, Øi,
A,
"e..0 (s, S u.
Intuitively, a small value of u means that we're not a problem where single agent can deviate and joint mistake happens that even the expert couldn't 't recover from for the rest of the episode. In the worst case, u is (H)). However, we believe that in many cases u is small. For instance, in the route planning example, at some point many this can be recovered within a constant time, even when a single driver chooses not to follow its recommendation, rather than increasing // increases.
may miss their turns/inerssctiios/ecitt but
This assumption can be thought of natural 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 a class (sup 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 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.
5.1 Assumption 1: Full Coverage of Expert Demonstrations
In this section, we introduce a coverage assumption on the expert's state distribution d=T (5) which states that the expert visits every state with positive probability. We will show that this assumption 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 (3 (ovovreag There exists a constant B 0 such that for the expert's 's policy g. holds that d= (s) 2 3 for all
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 's actions in counter-factual states.
We first show that under Assumption 5.2, J-BC and J-IRL get (relatively weak) regret gap guarantee.
5.1.1 Regret Gaps of J-BC and J-IRL under Full Demonstration Coverage
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 a that satisfies Ex (((TE(s), S e, then
Ra -R S
geull
[Proof]
We leave the proof in Appendix E.7. is worth to note that although the dependency of H is linear under our recoverability assumption, still need to pay for the term z 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 oe. and learner policy such that og satisfies Assumption 5.1 and Assumption 5.2, achieves BC error
7

---

(s)))s()) (e) ((og(s). Bendmr//tr/lz(())ooss))) & e. and
- - =s (
[Proof]
We now prove analogous results for joint inverse reinforcement learning (J-IRI.). 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, J-IRL returns a policy a with moment- error
I [(n, σn)
Σ
f(8hs (1sh))))))))))))))()))
sup FEF
ETTR
ETT
S.
H
H
then Rx(o) - R (OE) S so ()cuH)) [Proof]
There are interesting features of this theorem. The first that needed 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 not an artifact our analysis by providing a matching lower bound.
Corollary 5.4 (J-IRL Regret Gap Lower Bound). There exists Markov Game, expert policy de- and a policy a such that og satisfies Assumption 5.1 and Assumption 5.2, the trained policy gets moment-matching error
Σ f(sh, ōn)
Σ f(sh, ax))
sup E Bazg FEF
B..
SE
H
11
and (o) - Rx(0E) S (Heult): [Proof]
This result implies another fundamental distinction between SAIL and MAIL: in contrast to the value gap, interactive training alone not sufficient effectively minimize the regret gap.
5.1.2 MALICE: Multi-agent Aggregation of Losses to Imitate Cached Experts
Observe that the upper bounds for both J-BC and J-IRL include dependence on the inverse of the coverage coefficient 1. which can 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 interactive algorithm that, each round, uses importance sampling to re- neiwe the behavior cloning (BC) loss based on the density ratio between the current learner policy and that of the expert. Accordingly, ALICE requires full demonstration coverage assumption to ensure that these importance weights are finite. ALICE uses a no-regret algorithm to learn policy that minimizes reweighed on-policy error, which guarantees linear-in-Hf bound on the value gap under a recoverability assumption [20].
In Algorithm 1, describe Multi-agent ALICE (MALICE), where adapt ALICE the multi-agent setting (i.c. minimizing the regret gap). Specifically, we modify the ALICE loss function to include a maximum over all deviations. This gives us
<d (0) d (s)
(MALICE DE, a) = max max BywdroR :E[m] 0.E.,
(5)
convex loss function, and the maximum of convex functions is still convex function, know that (aLLICL(o, Dg, δ) is valid convex loss function with scales in [0, 1). As a result, we can run an (arbitrary) no-regret online convex optimization (OCO) algorithm efficiently optimize giving us efficient reduction from regret gap minimization to no-regret online convex optimization under demonstration coverage.
Since Eg-d'e z
We now provide regret gap guarantees on the policy returned by MALICE.

---

Algorithm MALICE (Multi-agent Aggregation of Losses to Imitate Cached Experts)
1: Input: Expert demonstrations DE.
2: Initialize σ(1) E.
3: for to N do
4: for = to m do
5: for E $ do
(1)
6: Sample states from 8 d.o...
7: end for
8:
end for
9:
Construct loss function (a) (MALICE(O, Dr,a("))
Run arbitrary no-regret algorithm on sequence losses, e.g. FT(R)::
11:
( + arg argmingex. ش==1 (a)
12:
end for Return Best of ((1:)) on validation data.
Theorem 5.5 (MALICE Regret Gap Upper Bound). Let a be a policy such that EMALICE DE, S Under Assumption 5.1 and Assumption 5.2, we have
(o Ro(or) OeuH)..
[Proof]
As promised, observe that adapting the importance sampling technique Spencer et al. [20] to the multi-agent setting allows to efficiently minimize the regret gap while avoiding 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 de that satisfies Assumption 5. and a trained policy that gets error (I DE, σ) S and
Ra(o)- - (x( (cuH).
[Proof]
We now turn attention to alternate assumption and the corresponding regret gap algorithm.
5.2 Assumption 2: Access to Queryable Expert
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 counter- factual states: access to a queryable expert. In their classic DAgger algorithm, Ross al. [18] showed that access to 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, covariate shift: potential strategic deviations by agents the population that push the learner outside of the support of the expert. We refer to multi-agent extension of DAgger as BLADES.
again use access queryable expert to handle yet another source of
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 loss functions:
(BLADES (a, à) max max B. (((oE(s)
*E|m] 0:E:;
Similar to MALICE, we know that the loss BBAADES is also a valid convex loss function, and thus we use 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 policy returned BLADES.
Theorem 5.7 (BLADES Regret Gap Upper Bound). Under Assumption 5.1, if a policy a satisfies fBLADES (a, σ) I c, then
Ro(a) - Ro(og) $ O(cuH).
[Proof]

---

Algorithm 2 BLADES (Bend Learner, Aggregate Datasets of Expert Suggestions)
1: Input: Expert demonstrations DE.
2: Initialize learner σ(1) arg min, Dn ((op(s).
to N do 4: for i = to m do
3: for
5: for E $ do
6:
Sample trajectories from " "0,0:"
(n)
Query expert for action recommendations to construct dataset D(d) {())) end for
7:
8:
9:
end for
10: Construct loss function (a) = (BLADES (()).
11:
Run arbitrary no-regret DCD algorithm sequence of losses, e.g. FT
12:
a(++1) + arg minginge... Σド=1 g(n)
13:
end for
14:
Return Best of (1:N)) validation data.
Theorem 5.8 (BLADES Regret Gap Lower Bound). There exists a Markov Game, an expert policy de. and a trained policy such that satisfies Assumption 5.1, a achieves error ETVBLADES (o, o) S e, and
Ra( - (+( (cuH).
[Proof]
In short, under either demonstration coverage assumption with access to queryable expert, are able to efficiently minimize the regret gap on recoverable MAIL problem.
Conclusion
Our work focuses on the core question of what fundamentally distinguishes multi-agent IL problems from single-agent ones. In short, answer is that on problems with strategic agents that are 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 future work.
7 Acknowledgements
We thank Drew Bagnell and Brian Ziebart for their incredible patience and detailed answers to a somewhat absurdly large numher of questions about their prior work. We thank Simon Shaolei Du for a discussion on our coverage assumptions and Noah Golowich for references to relevant lower bounds in the MARL literature. We also thank Sanjiban Choudhury and Wen Sun for comments our draft. ZSW, GS, and Jingwu Tang are supported in part by an Air Force STTR grant and the NSF Award #1 763786. ZSW is supported in part by the NSF FAI Award # #1939606. Google Faculty Research Award, a J.P. Morgan Faculty Award, a Facebook Research Award, an Okawa Foundation Research Grant, and Mozilla Research Grant. FF supported part by NSF grant IIS 2046600 (CAREER) and the Sloan Research Fellowship. GS is supported by his family and friends.
Contribution Statements
1. JT uncovered the distinction between the regret and value gaps, proved all of the core results in the paper, and drafted the initial version of the paper.
2. GS initially proposed the project, came up with the sufficient conditions and associated algorithms minimizing the regret gap, and wrote most of the final version of the paper.
3. FF and ZSW advised the project.
10

---

References
[1] Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforeement learning. In Proceedings of the twenty-first international conference Machine learning, page 1, 2004.
[2] R. J. Aumann. Correlated equilibrium expression of bayesian rationality. Econometrica: Journal of the Econometric Society, pages 1-18, 1987.
[3] M. Barnes, M. Abueg, O. F. Lange, M. Deeds, Trader, D. Molitor, M. Wulfmeier, and S. O'Banion. Massively scalable inverse reinforcement learning in google maps. arXiv preprint arXiv:2305.11290, 2023.
[4] R. P. Bhattacharyya, D. J. Phillips, B. Wulfe, J. Morton, A. Kuefler, and M. Kochender- fer. Multi-agent imitation learning for driving simulation. In 2018 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1534-1539. IEEE, 2018.
[5] L. Erez, Lancewicki, U. Sherman, T. Koren, and Y. Mansour. Regret minimization and convergence equilibria in general-sum markov games. In International Conference Machine Learning, pages
PMLR, 2023.
[6] J. Fu, K. Luo, and S. Levine. Learning robust rewards with adversarial inverse reinforcement learning. arXiv preprini arXiv: /248, 2017.
[7] J. Fu, A. Tacchetti, J. Perolat, and Y. Bachrach. Evaluating strategic structures in multi-agen inverse reinforcement learning, Journal of Artificial Intelligence Research, 7 71:925-951, 2021.
[8] D. Goktas, A. Greenwald, S. Zhao, A. Koppel, and S. Ganesh. Generative adversarial inverse multiagent learning. In The Twelfth International Conference Learning Representations, 2023.
[9] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Bengio. Generative adversarial networks. Communications of the ACM, 63(11)1139-144, 2020.
[10] C. Grimm, A. Barreto, S. Singh, and D. Silver. The value equivalence principle for model-based reinforcement learning. Advances in Neural Information Processing Systems, 33:5541-5552 2020.
[11] C. Gulino, J. Fu, W. Luo, G. Tucker, E. Bronstein, Y. Lu, J. Harb, X. Pan, Y. Wang, X. Chen, al. Waymax: An accelerated, data-driven simulator for large-scale autonomous driving research. Advances in Neural Information Processing Systems, 36, 2024.
[12] H. M. Le, Y. Yue, P. Carr, and P. Lucey. Coordinated multi-agent imitation learning. In International Conference on Machine Learning, pages 1995-2003. PMLR, 2017.
[13] X. Lin, S. C. Adams, and P. Beling. Multi-agent inverse reinforcement learning for certain general-sum stochastic games. Journal of Artificial Intelligence Research, 66:473-502, 2019.
[14] T. Osa, J. Pajarinen, G. Neumann, J. A. Bagnell, P. Abbeel, J. Peters, et al. An algorithmic perspective on imitation learning. Foundations and Trends@ in Robotics, 7(1-2):1-179, 2018.
[15] D. A. Pomerleau. Alvinn: An autonomous land vehicle in a neural network, Advances in neural information processing systems, 1, 1988.
[16] J. Ren, G. Swamy, S. S. Wu, J. A. Bagnell, and S. Choudhury. Hybrid inverse reinforcement learning. arXiv preprint arXiv:2402. 08848, 2024.
[17] S. Ross and D. Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
[18] Ross, G. Gordon, and D. Bagnell. reduction imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth international conference artifi- cial intelligence and statistics, pages 627-635. JMLR Workshop and Conference Proceedings. 2011.
11

---

[19] J. Song, H. Ren, D. Sadigh, and S. Ermon. Multi-agen generative adversarial imitation learning. Advances neural information processing systems, 31, 2018.
[20] J. Spencer, S. Choudhury, A. Venkatraman, B. Ziebart, and A. Bagnell. Feedback in imitation learning: The three regimes of covariate shift. arXiv preprint arXiv:2102.02872 2021.
[21] G. Swamy, S. Choudhury, J. A. Bagnell, and S. Wu. Of moments and matching: game- theoretic framework for closing the imitation gap. In International Conference on Machine Learning, pages 10022-10032 PMLR, 2021.
[22] G. Swamy, Choudhury, D. Bagnell, and S. Wu. Causal imitation learning under temporally correlated noise. In International Conference on Machine Learning, pages 20877-20890. PMLR, 2022.
[23] G. Swamy, S. Choudhury, J. Bagnell, and Z. Wu. Sequence model imitation learning with unobserved contexts. Advances in Neural Information Processing Systems, 35:17665177676 2022.
[24] G. Swamy, N. Rajaraman, M. Peng, S. Choudhury, J. Bagnell, S. Z. Wu, J. Jiao, and K. Ram- chandran. Minimax optimal online imitation learning via replay estimation. Advances in Neural Information Processing Systems, 35:7077-7088, 2022.
[25] G. Swamy, D. Wu, S. Choudhury, D. Bagnell, and S. Wu. Inverse reinforcement learning without reinforcement learning. In International Conference Machine Learning, pages 33299-33311, PMLR, 2023.
[26] E. Vinitsky, N. Lichtlé, X. Yang, B. Amos, and J. Foerster. Noctume: benchmark for bringing multi-an multi-agent learning one step closer the real world. Advances in Neural Information Processing Systems, 35:3962-3974, 2022.
scalable driving
[27] K. Waugh, B. D. Ziebart, and J. A. Bagnell. Computational rationalization: The inverse equilibrium problem. arXiv preprint 13Xiv:1308.3500 2013.
[28] B. D. Ziebart, A. L. Maas, J. A. Bagnell, A. K. Dey, et al. Maximum entropy inverse reinforce- ment learning. In Aaai, volume 8, pages 1433-1453 1438. Chicago, II. USA, 2008.
12

---

A Broader Impacts
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.
B Extending Single-Agent IL Algorithms to Minimize the Value Gap
B.1 Multi-Agent Joint Behavior Cloning
Behavioral Cloning (BC, Pomerleau [15]) treats the problem of imitation learning as supervised learning and performs maximum likelihood estimation with expert states 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 (learer 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 argued by Swamy al. [21], the same
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 example of MDP/MG that matches this bound, which shows that the bound is tight [21].
B.2 Multi-Agent Inverse Reinforcement Learning
A popular family of online techniques for imitation learning is inverse reinforcement learning (IRL). Intuitively, IRL can be thought 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 player and a policy player [21]. In each round, the reward player picks a reward function from F that maximizes the value gap between dg and a, while the policy player uses reinforcement learning algorithm to learn a new policy in E that maximizes the performance under this reward function.
two-player zero-sum game between a reward
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 ((e H). We now generalize this result the multi-agent setting. Accordingly, our policy class Σ becomes one of joint policies. We use reward function class FF 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], prove O(eff) value gap bound for multi-agent IRL algorithm in Theorem 4.7.
Algorithm 3 J-IRL
1: Input: expert demonstration DE, Policy class E, Reward class
2: Set (1) Σ
3: for n = 1 to N do
4: f(m) <- ara max J(ToE: ( R(f)
single-agent RL problem over joint action space under reward function p(n)
// Treat it
5:
( + MaxEntRL(r== (()))
6: end for
7: Return best (n) on validation
C Useful Lemmas
We introduce a lemma which will be very useful 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
13

---

it in the analysis for MAIL. It shows that if the policy achieves small on-policy enror, then, with recoverability assumption, the value gap is linear over H.
Lemma C.1. [Ross al. [18]] For ageni joint policy mi and ma, if the advantage of m is bounded under the true reward function vi, h 8, a. |A (8, a) S u, and wa get on-policy enror By (8),, x2())) S c, then [J((T1) J2(T2) cuH, Vi E [m].
Proof. Via the performance difference lemma, Vi E [m]]. we have
1
(T((T)) J((T2)] =
Σ
and [A (s, (T)))
4=1
(7)
< a [((m] (s), T2
euH
For our analysis of MALICE and BLADES, we will m any deviated expert policy Togie and m2 be the deviated trained policy To under the same deviation.
D Equivalence of Regret Gap and Value Gap in Single-Agent IL
For single-agent IL we prove that the regret gap and the value gap are equivalent.
Theorem D.1 (Equivalence Single-Agent IL... For single-ugent MDP, regret gap and value gup are equivalent to each other
(TTg)) - (Tx)) = Rx(o) R+(0E)
Proof. For single-agent MDP, we ignore the index 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 have
R+( max(J((T..)) (m=)) [[x²) J(To)
oE
where x² is the optimal policy under the true reward function. Similarly, we have
Ro(og) = J(x*) ((Fo)
Therefore.
Ro(o) - (J(T²) J(TT)) (J(x") (TTO)) J(Tox) J(TO)
In single-agent MDPs, the dynamics are fixed because no other agents affect the agent's dynamies, and therefore, the regret gap is equivalent to the value gap.
14

---

E
Proofs
Contents
E.1 Proof of Theorem 4.1
15
E.2 Proof of Theorem 4.2
15
E.3 Proof of Theorem 4.3
15
E.4 Proof of Theorem 4.4
16
E,5 Proof of Theorem 4.6
16
E.6 Proof of Theorem 4.7
16
E.7 Proof of Theorem 5.1
16
E.8 Proof of Theorem 5.2
17
E.9 Proof of Theorem 5.3
17
E,10 Proof of Corollary 5.4
18
E.11 Proof of Theorem 5.5
19
E.12 Proof of Theorem 5.6
19
E.13 Proof of Theorem
20
E.14 Proof of Theorem 5.8
20
E.1 Proof of Theorem 4.1
Proof. We prove the lemma by showing that the occupancy measures of To and Tog exactly match i.e. pa (s, () - (s, a) for every (s, ū). Consider cooperative reward function fs - 8'=0= ((2=a)) d.).
Under fa,. have J(m,) 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 s).
-pp"'(pp (s, d), J(TOR) - (s, a). The maximum value
Therefore R& = - (-Hp"* (s. = Hp" Ro(og) = 0 (-, = H H (s,ā). a).
(s. Since Ro (a) Ra (og) O, we know that p = pT (s, a). This implies that the occupancy measures of two policies exactly match. As a result,
sup max (Ji(FoR: f) Je(Foo f)) fEfie|m)
E.2 Proof of Theorem 4.2
Proof. We can construct an example in normal form games, in which there are mulitple CEs with different pay-offs. We can let the o plays CE and a plays CE Therefore, although the regret gap (a) - Ro(ag) = O, the value gap max;e[m] (Ji(To)) J((m))) & 0. The NFG in Figure is an example, where (01, a1) and (0z, 02) are two CEs with different values.
E.3 Proof of Theorem 4.3
Proof. We prove the theorem by constructing such a Markov Game and policies that can get Q(H) H) regret gap. For simplicity, we construct a two-player cooperative game where the reward identical for all agents. Agents can not visit the same state at different time steps. These allow us to omit the index in the reward function in the proof. The notation a,ay is used to represent the action pair (a,, a;).
15

---

The transition dynamics are illustrated in Figure 2, and the rewards are action free. The reward function r(sg) r(ss)
r($22113 3) with all other states yielding a reward of Each agent has an action space A, = {u1, 02 az).
The expert policy oæ satisfies o zo (a |so) 1. (aga3)s1) 1. Action all other states don't matter because the transition and the reward would be the same. The trained policy o satisfies a {ajai]so) (ara)()))))
and plays the same as the expert in all other states.
not hard to verify that øg plays a CE under this reward function, which means (o)g)
Ro
The worst deviation for a is to deviate action of agent 1 from playing to on both so and $1. We get
(x H -
Therefore, the regret gap Ro(a) Ro(0E) H (H)
E.4 Proof of Theorem 4.4
Proof. From the definition of CE, we know R (o S 61. Therefore, Rs (o) Ro(0E) (Ro R+(ox)) 51 62
(8) L
Thus, we know that induces 61 + 82-approximate CE.
E.5
Proof of Theorem 4.6
Proof. For any we view multi-agent problem single agent MDP over the joint action space under reward function ri. Following the proof in Ross and Bagnell [17]. Swamy et al. [21], we can prove Ji(Rag) (I, s Oe)))). Therefore, max4e[m] ( (Ji(Hog) (i(m))) S O(eH²).
n
E.6 Proof of Theorem 4.7
Proof. For any i,
H f(sn, Fn)
J((TTS) (TT) & sup BENTER JEF
Σ 1=11
-ENrs
Σ f(h
SEH
Therefore, max,g[m] (J.(F - J. S ((HH).
E.7 Proof of Theorem 5.1
Proof. With Assumption 5.2, we know that
Ex-ano (((on()) s (( (a ((o7(())00)) e
3
By Lemma C.I, we get
J((Tog) - J((TT) c
For any deviation di.
S Ea [V( (8), no.o, (8)) < Banddann (
By Lemma C. get
J((To)))) - Ji(TTR 100 (
Therefore,
Ji(Fa.o.) J1(TT) (Ji(TTnoo)) (T(Tnn))))) (J.(nan))))
J((Tan)) (Ji(Ton) (,(Ta))
Ji(aggoo))) - J((FTgg) +0 ( geull
(9)
16

---

0g01
all
$1
83
95
92u -1
82H
0241
clsc
90
elsc
all
82u
82H
Figure 3: Example of Q euff regret gap for J-BC and J-IRI.
Taking the maximum over i or we get
Rx Rx((F) S0 (
E.8
Proof of Theorem 5.2
Proof. We prove the theorem by constructing such Markov Game policies that can get O eu)H)) regret gap. We consider the two-player cooperative game similar to the example in Theorem 4.3. What we need to do 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(s3) rr(ss)
r8822' -a) = 1, with all other states yielding a reward O. 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 be the policy that ap(a 2: (((gagy)))1) 2- Action other states doesn't matter because the transition and the re- ward would be the same. satisfies Assumption 5.2.
- 23, o (a(aa]]ss)
23, og (22a, [s1]
Let trained policy be the policy that a(a]a]|s)) 3, (a |sl]=
23, (aga1|s0) 28, ((2ai[s])) 2 and or only differs at $1.
cH 27 (agag)ss))
Behavior cloning error of a satisfies
eH E (TTo(o 23 23
23
is not hard to verify, the worst deviation for Tog is to deviate action agent at so from playing ag d2, and thus
1 R (o (1 23) - 22)
The worst deviation of na is to deviate action of agent from playing a₁ to ag 8o and 81-
(a) = 1 (1- (13)
- -2) + cH (n' - 2)
23
Therefore, the regret gap (x( - (OE)
cH 23
(u' - 2) = ((felll).
E.9 Proof of Theorem 5.3
Proof. We prove by showing that under complete reward function class F, low IRI. error will imply low BC error, and then apply Theorem 5.1.
17

---

When F = F=
2h [sny σh))
Σ [isks an.)
sup ETo fEr
B.
H
H
sup fEJ
1p (8, σ) - pp (x)
(10)
s,
p T ( -pa (s,
Therefore, we have
E 10 (s, (s, a)] se.
Σ T (8, (s)
Σ
s,
(s)= (0 [rochppppp0ee-000003300000000000
d= (+))
(1I)
eod u (S)) Σ
- dst
=E EE " (V(
Σ Σ 10 [ - p= (s,
EE re [TV(oE(s)
Σ 1 p=a 50 (s,
R (V()
Therefore, we get
B (TV(oE(S), 2e
Directly applying Theorem 5.1, we get Ro(o) Ro(oE) so (felt)..
E.10 Proof of Corollary 5.4
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 p(s, @) at state 81. Therefore,
Σ" f(sh, dn)
ΣnI f(sh, an)
sup Bueg fCF
Ex.
H
H
sup fEF
1 TeR (s, - (s)
8.
(12)
p Tog (0,(s,,) (s, (s,
< < Tox (81: A303)
Tex
pT (8), 0303)) + 10 (81, p (81, a1a))
1 E'H
23
2
23
Let é' = fec Then the regret gap (o) R*(
13 (u' 2) [((euuH).
18

---

E.11 Proof of Theorem 5.5
Proof. From the definition of IMALICE: know
d ((TE()),=(())
(MLLIEE(O, DE,0) max max Bg iE ml de
d=
d
max max grd VE
d= E(TEO, (s), To. (8))
(13)
max max oo iE
[((TE,,(8) TT,
Tá. (8))
From Lemma C.I, we know that for all i, Ø1, we have
J((To, - (T( 5 O(euH)
And
[((TTg) J.(TT) O(eul))
Therefore, we get
J((Fo,..) (((TT) = (Ji(To,()) - (. + (Ji(Toz, - J((Foz)) (Ji(ToR) (((TT))
(i Ji(TTR) + O (eulf)
(14)
Taking the maximum over i, 0i, get
Ro Rs (o 5 (uel)
E.12
Proof of Theorem 5.6
Proof. We prove the theorem by constructing such a Markov Game policies that MALICE can get ((euH) regret gap. We consider single-agent MDP shown in Figure 4. The rewards action free. Let u' = [u]. , the reward function r(81) = =<(8)) =.. r(#2w' -a) = 1, with all other states yielding reward of O. 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 satisfied.
Let B be the policy that (a)))s)) 1 - 8, o (a2)s0) B. Action at all other states doesn't 't matter because the transition and the reward would be the same. It easy to verify that og satisfies Assumption 5.2.
Let trained policy be the policy that (a, =1 (e, B + He. and oF only differ at 80-
Now verify that TTV Atv,MALICE(O) (a, DE. Sc
Since a and og only differ at state so, and d = for any i, o. we have that
To
ExndTog
TV(oE(s), = E Eand ((()) H F
He =e
Therefore,
dd
DT..ALLcCLO,DDg.. = max max maxE,rdde Eg =E[m] (
TV(og(s).
se
d=
is not hard to verify, the worst deviation for Tg is to deviate action on so from playing 0g to d1 and thus
Ro(TE,r) = 3('
the worst deviation for mg is also to deviate action so from playing ag a1-
RT) (3 + e 1)
Therefore, the regret gap (x) R&( e(u' - 1) N(euHH).
19

---

all
all
$1
83
95
92u -1
82H
90
02
all
8/u
82H
Figure Example of (((uHH) regret gap for MALICE and BLADES
E.13 Proof of Theorem 5.7
Proof. From the definition of (BLADES, we know
(BLADES
max max MaaxE,,aa sE[m] 6;
and [((OE())
(15)
2 max max E oo [e(Tor (b); Ta (s))
xE [m]
From Lemma C.I, we know that for all Φi. we have
(T. - Jj (F S O(euH)
And
(((TTR) J1(TT) - O(euH)
Therefore, we get
Ji(Fo,o))) (i(TTO) (Ji(TT, - JI(TTon + (Ji(Ton. J((mow)) (Ji(ToR) Ji(T.))
- J.( - Ji(MOR) + 0 (cuH)
(16)
Taking the maximum over i, oi we get
R4(a) - (
L
E.14 Proof of Theorem 5.8
Proof. Let MDP, expert policy og and the trained policy a be the same example in the proof of Theorem 5.6.
Since and og only differ at state 8o, and To.s (80) 1 for any Φi. have
E To. [T(() - H He=
Therefore, the trained policy π satisfies
(TV.LLADE (0, σ) max E n. [T))
=E|m] 6:
The regret gap (a) (x( c(u' - 1)H R(cuH).
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 inverse game theory, where the goal is to recover reward function to rationalize the expert's behavior, i.c. the expert policy plays
20

---

01
02
@1
02
(1,1)
(0,0)
01
(1,1)
(0,0)
02
(0.0)
(2,2)
82
(0,0)
(1.1)
Figure 5: Multiple reward functions rationalize dE
an equilibrium under such reward function. However, in our setting, instead of recovering a singe reward function, our goal is to learn a robust policy that get similar regret performance under a class of reward functions. We will show later that if the ultimate goal is to learn this robust policy, simply recovering a single reward function is not enough.
Second, the solution concepts are different. they work on Nash equilibrium, while in setting, focus on correlated equilibrium. We note that our algorithms also work for learning independent policies, by restricting the policy class to be class of independent policies.
Third, finite demonstration setting, their objective policy plays local NE, under the constraints that & difference of the observations for behaviors of two learned policy small. We note that in general simply matching this difference is not enough to guarantee that the learned policy play an equilibrium. From Theorem 4.3, we know that even if the occupancy measures of two policies exactly match, the regrets can still be significantly different under the same reward function.
find reward function which the learned
In conclusion, they work on a inverse game theory style problem where the goal to recover single reward function to rationalize the agents behavior. We work on imitation learning problem, where the goal is not recovering single reward function but learning policy that matches the regret performance of the expert under class of reward functions.
We will give examples in normal form games (NFG) to show that recovering single reward function is not enough to learn a policy that minimizing the regret gap for a large class of reward functions. NFG can be viewed as MG in which H and |S =
Lemma F.1. For an expert policy dg. there may exist multiple reward functions that rationalize it.
Proof. We show this by an example of normal form games in Figure 5. Consider the policy to be ( 1, then the expert plays CE/NE under both reward functions and r', which means both reward functions rationalize dg.
Lemma F.2. For a fixed reward function, There may exist multiple CE/NEs.
Proof. For reward function r in Figure 5, can construct such two policies 01, 02. For ai let a (aI,a) = 1. Let (2 a1) = Ds 02 02) = 02(22, @1) = 2.2 (22, a2) = g. Tt not hard to verify that both 0n and play CE/NE under the reward function
Therefore, since there is no one-to-one mapping between the equilibria and the pay-off' structures, simply recovering single reward function might not help recover a policy that gets small regret gap.
For example, the true reward function is in Figure 5, and expert policy dg satisfies dg(a1 01) The algorithm may recover r' in Figure 5, and trained policy that plays NE/CE under recovered reward function r' would be (()),)) = (a), a²) = (as, @1) = ( (2) = However, this trained policy does not play NE/CE under the true reward function
21

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the
paper's contributions and scope?
Answer: [Yes]
Justification: We discuss the relationship between the two objectives, and list our contribu- tions in the introduction. We include the assumptions when introducing the algorithms.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We include limitations in ??, where we discuss the computational and sample complexity of the algorithms, the assumptions made, and the fact that the algorithms are designed for tabular MGs and have not yet been implemented practical algorithms.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: The assumptions are provided in Section 5 and full proofs are in Appendix E.6. We do not include proof sketches in the main paper. However, we provide links between the theorem statements and their corresponding proofs for the readers' convenience.
Guidelines:
The answer NA means that the paper does include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This is theory paper. We do not include experiments for the algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
23

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: This is theory paper. We do not include experiments for the algorithms.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
gabllce/guidesCooeeeStee www.:subbbbiiiooooooooooooo for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
ctspps.ccppullcc//ec htpppuulccguudeeeeeeeeeeepgpeeee guides/ CCodeSubmi ssi www.nnoollii..eeeeee.ooe onloiicy)) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This is theory paper. We not include experiments for the algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This is a theory paper. We not include experiments for the algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
This is 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 well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp:///nei...//eee
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 deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
25

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper is theory paper and does not pose such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses for existing assets
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?
Question:
Answer: [NA]
Justification: This is theory paper and does not use existing assets.
Guidelines:
The answer NA means that the paper does not 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
26

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
27


Reviews:
[{"review_id": "vwb3FrHxv8", "reviewer": "Reviewer_3HJn", "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.\n\nThe 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.\n\nThe 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.\n\nWhile 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.", "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.\n- 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.\n- 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.\n\nMinor comments:\n- 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?\n- I think $r$ and $f$ are used interchangeably when denoting the reward function. Nothing wrong, but I suppose they could be made consistent.\n- Line 183: Typo “even” => “even if”", "limitations": "Addressed in Section 6 and Appendix A. The paper is of a theoretical nature.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n\n[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.\n\n[1] Zhao, G., Zhu, B., Jiao, J., & Jordan, M. Online learning in Stackelberg games with an omniscient follower. International Conference on Machine Learning 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our submission! Please find our replies to your questions/comments below.\n\nRegarding 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.\n\nRegarding 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.\nAs 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.\n\nAnswer 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.\n\nAnswer to Q2: We use the word \"surprising\" to highlight our findings:\n1. 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.\n2. 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*.\n\nAnswer 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.\n\nRegarding Minor Comments:\n\n[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.\n\n[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.\n\n[3]Thank you for pointing this out. We will fix this typo.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wUxzIJ2pN0", "reviewer": "Reviewer_NThg", "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.", "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?\n\n2. 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. \n\n3. 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": "The authors have adequately addressed the limitations of the proposed algorithms.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "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.\n2. **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.\n3. **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.\n4. **Clarity and Readability**: The paper is well-written and easy to follow, making complex concepts accessible to the reader.\n5. **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.\n2. **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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our submission! Please find our replies to your questions/comments below.\n\nResponse 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.\n\nResponse 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.\nAs 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.\n\nAnswer 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.\n\nAnswer 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.\n\nAnswer 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "HLYHQrLHcK", "reviewer": "Reviewer_aTBa", "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.", "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?\n\nQ2: 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?\n\nQ3: It would be helpful if the authors could state the challenges encountered when obtaining new theoretical results based on previous works.\n\nQ4: It would be helpful if there is an experimental plan to verify the algorithms, such as in simulated driver routing games.\n\nMinor suggestions:\nIs there a typo in line 147 that begins with \"identity mapping ...\"? Should that sentence end with \"Φi\"?", "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.", "rating": 5, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "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.\n\nThe paper contains both upper and lower bounds for regret gap optimization, along with detailed proofs.\n\nThe 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.\n\nProposed algorithms seems like straight forward applications of existing algorithms, it would be nice to list the challenges when applying existing results.\n\nNo experimentation or code is included with the work, making it difficult to examine whether the proposed algorithms are efficient in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our submission! Please find our replies to your questions/comments below. \n\nRegarding the assumptions:\n\n1. 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]).\n\n2. 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.\n\n3. 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.\n\nRegarding 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.\n\nRegarding 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.\n\nAnswer 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.\n\nAnswer 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]).\n\nAnswer 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.\n\nAnswer 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.\nAs 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.\n\nFor Minor Suggestions: Thank you for pointing that out. We will fix this typo.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yhSgftccAE", "reviewer": "Reviewer_SJkf", "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.", "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}$ ? \n\n\n2-Please see the points above under Weaknesses.", "limitations": "I think the limitations were properly addressed.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "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. \n\n2-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. \n\n2-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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our submission! Please find our replies to your questions/comments below.\n\nResponse 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.\n\nResponse 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.\n\nAnswer 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$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)