On Imitation in Mean-field Games
Authors: Giorgia Ramponi
Pavel Kolev
Olivier Pietquin
Niao He
Mathieu Lauriere
Matthieu Geist
Venue: NeurIPS 2023 poster (2023)
Keywords: Mean-field games
Imitation Learning

Abstract: We explore the problem of imitation learning (IL) in the context of mean-field games (MFGs), where the goal is to imitate the behavior of a population of agents following a Nash equilibrium policy according to some unknown payoff function. IL in MFGs presents new challenges compared to single-agent IL, particularly when both the reward function and the transition kernel depend on the population distribution. In this paper, departing from the existing literature on IL for MFGs, we introduce a new solution concept called the Nash imitation gap. Then we show that when only the reward depends on the population distribution, IL in MFGs can be reduced to single-agent IL with similar guarantees. However, when the dynamics is population-dependent, we provide a novel upper-bound that suggests IL is harder in this setting. To address this issue, we propose a new adversarial formulation where the reinforcement learning problem is replaced by a mean-field control (MFC) problem, suggesting progress in IL within MFGs may have to build upon MFC.

On Imitation in Mean-field Games
Giorgia Ramponi
Pavel Kolev² Mathieu Laurière
Olivier Pietquin Matthieu Geist
Niao He*
ETH AI Center, Zurich Max Planck Institute for Intelligent Systems, Tübingen, Germany Google DeepMind ETH Zurich, Department of Computer Science Shanghai Frontiers Science Center of Artificial Intelligence and Deep Learning, NYU Shanghai
Abstract
We explore the problem of imitation learning (II.) in the context of mean-field games (MFGs), where the goal is to imitate the behavior of population of agents following a Nash equilibrium policy according some unknown payoff function. IL in MFGs presents new challenges compared to single-agent IL, particularly when both the reward function and the transition kernel depend on the population distribution. In this paper, departing from the existing literature on IL for MFGs, we introduce new solution concept called the Nash imitation gap. Then we show that when only the reward depends on the population distribution, IL in MFGs can be reduced to single-agent with similar guarantees. However, when the dynamics is population-dependent, we provide novel upper-bound that suggests IL is harder in this setting. To address this issue, we propose a new adversarial formulation where the reinforcement learning problem is replaced by mean-field control (MFC) problem, suggesting progress in within MFGs may have to build upon MFC.
Introduction
Imitation learning (II.) is popular framework involving apprentice agent who learns to imitate the behavior an expert agent by observing its actions and transitions. the context of mean-field games (MFGs). IL is used to learn policy that imitates the behavior of population of infinitely-many expert agents that are following a Nash equilibrium policy, according to some unknown payoff function. Mean-field games are approximation introduced to simplify the analysis of games with large (but finite) number of identical players, where we can look at the interaction between a representative infinitesimal player and a term capturing the population's 's behavior. The MFG framework enables to scale to an infinite number of agents, where both the reward and the transition are population- dependent. The aim is learn effective policies that effectively leam and imitate the behavior of a large population of agents, which is a crucial problem in many real-world applications, such as and financial markets
traffic management
crowd control
IL MFGs presents new challenges compared to single-agent IL, as both the (unknown) reward function and the transition kernel can depend on the population distribution. Furthermore, algorithms will depend on whether we can only observe the trajectories drawn from the Nash Equilibrium (NE) or if access the MFG itself, either driven by the expert population the imitating one.
The main question we address is whether IL in MFGs is actually harder than IL in single-agent settings and if we can use single-agent techniques to solve II. in the MFGs framework.
Although there exist IL algorithms for MFGs in the literature, of the quality of the learnt imitation policy. We will also explain that they essentially amount to reduction classic IL, and explain the underlying possible issues. So compare algorithms
comes with characterization
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

rational basis, we provide an extension of the concept of imitation gap to this setting and study it. Our contributions are:
We introduce a new solution concept for II. in MFGs called Nash imitation gap, which is a strict generalization of the classic imitation gap and that think may be more widely applicable to Multi-agent Reinforcement Learning.
In light of this new criterion, we first study the setting where only the reward depends on the population's ' distribution, while the dynamics does not. This setting was largely studied in the past few years [6 4 14 22], and we show that in this case IL in MFGs reduces to single-agent IL with similar guarantees for Behavioral Cloning (BC) and Adversarial Imitation (ADV) type of algorithms.
Then, we provide similar analysis in the more general setting where the dynamics depends on the population's ' distribution. In this case, we provide for BC and ADV approaches upper-bounds that are exponential in the horizon, suggesting that II. is harder in this setting. On an abstract way, all previous works of the existing literature correspond to this setting.
Due to these negative results, we introduce new proxy to the Nash imitation gap, for which we can derive a quadratic upper bound on the horizon. Then, we discuss how a practical algorithm could be designed with an adversarial learning viewpoint. The idea behind it is to use an approach similar to adversarial IL, where the underlying RL problem is replaced by Mean-Field Control (MFC) problem. We leave the design and experimentation of practical algorithms for future works, but this suggests that making progress on II. in MFGs may have to build upon MFC. We also provide a numerical illustration empirically supporting our claims in the appendix.
2 Background
2.1 Mean-field Games
Intuitively, an MFG corresponds to the limit of an N-player game when N tends towards infinity. We focus on the finite-horizon setting, in discrete time, and with finite state and action spaces. Mathematically, the MFG is defined by tuple M = (S, P.r. H. pu) where S is a finite state space, .A is a finite action space. P: x A x As + As is a transition kemeel, r S x A x As + R initial states. The first
is a reward function, H is finite horizon and po As is distribution and second imputs of P and r represent respectively the individual player's 's state and action, while the third input represents the distribution of the population. This allows the model capture interactions or mean field type. We denote H - 11] (0..... H - 1}. Since the problem is set in finite time horizon, we consider non-stationary stochastic policies of the form each n E [H - 1]. n. S + A This means that, at time n, a representative player whose state is 8n E S picks and use the notation Tn (a) (8)) to denote the probability to pick action a according to T (8x). We non-stationary rewards uniformly bound by that
(Top-... -H where for
action according to n. (.... We will also view n. as a function from S A to [0, 1]
also introduce the set of population populattionindependeen
will be useful later, R- = {r S x A x H - 1] + []}, 1]].
When a player is at state and uses action while the population distribution is p. it gets the reward r(s, a, p). In a finite-player game, P would be replaced by the empirical distribution of the other players' states. These players would be influenced by the player under consideration, leading to complex interactions. However, the influence of a single player on the population distribution becomes smaller as the number of players increases. In the limit, we can expect that each player has no influence on the distribution. We will use interchangeably the terms "agent" and "player".
The MFG framework allows to formalize this idea. So the problem faced by a single representative player is a Markov Decision Process (MDP), in which the distribution is fixed: Given a mean field sequence م (Pn)ne(n-11) 1]. the player wants to find a policy maximizing the value function V defined by:
H V(T,p)) E Σ r(S,, An. pw)
where So is distributed according to the initial state distribution Po. An (Sn),, and S P(Sn; Ans Pn)). The resulting policy is called a best response to the mean field p. We will sometime write V, (T,, p) to make explicit to reward of the value function.

---

Definition (Best response). A policy x is best response to if: (( = max, V(T',p)
Intuitively, p is Nash equilibrium if it is the distribution sequence obtained when all the players use best response policy against To formalize this idea, we introduce the notion of population distribution sequence induced by policy that does influence the transition kernel.
Definition (Population distribution sequence). We denote by p! the state state- cate-distribution sequence induced by the population following policy ग,, which is defined as:
Po (s)
=po(s);
pp(())
8 VES
Poti(s')
E. Pr (s) Ea In (((ss) 1i)),
(n, H S.
The state-action distribution sequence, denoted by p(m), is defined as:
1/ (s.
(n, [H ( A.
We can now give formal definition of Nash equilibrium
!
Definition (Nash equilibrium). A policy π is called a Nash equilibrium policy if it a best response against p², i.e., π is maximizer of n' + (=',p")) The distribution sequence p" induced by Nash equilibrium policy π is called a Nash equilibrium mean field sequence.
The value function can be written without expectation by introducing the state and state-action distributions for a single agent, which does not influence the transition kernel (only the population does, it is core reason for considering the mean-field limit).
Definition 4 (Single-agem distribution sequence). Consider an agent using policy x² who evolves among population using policy æ. We denote by plax)a' the state-distribution sequence of this single agent, which is defined by:
Po (s) = =Poss;
(z) (x)
s SES
(9) (8) = E. pn (1)a
(.) ((dl)))))))
(n,8") E H - 1] x S.
The state-action distribution sequence is defined as:
Na )5) (s) (<((ass)p (7) (s), (n,s,a) E A.
From these definitions we directly have that pla)x = plx) and wlnra = j(xr), Furthermore, for any policies and n², define generalized value function
#-1
(i''' (())
n=0 8,a
Definition 5 (Exploitability). The exploitability of a policy quantifies the gain for a representative player to replace its policy by best response:
E {xx) max ((()) - pin.
Nash equilibrium policy can be defined equivalently as a policy such that its exploitability is 0.
Finding Nash Equilibrium policy is different from trying to maximize the value function, which can be interpreted as social optimum. This problem is sometimes referred as mean field control problem (MFC) because it can be interpreted as optimal control for MDP where the state is augmented with the distribution.
Definition 6 (Social optimum). A policy स is socially optimal V p²) max V(T', p²
In general the Nash equilibrium and the social optimum do not coincide, i.e., the MFG policy and the MFC solution can be different. In other words, if π is an MFG solution, then we might have (T,p")) < max, (TT', p= ), and if π is an MFC policy, then we might have ((r) of 0.
In this work, will frequently make two common assumptions (e.g.. Asm. 1], 34 Asm. 1J).
We will sometimes omit the term "Nash" and simply write "equilibrium" when the context clear.

---

Assumption 1. The reward function r and the transition kernel P are Lipschitz continuous w.E.. the population distribution and have corresponding Lipschitz constants L, and Lp. In particular, for any state-action pair (8, a) it holds for any state distributions p. p² E A that
|r(s, a. p) - r(s, (."s,,,,'1 p')1 S Trllp p'111-
|P a, - P(-|s, a p') - Lpl p 1/11.
These assumptions mean that the reward and the transitions depend on the mean field in a smooth way. For example, r(s, a, p) = p() + F(ss (a) satisfies the assumption with L, = Cy. A reward of this form penalizes the agent for being in a crowded state. In particular, these assumptions imply that and P are continuous with respect to the distribution and since S and A are finite sets and we consider a discrete-timg finite horizon MFG, these assumptions are sufficient to ensure existence of a Nash equilibrium, see e.g. 100 Proposition 1].
Note that these assumptions do not assume that L, or Lp need to be small. However, we will consider separately the case Lp = 0, which has received attention in the MFG literature and which corresponds to situations where the mean-field interactions occur through the reward only. Note that when Lp L, 0, then there are no interactions so the Nash equilibrium condition becomes trivial and the problem reduces to a single agent MDP. We will write the value function as ((T)..
2.2 Classic imitation learning
The single-agent setting is special case of the above, with Lp = L, = O. In this case, the Imitation Learning (IL.) problem has been extensively studied (0 In IL we assume that we observe state-action trajectories generated by an expert who is using an optimal policy n² ,i.e., x E argmax V(T). We do not know π F V. r nor P. The goal learn policy, denoted by Æ which performs as well as the expert policy x according to the unknown reward: V(*^) = V(**) max,'' V(r').
Given the imitation policy A the imitation gap is non-negative quantity defined by VV( (2)] The goal is to learn a policy F whose imitation gap is as close to 0 as possible. However, when we do not know the model, this quantity cannot be minimized directly. For this reason, different methods were introduced in literature. Here we focus on the following two prominent methods: Behavioral Cloning (BC) 2 and adversarial IL such as Generative Adversarial IL (GAIL) [8.
For simplicity. we will denote pm = )==" _t= = p p(a")=A and μM = p((T
When the dynamics does not depend on the population (Lp 0), we will write p² p(
fx8 2u u )ar as the population driven by any has no effect the transition kernel.
Behavioral Cloning. In this work, we frame BC as minimizing the expected & dddistance between the action probability distributions of the expert and the imitation policy, where the expectation is over the expert state occupancy. Although practice it consists in a reverse KL-divergence, or equivalently as the maximum likelihood estimation in supervised learning, here we consider the f--nrrm distance (or scaled total variation), which is more convenient for the analysis. However, the analysis could be adapted to this maximum likelihood estimation with minor changes thanks to Pinsker's 's inequality (see App. A). In the finite-horizon case, one obtains a bound on quantities of the form:
BC = Eampg (I] x (s) n (O...., H 1}.
(1)
That is, we solve one BC problem per time-step, from data generated by an expert. The single-agent imitation-learning gap is bounded by O (B3) where BC = (a... will retrieve this result as special case of our analysis.
BC
26
We
Adversarial Imitation Learning. Using adversarial-lie approaches 18 13 or divergence between the state-action occupancy measures of the expert and the imitation policy. In the single-agent IL setting this divergence can be expressed as:
we control a distance
ADV = 11 1 c
n E (0. (O....,, -
Similar IL quantities are extensively studied in the single-agent case, leading to algorithms minimizing a divergence or distance such as Generative Adversarial Imitation Learning [8]] or IQ-learn [3]. we control the state-action occupancy measure errors, then we get a single-agent imitation-learning ADV gaining an H factor compared to
gap of order ( (DV H), where <DVV = maxne(0...... H-1] en
the BC bound 32

---

To make the link to adversarial approaches, controlling the terms of Eq. can be achieved through the following equivalent formulation, based on the Integral Probability Metric (IPM) formulation of the total variation (see Appx. Bor detailed derivation and additional discussions):
H min
max min (V (y()))
(3)
JER
with R. defined in Sec. 2.1 (non-stationary ingulation-indeeendenn rewards functions uniformly bounded by 1). This form is similar to classic adversarial imitation approach, learning both a reward function and a policy, the inner problem being a reinforcement learning (RL) problem. Previous work usually consider an f-divergence [15] [ between state-action occupation measures, which leads to different min-max problems. However, in this paper, we will focus on the li-distance, that we think is meaningful and practical abstraction of adversarial approaches. Our results could be extended to other settings by using tools like the Pinsker inequality.
Remark 1. Remember that in the single-agent case (same as when we have = 0) the transition dynamics and the reward function do not depend on the population distribution. In the mean-field game, on the other hand, the transition dynamics and the reward function can depend on the population distribution. For this reason, we need consider different quantities to be controlled. We will see more about it in the next section.
3 Related works
We provide a commented review of the literature focusing on the fundamentals of the different approaches, their pros and their cons.
To the best of our knowledge, the first work addressing the IL problem in MFGs is 33 The authors consider a discrete-time MFG over complete graph, and they propose a reduction from MFGs to finite-horizon MDP (with a population-augmentel state) and then use single-agent IL algorithms on the new MDP. In the reduction, the new reward function is computed in the following way: F(p, m) = Σ. p(s) Σ. T(als)r(s, a, p). considering that the state is the population distribution and the actions are the possible policies æ. Using this reduction, the authors implicitly assume that the observed expert is solving an MFC problem, i.c. she is looking for socially optimal policy (see Def. 6 However, in general, this does not actually coincide with Nash Equilibrium policy (see Def. 3 Then, the reduction works only for cooperative MFGs, but is prone to biased reward inference non-cooperative environments.
The first work enlightening this issue is [.] The authors consider a discounted finite-horizon MFG and propose a novel method called Mean Field IRL. They reframe the problem as finding a reward function that makes the expert policy x the best response with respect to the expert population distribution p², i.c., find a rppulation-dependeee solve this problem they use a max-
such that V( pf)) E argmax,, V(T, pf). To max-margin margin approach similar to 25 in the single-agent case. In fact, fixing the population distribution p², the MFG is reduced an MDP, and the imitation problem is reduced to single-agent IL. However, since they do not have access to the actual population distribution p they need to estimate it from samples. In this way, the authors do not have any actual theoretical guarantee on the performances of the recovered policy, since it depends on the estimation of p..
Recently, [ proposed a novel approach reusing ideas from adversarial learning 18 and max- imum entropy (36). The authors assume they have access to an expert optimizing mean- field-regularized Nash-equilibrium, i.e., the value-function has an additional regularization term:
V(x',p""= -M= H-! E. (H((T(-lss) + Σ. un (T)=" (s, a)r(s, a, pr (T))) with H the Shannon entropy. This term guarantees that the MFG has unique equilibrium solution, and only one best response policy. Then, they assume to have access to the population distribution p" or to be able to estimate this population distribution from samples. Fixing the population distribution. the MFG problem reduces to the single-agent setting, which allows applying GAIL [18 or maximum entropy IRI. to learn an approximate policy A This leads to two main problems. (i) We are actually estimating e from samples, trying to find a policy which gives us the true EE; this circulating reasoning leads to many estimation errors. (ii) From an abstract viewpoint, the final theoretical guarantee we can hope to have for the recovered policy A would approximately be || ()) [)( ||: (in practice for different distance or divergence, but involving the same occupancy measures), which may not
5

---

be sufficient as we will show in Sec.
12
We will see that the upper- upper-bound for this case has an
exponential dependency on the horizon.
In [5 the authors assume observing an MFG where the agents are acting according to a correlated equilibrium. The authors justify the study of correlated equilibrium by some applications where we can have access to some correlation device (c.g., traffic network equilibrium induced from the public routing recommendations). Similar M. the authors of this work reuse ideas from adversarial learning T8] to recover a policy observing a correlated equilibrium policy. As in 2 they fix the population distribution to be the expert one and then apply Single-agent GAIL to the problem. Then, although the solution concept is different, this approach faces similar problems as in 19 where instead the authors considered to observe an expert following Nash Equilibrium policy. We will focus on experts achieving a Nash equilibrium. Extending our results (see Sec. ! to more general equílibria such as coarse correlated ones is an interesting future research direction.
Notice also that all GAlL-like approaches discussed above learn an intermediate population-dependen reward function. This is complicated (as the population is a distribution over the state space, generally difficult to represent compactly), and in fact superfluous in their setting. Indeed, as all these approaches assume that the interaction done with the MFG driven by the expert population (or given approximation of it), it is sufficient to consider an intermediate population-indeeendenr but non-stationary reward. This will appears clearly in the IPM formulations we propose Sec. 5
4
Nash imitation gap and imitation in MFGs
We consider the imitation learning problem in MFGs. Similar to single-agent II., we observe the interactions between an expert and fixed MFG environment, for which we do not know the reward function r nor the transition kernel P. We only observe samples coming from an expert policy denoted by = which we assume to be a Nash equilibrium policy, i.e., E O. In single-agent IL the goal is clear: Find a policy x to minimize the imitation gap max; V(T) ) - V (T However, in MFG. the goal is less clear. Previous works focused on solving IL for single agent in population that stays at equilibrium, but this is not relevant for many applications, in which the population might use the learnt policy. The learnt policy should thus not only be good at the individual level, but it should also be an equilibrium policy. As a first contribution, we propose a natural formulation for studying the performance of imitation learning in MFG, called Nash imitation gap: Definition 7. The Nash imitation gap (NIG) of a policy π A is defined as:
{(xA)
max V(T',, (((*))) ((T (((*))) r'Ell
Therefore, the NIG is simply detined as being the exploitability of the considered policy. The NIG has many interesting and useful properties. (i) If it is zero, the recovered policy π a Nash equilibrium policy. (ii) It is generalization of the single-agent imitation gap (see above and See. 2.2 which is recovered as a special case when Lp = L, O.
As for the single-agent imitation gap, we cannot optimize it directly, since we do not know the reward function, but instead we can envision proxys, such as reducing the distance between the recovered policy A and the expert policy T (BC-like) or their occupancy measures (GAlL-like) as in the classic IL setting (see Sec. 2.2. In this section, we first discuss the imitation learning problem when the dynamics does not depend on the population, i.e. Lp O, common setting largely explored in the last years 22 p3) Then, we present our results for the general setting when the dynamics depends on the population, i.e. when Lp > 0.
For what follows, in addition to the Lipschitz assumption (Asm. D. we will also assume that the unknown reward function r for which the expert π is Nash equilibrium is uniformly bounded when the population the expert one.
Assumption 2. The unknown reward r satisfies
a,,,,,, max (r(s, a, p(*))))))))))))))))) S T Tmay- 8,0
4.1 Population-indeeendder dynamics: reduction to classic imitation
We start by analyzing simpler but commonly used setting (e.g., see 23 in the context of reinforce- ment learning methods, or [6 4 || in the context of the analysis of discrete continuous space

---

MFGs), where the dynamics does not depend on the population. Here the MFG interaction is without reward and is only the (unknown) reward function that depends on the population. This setting equivalent to observing interaction between an expert and an MDP, since the state-distribution does not depend on the population, i.e., p!=))' =p=
Behavioral Cloning. The behavioral cloning setting is the same as the single agent setting (see Sec.
2.2 i.e, we control:
BC := E>
TH (s)
{0, H 1}.
(4)
'n
where T is the expert policy and z the imitation policy. Under the assumption of the BC-type error, we give the following bound on the Nash imitation gap (proof in Appx. C
Theorem 1. Let BC ma... H01. c If Lp the Nash imitation gap satisfies
E(x²) S (2 + ) BC
Theorem shows that when Lp = we recover the single-agent imitation learning bound. Perhaps surprisingly, the simple BC approach not previously considered for MFG, to the best of our knowledge.
Adversarial learning, In the adversarial setting, similar to the single-agent case (see Sec. 2.2 we control distance or divergence between occupancy measures. More precisely, we consider the following distance between occupancy measures:
ADV
|p p Il n (0,
H 13
It important to recall that in this setting, the dynamics do not depend on the population, thus (m))"" ((=')=+ for every triplet of policies (I,, ,",").
Since this case the dynamics do not depend on the population distribution, the same IPM approach (see Eq. 3 of single-agent imitation-leandn
also works in this context. Then practically
solve the MFG IL problem using GAlL-like approaches [IS 19 [3.
We now provide novel bound on the Nash imitation gap (proof in Appx.
Theorem 2. Let ADV = max (U..... ADV If Lp = 0, the Nash imitation gap satisfies
E(TA) S H(L,, + Tmmax) )
In contrast to the quadratic horizon dependence in Theorem we derive here a linear horizon dependence. Furthermore, the bound in Theorem 2 almost the same (similarly the BC case) in the single-agent IL problem. In fact, it recovers the bound of 32 by setting L,- = O.
Discussion.
When Lp 0 interacting with the MFG without reward amounts interact with and MDP without reward, so from practical aspect any classic IL approach could be used, including Dagger-like approaches 2/ that do not analyse here. Our upper bounds show that when the dynamics is independent of the population, IL for MFG has similar guarantees as in single- agent imitation learning. In fact, results suggest that population-dependee function affects the IL policy performance very moderately (through the L, constant). However, new challenges may arise if we also want to recover the reward function, in the case of Inverse Reinforcement Learning. We leave this interesting research direction for future work.
unkown reward
4.2 Population-dependent dynamies
When the dynamics of the MFG depend on the population. i.c., Lp > O, then the previous results do not apply anymore. In this section, we present results on MFGs with population-dependent dynamics, for the same proxys introduced above (BC and adversarial).
Behavioral Cloning. The BC proxy to the NIG is the same in Equation 4 In this case, however, the bound we get is no longer comparable to the classic IL setting (proof in Appx. D
Theorem 3. Let BC max.e(0.....f H-
If Lp > O, the Nash imitation gap satisfies:
(( + Tmmxa)
E(TA) <
(1 + T.p.) Tmmx .72 BC
L2
7

---

We observe that when the dynamics depend on the population, the dependence on the horizon is no longer quadratic but exponential. From technical viewpoint, this comes from the dependency of the transition kernel to the population. A worse dependency makes sense intuitively. In the classic II setting, an error on policies will amplify the occupancy measure level (drift phenomenon in imitation learning). Here, this problem is even more amplified by the fact that the transition kernel that defines the occupancy measure itself depends on the related population, amplifying even more the imitation error. Sec. 5 provides some empirical evidence that IL in MFGs has exponential dependence on the horizon for BC as Lp increases.
Although we cannot claim our result is tight, this suggests that in MFGs we cannot hope to use BC to obtain a good imitation policy π but we need control the divergence between the state-action occupancy induced by π and the one induced by x²
Adversarial learning. In contrast the aopulation-independeee case, the quantity control in this setting is not trivial. In fact, it depends on the MFG interaction assumption. We can assume to have the possibility to interact with only the MFG or with the MFG driven by مf. These two types of interactions lead us to consider two different errors, We start by considering the error we would like minimize we can interact with the MFG driven by the expert population Of. Assuming access to this MFG, the IL problem reduces to doing classic IL in an MDP without reward and with transition distribution P- a, pm The error is defined follows:
vanilla- ADV || (1(("))=" )m
1/ jx II., E (0. (O...... H 13.
77
This assumption was implicitly made in all previous works (see Sec. 5 where the authors assume to fix the expert distribution of and then solve the IL problem. However, assuming have access to the expert distribution may not be reasonable in practice, and due to this in [9] g the authors replace the expert population distribution of with its approximation from sampling p in order learn {(="==" In reality, however, we seek to learn
μ {)= and then p². which is the ultimate goal of the problem. This circular reasoning leads to not easily having theoretical guarantees for this setting.
In this case, for obtaining an adversarial formulation, we can use similar approach as the one for the non-population dependent dynamics, Eq. @.. providing (details in Appx. B
H-
Iln (n
11(=5)= (x - Mh 1111 max min (T pp(r5) -V((T, ((
min
JER
n==
We can observe that the inner problem is again RL problem (for the MDP induced by p!=()) and in practice any single-agent adversarial approach could be applied to solve for a similar proxy (related to different min-max problem).
We provide bound for this approach (proof in Appx. M- en yauilla-ADY Lp > 0 the NE imitation gap E(TA) < (2 + Tmax)
Theorem 4. Let e vanilla-ADY ADV satisfies:
(1 + Lp) + +rmax
vanilla-ADV
Lr
Therefore, in this case, in practice we can apply GAlL-like approaches the MDP with transition distribution P(-|s, a, p²), we have an exponential dependency in the horizon. Interestingly this is close to the quantity that previous works ? g tried to control. Although we do not know if this bound is tight, reasonably controlling this quantity can lead to weak theoretical guarantees. Sec. provides empirical evidences that, when H and Lp are large enough, vanilla-ADV exponential depends the horizon like BC.
4.3 Population-dependent dynamics: new efficient proxy
Although the vanilla-ADV error a reasonable quantity to control, another interesting proxy is to consider state-action occupancy measures with population induced by the associated policy, namely
MFC-ADV : || ) 1
)x Il
{O...., H -1).
To control this quantity, we do not need to have access to the expert population (except through data), we can directly interact with the MFG, driven by what are learning. As explained in Sec.
8

---

L=0.01
L=0.05
L=0.1
L=0.5
10a
10a
BC
10*
10a
vanilia-DVV MFC-ADV
10a
2015
10a
10a
20
empinca
10
10
10
10
10a
10a
10:
0
50 100 0
50 100
50
100
50
100
H
Figure 1: For each the curves in Fig. each one for a specific value of L, of H, and for a type of error (BC, van and MFC-ADV), we consider the points (NIGR, ex) making the curve, and compute the value max NIGK) as an empirical upper-bound for the specific value of L, H and kind of eπror. Then, for each value of L and each kind of eπror, we plot this empirical upper-bound as function of the horizon H, with log-scale on the y-axis.
if Lp = O then this quantity is the same as the vanilla-ADV error. Before presenting and discussing an adversarial formulation (that will explain the naming choice for the error), we provide novel bound for this quantity (proof in Appx.
Theorem 5.
Let MFC-ADV
MPC If Lp > O, the Nash imitation gap max,e E (O...., ..... Cn
satisfies:
{(T S [3p H (2Lr + Tmax) MRC-ADV
This gives us significant improvement compared to the BC case and the vanilla-ADV error. Indeed, the dependency the horizon is now quadratic and not anymore exponential. Comparing this result with classic imitation learning we have worse dependency on H, since in the classic setting is only linear (we can recover this dependency when Lp 0). However, explained before, the fact that the transition kernel does depend on the population indeed intuitively implies larger amplification of errors. Sec. 5 provides empirical evidence that this approach is better than the previous two, with much less influence from H and Lp.
Now, we provide an adversarial formulation, to get sense of what a practical algorithm could look like. Using again an IPM argument, we have that (details in Appx. B
H-1
-14 (T)) min max
FRR { V7 ((T,, ((==)) - Vy(T,,(T))
min
1==0
Notice that it is not obvious if we can switch the min and the max here, due to the underlying set of policy-inducee induced occupancy measures being not necessarily convex (due to the dependency of the dynamics on the population). Assuming we can, we still learn an intermediate population-indeeendeen non-stationary reward, but now the underlying control problem is longer RL, it an MFC problem, as it implies studying max,, Vy( p!*)), where the population does depend the optimized policy. This suggests that in practice one could start from classic ad versarial IL approach, and replace the un- derlying RL algorithm by an inner MFC algorithm (e.g. (28]
B)). We leave the design and im- plementation of such a practical algorithm for future work, which may be more complex than straight replacement of the control part (notably, many MFC approaches learn population-dependen policy). However, this overall suggests that making progress on IL for MFGs may have to build upon MFC.
5 Simulation
In order to provide some empirical evidences of the insights given by our analysis (influence of the horizon and the dependency of the dynamics to the population on the various considered proxys to
the Nash imitation gap), we introduce the "Attractor MFG" (see more details about it in App. D This is a 2-state and 2-action MFG with initial distribution satisfying An (#p) 1, with horizon H and with Lipschitz parameter L. The reward only depends on the state (not on the distribution nor the

---

action) and satisfies for all a E A. As.
r(50, a, p) = 0 and r(s1, = 11
In the state 81, any choice of actions leads deterministically to 81, the transition kernel satisfies P(s1|8i a, p) for all E A. E As. In the state 8o, the action an leads deterministically to 81, while action dg leads stochastically to one of the two states: the higher the fraction of the population in 81, the higher the chance to transit to 81 after choosing 0g-
P(s (9, 01 p) and (5 40, p) - min [1, Lp(s1)}
Therefore, the state 81 is an attractor, hence the chosen name for the MFG.
The experiment consists in computing the errors BC panilla-ADY and en MFC--AD for various values of L. (0.01, 0.05, 0.1, 0.5) and H (3. 25, 50, 75, 100} and we show the NIG as a function of the mentioned errors. From Fig. D we can observe exponential dependency of the horizon for both BC and vanilla-ADV when L increases, while this does not happen for MFC-ADV. This experiment demonstrates empirically what our theoretical upper bound shows, supporting the insights of our analysis. This suggests that a practical algorithm for IL MFGs needs to minimize the MFC-ADV error (see Section 4.2) In Appx. D we provide more experimental results.
6 Conclusion
In this paper, we have studied the recent question of imitation learning in mean-field games. We have reviewed the few previous works tackling this problem and provided a critical discussion on the proposed approach. We then have introduced the new solution concept of Nash imitation gap to quantify the quality of imitation. In the simpler case of a population-indeeendenn dynamics, we have shown that the problem basically reduces to single-agent imitation learning, and that abstractions of the canonical BC and adversarial approaches come with a similar performance guarantee. In the harder nopulation-deeendee horizon, for both BC and adversarial IL. the latter being the approach adopted in previous work. We also introduce a new proxy that amounts to control different occupancy measures, not solely driven by the expert population but by the policy-induced population. From a practical viewpoint, it only implies interacting with the MFG (without access to the expert population for driving the dynamies), and from a theoretical viewpoint it enjoys much better quadratic dependency to the horizon. The associated adversarial formulation suggests that classic adversarial II. approaches could be adapted by replacing the inner RI. loop by an MFC one.
case, we have provided upper-bounds that are exponential in the
This work opens a number of interesting research questions. Our last result suggests a simple modification of existing adversarial approaches, but in practice it may be more difficult than just replacing the control part, and could call for additional research in MFC and MFGs. Maybe also that controlling other kinds of occupancy measures, or even different quantities related to the policy and dynamics, may lead to even better guarantees, ideally recovering the linear dependency to the horizon of the single-agent case. We provided upper-bounds, but there is no known associated lower-boum in this setting, which is another interesting research direction. We focused on experts achieving a Nash equilibrium, and extending our work to different kind of equilibria another possible direction. We focused on imitating the expert, not on recovering the underlying optimized reward (inverse RL). Doing so may require different approach, as our adversarial formulations all rely on population-iindeendeen rewards (which is convenient from practical viewpoint, whenever one just wants to recover the policy). We also plan to work on the extension of Nash imitation gap to other kinds of games.
Funding and Acknowledgements
Giorgia Ramponi was supported by the ETH AI Center and Google Deepmind. Pavel Kolev was supported by the Cyber Valley Research Fund and the Volkswagen Stiftung (No 98 571). Mathieu Lauriere is with the NYU Shanghai Frontiers Science Center of Artificial Intelligence and Deep Learning, and the NYU-ECNU Institute of Mathematical Sciences NYU Shanghai. Part of the work was done while Mathieu Lauriere was visiting faculty at Google Brain. We thank anonymous reviewers for comments, which helped improve the presentation of the paper.
10

---

References
[1] Yves Achdou and Jean-Miched Lasry. Mean field games for modeling crowd motion. Contribu- tions to partial differential equations and applications, pages 17-42, 2019.
[2] Berkay Anahtarei, Can Deha Kariksiz, and Naci Saldi. Q-learning in regularized mean-field games. Dynamic Games and Applications, 13(1):89-117,22 2023.
[3] Andrea Angiuli, Jean-Pierre Fouque, and Mathieu Laurière. Unified reinforcement Q-learning for mean field game and control problems. Mathematics of Control, Signals, and Systems, 34(2):217-271, 2022.
[4] Pierre Cardaliaguet and P Jameson Graber. Mean field games systems first order. ESAIM: Control, Optimisation and Calculus of Variations, (13):660-722,, 2015.
[5] Rene Carmona. Applicatioons of mean field games in financial engineering and economic theory. arXiv preprint arXiv:2012.00533,, 2020.
[6] René Carmona and Mathieu Laurière. Deep learning for mean field games and mean field control with applications to finance. arXiv preprint arXiv:2107.04566 04568, 2021.
[7] René Carmona, Mathieu Laurière, and Zongjun Tan. Model-free mean-field reinforcement learning: mean-field MDP and mean-field Q-learning. arXiv preprint arXiv:1910. 12802, 2019.
[8] Yang Chen, Libo Zhang, Jiamou Liu, and Shuyue Hu. Individual-level inverse reinforce- ment learning for mean field games. In Proceedings of the 21 International Conference Autonomous Agents and Multiagent Systems, pages 253-262- 2022.
[9] Yang Chen, Libo Zhang, Jiamou Liu, and Michael Withrock. Adversarial inverse reinforcement learning for mean field games. arXiv preprint arXiv:2 14654, 2021.
[10] Kai Cui and Heinz Koeppl. Approximately solving mean field games via entropy reeropy-regularizedd deep reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1909-1917. PMLR, 2021.
[11] Christian Dogbé. Modeling crowd dynamics by the mean-field limit approach. Mathematical and Computer Modelling, 12(9-10):1506-5553 2010.
[12] Mohammed Elhenawy, Ahmed A Elbery, Abdallah A Hassan, and Hesham A Rakha. An intersection game-theory-basse traffic control algorithm in a connected vehicle environment. In 2015 IEEE 18th international conference on intelligent transportation systems, pages 343-347. IEEE, 2015.
[13] Divyansh Garg, Shuvam Chakraborty, Chris Cundy, Jiaming Song. and Stefano Ermon. Iq-learn: Inverse soft-q learning for imitation. Advances in Neural Information Processing Systems, 34:4028-4034 2021.
[14] Matthieu Geist, Julien Pérolat, Mathieu Laurière, Romuald Elie, Sarah Perrin, Oliver Bachem, Rémi Munos, and Olivier Pietquin. Concave utility reinforcement learning: The mean-fieh field game viewpoint. Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pages 489 2022.
[15] Seyed Kamyar Seyed Ghasemipour, Richard Zemel, and Shixiang Gu. A divergence mini- mization perspective on imitation learning methods. In Conference on Robot Learning, pages 1 1259-1277. PMLR, 2020.
[16] Diogo A Gomes, Joana Mohr, and Rafael Rigao Souza. Discrete time, finite state space mean field games. Journal de mathématiques pures et appliquées, 93(3):308-328, 2010.
[17] Haotian Gu, Xin Guo, Xiaoli Wei, and Renyuan Xu. Mean-field controls with Q-learning for cooperative MARL: convergence and complexity analysis. SIAM Journal on Mathematics of Data Science, 3(4): 168-1196, 2021.
[18] Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. In Advances in neural information processing systems (NeurIPS), 2016.

---

[19] Liyiming Ke. Sanjiban Choudhury. Matt Barnes, Wen Sun, Gilwoo Lee, and Siddhartha Srini- vasa. Imitation learning as f-divergence minimization. In Algorithmic Foundations of Roboties XIV: Proceedings of the Fourteenth Workshop on the Algorithmic Foundations of Robotics 14, pages 313-329. Springer, 2021.
[20] Takayuki Osa, Joni Pajarinen, Gerhard Neumann, J Andrew Bagnell, Pieter Abbeel, Jan Peters, et al. An algorithmic perspective on imitation learning. Foundations and Trends() in Robotics, 7(1-2)11-199 2018.
[21] Barna Pasztor, Ilija Bogunovie, and Andreas Krause. Efficient model-based multi-agent mean- field reinforcement learning. arXiv preprint arXiv:2107.04050) 2021.
[22] Julien Pérolat, Sarah Perrin, Romuald Elie, Mathieu Laurière, Georgios Piliouras, Matthieu Geist, Karl Tuyls, and Olivier Pietquin. Scaling mean field games by online mirror descent. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pages 1028-1037, 2022.
[23] Sarah Perrin, Julien Pérolat, Mathicu Laurière, Matthieu Geist, Romuald Elie, and Olivier Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems, 33:13 1319991312111 2020.
[24] Dean A Pomerleau. Efficient training of artificial neural networks for autonomous navigation. Neural computation, 3(1):88-97) 97, 1991.
[25] Nathan D Ratliff, J Andrew Bagnell, and Martin A Zinkevich. Maximum margin planning. In Proceedings of the 23rd international conference on Machine learning, pages 729-736, 2006.
[26] Stéphane Ross and Drew 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.
[27] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-regret online learning. In Proceedings of the fourteenth interna- tional conference on artificial intelligence and statistics, pages 627-635. JMLR Workshop and Conference Proceedings, 2011.
[28] Jayakumar Subramanian and Aditya Mahajan. Reinforcement learning in stationary mean- field games. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 251-259, 2019.
[29] Gokul Swamy, Sanjiban Choudhury, Andrew Bagnell, and Steven Wu. Of moments and match- ing: A game-theoretic framework for closing the imitation gap. In International Conference on Machine Learning, pages 10022-10032. PMLR, 2021.
[30] Takashi Tanaka, Ehsan Nekouei, and Karl Henrik Johansson. Linearly solvable mean-field road traffic games. In 2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 283 289. IEEE, 2018.
[31] Huisheng Wang, Yuejiang Li, and H Vicky Zhao. Research on intelligent traffic control methods at intersections based on game theory. arXiv preprint arXiv:2009.05.: 05216, 2020.
[32] Tian Xu, Ziniu Li, and Yang Yu. Error bounds of imitating policies and environments. Advances in Neural Information Processing Systems, 33:15737-15749, 2020.
[33] Jiachen Yang. Xiaojing Ye, Rakshit Trivedi. Huan Xu, and Hongyuan Zha. Learning deep mean field games for modeling large population behavior. arXiv preprint
2017.
[34] Batuhan Yardim, Semih Cayci, Matthieu Geist, and Niao He. Policy mirror ascent for efficient and independent learning in mean field games. arXiv preprint 1xXx::2212..144999 2022.
[35] Zhiyu Zhao, Renyuan Xu, Haifeng Zhang, Jun Wang, Mingyuan Zhang, and Yaodong Yang. Imitation learning for mean field games with correlated equilibria. openreview preprint:
WU= 2023.
[36] Brian D Ziebart, Andrew Maas, J Andrew Bagnell, and Anind K Dey. Maximum entropy inverse reinforcement learning. In Proceedings of the 23rd national conference on Artificial intelligence- voliliennceeooueeeee. 3, pages 1433 1438, 2008.
12


Reviews:
[{"review_id": "sozNxVxADW", "reviewer": "Reviewer_4ip4", "summary": "In this work, the authors propose a newly defined measure called the Nash imitation gap for imitation learning in mean-field games (MFG). They establish upper bounds for the Nash imitation gap of behavioral cloning and adversarial imitation learning in both population independent and dependent dynamics in MFG. Additionally, they introduce the formulation of mean-field control (MFC) problem as a proxy to address population-dependent dynamics in imitation learning scenarios.", "questions": "Questions:\n\n1.In line 169, could you provide a more concrete justification for the use of the L1 distance as a measure?\n\n2.Line 238 mentions the need for the learned policy to be an equilibrium policy, but it's not clear why this is necessary. Could you elaborate on the significance and potential applications of requiring an equilibrium policy?\n\n3.Could you justify the need for defining the Nash imitation gap when exploitability is already defined? Are these measures equivalent, and is it possible to simplify by using just one of them?\n\n4.The distinction between the learner's population and expert's population in the paper reminds me of the difference between online imitation learning (e.g., DAgger) and offline imitation learning (e.g., behavior cloning). Are these pairs of concepts related, and if so, how do they connect to the ideas presented in the paper?", "limitations": "1.The lack of a clear motivation for the inclusion of the newly proposed performance measure undermines its justification and relevance. \n\n2.The limited scope of experiments and the absence of quantitative evaluations and comparisons with other approaches weaken the justification for using the Nash imitation gap as a measure for quantifying the quality of imitation. \n\n3.The ambiguous goal of mean-field games (MFG) and the using the Nash imitation gap as a performance measure may limit its applicability in real-world applications.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1.The authors of this paper demonstrate a high level of clarity in their definitions and statements, making the paper easily readable and accessible to the readers. This clarity enhances the understanding and comprehension of the presented concepts and results.\n\n2.One notable contribution of this paper is the introduction of an alternative optimization goal for imitation learning in mean-field games (MFG). By adopting this alternative goal, the paper avoids the need for approximating the MFG dynamics driven by the expert population. This alternative approach provides a novel perspective and potential solution for tackling the challenges associated with MFG-driven imitation learning.", "weaknesses": "1.While the authors provide a numerical illustration in the appendx, the lack of comprehensive experiments weakens the justification for using the Nash imitation gap as a measure for quantifying the quality of imitation. The absence of quantitative evaluations and comparisons with other approaches limits the ability to fully assess the effectiveness and practical significance of the proposed measure.\n\n2.Despite introducing a new perspective through the Nash imitation gap, this paper does not present any new algorithms or methods specifically designed for addressing this measure. This limitation reduces the overall significance and contribution of the work, as it does not offer novel practical solutions or techniques that directly leverage the Nash imitation gap.\n\n3.The lack of clear motivation for the use of the newly proposed performance measure undermines the justification and relevance of its inclusion. Providing a comprehensive rationale would strengthen the understanding and significance of the contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the insightful comments and for recognizing the clarity and the novelty of the work. We answer the raised questions below.\n\n### Weaknesses\n\n1. ¨*the lack of comprehensive experiments weakens the justification for using the Nash imitation gap as a measure for quantifying the quality of imitation*¨. (answer also Limitations 2) In our work we provide the **first measure** to evaluate the performance of imitation learning algorithms for MFGs. We believe that providing a valid performance measure is a preliminary step needed to design a valid algorithm for a specific problem (in this case for imitation learning in MFGs). Moreover, our analysis suggests that with population-independent dynamics MFGs, single-agent imitation learning algorithms such as Behavioral Cloning or adversarial approaches will achieve good performances also in MFGs. This is a notable result, since previous works (add citations) are, from an abstract perspective, instances of what we called vanilla-ADV which shows similar performances of easier methods as BC (surprisingly not considered in the literature). To summarize, in the case of MFGs with population-independent dynamics, we can use single-agent IL algorithms whereas on MFGs with population-dependent dynamics, we need different algorithms than the ones used in literature. For the latter setting, we propose a new algorithm design principle (MFC-ADV), which leads to better performance.\n\n\n2. ¨*this paper does not present any new algorithms or methods specifically designed for addressing this measure*¨. The main contribution of this paper is to provide a **systematic analysis** of the MFG imitation learning problem setting. Moreover, we showed which distance needs to be optimized, i.e., the MFC-ADV. We do not provide a practical algorithm to optimize this, but we explain which proxy should be used and considered. We believe that our work advances the study of the IL problem, providing a relevant measure of how good the imitation is (the NIG) and how to achieve good performances with respect to this metric (optimizing the MFC-ADV).\n\n3. ¨*The lack of clear motivation for the use of the newly proposed performance measure*¨. (answer also Limitation 1-3) The single agent imitation learning problem aims at minimizing the imitation gap assuming the expert is optimizing an unknown reward function. The imitation gap is the value function difference between the policy we are recovering with the imitation learning algorithm and the expert’s policy, for the unknown reward function. In our work we proposed the Nash Imitation Gap, which is the **natural extension** of the imitation gap to the MFG setting. Doing this we are defining the problem setting, and the goal of imitation learning in MFGs. As pointed out by reviewer Qrta, our work ¨ proposes a novel solution concept, NIG, which generalized the classic imitation gap¨. We will add this explanation more clearly in the final version of the paper.\n\n### Questions\n\n1. ¨*justification for the use of the L1 distance as a measure*¨. The main reason to use the L1 distance is its simplicity for conveying the main message. However, the whole analysis can be easily extended to other distance metrics (as KL-divergence). In fact, using tools such as Pinsker inequality (as mentioned eg l.149-150); we would get similar bounds with $\\sqrt{\\epsilon}$ rather than $\\epsilon$. This would not influence the main message of the paper which is the exponential dependency to the horizon of the BC and vanilla-ADV, whenever the dynamics does depend on the population. \n\n2. ¨ *the need for the learned policy to be an equilibrium policy, but it's not clear why this is necessary.* ¨ For single-agent imitation learning is usually assumed that the observed policy is the optimal policy for some unknown reward function. We extended this concept to the MFG setting, assuming that the observed policy is a Nash equilibrium for some unknown reward function, and we quantified the quality of the imitation accordingly to it.\n\n3. ¨ *justify the need for defining the Nash imitation gap when exploitability is already defined* ¨. In the single-agent imitation learning setting, the imitation gap is just the value function difference between the expert´s policy and the imitating policy. We extended this to the MFG setting. In fact, as stated in the paper (see l.242), \"the NIG is simply defined as being the exploitability of the considered policy\" (for the unknown reward function). \n\n4. ¨ *Are these pairs of concepts related, and if so, how do they connect to the ideas presented in the paper?* ¨ Thanks for the interesting question. We can say yes and no. In fact, in the single-agent imitation learning we have only the policy as the state-action distribution induced by it. Then, in the offline and online setting are considered distance metrics which depends on the state-action distribution of the expert´s policy or the imitating policy. In the MFG setting we are on a different level, since we have both the policy and the population (which can be induced by a different policy). Then we need to consider if the population is induced by the imitating policy or by the expert´s one.\n\n"}, {"review_id": "NHFZsvCwKF", "reviewer": "Reviewer_MgoB", "summary": "The authors prove new upper bounds on the error in imitation learning for mean-field games. They then propose a new approach based on using mean-field control, which might provide a more reasonable imitation goal for imitation learning.", "questions": "Which further studies should be executed to solidify empirical evidence and why did you choose the setting you did in the appendix? Can a  small explanation be fit into the main text?", "limitations": "The authors discuss the limitations of their work generally very well. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clear in its description of connections and provides extensive mathematical arguments. The authors clearly show a gap in current literature and proceed with an ample analysis of how to fill it, which -- albeit very preliminary -- may lay substantial ground work for future research, as described in the paper's very own conclusion.", "weaknesses": "In my opinion, the paper's biggest weakness is that it talks about practical applications only in the introduction and then never again. The whole paper would benefit from presenting concrete examples for the various settings that are discussed and including references, where these settings might occur \"in the wild\". Most notably the link to practice is lacking in l.s 235-239 and 321-324. Numerical analysis was suggested in the paper and is, in fact, presented in the appendix to some extent, but might have also deserved a little bit of space in the main paper. As it is, it is hard to see the practical applications of the proposed techniques.\n\nWhile related work is discussed very well, I do not see why it is pointed out as a separate contribution. Overall, the list of contributions could be stream-lined when strengthening the overall story (by referring to the beginning in the conclusion, e.g.).\n\nThe writing style is very good. Minor mistakes persist:\n- l. 87 \"policy, that\" --> \"policy that\"\n- l. 135: \\pi_E ---> \\pi^E\n- l. 319: \"kind\" ---> \"kinds\"\n- l. 379: \"works open\" --> \"work opens\"\n- throughout: comma after \"i.e.\" is set inconsistently.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the insightful comments. We would like to thank the reviewer also for recognizing the clarity of our work and how our paper  ¨shows a gap in current literature and proceeds with an ample analysis of how to fill it¨. \nWe answer the raised questions below. Thank you for pointing out the typos, we corrected them according to your suggestions.\n\n### Weaknesses\n\n- Practical applications are the main reason which drives our study on Imitation Learning for MFGs. Many real-world sequential decision making problems can be formulated as a MFG, from traffic routing to financial management or online business with a large customer body. We will extend the discussion about the relevant applications in the main paper. Furthermore, we will add the empirical evaluation in the main body, using the new results provided in the pdf file. It is also important to notice that, with our last experiment, we showed empirically the exponential dependency of BC and vanilla-ADV on the horizon.\n\n- We described the related work as one of the main contributions of the paper since with this paper we tried to harmonize the different solution concepts presented in the SotA. However, we have no objection in toning this down.\n\n### Questions\n\n- The numerical simulation provides an experimental verification of the theoretical results presented in the paper. This hard-instance MFG is inspired by the hard-instance MDP used to show the lower bound for vanilla imitation learning. We provide a new experiment in the pdf file which shows empirically the exponential dependency of BC and vanilla-ADV on the horizon, for this hard-instance MFG.\n"}, {"review_id": "KHE5tel9Gw", "reviewer": "Reviewer_uQRX", "summary": "This paper focuses on the imitation learning problem in mean-field games. The authors propose a new performance metric Nash imitation gap. They show that when the transition kernels of MDP are independent of the mean fields, the imitation learning problem reduces to that in the single-agent MDP. When the transition kernels of MDP depend on the mean fields, the upper bound of the suboptimality grows exponentially in horizon H. A new adversarial algorithm is proposed to mitigate such exponential dependency.", "questions": "The questions are provided in the previous section.", "limitations": "Limitation part is missing in the paper.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper focuses on provably efficient imitation learning algorithms. The previous works do not provide any performance guarantee for imitation learning algorithms in MFG. In contrast, the authors derive the suboptimality bounds for BC and adversarial imitation learning algorithms. Particularly, when the transition kernels depend on the mean field, the authors propose a new adversarial algorithm to mitigate the exponential dependency on the horizon.", "weaknesses": "1. More justifications should be provided for the l_1 norm-based algorithm. The previous works for BC all focus on the log-likelihood type algorithms, and algorithms for GAIL focus on the Jensen-Shannon divergence-based algorithm. However, this paper adopts the l_1 error optimization framework, which is quite different from the empirical implementation. More discussions should be provided to justify this new framework. In addition, how to transfer the results in this paper to the analysis of the original algorithms should be discussed.\n\n2. As stated in the paper, when the transition kernels depend on the mean field, the exponential dependence on the horizon may not be tight. The empirical verification will be very helpful to demonstrate the true dependency on the horizon.\n\n3. For the proposed algorithm in Section 4.3, the reformulation of the algorithm below line 353 requires the value of $\\rho^{(\\pi)}$. However, it is not clear how to calculate this quantity from the paper. More clarification is required here.\n\n4. For the algorithm in Section 4.3, it is not clear why we can assume that min and max are exchangeable in the reformulation. What kind of condition is required should be explained.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the insightful comments and for recognizing that our work is the first one to provide theoretical guarantees, which shows how previous approaches have exponential dependency on the horizon. Thanks also for recognizing that we ¨propose a new adversarial algorithm to mitigate the exponential dependency on the horizon¨.\nWe answer the raised questions below.\n\n\n### Weaknesses\n\n1. ¨ *More justifications should be provided for the l_1 norm-based algorithm.* ¨ The main reason to use the L1 distance is that its simplicity conveys the main message. However, the whole analysis can be easily extended to other distance metrics (as KL-divergence). In fact, using tools such as Pinsker inequality (eg, see l.149-150), we would get similar bounds with $\\sqrt{\\epsilon}$ rather than $\\epsilon$. This would not influence the main message of the paper which is the exponential dependency to the horizon of the BC and vanilla-ADV.\n\n2. ¨ *The empirical verification will be very helpful to demonstrate the true dependency on the horizon.* ¨ We provide a numerical simulation in Appendix C. The experiments show that on a difficult instance, whenever the Lipschitz constant L or the horizon H are large, vanilla-ADV behaves as badly as BC, and, on the other hand, MFC-ADV continues to have a better behavior. Moreover, we provide another figure with this rebuttal (see the 1-page pdf attached to this rebuttal), that showcase the empirical upper-bound for this hard instance as a function of the horizon, where both BC and vanilla-ADV are exponential for large enough L, while MFC-ADV is not, confirming our analysis.\n\n3. ¨ *it is not clear how to calculate this quantity from the paper.* ¨ The $\\rho^\\pi$ quantity can be evaluated following definition 2 (see l.88).\n\n4. ¨ *it is not clear why we can assume that min and max are exchangeable in the reformulation.* ¨ We thank the reviewer for pointing out this relevant point. As we discussed in appendix A (557-563), we cannot always switch the min and max. In fact, we need the set of policy-induced occupancy measures to be a convex set (in addition to the linearity of the value in both the reward and the occupancy measure). Whenever the dynamics does not depend on the population, this is true, this set is even a polytope. When the dynamics depends on the population, it is less clear, and ensuring the convexity of the underlying set may require additional assumptions on the transition kernel. The MFG used in the experiment, for example, satisfies this property. \n"}, {"review_id": "u24r6LLNfO", "reviewer": "Reviewer_Qrta", "summary": "The paper presents a novel solution concept Nash imitation gap (NIG) for imitation learning problems in Mean-field games. For both population-independent and population-dependent dynamics, the author provides the upper-bounds of NIG for behavioral cloning (BC), vanilla adversarial imitation learning (vanilla-ADV), and mean-field controlling adversarial imitation learning (MFC-ADV). The empirical results show that MFC-ADV is better than vanilla-ADV which is better than BC.", "questions": "1. Could the upper-bounds for BC and vanilla-ADV be improved to polynomial in the horizon? Are there any evidence showing that their NIGs should be exponential in horizon?\n2. Is MFC-ADV still the best one if $s_1$ is no longer a sink in the experiment? For example, $P(s_0 \\vert s_1,a_0,\\rho)>0$.\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The paper proposes a novel solution concept, NIG, which generalized the classic imitation gap, and shows the upper-bounds of NIG for several different settings.\nQuality: The theoretical analyze is solid and supports the upper bounds well.\nClarity: The paper is clearly written and well organized.\nSignificance: Both the theoretical upper bounds and the empirical results suggest that the adversarial imitation learning could replace the inner RL by an MFC.\n", "weaknesses": "No lower bound of NIG is provided so that the theoretical results cannot directly indicate which methods (BC, vanilla-ADV, MFC-ADV) is the best one.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the insightful comments. We would like to thank the reviewer to recognize the originality of our paper (¨a novel solution concept, NIG, which generalized the classic imitation gap, and shows the upper-bounds of NIG for several different settings¨), and the clarity of our work and the significance (¨both the theoretical upper bounds and the empirical results suggest that the adversarial imitation learning could replace the inner RL by an MFC.¨). \nWe answer the raised question below.\n\n### Questions\n\n1. (Also answer to Weaknesses) We provide a new figure with the rebuttal (see the 1-page pdf attached to this rebuttal), related to the experiment in Appx C. This figure shows the empirical upper-bound as a function of $H$, for this hard-instance MFG, for various values of L. One can observe that as L increases, the dependency of the (empirical) bound for both BC and Vanilla-ADV is **clearly exponential**, while that of MFC-ADV is not. This supports our theoretical analysis, and provides empirical evidence that the bound cannot be improved to be polynomial in the horizon. We plan to add this figure to the main text. \n\n2. Choosing $P(s_0|s_1, a_0, \\rho) >0$ would make the problem easier (this problem was designed specifically as being a hard MFG, hence the sink, inspired by the hard MDP construct used to showcase lower-bounds for single-agent imitation learning). However, MFC-ADV would still be better than Vanilla-ADV. The reason for this is that there will still be compounding errors at the population level (in the MFG setting, we don’t only have compounding errors at the policy level, but also at the population level, when the dynamics does depend on the population). The only way to get rid of these population-level compounding errors is to have L=0 (that depends on the problem at hand).\n"}]

Author rebuttal:
We would like to thank the reviewers for the time they spent reviewing our paper and for their valuable feedback. 

All the reviewers recognized the **clarity** and the **novelty** of our work, providing **new** and **first** theoretical guarantees for this setting. Moreover, MgoB, underlined how our work ¨shows a gap in current literature and proceeds with an ample analysis of how to fill it¨; uQRX noticed that we ¨propose a new adversarial algorithm to mitigate the exponential dependency on the horizon¨; and Qrta wrote that our work  ¨suggests that the adversarial imitation learning could replace the inner RL by an MFC¨. Thanks for the positive feedback.

The main concerns raised relate to experimental evaluation (4ip4, MgoB, uQRX), and the used L1 distance (4ip4, uQRX).

- **Experimental evaluation.** The concern mainly regards the absence of it in the main body of the paper and the fact that this did not show the exponential dependency of BC and vanilla-ADV on the horizon. We provide in the pdf file attached to the rebuttal a new experiment which shows empirically the exponential dependency of BC and vanilla-ADV on the horizon. We will add the results of this experiment to the main text of the paper.

- **L1 distance.** The main reason to use the L1 distance is its simplicity for conveying the main message. However, the whole analysis can be easily extended to other distance metrics (as KL-divergence). In fact, using tools such as Pinsker inequality (as mentioned eg l.149-150); we would get similar bounds with $\sqrt{\epsilon}$ rather than $\epsilon$. This would not influence the main message of the paper, which is the exponential dependency to the horizon of the BC and vanilla-ADV, whenever the dynamics does depend on the population.

We hope our answers clarify the raised questions about our work. We will be happy to take any further questions they might have during the discussion period.


Meta-review: This paper presents a novel solution concept, NIG, which generalized the classic imitation gap, and shows the upper-bounds of NIG for several different settings. Reviewers agree that the theoretical analysis is solid and supports the upper bounds well.  The paper is clearly written and well organized, and both the theoretical upper bounds and the empirical results suggest that the adversarial imitation learning could replace the inner RL by an MFC. There were some concerns about the gap between the theoretical results and empirical algorithm - the authors acknowledge those gaps but make the argument that the novel theoretical result is the main contribution, namely that there is an exponential gap between single agent and mean-field games in the imitation learning settings. I am voting to accept this paper mainly due to this contribution. I encourage the authors to be more clear about the empirical gap and add discussion about this and the ramifications in the camera ready version.
Decision: Accept (poster)